О курсе

Цель данного курса – изучить классический набор алгоритмов и структур данных, использующихся в программировании, охватив все области алгоритмических задач – от поиска по массиву до работы со строковыми данными и геометрией. В ходе курса студенты не только получат теоретические знания в теории алгоритмов, но и разовьют алгоритмическое мышление, необходимое для эффективного решение программных задач.

  • Чему вы научитесь?

    Студент освоит фундаментальные алгоритмы и структуры данных, научится реализовывать их на произвольном языке программирования, а также получит практику в решение алгоритмических задач.

  • На кого ориентирован курс?

    Курс ориентирован на любых студентов, заинтересованных в углублении своих знаний в программировании и алгоритмике.

  • Пререквизиты

    Владение любым языком программирования на базовом уровне (переменные, условные операторы, циклы, массивы, функции, структуры)

Преподаватели

  • Денис Крахмалев

    Java-разработчик, аспирант МФТИ

Программа

01

•Определение алгоритма.
•Переменные, массивы.
•Циклы, условные переходы.
•Рекурсия.
•Примеры простых алгоритмов: вычисление числа Фибоначчи, проверка числа на простоту.
•Определение структуры данных, абстрактного типа данных (интерфейса).
•Динамический массив.
•Двусвязный и односвязный список.
•Стек.
•Очередь.
•Дек.
•Массив. Линейный поиск. Бинарный поиск.
•Асимптотические обозначения, работа с ними.
•Асимптотика простых алгоритмов.
•Двоичная куча. АТД “Очередь с приоритетом”.

02

•Общая идея жадных алгоритмов. Задача о рюкзаке.
•Динамическое программирование. Восходящее ДП. Нисходящее ДП, кэширование результатов. Вычисление чисел Фибоначчи.
•Нахождение наибольшей возрастающей подпоследовательности за O(N2) и за O(N log N).
•Нахождение наибольшей общей подпоследовательности.
•Методы восстановления ответа в задачах динамического программирования.
•Расстояние Левенштейна. Восстановление редакционного пути.
•Задача Коммивояжёра. Метод ветвей и границ.
•Естественные алгоритмы. Алгоритм муравьиной колонии.
•Алгоритм роя пчёл (два варианта).

03

•Формулировка задачи. Устойчивость, локальность.
•Квадратичные сортировки: сортировка вставками, выбором.
•Сортировка слиянием.
•Сортировка с помощью кучи.
•Быстрая сортировка. Выбор опорного элемента. Доказательство среднего времени работы.
•Сортировка подсчетом. Карманная сортировка.
•Поразрядная сортировка.
•MSD, LSD. Сортировка строк.
•Хеш-функции. Остаток от деления, мультипликативная.
•Полиномиальная. Ее использование для строк. Метод Горнера для уменьшения количества операций умножения при ее вычислении.
•Хеш-таблицы. Понятие коллизии.
•Метод цепочек (открытое хеширование).
•Метод прямой адресации (закрытое хеширование).
•Линейное пробирование. Проблема кластеризации.
•Квадратичное пробирование.
•Двойное хеширование.

04

•Определение дерева, дерева с корнем. Высота дерева, родительские, дочерние узлы, листья. Количество ребер.
•Обходы в глубину. pre-order, post-order и in-order для бинарных деревьев.
•Обход в ширину.
•Дерево поиска.
•Поиск ключа, вставка, удаление.
•Необходимость балансировки. Три типа самобалансирующихся деревьев.
•АВЛ-дерево. Вращения. (кратко)
•Сплей-дерево. Операция Splay. (кратко)
•Поиск, вставка, удаление в сплей-дереве.
•Декартово дерево. Оценка средней высоты декартового дерева при случайных приоритетах (без доказательства).
•Декартово дерево по неявному ключу.
•Интерфейс быстрого массива: Доступ к элементу в позиции i, Вставка элемента в позицию i, Удаление элемента из позиции i, Конкатенация двух массивов, разделение массива на два.
•Красно-чёрное дерево.

05

•Ориентированный граф, неориентированный граф, псевдограф.
•Обход в глубину. Цвета вершин. Времена входа и выхода. Лемма о белых путях.
•Проверка связности неориентированного графа.
•Поиск цикла в неориентированном и ориентированном графе.
•Топологическая сортировка.
•Связность в неор. графе, компоненты связности.Слабая и сильная связность в ор. графе. Компоненты слабой, сильной связности.
•Нахождение компонент сильной связности. Алгоритм Косарайю.
•Компоненты реберной двусвязности. Мосты. Поиск мостов.
•Компоненты вершинной двусвязности. Точки сочленения. Поиск точек сочленения.
•Волновой алгоритм. Обход в ширину (применение очереди в волновом алгоритме).
•Критерий существования Эйлерова пути и цикла в ориентированном и неориентированном графе. Поиск эйлерова пути и цикла.

06

•Алгоритм Дейкстры. Доказательство корректности. Оценка времени работы. Дерево кратчайших путей.
•Алгоритм Флойда. Доказательство. Восстановление пути.
•Нахождение цикла отрицательного веса.
•Алгоритм Форда-Беллмана.
•Восстановление пути.
•Алгоритм A*. Условие монотонности на эвристику. Допустимость эвристики. Примеры эвристик.
•Остовное дерево. Построение с помощью обхода в глубину и в ширину.
•Определение минимального остовного дерева.
•Теорема о разрезе. Доказательство.
•Алгоритм Прима. Аналогия с алгоритмом Дейкстры.
•Определение сети. Определение потока.
•Определение разреза. Понятия потока через разрез.
•Доказательство факта, что поток через любой разрез одинаковый.
•Понятие остаточной сети. Понятие дополняющего пути.
•Необходимость отсутствия дополняющего пути для максимальности потока.
•Теорема Форда-Фалкерсона.
•Алгоритм Форда-Фалкерсона. Поиск минимального разреза.

07

•RSQ и RMQ.
•Sparse-table.
•Дерево отрезков.
•Обработка запросов от листьев.
•Обработка запросов от корня.
•Изменение значения в массиве, обновление дерева отрезков.
•Множественные операции.
•LCA. Метод двоичного подъема.
•Сведение LCA к задаче RMQ.
•Сведение RMQ к задаче LCA.

08

•Понятие префикс, суффикс, подстрока. Понятие собственных префикса и суффикса.
•Постановка задачи поиска подстроки в строке. Тривиальный алгоритм поиска подстроки в строке.
•Префикс-функция. Тривиальный алгоритм нахождения.
•Линейный алгоритм нахождения. Доказательство времени работы.
•Подсчет префикс-функции для строки q$t, где q — образец, а t — текст.
•Алгоритм Кнута-Морриса-Пратта. Поточная обработка текста без хранения префикс-функции для всей строки q$t.
•Z-функция. Тривиальный алгоритм нахождения.
•Линейный поиск Z-функции. Доказательство времени работы
•Применение для поиска подстроки в строке (КМП-2). Хранение Z-функции только для образца, а не для всей строки q$t.
•Построение строки по z-функции.
•Построение Префикс-функции строки при известной z-функции.
•Структура данных Бор. Построение, оценка времени построения и объема памяти.
•Алгоритм Ахо-Корасик. Суффиксная ссылка. Построение бора. Построение суффиксной ссылки. Оценка времени работы.
•Ситуации, когда один образец является суффиксом другого. «Длинные» суффиксные ссылки, то есть ссылки, идущие в следующую терминальную вершину, которая является суффиксом текущей.

09

•Суффиксный массив. Построение за O(n^2 log n).
•Поиск подстроки в тексте с использованием суффиксного массива.
•Построение суффиксного массива за O(n log n) с помощью удвоения префикса, по которому происходит цифровая сортировка.
•Алгоритм Касаи. Доказательство времени работы.
•Суффиксное дерево.
•Сжатое суффиксное дерево. Хранение сжатого суффиксного дерева. Тривиальное построение сжатого суффиксного дерева.
•Линейность числа вершин и ребер.

10

•Введение. Точка, вектор, отрезок. Скалярное произведение, векторное произведение. Прямая, плоскость.
•Выпуклая оболочка 2D.
•Алгоритм Джарвиса. Алгоритм Грэхема.
•Сумма Минковского двух выпуклых многоугольников за O(m + n).
•Сканирующая прямая.
•Проверка факта пересечения какой-либо пары отрезков из множества за O(n log n).

  • Кормен Томас Х., Лейзерсон Чарльз И., Ривест Рональд Л., Штайн Клиффорд “Алгоритмы. Построение и анализ
  • Роберт Седжвик “Algorithms in C++
  • Дональд Кнут “The Art of Computer Programming
  • Бхаргава Адитья “Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих
  • Bernhard von Stenge “Game Theory Basics
  • Муртаф Б “Современное линейное программирование

Поступающим

Как подать заявку на курс?

  • Написать мотивационное письмо

    В мотивационном письме студент должен пояснить зачем ему нужен курс, как он в дальнейшем планирует использовать полученные знания.

    Рекомендации для мотивационного письма →
  • Отправить письмо

    Мотивационные письма принимаются на почту [email protected] в формате PDF.

    В теме письма обязательно указать название интересующего вас курса.