Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 13 лет назад пользователемmaxkalachev
1 Soft war e Clou d Serv ices Обзор современного состояния области алгоритмов и структур данных Калачёв Максим Александрович Разработчик
2 l SoftwareSoftware CloudCloud ServicesServices Идеи
3 l SoftwareSoftware CloudCloud ServicesServices План Computer Science Web-графы Случайные графы Highway dimenstion NP vs P Что осталось нерассмотренным Послесловие
4 l SoftwareSoftware CloudCloud ServicesServices Теоретики
5 l SoftwareSoftware CloudCloud ServicesServices Практики
6 l SoftwareSoftware CloudCloud ServicesServices Программисты
7 l SoftwareSoftware CloudCloud ServicesServices Эдгар Дейкстра
8 l SoftwareSoftware CloudCloud ServicesServices Никлаус Вирт
9 l SoftwareSoftware CloudCloud ServicesServices Чарльз Хоар
10 l SoftwareSoftware CloudCloud ServicesServices Дональт Кнут
11 l SoftwareSoftware CloudCloud ServicesServices Программа +
12 l SoftwareSoftware CloudCloud ServicesServices Computer Science Закон Вирта Программы становятся медленне более быстро, чем компьютеры становятся быстрее P = A = M - множество процедур решения задачи R 2 M ² - бинарное отношение на M ( i, j ) R 2 после пройедуры i выполняется процедура j
13 l SoftwareSoftware CloudCloud ServicesServices Абстракции
14 l SoftwareSoftware CloudCloud ServicesServices Математическое моделирование
15 l SoftwareSoftware CloudCloud ServicesServices Теория графов + Теория вероятностей = PROFIT +
16 l SoftwareSoftware CloudCloud ServicesServices Веб-графы
17 l SoftwareSoftware CloudCloud ServicesServices Веб-графы
18 l SoftwareSoftware CloudCloud ServicesServices Случайные графы Наблюдения Барабаши-Альберт Как устроен web-граф? Barabashi, Albert, 1999, млрд вершин, псевдомультиорграф Ключевые свойства веб-графа: Разрежённость на k вершин kt рёбер, k 1 Диаметр графа {5, 6} Теория о шести рукопожатиях Степенное распределение степеней вершин P(d) c / d 2.1, c – нормирующий множитель
19 l SoftwareSoftware CloudCloud ServicesServices Случайные графы Наблюдения Барабаши-Альберт Веб-граф очень специфичен – разрежен и тесен Степенной закон объединяет социальные, биологические и транспортные сети Модели предпочтительного соединения
20 l SoftwareSoftware CloudCloud ServicesServices Случайные графы Модель Эрдёша-Реньи G(n,p) V = {1, 2, …, n}, E рёбра проводятся взаимно-независимо с вероятностью p [0, 1] в соответствии со схемой Бернулли e 1, …, e m, m = C 2 n – количество всех испытаний Вероятностное пространство n = {G = (V n, E)} – множество элементарных событий F n = 2 n – множество событий P n,p (G) = p |E| (1-p) m-|E| - вероятность повления конкретного графа
21 l SoftwareSoftware CloudCloud ServicesServices Транспортная интерпретация
22 l SoftwareSoftware CloudCloud ServicesServices Highway dimension
23 l SoftwareSoftware CloudCloud ServicesServices Highway dimension Почему современные алгоритмы на картах работают очень быстро млн вершин Время работы c Интуитивные идеи: Указатели на дугах Поиск A* Достижимость Шоссейная и желаемые иерархии Перевалочные пункты
24 l SoftwareSoftware CloudCloud ServicesServices P vs NP
25 l SoftwareSoftware CloudCloud ServicesServices 1 миллион долларов!
26 l SoftwareSoftware CloudCloud ServicesServices Классы задач
27 l SoftwareSoftware CloudCloud ServicesServices P vs NP Задача поиска задаётся алгоритмом C, который получает на вход условие I и кандидата на решение S и имеет полиномиальное, относительно I время работы. S называется решением если и только если C(S, I) = true NP – класс всех задач поиска, решение для которых может быть быстро проверено P – класс задач поиска, решение для которых может быть быстро найдено P NP – верно ли, что каждый раз, когда решение можно быстро проверить, его можно быстро найти Задача о расписании Задача о вершинном покрытии A B
28 l SoftwareSoftware CloudCloud ServicesServices Андрей Михайлович Райгородский
29 l SoftwareSoftware CloudCloud ServicesServices Андрей Гольдберг
30 l SoftwareSoftware CloudCloud ServicesServices Что осталось нерассмотренным Параллельные алгоритмы Распознавание изображений Нейронные сети Генетические алгоритмы Нечёткие модели Строковые алгоритмы Комбинаторная оптимизация Численные алгоритмы Вычислительная геометрия Криптографические алгоритмы Компьютерная лингвистика ……..
31 l SoftwareSoftware CloudCloud ServicesServices Так говорил Дейкстра I think it wise, and only honest, to warn you that my goal is immodest. It is not my purpose to "transfer knowledge" to you that, subsequently, you can forget again. My purpose is no less than to effectuate in each of you a noticeable, irreversable change. I want you to see and absorb calculational arguments so effective that you will never be able to forget that exposure. I want you to gain, for the rest of your lives, the insight that beautiful proofs are not "found" by trial and error but are the result of a consciously applied design discipline. I want to inspire you to raise your quality standards. I mean, if 10 years from now, when you are doing something quick and dirty, you suddenly visualize that I am looking over your shoulders and say to yourself "Dijkstra would not have liked this.", well, that would be enough immortality for me.
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.