'

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

Понравилась презентация – покажи это...





Слайд 0

О том, как Computer Science нам жить помогает или современные приложения теории графов Калачёв Максим Александрович Разработчик kalachevmax@gmail.com


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

Веб-графы


Слайд 6

Веб-графы


Слайд 7

Веб-графы


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 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 – нормирующий множитель


Слайд 12

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


Слайд 13

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


Слайд 14

Six degrees of separations


Слайд 15

Six degrees of separations


Слайд 16

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


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

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


Слайд 21

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


Слайд 22

Shortest path problem Andrew Goldberg Microsoft Research


Слайд 23

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


Слайд 24

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


Слайд 25

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


Слайд 26

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


×

HTML:





Ссылка: