Обзор современного состояния области алгоритмов и структур данных

Идеи

План
Computer Science
Web-графы
Случайные графы
Highway dimenstion
NP vs P
Что осталось нерассмотренным
Послесловие

Теоретики

Практики

Программисты

Эдгар Дейкстра

Никлаус Вирт

Чарльз Хоар

Дональт Кнут

Программа
+

Computer Science
Закон Вирта
Программы становятся медленне более быстро, чем компьютеры становятся быстрее
P =
A =
Mρ - множество процедур решения задачи
R2 ⊂ Mρ ² - бинарное отношение на Mρ
(ρi, ρj) ∈ R2 ⇔ после пройедуры ρi выполняется процедура ρj

Абстракции

Математическое моделирование

Теория графов + Теория вероятностей = PROFIT
+

Веб-графы

Веб-графы

Случайные графы
Наблюдения Барабаши-Альберт
Как устроен web-граф?
Barabashi, Albert, 1999, 2000
5 млрд вершин, псевдомультиорграф
Ключевые свойства веб-графа:
∙ Разрежённость
на k вершин kt рёбер, k ≥ 1
∙ Диаметр графа ∈ {5, 6}
Теория о шести рукопожатиях
∙ Степенное распределение степеней вершин
P(d) ~ c / d λ
λ ≈ 2.1, c – нормирующий множитель

Случайные графы
Наблюдения Барабаши-Альберт
Веб-граф очень специфичен – разрежен и тесен
Степенной закон объединяет социальные, биологические и транспортные сети
Модели предпочтительного соединения

Случайные графы
Модель Эрдёша-Реньи
G(n,p)
V = {1, 2, …, n}, E
рёбра проводятся взаимно-независимо с
вероятностью p ∈ [0, 1] в соответствии со
схемой Бернулли
e1, …, em, m = C2n – количество всех испытаний
Вероятностное пространство <Ωn, Fn, Pn,p>
Ωn = {G = (Vn, E)} – множество элементарных событий
Fn = 2Ωn – множество событий
Pn,p(G) = p|E|(1-p)m-|E| - вероятность повления конкретного графа

Транспортная интерпретация

Highway dimension

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

P vs NP

1 миллион долларов!

Классы задач

P vs NP
Задача поиска задаётся алгоритмом C, который получает на вход условие I и кандидата на решение S и имеет полиномиальное, относительно I время работы.
S называется решением если и только если C(S, I) = true
NP – класс всех задач поиска, решение для которых может быть быстро проверено
P – класс задач поиска, решение для которых может быть быстро найдено
P ≠ NP – верно ли, что каждый раз, когда решение можно быстро проверить, его можно быстро найти
Задача о расписании
Задача о вершинном покрытии
A → B

Андрей Михайлович Райгородский

Андрей Гольдберг

Что осталось нерассмотренным
Параллельные алгоритмы
Распознавание изображений
Нейронные сети
Генетические алгоритмы
Нечёткие модели
Строковые алгоритмы
Комбинаторная оптимизация
Численные алгоритмы
Вычислительная геометрия
Криптографические алгоритмы
Компьютерная лингвистика
……..