Слайд 3План
Computer Science
Web-графы
Случайные графы
Highway dimenstion
NP vs P
Что осталось нерассмотренным
Послесловие
![План Computer Science Web-графы Случайные графы Highway dimenstion NP vs P Что осталось нерассмотренным Послесловие](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/388753/slide-2.jpg)
Слайд 12Computer Science
Закон Вирта
Программы становятся медленне более быстро, чем компьютеры становятся быстрее
P =
![Computer Science Закон Вирта Программы становятся медленне более быстро, чем компьютеры становятся](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/388753/slide-11.jpg)
A =
Mρ - множество процедур решения задачи
R2 ⊂ Mρ ² - бинарное отношение на Mρ
(ρi, ρj) ∈ R2 ⇔ после пройедуры ρi выполняется процедура ρj
Слайд 15Теория графов + Теория вероятностей = PROFIT
+
![Теория графов + Теория вероятностей = PROFIT +](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/388753/slide-14.jpg)
Слайд 18Случайные графы
Наблюдения Барабаши-Альберт
Как устроен web-граф?
Barabashi, Albert, 1999, 2000
5 млрд вершин, псевдомультиорграф
Ключевые свойства
![Случайные графы Наблюдения Барабаши-Альберт Как устроен web-граф? Barabashi, Albert, 1999, 2000 5](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/388753/slide-17.jpg)
веб-графа:
∙ Разрежённость
на k вершин kt рёбер, k ≥ 1
∙ Диаметр графа ∈ {5, 6}
Теория о шести рукопожатиях
∙ Степенное распределение степеней вершин
P(d) ~ c / d λ
λ ≈ 2.1, c – нормирующий множитель
Слайд 19Случайные графы
Наблюдения Барабаши-Альберт
Веб-граф очень специфичен – разрежен и тесен
Степенной закон объединяет социальные,
![Случайные графы Наблюдения Барабаши-Альберт Веб-граф очень специфичен – разрежен и тесен Степенной](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/388753/slide-18.jpg)
биологические и транспортные сети
Модели предпочтительного соединения
Слайд 20Случайные графы
Модель Эрдёша-Реньи
G(n,p)
V = {1, 2, …, n}, E
рёбра проводятся взаимно-независимо с
вероятностью
![Случайные графы Модель Эрдёша-Реньи G(n,p) V = {1, 2, …, n}, E](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/388753/slide-19.jpg)
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| - вероятность повления конкретного графа
Слайд 23Highway dimension
Почему современные алгоритмы на картах работают очень быстро
100000 млн вершин
Время работы
![Highway dimension Почему современные алгоритмы на картах работают очень быстро 100000 млн](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/388753/slide-22.jpg)
10-2 c
Интуитивные идеи:
Указатели на дугах
Поиск A*
Достижимость
Шоссейная и желаемые иерархии
Перевалочные пункты
Слайд 27P vs NP
Задача поиска задаётся алгоритмом C, который получает на вход условие
![P vs NP Задача поиска задаётся алгоритмом C, который получает на вход](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/388753/slide-26.jpg)
I и кандидата на решение S и имеет полиномиальное, относительно I время работы.
S называется решением если и только если C(S, I) = true
NP – класс всех задач поиска, решение для которых может быть быстро проверено
P – класс задач поиска, решение для которых может быть быстро найдено
P ≠ NP – верно ли, что каждый раз, когда решение можно быстро проверить, его можно быстро найти
Задача о расписании
Задача о вершинном покрытии
A → B
Слайд 30Что осталось нерассмотренным
Параллельные алгоритмы
Распознавание изображений
Нейронные сети
Генетические алгоритмы
Нечёткие модели
Строковые алгоритмы
Комбинаторная оптимизация
Численные алгоритмы
Вычислительная геометрия
Криптографические
![Что осталось нерассмотренным Параллельные алгоритмы Распознавание изображений Нейронные сети Генетические алгоритмы Нечёткие](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/388753/slide-29.jpg)
алгоритмы
Компьютерная лингвистика
……..