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

2024/2025

Учебный год

RUS

Обучение ведется на русском языке

7

Кредиты

Кто читает:

Департамент больших данных и информационного поиска

Статус:

Курс обязательный

Когда читается:

1-й курс, 2, 3 модуль

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

Горденко Мария Константиновна

Мануйленко Никита Сергеевич

Программа дисциплины

Аннотация

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

Цель освоения дисциплины

• Изучение базовых алгоритмов и структур данных.
• Развитие навыков обоснования корректности алгоритмов, их практической реализации, теоретической и экспериментальной оценки их временной сложности.

Планируемые результаты обучения

• Знать о наиболее важных алгоритмах и структурах данных и основных принципах их проектирования и анализа
• Уметь обосновывать корректность алгоритмов, проводить теоретическую и экспериментальную оценки их временной сложности
• Уметь формализовать условие задачи, требующей алгоритмического решения, разбить задачу на подзадачи, сформулировать эффективный алгоритм решения задачи
• Иметь навыки реализации алгоритмов на языках Python

Содержание учебной дисциплины

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

Элементы контроля

• Домашнее задание
  Еженедельное домашнее задание в виде контеста, состоящее из задач, которые необходимо сдать в систему для автоматической проверки. Выдается после проведения занятия по соответствующей теме.
• Активность
  Балл за работу и активность на семинаре, ответы на вопросы.
• Контрольная работа 1
  Контрольная работа содержит задачи по пройденной теме и выдается по окончании модуля.
• Контрольная работа 2
• Экзамен
  Экзамен письменный, проходит посредством сдачи теории и задач автоматически проверяемых (контестов).

Промежуточная аттестация

• 2024/2025 3rd module
  0.1 * Активность + 0.2 * Домашнее задание + 0.2 * Контрольная работа 1 + 0.3 * Контрольная работа 2 + 0.2 * Экзамен

Список литературы

Рекомендуемая основная литература

• Алгоритмы: построение и анализ : пер.с англ., Кормен, Т., 2013

Рекомендуемая дополнительная литература

• Computational Complexity, A Modern Approach, 1st published 2009, 4th printing, XXIV, 579 p., Arora, S., Barak, B., 2016
• Искусство программирования для ЭВМ. Т. 3: Сортировка и поиск, Кнут, Д., 1978
• Искусство программирования. Т. 2: Получисленные алгоритмы, Кнут, Д., 1977

Авторы

• Сысоева Алевтина Александровна
• Кононова Елизавета Дмитриевна