• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Algorithms and Data Structures 1

2024/2025
Academic Year
RUS
Instruction in Russian
7
ECTS credits
Course type:
Compulsory course
When:
1 year, 2, 3 module

Instructor

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

Аннотация

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

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

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

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

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

Авторы

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