Soft war e Clou d Serv ices Обзор современного состояния области алгоритмов и структур данных Калачёв Максим Александрович Разработчик maxkalache

Август 29, 2022

Главная
Алгебра
Soft war e Clou d Serv ices Обзор современного состояния области алгоритмов и структур данных Калачёв Максим Александрович Разработчик maxkalache

Содержание

2. Идеи
3. План Computer Science Web-графы Случайные графы Highway dimenstion NP vs P Что осталось нерассмотренным Послесловие
4. Теоретики
5. Практики
6. Программисты
7. Эдгар Дейкстра
8. Никлаус Вирт
9. Чарльз Хоар
10. Дональт Кнут
11. Программа +
12. Computer Science Закон Вирта Программы становятся медленне более быстро, чем компьютеры становятся быстрее P = A
13. Абстракции
14. Математическое моделирование
15. Теория графов + Теория вероятностей = PROFIT +
16. Веб-графы
17. Веб-графы
18. Случайные графы Наблюдения Барабаши-Альберт Как устроен web-граф? Barabashi, Albert, 1999, 2000 5 млрд вершин, псевдомультиорграф Ключевые
19. Случайные графы Наблюдения Барабаши-Альберт Веб-граф очень специфичен – разрежен и тесен Степенной закон объединяет социальные, биологические
20. Случайные графы Модель Эрдёша-Реньи G(n,p) V = {1, 2, …, n}, E рёбра проводятся взаимно-независимо с
21. Транспортная интерпретация
22. Highway dimension
23. Highway dimension Почему современные алгоритмы на картах работают очень быстро 100000 млн вершин Время работы 10-2
24. P vs NP
25. 1 миллион долларов!
26. Классы задач
27. P vs NP Задача поиска задаётся алгоритмом C, который получает на вход условие I и кандидата
28. Андрей Михайлович Райгородский
29. Андрей Гольдберг
30. Что осталось нерассмотренным Параллельные алгоритмы Распознавание изображений Нейронные сети Генетические алгоритмы Нечёткие модели Строковые алгоритмы Комбинаторная
32. Скачать презентацию

Слайд 2

Идеи

Слайд 3

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

Слайд 4

Теоретики

Слайд 5

Практики

Слайд 6

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

Слайд 7

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

Слайд 8

Никлаус Вирт

Слайд 9

Чарльз Хоар

Слайд 10

Дональт Кнут

Слайд 11

Программа
+

Слайд 12

Computer Science
Закон Вирта
Программы становятся медленне более быстро, чем компьютеры становятся быстрее
P

=
A =
Mρ - множество процедур решения задачи
R2 ⊂ Mρ ² - бинарное отношение на Mρ
(ρi, ρj) ∈ R2 ⇔ после пройедуры ρi выполняется процедура ρj

Слайд 13

Абстракции

Слайд 14

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

Слайд 15

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

Слайд 16

Веб-графы

Слайд 17

Веб-графы

Слайд 18

Случайные графы
Наблюдения Барабаши-Альберт
Как устроен web-граф?
Barabashi, Albert, 1999, 2000
5 млрд вершин, псевдомультиорграф
Ключевые

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

Слайд 19

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

социальные, биологические и транспортные сети
Модели предпочтительного соединения

Слайд 20

Случайные графы
Модель Эрдёша-Реньи
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| - вероятность повления конкретного графа

Слайд 21

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

Слайд 22

Highway dimension

Слайд 23

Highway dimension
Почему современные алгоритмы на картах работают очень быстро
100000 млн вершин
Время

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

Слайд 24

P vs NP

Слайд 25

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

Слайд 26

Классы задач

Слайд 27

P vs NP
Задача поиска задаётся алгоритмом C, который получает на вход

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

Слайд 28

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

Слайд 29

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

Слайд 30

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

геометрия
Криптографические алгоритмы
Компьютерная лингвистика
……..

Soft war e Clou d Serv ices Обзор современного состояния области алгоритмов и структур данных Калачёв Максим Александрович Разработчик maxkalache

Содержание

Идеи

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

Теоретики

Практики

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

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

Никлаус Вирт

Чарльз Хоар

Дональт Кнут

Программа+

Computer ScienceЗакон ВиртаПрограммы становятся медленне более быстро, чем компьютеры становятся быстрееP

Абстракции

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

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

Веб-графы

Веб-графы

Случайные графыНаблюдения Барабаши-АльбертКак устроен web-граф?Barabashi, Albert, 1999, 20005 млрд вершин, псевдомультиорграфКлючевые

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

Случайные графыМодель Эрдёша-РеньиG(n,p)V = {1, 2, …, n}, Eрёбра проводятся взаимно-независимо

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

Highway dimension

Highway dimensionПочему современные алгоритмы на картах работают очень быстро100000 млн вершинВремя

P vs NP

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

Классы задач

P vs NPЗадача поиска задаётся алгоритмом C, который получает на вход

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

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

Похожие презентации

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

Программа
+

Computer Science
Закон Вирта
Программы становятся медленне более быстро, чем компьютеры становятся быстрее
P

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

Случайные графы
Наблюдения Барабаши-Альберт
Как устроен web-граф?
Barabashi, Albert, 1999, 2000
5 млрд вершин, псевдомультиорграф
Ключевые

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

Случайные графы
Модель Эрдёша-Реньи
G(n,p)
V = {1, 2, …, n}, E
рёбра проводятся взаимно-независимо

Highway dimension
Почему современные алгоритмы на картах работают очень быстро
100000 млн вершин
Время

P vs NP
Задача поиска задаётся алгоритмом C, который получает на вход