ShareMIPT. Алгоритмы и структуры данных.

Лекции

Лекция 1. Введение. Сложность алгоритмов. Корректность алгоритмов. Сложность операций. Абстракции.

Лекция 2. Рекурсия. Разделяй и властвуй. Основная теорема о рекурсии. Быстрое вычисление степеней.

Лекция 3. Жадные алгоритмы.

Лекция 4. Сортировка.

Лекция 5. Сортировка. Поиск.

Лекция 6. Специальные деревья.

Лекция 7. Списки и деревья.

Лекция 8. Сбалансированные деревья.

Лекция 9. Хеш-функции.

Лекция 10. Хеш-таблицы.

Лекция 11. Динамическое программирование.

Лекция 12. Динамическое программирование-2.

Лекция 13. Графы-1. Представление. Обход BFS, DFS. Топологическая сортрировка.

Лекция 14. Графы-2. Поиск компонент сильной связности. Поиск точек сочленения и мостов. Минимальные остовные деревья. Алгоритма Прима.

Лекция 15. Графы-3. Система непересекающихся множеств. Алгоритм Краскала. Поиск кратчайшего пути. Алгоритм Дейкстры.

Лекция 16. Графы-4. Алгоритм Флойда-Уоршалла. Потоки. Двудольные графы и паросочетания.

Лекция 17. Числа. Клеточные автоматы. Работа с битами. Простые числа. Решето Эратосфена. Решето Аткинса.

Лекция 18. Числа. ОТА. Теорема Ферма. Функция Эйлера. Китайская теорема об остатках. Обратные числа по модулю. Алгоритм Гарнера.

Лекция 18. Числа. Побитовый GCD. Теорема Ферма. Функция Эйлера. КТО. Алгоритм Гарнера.

Лекция 19. Числа. Определение простоты числа. Алгоритм Миллера-Рабина. Разложение на простые множители. Алгоритм ро-Полларда.

Лекция 20. Числа. Длинная арифметика. Быстрое преобразование Фурье. Деление. Извлечение корня.

Лекция 21. Вычислительная геометрия. Основные понятия. Триангуляция многоугольника.

Лекция 22. Вычислительная геометрия. Выпуклые оболочки. Алгоритмы Джарвиса, Энжрю, Грэхема. Динамические выпуклые оболочки. Convex Hull Trick.

Лекция 23. Вычислительная геометрия. Диаметр множества точек – алгоритм вращающиеся калиперы. Сумма Минковского. Нахождение общих точек выпуклых многоугольников.

Лекция 25. Строки. Префикс-функция. Бор. Алгоритм Ахо-Корасик.

Лекция 26. Суффиксный массив. LCP. Алгоритм Касаи. Sparse table.

Лекция 27. Вокруг неполиномиальности.

....

Контесты

Пробный контест.

Семинарский контест.

Домашняя работа 1.

Домашняя работа 2.

Домашняя работа 3.

Домашняя работа 4.

Домашняя работа 5.

Домашняя работа 6.

Домашняя работа 7.

Домашняя работа 8.

Домашняя работа 9.

Контрольная работа 1.

Семинары

Исходные файлы для семинарских занятий.