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

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

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

Кто читает: Базовая кафедра Т-Банка

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

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

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

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

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

Кредиты: 8

Дополнительные материалы в LMS Задать вопрос

Аннотация

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

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

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

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

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

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

Понятие алгоритма. Способы измерения времени выполнения алгоритмов. Асимптотические нотации.
Мастер-теорема. Реккурентные соотношения
Линейные алгоритмы. Метод двух указателей.
Сортировка событий. Скользящее окно
Теория чисел. Алгоритм Евклида. СР
Решето Эратосфена. Факторизация чисел.
Рекурсивные алгоритмы.
Бинарный поиск. Целочисленный, вещественный бинарный поиск по ответу.
Тернарный поиск. Интерполяционный поиск.
Подготовка к контрольной.
Базовые сортировки.
Сортировка слиянием. Быстрая сортировка.
Структура данных куча. Пирамидальная сортировка.
Структуры данных и их классификация. Статический и динамический массив (Static and Dynamic Array). Стек (Stack). Очередь (Queue). Дек (Deque). Очередь с приоритетом (Priority Queue)
Односвязный список (Singly Linked List). Двусвязный список (Doubly Linked List).
Односвязный список (Singly Linked List). Двусвязный список (Doubly Linked List). СР
Хеш-функция и коллизии. Методы разрешения коллизий: метод цепочек и открытая адресация. Хеш-таблица.
Множество (Set) и словарь (Dictionary) несортированные.
Множество (Set) и словарь (Dictionary) сортированные.
Подготовка к коллоквиуму
Одномерная динамика.
Задача о рюкзаке.
Строки. Z-функция. Префикс функция.
Работа со строками. Строки. Динамика на строках.
Подготовка к контрольной
Графы. Основные понятия и определения. Способы задания графов. Поиск в глубину.
Алгоритмы на графах. Поиск в ширину.
Алгоритмы на основе обходов.
Кратчайшие пути.
Кратчайшие пути. СР
Система непересекающихся множеств. Алгоритмы построения остовного дерева.
Потоки-1.
Подготовка к коллоквиуму.
Потоки-2.
Деревья. Терминология деревьев.
Сбалансированные деревья. AVL-дерево. СР
Splay
Декартово дерево.
B-дерево/Красно-черное дерево
Подготовка к экзамену.

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

Домашнее задание
Контрольная работа
Коллоквиум
Самостоятельная работа
Экзамен

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

2025/2026 4th module
Формула оценки: О =0.15 * ОКЛ1 + 0.15 * ОКЛ2 + 0.15 * О ДЗ + 0.1 * ОКР1 + 0.1 * ОКР2 + 0.1 * ОСР + 0.25 * ОЭ Все оценки подставляются в формулу дробными, округляется только итог арифметически. ДЗ — оценка за ДЗ, СР - оценка за самостоятельные работы, КЛ1 и КЛ2 - оценка за коллоквиум, КР1 и КР2 — оценка за контрольную работу, Э — оценка за экзамен.

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

Авторы

Солдатова Татьяна Владимировна

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