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

О курсе

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

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

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

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

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

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

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

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

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

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

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

Руководитель и лектор курса: Дивари Ирина Николаевна

Ассистент: Карецкий Владислав Олегович

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

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

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