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

Цели дисциплины

Дисциплина предназначена для студенов младших курсов, профессионально направленных на профессию программиста. Изучение дисциплины требует наличия базовых навыков алгоритмизации, склонности к математическому и техническому мышлению, готовности к высокой нагрузке.

Данная дисциплина НЕ рекомендуется как введение в программирование для непрофильных направлений подготовки.

Критерии оценки

На оценку по данной дисциплине влияют теоретические знания в форме устного экзамена и/или колловкиумов (30-50%), практическое решения задач на онлайн-платформе (30-50%), участие в специализированных мероприятиях (в том числе Rucode, ICPC) (30-50%).

Основы информатики и языка программирования

1. Общее устройство универсального компьютера. Архитектура фон-Неймана. Принцип хранимой программы. Гарвардская архитектура.
2. Представление целых чисел. Прямое, обратное и дополнительное кодирование.
3. Представление вещественных чисел. Проблемы точности вычислений. Абсолютная и относительная погрешность.
4. Основные операторы языка C/С++.
5. Скалярные типы данных языка C/С++.
6. Операции и приоритеты в языке C/С++.
7. Массивы и структуре в языке C/С++.
8. Указатели и управление памятью в языке C/С++.
9. Функции, передача параметров в языке C/С++.

Алгоритмы 1 (1 семестр)

Ответы на все вопросы должны включать:

Определения структур данных. Описания алгоритмов. Оценки затрат времени и памяти. Неформальные доказательства корректности и эффективности.

1. Поиск. Бинарный поиск, бинарный поиск строк. Интерполяционный поиск. Бинарный поиск по ответу. Тернарный поиск.
2. Простейшие структуры данных. Динамические массивы. Связные списки.
3. Поиск в глубину, поиск в ширину, задачи на лабиринтах.
4. Сортировка слиянием. Сортировка связных списков. Сортировка подсчётом, карманная (bucket) и поразрядная сортировка. Сортировка patience.
5. Быстрая сортировка, порядковые статистики. Нахождение порядковой статистики за линейное в среднем время.
6. Куча. Свойства, операции, построение. Очереди с приоритетами, сортировка кучей.
7. Запросы суммы и минимума на отрезке. Частичные суммы, дерево минимумов. Деревья отрезков, операции обновления и поиска.
8. Запросы суммы и минимума в многомерном случае. Поиск ближайшего общего предка.
9. Отображения. Хэш-таблицы. Подбор хэш-функции. Способы разрешения коллизий в хэш-таблицах: списки, открытая адресация.
10. Перебор, перебор с возвратом, комбинаторика, отсечения, метод ветвей и границ, альфа-бета-отсечение.
11. Динамическое программирование. Принцип оптимальности Беллмана. Задачи о наибольшей общей/возрастающей подпоследовательности, порядке перемножения матриц. Восстановление ответа.
12. Жадные алгоритмы. Эвристические применения. Задача о покрытии отрезка (выборе заявок). Метод двух указателей.
13. Динамическое программирование в пространстве ответа. Задачи о разрезании стержня, рюкзаке дискретном и непрерывном.
14. Поиск подстрок. Префикс-функция. z-функция. Алгоритмы Кнута-Морриса-Пратта, Рабина-Карпа.

Алгоритмы 2 (2 семестр)

1. Метод разделения на подзадачи. Рекуррентные соотношения и способы их решения. Мастер-теорема.
2. Факторизация целых чисел. НОД и НОК. Решето Эратосфена. Малая теорема Ферма. Операции по модулю.
3. Кратное хеширование. Неточный поиск. Фильтры Блума, оценка вероятности ошибки. Операции объединения, пересечения, удаления.
4. Хеширование методами кукушки и Робин-Гуда. Совершенное хеширование.
5. Алгоритм Бойера-Мура (с правилом Галила).
6. Бинарные деревья поиска. Операции добавления, удаления, поиска. АВЛ-деревья: условие балансировки, вывод оценки высоты, повороты, балансировка.
7. Красно-чёрные деревья.
8. Понятия графа, орграфа, петель, кратных рёбер, цепочек, циклов, простых цепочек, простых циклов. Поиск в ширину.
9. Поиск в глубину, леммы о белом пути и отсутствии перекрёстных рёбер. Поиск циклов. Эйлеров граф, эйлеров путь. Топологическая сортировка. Связные и сильно связные компоненты.
10. Минимальное остовное дерево. Алгоритмы Крускала (без разбора СНМ), Прима, Борувки.
11. Кратчайшие пути. Алгоритмы Дейкстры, Беллмана-Форда, Флойда-Уоршалла.
12. Мосты, точки сочленения.
13. Лес непересекающихся множеств.
14. Двудольные графы. Паросочетания в двудольном графе.
15. Понятия задачи, алгоритма, класса сложности P, проверяющего алгоритма, класса сложности NP, сводимости одной задачи к другой, классов сложности NP-complete, NP-hard.

Дополнительные вопросы

Ответ на каждый вопрос даёт от 0 до 2 баллов.

• Динамика по подмножествам, динамика по рваному краю.
• Деревья Фенвика.
• Палиндромы, алгоритм Манакера.
• Порядковые статистики за линейное в худшем случае время (медиана медиан, BFPRT).
• Фибоначчиева куча.
• Преобразование Барроуза-Уилера. Преобразование Move-to-Front.

• Конечные автоматы. Автомат Кнута-Морриса-Пратта.

• Умножение Карацубы.

• Префиксное дерево.
• Сильная и кратная связность графов.
• Изоморфизм графов. Изоморфизм деревьев.
• Потоки на графах. Алгоритм Эдмондса-Карпа.