Чат курса https://t.me/icpc_msu
Спецкурс рассчитан на начинающих студентов, которые хотят узнать больше о спортивном программировании, освоить базовые алгоритмы и структуры данных.
Курс состоит из онлайн лекций и семинаров. Лекции будут проходить по четвергам с 16:45, семинары — по средам в то же время. Первое занятие состоится 29 февраля. На лекции рассматриваются алгоритмы и структуры данных, примеры задач с их использованием. Записи лекций публикуются. На семинаре мы разбираем и обсуждаем задачи.
1. Вводная лекция. C++.
Примитивные типы данных. Операторы (арифметические, сравнения, IO). Синтаксические кон
струкции (условия, циклы, функции). Оценка времени работы программы. IDE. Отладчик.
2. Линейные структуры данных.
Динамический массив. Стек. Очередь. Дек. Список. Реализация на массиве и на указателях.
Классы vector, stack, queue, deque, list, forward_list.
3. Сортировки.
Сортировка пузырьком, выбором. Быстрая сортировка. Сортировка слиянием. Сортировка подсчетом. Функция sort. Компараторы.
4. Бинарный поиск.
Бинарный поиск в массиве. Бинарный поиск по функции. Бинарный поиск по ответу. Функции
lower_bound, upper_bound, binary_search.
5. Древовидные структуры данных.
Бинарное поисковое дерево. Бинарная куча. Упорядоченное множество. Ассоциативный массив. Классы set, multiset, map. Компараторы.
6. Теория чисел.
Проверка числа на простоту. Решето Эратосфена. Факторизация. Алгоритм Евклида. Быстрое
возведение в степень. Арифметика по модулю. Поиск обратного числа по простому модулю.
7. Жадные алгоритмы.
Жадные алгоритмы. Применения в задачах.
8. Динамическое программирование.
Одномерное ДП. Наибольшая возрастающая подпоследовательность. Многомерное ДП. Задача о рюкзаке. Наибольшая общая подпоследовательность.
9. Графы.
Определения. Обход в глубину. Поиск компонент связности. Поиск цикла.
10. Кратчайшие пути в графах.
Обход в ширину. Алгоритм Дейкстры. Алгоритм Форда-Беллмана. Алгоритм Флойда.
11. Строки.
Хеш. Полиномиальный хеш. Префикс-функция. Z-функция.