О том, как Computer Science нам жить помогает или современные приложения теории графов


The Presentation inside:

Slide 0

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


Slide 1

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


Slide 2

Метафизический вопрос №1


Slide 3

Метафизический вопрос №2


Slide 4

Графы, вероятность, приложения


Slide 5

Веб-графы


Slide 6

Веб-графы


Slide 7

Веб-графы


Slide 8

Социальные сети


Slide 9

Социальные сети


Slide 10

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


Slide 11

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


Slide 12

Степенной закон распределения


Slide 13

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


Slide 14

Six degrees of separations


Slide 15

Six degrees of separations


Slide 16

Масштабная инвариантность


Slide 17

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


Slide 18

Ранжирование в поисковых системах


Slide 19

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


Slide 20

Выявление веб-структур


Slide 21

Выявление веб-структур


Slide 22

Shortest path problem Andrew Goldberg Microsoft Research


Slide 23

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


Slide 24

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


Slide 25

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


Slide 26

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


×

HTML:





Ссылка: