Software Cloud Services О том, как Computer Science нам жить помогает или современные приложения теории графов Калачёв Максим Александрович Разработчик. - презентация

1 Software Cloud Services О том, как Computer Science нам жить помогает или современные приложения теории графов Калачёв Максим Александрович Разработчик

2 l Software Cloud Services Agenda веб-графы методы моделирования ранжирование неестественные структуры shortest path problem нерешённые проблемы

3 l Software Cloud Services Метафизический вопрос 1

4 l Software Cloud Services Метафизический вопрос 2

5 l Software Cloud Services Графы, вероятность, приложения

6 l Software Cloud Services Веб-графы

7 l Software Cloud Services Веб-графы

8 l Software Cloud Services Веб-графы

9 l Software Cloud Services Социальные сети

10 l Software Cloud Services Социальные сети

11 l Software Cloud Services Моделирование веб-графов Случайные графы Исследования Barabasi-Albert Модель Bollobas-Riordan Модификации модели

12 l Software Cloud Services Как устроен веб-граф? Albert-Laszlo Barabasi and Reka Albert. Emergence of scaling in random networks. Science, 286:509, млрд вершин, псевдомультиорграф Ключевые свойства веб-графа: Разрежённость на k вершин kt рёбер, k 1 Диаметр графа {5, 6} Теория о шести рукопожатиях Степенное распределение степеней вершин P(d) c / d 2.1, c – нормирующий множитель

13 l Software Cloud Services Степенной закон распределения

14 l Software Cloud Services Эволюция веб-графа Модель предпочтительного соединения (preferential attachment)

15 l Software Cloud Services Six degrees of separations

16 l Software Cloud Services Six degrees of separations

17 l Software Cloud Services Масштабная инвариантность

18 l Software Cloud Services Scale-free networks Техника: Сети электропередачи, VLSI, Интернет, Веб Социум: контакты, связи, организации, язык, дороги, авиамаршруты Биология: нейроны; пищевые, экологические, метаболические сети Физика: молекулы, галактики

19 l Software Cloud Services Ранжирование в поисковых системах

20 l Software Cloud Services Ранжирование в семантических сетях проект WordNet (wordnet.princeton.edu)

21 l Software Cloud Services Выявление веб-структур

22 l Software Cloud Services Выявление веб-структур

23 l Software Cloud Services Shortest path problem Andrew Goldberg Microsoft Research

24 l Software Cloud Services Shortest path problem Почему современные алгоритмы на картах работают очень быстро млн вершин Время работы c Интуитивные идеи: Указатели на дугах Поиск A* Достижимость Шоссейная и желаемые иерархии Перевалочные пункты

25 l Software Cloud Services Нерешённые вопросы Самое главное, что ученик должен узнать от учителя - это что некоторый вопрос ещё не решён. Петровский И.Г. brainwarehardware

26 l Software Cloud Services P vs NP NP – класс всех задач поиска, решение для которых может быть быстро проверено. P – класс задач поиска, решение для которых может быть быстро найдено. P NP – верно ли, что каждый раз, когда решение можно быстро проверить, его можно быстро найти.

27 l Software Cloud Services Послесловие Я.Б. Зельдович считал, что постановка задачи – искусство куда более тонкое, чем решение. Стоит точно сформулировать вопрос, - говорил он, - как тотчас найдётся подходящий математик для решения. Ведь математики, они как мухи, - умеют ходить по потолку! В.И. Арнольд, Задачи Арнольда.