Программа дисциплины Web графы и поиск для направления 010400. 68 «Прикладная математика и информатика» - shikardos.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Программа дисциплины для направления 010400. 62 «Прикладная математика... 1 243.61kb.
Программа дисциплины «История» для направления 231300. 62 и 230700. 3 676.37kb.
Программа дисциплины «Герменевтика» 1 269.47kb.
Программа дисциплины Технологии баз данных Oracle для направления... 1 206.89kb.
Программа дисциплины «Иностранный язык (английский)» 3 1560.34kb.
Программа дисциплины Управление инвестициями в ит для направления... 1 191.71kb.
Программа дисциплины [Введите название дисциплины] для направления/... 1 268.08kb.
Основная образовательная программа магистратуры, реализуемая вузом... 1 308.87kb.
Основная образовательная программа бакалавриата, реализуемая вузом... 1 314.01kb.
Программа дисциплины Основы офисного программирования для направления... 1 236.25kb.
Учебное пособие для обучающихся в спбгу по направлениям астрономия... 11 4393.25kb.
Контрольная работа №2 По курсу «Английский язык» Вариант №2 2012 I 1 67.83kb.
- 4 1234.94kb.
Программа дисциплины Web графы и поиск для направления 010400. 68 «Прикладная математика - страница №1/1


Правительство Российской Федерации

Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"

Факультет Бизнес-информатики

Отделение Прикладной математики и информатики

Программа дисциплины

Web-графы и поиск

для направления 010400.68 «Прикладная математика и информатика» подготовки магистров


Автор программы:

Райгородский А.М., д.ф.-м.н., MRaigor@yandex.ru

Одобрена на заседании базовой кафедры Яндекс «___»____________ 20 г

Зав. кафедрой И.В. Аржанцев

Рекомендована профессиональной коллегией УМС «Прикладная математика»

«___»____________ 20 г

Председатель А.А. Макаров

Утверждена УС факультета бизнес-информатики «___»_____________20 г.

Ученый секретарь ________________________

Москва, 2013



Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы.

Пояснительная записка


Автор программы


Райгородский А.М.,д.ф.-м.н.

Требования к студентам


Изучение курса «Web-графы и поиск»требует предварительных знаний потеории вероятностей, дискретной математике и комбинаторике.

Аннотация


Дисциплина «Web-графы и поиск» предназначена для подготовки магистров 010400.68 – Прикладная математика и информатика.

Учебная дисциплина "Web-графы и поиск" предназначена для того, чтобы познакомить студентов, проходящих обучение по магистерской программе «Анализ интернет-данных», с современными моделями Интернета и использованием этих моделей при поиске в Интернете. Будут рассмотрены различные модели случайных графов, исследована адекватность различных моделей эмпирическим свойствам графа интернет-ссылок, способа оценки «качества» интернет-страниц (PageRank). В ходе курса будут кратко представлены необходимые сведения из теории графов и смежных областей математики.

Теоретическая часть курса подкреплена многочисленными задачами и примерами. Так же студентам будут предоставлены задачи для самостоятельного решения

Программа курса предусматривает лекции (64 часа), практические занятия (64 часа).


Учебные задачи курса


Цель курса - познакомить студентовс современными моделями Интернета и использованием этих моделей при поиске в Интернете. В результате изучения курса студенты должны:

  • знать основные модели случайных графов и случайных блужданий на них

  • знать свойства этих моделей и адекватность моделей при моделировании различных свойств сети Интернет

  • знать различные способы оценки «качества» интернет-страниц (PageRank) и уметь использовать эти знания при построении алгоритмов поиска в Интернете

Тематический план дисциплины «Многомерный статистический анализ»



Название темы

Всего часов по дисциплине

Аудиторные часы

Самосто-ятельная работа

Лекции

Сем.и практика занятия

1

Тема 1.Случайные web-графы и их модели.

67

20

20

27

2

Тема 2.Случайные блуждания на графах.

67

20

20

27

3

Тема 3.Оценка «качества» web-страниц и поиск

92

24

24

34




Итого

216

64

64

88


I.Источники информации



Список литературы

Основная литература

1. R. Durrett, «Random graph dynamics», Cambridge, 2007.

2. L.-A. Barabasi, R. Albert, H. Jeong, «Scale-free characteristics of random networks: the topology of the world-wide web», Physica, A281 (2000), 69-77.

3. R. Kumar et al., «Stochastic models for the web graph», 41st Annual Symposium on Foundations of Computer Science, 2000.

4. B. Bollobas, O. Riordan, J. Spencer, G. Tusnady, «The degree sequence of a scale-free random graph process», Random Structures Algorithms, 18 (2001), N3, 279-290.

5. B. Bollobas, O. Riordan, «Mathematical results on scale-free random graphs», Handbook of graphs and networks, 1 - 34, Wiley-VCH, Weinheim, 2003.

6. B. Bollobas, O. Riordan, «Robustness and vulnerability of scale-free random graphs», Internet Math., 1 (2003), N1, 1-35.

7. R. Karp, C. Schindelhauer, S. Shenker, B. Vocking. Randomized Rumor Spreading.41st IEEE Symposium on Foundations of Computer Science, 2000.

8. L. Lovasz. Random Walks on Graphs: A Survey. Combinatorics: Paul Erdos is Eighty (vol. 2), 1996, pp. 353-398.

9. S. Dill, R. Kumar, K. McCurley, S. Rajagopalan, D. Sivakumar, A. Tomkins. Self-similarity in the Web.27th International Conference on Very Large Data Bases, 2001.

10. Gary Flake, K. Tsioutsiouliklis, R.E. Tarjan. Graph Clustering Techniques based on Minimum Cut Trees. Internet Mathematics, 2002.

Дополнительнаялитература

1. R. Albert, H. Jeong, L.-A. Barabasi, «Diameter of the world-wide web», Nature, 401 (1999), 130-131.

2. A. Broder et al., «Graph structure in the Web», Computer Networks, 33 (2000), 309-320.

3. J. Leskovec, J. Kleinberg, Ch. Faloutsos, «Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations», Proc. of KDD'05, August 21-24, 2005, Chicago, Illinois, USA.

4. B. Bollobas, O. Riordan, «The diameter of a scale-free random graph», Combinatorica, 24 (2004), N1, 5-34.



II.Формы контроля и структура итоговой оценки


• Текущий контроль: - письменная аудиторная контрольная работа в каждом модуле (60 мин.) и индивидуальные домашние задания (одно в первом модуле и два во втором).

• Промежуточный контроль - зачет в конце каждого модуля;

• Итоговый контроль – письменный экзамен (120 мин.)

Формирование оценки.

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

Результирующая оценка за текущий контроль в первом модуле учитывает результаты студента по текущему контролю следующим образом:



Отекущий = 0,4·Ок/р+0,4Одз+ 0,2·Оаудиторная ;

Ок/р - оценка за контрольную работу, Одз - оценка за домашнее задание.

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



Оитоговый1 =0,3·Озач +0,7·Отекущий·

Результирующая оценка за текущий контроль во втором модуле учитывает результаты студента по текущему контролю следующим образом:



Отекущий =0,2•Озач +0,2•Оаудиторная + 0,2Одз1+ 0,2Одз2+ 0,2·Ок/р .

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



Оитоговый =0,4·Оэкзамен +0,3·Отекущий +0,3·Оитоговый1.

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


Таблица соответствия оценок по десятибалльной и системе зачет/незачет


Оценка по 10-балльной шкале

Оценка по 5-балльной шкале

1

Незачет

2

3

4

Зачет

5

6

7

8

9

10


Таблица соответствия оценок по десятибалльной и пятибалльной системе


По десятибалльной шкале

По пятибалльной системе

1 – неудовлетворительно

2 – очень плохо

3 – плохо


неудовлетворительно – 2

4 – удовлетворительно

5 – весьма удовлетворительно



удовлетворительно – 3

6 – хорошо

7 – очень хорошо



хорошо – 4

8 – почти отлично

9 – отлично

10 - блестяще


отлично – 5


III.Программа дисциплины «Web-графы и поиск»


Тема 1. Случайные web-графы и их модели

Различные эмпирические данные об устройстве ссылочного веб-графа и ему подобных структур: «мир тесен», степенной закон, предпочтительное присоединение и пр. Обзор существующих моделей случайного графа и веб-графа. Сравнение существующих моделей случайного веб-графа. Распределение степеней вершин и диаметр случайного веб-графа в модели Барабаши – Альберт (теорема Боллобаша – Риордана).


Основнаялитература

1. R. Durrett, «Random graph dynamics», Cambridge, 2007.

2. L.-A. Barabasi, R. Albert, H. Jeong, «Scale-free characteristics of random networks: the topology of the world-wide web», Physica, A281 (2000), 69-77.

3. R. Kumar et al., «Stochastic models for the web graph», 41st Annual Symposium on Foundations of Computer Science, 2000.

4. B. Bollobas, O. Riordan, J. Spencer, G. Tusnady, «The degree sequence of a scale-free random graph process», Random Structures Algorithms, 18 (2001), N3, 279-290.


Дополнительнаялитература

1. B. Bollobas, O. Riordan, «Mathematical results on scale-free random graphs», Handbook of graphs and networks, 1 - 34, Wiley-VCH, Weinheim, 2003.

2. B. Bollobas, O. Riordan, «Robustness and vulnerability of scale-free random graphs», Internet Math., 1 (2003), N1, 1-35.

Тема 2.Случайные блуждания на графах


Понятие случайного блуждания на графе. Марковский процесс и стохастические матрицы.Стационарное состояние. Фундаментальная теорема Марковских цепей. Теорема Перрона-Фрабениуса. Основные характеристики случайных блужданий для различных видов графов. Анализ различных моделей случайных графов. Перколяция.

Основнаялитература

1. R. Karp, C. Schindelhauer, S. Shenker, B. Vocking. Randomized Rumor Spreading.41st IEEE Symposium on Foundations of Computer Science, 2000.

2. L. Lovasz. Random Walks on Graphs: A Survey. Combinatorics: Paul Erdos is Eighty (vol. 2), 1996, pp. 353-398.

3. S. Dill, R. Kumar, K. McCurley, S. Rajagopalan, D. Sivakumar, A. Tomkins. Self-similarity in the Web.27th International Conference on Very Large Data Bases, 2001.


Дополнительнаялитература

  1. Т. Мори, “Случайные блуждания на графах де Брейна”, ТВП, 37:1 (1992), 194–197

Тема 3. Оценка «качества» web-страниц и поиск

Архитектура и методы работы поисковых систем. Методы ранжирования узлов графа. Алгоритм PageRank. Сравнение порядка ранжирования. Kendall'stau. Spearman'scoefficient

Сильно связанные компонентыWeb-графа. Распределение степеней узлов. Диаметр графа. Понятия Hubs и Authorities. HITS алгоритм. Архитектура поисковых систем.

Качество поиска. Tочность и полнота. Метрики MAP и nDCG.

Основная литература

1. S. Dill, R. Kumar, K. McCurley, S. Rajagopalan, D. Sivakumar, A. Tomkins. Self-similarity in the Web.27th International Conference on Very Large Data Bases, 2001.

2. Gary Flake, K. Tsioutsiouliklis, R.E. Tarjan. Graph Clustering Techniques based on Minimum Cut Trees. Internet Mathematics, 2002.


3. Lawrence Page, Sergey Brin, Rajeev Motwani and Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web. — 1998. (англ.)

4. SergeyBrin, LawrencePage. TheAnatomyofaLarge-ScaleHypertextualWebSearchEngine. — 1998. (англ.)


IV.Методические указания студентам


Самостоятельная работа студента предусматривает выполнение теоретических заданий, направленных на овладение способами оценки «качества» интернет-страниц (PageRank) и умениями использовать эти знания при построении алгоритмов поиска в Интернете.

Автор программы: _____________________________/ <Райгородский А.М.> /