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

Бакалавриат 2024/2025

Статус: Курс обязательный (Дизайн и разработка информационных продуктов)

Направление: 09.03.04. Программная инженерия

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

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 2, 3 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Горденко Мария Константиновна, Мануйленко Никита Сергеевич

Язык: русский

Кредиты: 7

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

Авторы

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

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