Программа дисциплины Web-графы и поиск для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Программа дисциплины Web графы и поиск для направления 010400. 1 70.09kb.
Программа дисциплины Дискретная математика для направления 010400. 1 145.02kb.
Программа дисциплины Операционная система unix для направления 010400. 1 201.94kb.
Программа дисциплины для направления 010400. 62 «Прикладная математика... 1 243.61kb.
Программа дисциплины Прогнозирование временных рядов для направления... 1 144.11kb.
Программа дисциплины Безопасность информационных сетей для направления... 1 210.13kb.
Программа дисциплины Комплексный анализ  для направления 010400. 1 140.73kb.
Программа дисциплины Уравнения математической физики для направления... 1 197.02kb.
Программа дисциплины «Социология» для направления 010400. 62 "Прикладная... 1 291.63kb.
Программа дисциплины и управление жизненным циклом для направления... 1 335.65kb.
Программа дисциплины [Введите название дисциплины] для направления/... 1 314.05kb.
Тромбопластин 1 93.34kb.
Направления изучения представлений о справедливости 1 202.17kb.

Программа дисциплины Web-графы и поиск для направления 010400. 68 «Прикладная математика - страница №1/1



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

«Национальный исследовательский университет

«Высшая школа экономики»
Факультет БИЗНЕС-ИНФОРМАТИКИ

Отделение ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ



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

Автор РайгородскийА.М. (MRaigor@yandex.ru)




Рекомендована секцией УМС

«Прикладная математика

и информатика»
Председатель

__________________ Кузнецов С.О.

«_____» __________________ 20____ г.


Одобрена на заседании базовой кафедры

Яндекса


Зав. кафедрой

__________________ Ройтберг М.А.

«_____» __________________ 20____ г.


Утверждена УС факультета

бизнес-информатики


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

__________________ Фомичев В.А.

« ____» ___________________20____ г.





Москва


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

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


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

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


Изучение курса «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) и умениями использовать эти знания при построении алгоритмов поиска в Интернете.

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








В кокетстве молодых девушек много садизма — говорят люди в возрасте. Станислав Ежи Лец
ещё >>