Software Cloud Services О том, как Computer Science нам жить помогает или современные приложения теории графов Калачёв Максим Александрович Разработчик
l Software Cloud Services Agenda веб-графы методы моделирования ранжирование неестественные структуры shortest path problem нерешённые проблемы
l Software Cloud Services Метафизический вопрос 1
l Software Cloud Services Метафизический вопрос 2
l Software Cloud Services Графы, вероятность, приложения
l Software Cloud Services Веб-графы
l Software Cloud Services Веб-графы
l Software Cloud Services Веб-графы
l Software Cloud Services Социальные сети
l Software Cloud Services Социальные сети
l Software Cloud Services Моделирование веб-графов Случайные графы Исследования Barabasi-Albert Модель Bollobas-Riordan Модификации модели
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 – нормирующий множитель
l Software Cloud Services Степенной закон распределения
l Software Cloud Services Эволюция веб-графа Модель предпочтительного соединения (preferential attachment)
l Software Cloud Services Six degrees of separations
l Software Cloud Services Six degrees of separations
l Software Cloud Services Масштабная инвариантность
l Software Cloud Services Scale-free networks Техника: Сети электропередачи, VLSI, Интернет, Веб Социум: контакты, связи, организации, язык, дороги, авиамаршруты Биология: нейроны; пищевые, экологические, метаболические сети Физика: молекулы, галактики
l Software Cloud Services Ранжирование в поисковых системах
l Software Cloud Services Ранжирование в семантических сетях проект WordNet (wordnet.princeton.edu)
l Software Cloud Services Выявление веб-структур
l Software Cloud Services Выявление веб-структур
l Software Cloud Services Shortest path problem Andrew Goldberg Microsoft Research
l Software Cloud Services Shortest path problem Почему современные алгоритмы на картах работают очень быстро млн вершин Время работы c Интуитивные идеи: Указатели на дугах Поиск A* Достижимость Шоссейная и желаемые иерархии Перевалочные пункты
l Software Cloud Services Нерешённые вопросы Самое главное, что ученик должен узнать от учителя - это что некоторый вопрос ещё не решён. Петровский И.Г. brainwarehardware
l Software Cloud Services P vs NP NP – класс всех задач поиска, решение для которых может быть быстро проверено. P – класс задач поиска, решение для которых может быть быстро найдено. P NP – верно ли, что каждый раз, когда решение можно быстро проверить, его можно быстро найти.
l Software Cloud Services Послесловие Я.Б. Зельдович считал, что постановка задачи – искусство куда более тонкое, чем решение. Стоит точно сформулировать вопрос, - говорил он, - как тотчас найдётся подходящий математик для решения. Ведь математики, они как мухи, - умеют ходить по потолку! В.И. Арнольд, Задачи Арнольда.