Простые алгоритмы и базовые структуры данных
В первом модуле мы научимся решать комбинаторные задачи полным перебором с использованием вложенных циклов и рекурсии, сравним эффективности различных алгебраических алгоритмов, поработаем с битовой арифметикой на примере шахматной доски, а также напишем реализацию базовых структур данных, которые вы будете использовать при составлении программ в рамках этого курса.
Тема 1: Циклы и рекурсия
Тема 2: Как выполнять домашние задания
Тема 3: Алгебраические алгоритмы
Тема 4: Базовые структуры данных
Тема 5: Битовая арифметика
Алгоритмы сортировки
В этом модуле мы рассмотрим самые разные алгоритмы сортировки данных, начиная самыми медленными и заканчивая эффективными алгоритмами, которые работают за линейное время, также мы напишем алгоритм внешней сортировки, когда все данные не могут быть загружены в память программы. На последнем занятии мы рассмотрим алгоритм нахождения порядковых статистик за линейное время.
Тема 1: Простые сортировки
Тема 2: Пирамидальная сортировка
Тема 3: Быстрая и внешняя сортировка
Тема 4: Линейная сортировка
Деревья поиска
В этом модуле мы окажемся в заповеднике деревьев поиска, познакомимся с их разновидностями, особенностями, правилами добавления и удаления элементов, методами балансировки на больших и малых поворотах. Вы узнаете про АВЛ и красно-чёрные деревья, расширяющиеся и рандомизированные деревья, о сильноветвящихся В-деревьях и про дерево отрезков, которое помогает быстро и просто вычислять ассоциативную функцию на любом отрезке массива.
Тема 1: Двоичные деревья поиска АВЛ
Тема 2: Красно-чёрные деревья
Тема 3: Другие варианты деревьев поиска
Хеш-таблицы
В этом модуле мы познакомимся с хэшированием, научимся создавать хэш-функции, вычислять хэш-значения для разных ключей-объектов, добавлять и удалять элементы в хэш-таблицу, рассмотрим различные способы разрешения коллизий. Мы также узнаем, что такое универсальное хэширование и как сэкономить время и место, используя идеальное хэширование для статического набора ключей.
Тема 1: Хэш-функции и хэш-таблицы
Тема 2: Разрешение коллизий
Тема 3: Универсальное и идеальное хэширование
Тема 4: «Префиксное дерево»
Тема 5: Зачётный англо-русский словарь.
Теория графов
В этом модуле мы повторим основные понятия и принципы теории графов, разберём алгоритмы поиска вширь и вглубь, топологической сортировки вершин и поиск минимального скелета, изучим несколько алгоритмов поиска кратчайшего пути и решения задачи коммивояжера. На отдельном занятии мы рассмотрим алгоритмы работы с виртуальной памятью.
Тема 1: Определения и представления
Тема 2: Поиск и сортировка
Тема 3: Минимальный скелет
Тема 4: Кратчайший путь
Тема 5: Задача коммивояжёра
Тема 6: Управление памятью
Алгоритмы на строках
В этом модуле мы рассмотрим разные алгоритмы поиска шаблона в тексте, от самых примитивных до более сложных с построением бора для конечного недетерминированного автомата с возможностью поиска нескольких шаблонов за один подход. В конце модуля мы рассмотрим три алгоритма сжатия данных, а также введение в теорию криптоанализа на конкретных примерах де/шифрования, обмена ключами, подбора паролей.
Тема 1: Алгоритм Бойера-Мура
Тема 2: Алгоритм Ахо-Корасика
Тема 3: Алгоритм Кнута-Морриса-Пратта
Тема 4: Алгоритмы сжатия
Тема 5: Шифрование данных
Динамическое программирование
В этом модуле мы рассмотрим различные способы кэширования в некоторых языках программирования, познакомимся с методом динамического программирования и решим несколько задач.
Тема 1: Алгоритмы кэширования
Тема 2: Динамическое программирование
Олимпиадное программирование
В этом модуле мы решим несколько задач различной сложности на сайте leetcode.com. Задачи решаем разными способами, на нескольких языках программирования.
Тема 1: Сложная задача
Тема 2: Dancing Links
Вероятностные алгоритмы
Рассматриваем и решаем задачи из области больших данных вероятностными методами с использованием различных структур данных.
Тема 1: Фильтр Блума
Тема 2: Алгоритмы MinHash, SimHash
Тема 3: Алгоритмы HyperLogLog, Count-Min Sketch
Проектная работа
Заключительный месяц курса посвящен проектной работе. Свой проект — это то, что интересно писать слушателю. То, что можно создать на основе знаний, полученных на курсе. При этом не обязательно закончить его за месяц. В процессе написания по проекту можно получить консультации преподавателей.
Тема 1: Выбор темы и организация проектной работы
Тема 2: Консультация по проектам и домашним заданиям
Тема 3: Защита проектных работ
Тема 4: Подведение итогов курса
