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

ru en cn

с начала прошло: 8968 д. 07:37
страница обновлена: 21.07.2024 07:36

Алгоритмы и структуры данных 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.
  • Конечные автоматы. Автомат Кнута-Морриса-Пратта.

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

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