ИВТ. Алгоритмы и структуры данных. Базовый поток 2026

1. О курсе

Дисциплина включает подробное освещение практики реализации структур данных и программ, решений практических задач, а также предполагает самостоятельное изучение студентами материала предмета через решение домашних практических задач. Большое внимание уделяется базовым принципам построения архитектуры ПО, практикам разработки.

Пререквизиты: Для освоения курса необходимы базовые понимания о понятии алгоритма и работе компьютера.

2. Программа курса

Неделя	Лекция/Семинар	Д/З	Контроль / событие	Дедлайн
1–3	Основные понятия структур данных. Концепция типа данных. Простейшие типы данных. Простейшие стандартные типы данных. Ограниченные типы (диапазоны). Массивы. Записи. Записи с вариантами. Множества. Представление массивов, записей и множеств. Последовательности (элементарные операции, буферизация, стандартные ввод и вывод).
4–6	Данные с динамической структурой. Линейные списки: основные операции, упорядоченные списки и перестройка списков. Стеки, очереди, деки, нелинейные структуры данных, иерархические списки, мультисписки. Реализация перечисленных структур данных. Стандартные классы в ООП, поддерживающие динамические структуры.
7–11	Алгоритмы поиска. Задачи поиска и кодирования (сжатия) данных. Кодовые деревья, оптимальные префиксные коды, исчерпывающий поиск. Линейный поиск. Поиск делением пополам (двоичный поиск). Поиск в таблице. Прямой поиск строки. Поиск в строке (алгоритмы Кнута, Мориса и Прата). Алгоритмы Боуэра-Мура. Алгоритмы Рабина-Карпа.
12–16	Быстрый доступ к данным. Хеширование данных. Способы вычисления хеш-функций. Разрешение коллизий. Линейное, квадратичное опробование. Метод цепочек, двойное хеширование. Оценка качества хеш-функций. Инвертированные индексы. Битовые карты.

3. Коммуникация

Чат курса (Telegram или другой мессенджер).

4. Прогресс студентов

Таблица с оценками, доступная студентам.

5. Критерии оценивания и формы контроля успеваемости

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

6. Команда курса

Руководитель и лектор курса: Дивари Ирина Николаевна Ассистент: Карецкий Владислав Олегович

7. Материалы курса

Перечень типовых вопросов для промежуточной аттестации:

1. Моделирование абстрактных типов данных (АТД) для различных реализаций (табличное, списковое, комбинированное и т.д.).
2. Поиск информации в различных структурах данных с использованием классических алгоритмов поиска в текстовой информации.
3. Исследование эффективности алгоритмов сортировок для различных структур и размерностей данных.
4. Реализация структур данных типа дерево и типовые алгоритмы их обработки.
5. Реализация функций расстановки (хеширование) и различных методов разрешения коллизий.
6. Реализовать алгоритмы поиска: КМП – алгоритм.
7. Реализация алгоритма Боуэра-Мура.
8. Алгоритм Рабина-Карпа.
9. Построение графика зависимости количества операций сравнения от количества символов в массиве.
10. Определение временной сложности алгоритма и сравнение с экспериментальными исследованиями.