Учебная программа дисциплины дс. Ф. 02. Алгоритмы для Интернет Специальность: 080801 Прикладная информатика (в образовании) icon

Учебная программа дисциплины дс. Ф. 02. Алгоритмы для Интернет Специальность: 080801 Прикладная информатика (в образовании)



Смотрите также:
Учебная программа дисциплины ен. Р. 06...
Учебная программа дисциплины опд. Ф. 04...
Программа итогового экзамена по информатике для специальности «080801 Прикладная информатика (в...
Учебная программа дисциплины ен. Ф. 01...
Учебная программа дисциплины «Интегрированные среды разработки экономических информационных...
Рабочая программа дисциплина «Интернет-маркетинг» Специальность 080801 Прикладная информатика в...
Рабочая программа дисциплина «Интернет-маркетинг» Специальность 080801 Прикладная информатика в...
Рабочая программа дисциплина «Интернет-маркетинг» Специальность 080801 Прикладная информатика в...
Рабочая программа дисциплина «Интернет-маркетинг» Специальность 080801 Прикладная информатика в...
Программа по курсу «Введение в специальность» для специальности 080801 «Прикладная информатика...
Рабочая программа для специальности 080801 "Прикладная информатика (в экономике)"...
Учебная программа дисциплины метрология и сертификация программного обеспечения для студентов...



скачать


Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«Иркутский государственный педагогический университет»

Факультет математики, физики и информатики


Утверждено

на заседании совета факультета

математики, физики и информатики

протокол №­­­­­­_____от __________2007 г.

Председатель совета________________

(Кузьмина Н.Д.)





УЧЕБНАЯ ПРОГРАММА ДИСЦИПЛИНЫ

ДС.Ф.02. Алгоритмы для Интернет


^ Специальность: 080801 Прикладная информатика (в образовании)

Квалификация: информатик в образовании


Курс: 4

Семестр: 8

Форма обучения: очная


Количество часов на дисциплину: 78 час.

Количество аудиторных часов: 39 час.; из них:

Лекций: 18 час.

Лабораторных занятий: 21 час.

Самостоятельная работа: 39 час.


Итоговый контроль: зачет.


^ I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ

1. Место дисциплины

Дисциплина “Компьютерные издательские системы” является практически-ориентированной, включена в учебный план в рамках федерального компонента в качестве специальной дисциплины. Она является неотъемлемой частью подготовки специалиста в области информационных технологий.


^ 2. Цель дисциплины

Цель дисциплины – познакомить студентов с приемами решения практических задач в сети Интернет с помощью алгоритмов поиска и индексации данных.

^ 3. Задачи дисциплины

Задачи курса – обучить студентов алгоритмам, которые применяются в поисковых системах Интернет.

4. Принципы отбора содержания и организации учебного материала

Учебный материал содержит различные алгоритмы, применяемые в сети Интернет. В основу отбора материала положен принцип обзора различных математических моделей алгоритмов и методов их построения.

^ 5. Требования к освоению содержания дисциплины

Содержание курса входит в необходимый минимум профессиональных знаний выпускников по специальности, а также является необходимой основой для усвоения специальных курсов, выполнения курсовых и дипломных работ.

^ 6. Виды контроля

Текущий – проводится по учебной единице в форме проверки задания для самостоятельного выполнения.

Итоговый – проводится в форме зачета.

^ 7. Планирование содержания дисциплины



Название модуля

Часы аудиторных занятий

Часы самостоятельной работы

Всего часов

Лекции

Практ.

занятия

1

Алгоритмы для Интернет

20

19

39

78


^ II. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ


Модуль №1. Алгоритмы для Интернет

1. Построение суффиксного дерева (по Укконену)

Суффиское дерево: способ представления текста. Применение: поиск подстрок, поиск наибольшей общей подстроки. Основные идеи алгоритма: on-line построение, вспомогательные суффиксные стрелки, неравномерная оценка времени работы.

^ 2. Преобразование Берроуза-Вилера

Вычисление преобразования Берроуза-Вилера, вычисление обратного преобразования, применение к архивированию.

3. Архитектура поисковых систем. Pagerank

Модели информационного поиска: булевская, векторная, вероятностная. PageRank: модель случайного блуждания, основное уравнения PageRank, PageRank как собственный вектор матрицы всех ссылок.

^ 4. Структура сложных сетей

примеры реальных сетей: биологические, социальные, информационные, технологические. Свойства сетей: связность, кластеризация, распределение сетей, корреляции базовых свойств между собой. Модели сетей: Пуассона, конфигурационная, Прайса, Small World.

^ 5. Введение в байесовские сети

Понятие байесовской сети. Применение байесовских сетей. Вероятностная логика. Фрагменты знаний.

6. Автоматическая классификация текстов

Постановка задачи, подходы и применение. Индексация документов: базовый подход, уменьшение размерности векторов. Построение и обучение классификатора: выбор порога, линейные on-line классификатор, метод регрессии, ДНФ-правило, нейронные сети. Оценка качества классификации: метрики из информационного поиска, методы сравнения двух классификаторов.

^ 7. Метод опорных векторов

Постановка задачи классификации. Оптимальная разделяющая гиперплоскость: разделение прямой, разделение полосой, случай линейной разделимости, случай отсутствия линейной разделимости. Обучение машины опорных векторов. Расширение пространства признаков. Примеры.

^ 8. Семантический Веб

История и мотивация. Архитектура семантического Веба: общая архитектура, RDF – синтаксис семантического Веба, OWL – язык описания онтологий. Проекты семантического Веба.

^ 9. Проектирование протоколов

Эгоистические агенты и кратчайший путь. Аукцион Викри, эгоистические подрядчики и составление расписаний. Общий механизм Викри-Грувса-Кларка.

^ 10. Открытые проблемы по веб-алгоритмам

Крупномасштабная фильтрация. Распространение меток. Выявление структур.


Основные понятия

Суффиксное дерево, неявное суффиксное дерево, фаза, типы продлений, суффиксная стрелка, преобразование Берроуза-Вилера, общий алгоритм образного преобразования Берроуза-Вилера, булевская модель информационного поиска, векторная модель информационного поиска, релевантность векторной модели, вероятностная модель информационного поиска, функция соответствия, прямой индекс, обратный индекс, релевантность, оценки качества поиска, модель случайного блуждания, основное уравнение PageRank, понятие информационной сети, отношения между информационными объектами, технологические сети, биологические сети, эффект «маленького мира», распределение степеней, корреляции, случайные пуассоновские графы, конфигурационная модель, модель «маленького мира», модель Прайса, байесовские сети, байесовские сети доверия, алгебраические байесовские сети, виды классификации, индексация документов, обучение классификатора, оценка качества классификации, ранжирование и четкая классификация, линейные on-line классификатор, метод регрессии, ДНФ-правило, нейронные сети, метрики из информационного поиска, абстрактная задача классификации, линейный классификатор, шумы и штрафы, синтансис и семантика Веб, язык RDF, язык OWL, «пирог» Тима Бернерса-Ли, дублинское ядро, эгоистические агенты, задача кратчайшего пути, игры с неполной информацией, механизм Викри-Грувса-Крарка, проблема крупномасштабной фильтрации, задача распространения меток, задача выявления структур.


^ III. ОРГАНИЗАЦИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ


Студенты должны подготовить доклад по одной из предложенных тем и выступить на семинаре. Подготовка доклада делается парами. К докладу должны быть сделаны слайды. Доклад должен длиться не более 70 минут. После его окончания проводится дискуссия с аудиторией. План доклада должен содержать, по возможности, максимум из следующего списка:

  • Представление плана доклада

  • История области, время начала исследований, время расцвета и ключевых результатов, текущее состояние области

  • Ключевая литература и адреса сайтов посвященных этой области, источники использованные при подготовке доклада

  • Основные определения в данной области

  • Многочисленные примеры и иллюстрации

  • Главные результаты теории

  • Описание техники и методов, применяемых в исследованиях

  • Небольшие упражнения для аудитории, вопросы на понимание

  • Возможные области применения теории

  • Перспективы дальнейших исследований, формулировки открытых вопросов

  • Мнение докладчика о докладываемой науке

  • Дискуссия с аудиторией (после окончания собственно доклада)

Темы для докладов:

  1. Введение в Data Mining.

  2. Алгоритмы кластеризации.

  3. Генетические алгоритмы.

  4. Вычисления с помощью ДНК.

  5. Маршрутизация и парадокс заключенного.

  6. Вопросно-ответные системы.

  7. Рекомендательные системы.

  8. Поиск в полуструктурированных данных.

  9. Индексация текста для поиска с учетом орфографических ошибок.

  10. «Мир тесен» по Дж. Клейнбергу.

Литература.

  1. Электронный курс, выставленный в информационно-образовательной среде кафедры математической информатики «DOMIC» (http://matinf.igpu.ru/domic/).

  2. Вороновский Г.К., Махотило К.В., Петрашев С.Н., Сергеев С.А., Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности, Харьков, ОСНОВА, 1997. – 112с.

  3. Малинецкий Г.Г., Науменко С.А. Вычисления на ДНК.

  4. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход.

  5. http://www.rco.ru/

  6. http://algolist.manual.ru/ai/ga/ga1.php

  7. http://neuronet.alo.ru/

  8. http://www.intuit.ru/department/database/datamining/


^ IV. КОНТРОЛЬ КАЧЕСТВА ОСВОЕНИЯ ДИСЦИПЛИНЫ

Текущий контроль

Производится оценка качества сделанных докладов и презентаций.

Итоговый контроль


Примерные вопросы к зачету

  1. Способ представления текста суффиксными деревьями.

  2. Суффиксные деревья: поиск подстрок, поиск наибольшей общей подстроки.

  3. On-line построение суффиксных деревьев, вспомогательные суффиксные стрелки, оценка времени работы.

  4. Вычисление преобразования Берроуза-Вилера.

  5. Вычисление обратного преобразования Берроуза-Вилера.

  6. Применение преобразования Берроуза-Вилера к архивированию.

  7. Модели информационного поиска: булевская, векторная, вероятностная.

  8. PageRank: модель случайного блуждания.

  9. Основное уравнения PageRank. PageRank как собственный вектор матрицы всех ссылок.

  10. Примеры структуры сложных сетей: биологические, социальные, информационные, технологические.

  11. Свойства сетей: связность, кластеризация, распределение сетей, корреляции базовых свойств между собой.

  12. Модели сетей: Пуассона, конфигурационная, Прайса, Small World.

  13. Понятие байесовской сети.

  14. Применение байесовских сетей.

  15. Вероятностная логика.

  16. Фрагменты знаний.

  17. Автоматическая классификация текстов. Постановка задачи, подходы и применение.

  18. Индексация документов: базовый подход, уменьшение размерности векторов.

  19. Построение и обучение классификатора: выбор порога, линейные on-line классификатор.

  20. Построение и обучение классификатора: метод регрессии, ДНФ-правило, нейронные сети.

  21. Оценка качества классификации: метрики из информационного поиска, методы сравнения двух классификаторов.

  22. Метод опорных векторов. Постановка задачи классификации.

  23. Оптимальная разделяющая гиперплоскость: разделение прямой, разделение полосой, случай линейной разделимости, случай отсутствия линейной разделимости.

  24. Обучение машины опорных векторов. Расширение пространства признаков.

  25. Архитектура семантического Веба: общая архитектура. Проекты семантического Веба.

  26. RDF – синтаксис семантического Веба. OWL – язык описания онтологий.

  27. Проектирование протоколов. Эгоистические агенты и кратчайший путь.

  28. Проектирование протоколов. Аукцион Викри, эгоистические подрядчики и составление расписаний.

  29. Общий механизм Викри-Грувса-Кларка.

  30. Проблема крупномасштабной фильтрации.

  31. Проблема распространения меток.

  32. Проблема выявления структур.



^ V. УЧЕБНО-МЕТОДИЧЕКСОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ


1. Рекомендуемая литература

а) Учебная (основная)

  1. Вороновский Г.К., Махотило К.В., Петрашев С.Н., Сергеев С.А., Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности, Харьков, ОСНОВА, 1997. – 112с.

  2. Малинецкий Г.Г., Науменко С.А. Вычисления на ДНК.

  3. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход.

  4. http://www.rco.ru/

  5. http://algolist.manual.ru/ai/ga/ga1.php

  6. http://neuronet.alo.ru/

  7. http://www.intuit.ru/department/database/datamining/

б) Учебная (дополнительная)

  1. http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

  2. http://www.mfn.unipmn.it/.manzini/papers/mfcs99x.pdf

  3. http://marknelson.us/1996/09/01/bwt/

  4. http://www-db.stanford.edu/pub/papers/google.pdf

  5. http://company.yandex.ru/articles/article10.html

  6. http://meyer.math.ncsu.edu/Meyer/PS_Files/DeeperInsidePR.pdf

  7. http://www.santafe.edu/files/gems/paleofoodwebs/Newman2003SIAM.pdf

  8. http://www.people.cornell.edu/pages/dc288/Paper1.pdf

  9. http://nmis.isti.cnr.it/sebastiani/Publications/ACMCS02.pdf

  10. http://en.wikipedia.org/wiki/Support_vector_machine

  11. http://www.ccas.ru/voron/download/SVM.pdf

  12. http://research.microsoft.com/users/jplatt/smo.html

  13. http://ezolin.pisem.net/logic/semantic_web_rus.html

  14. http://sherdim.rsu.ru/pts/semantic_web/REC-owl-guide-20040210_ru.html

  15. http://teacode.com/concept/eor/dc.html

  16. http://iew3.technion.ac.il/.amirr/AMDJ.pdf

  17. http://en.wikipedia.org/wiki/Vickrey-Clarke-Groves

  18. http://citeseer.ist.psu.edu/kleinberg97two.html

  19. http://meyer.math.ncsu.edu/Meyer/PS_Files/DeeperInsidePR.pdf


^ 2. Электронно-программные средства

а) Электронный курс, выставленный в информационно-образовательной среде кафедры математической информатики «DOMIC» (http://matinf.igpu.ru/domic/). Электронный курс содержат лекции, презентации к лекциям.

Составитель: старший преподаватель кафедры математической информатики Зинченко А.С.




Рекомендовано

на заседании кафедры

математической информатики

протокол № ___ от ________________ 200_ г.

Зав. кафедрой __________________________ Н.А. Перязев


_____________________________


Одобрено

на заседании УМК факультета

математики, физики и информатики

протокол № ___ от ________________ 200_ г.

Председатель УМК ______________________





Скачать 97,68 Kb.
оставить комментарий
Дата29.09.2011
Размер97,68 Kb.
ТипПрограмма дисциплины, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Документы

наверх