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

1. О курсе

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

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

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

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

Устный опрос в начале занятия по теме прошлой лекции или в конце занятия по пройденной теме. Лабораторные работы по профилированию производительности (построение графиков зависимости количества операций от размера входных данных). Групповой проект по разработке программного модуля с использованием изученных архитектурных паттернов. Участие в командном соревновании по спортивному программированию (внутрисеместровое). Ведение технического дневника разработчика (лог принятых решений при реализации Д/З).

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

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

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

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

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

Итоговая оценка складывается из следующих компонентов:

Накопленная оценка за домашние задания и практические задачи — 50%. Посещаемость и активность на семинарах (включая устные опросы) — 20% (бонусный компонент). Дифференцированный зачет (устная форма) — 30%.

6.1 Бонусы

Рекомендуется учитывать посещаемость и активность (~20%). Дополнительные баллы могут начисляться за:

досрочную сдачу работ; помощь одногруппникам в чате курса; выявление ошибок в методических материалах; участие во внешних хакатонах по профилю курса.

6.2 Дедлайны и штрафы

Если используется система штрафов — важно её прописать. Пример стандартной политики:

Задержка до 24 часов: штраф -10% от балла за работу. Задержка от 24 до 72 часов: штраф -30% от балла за работу. Более 72 часов без уважительной причины: работа не принимается (0 баллов). Правило «жизни»: одна работа может быть сдана без штрафа позже срока при условии предварительного уведомления.

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

Руководитель курса: Дединский И.Р. Преподаватели: [ФИО будут добавлены] Ассистенты: [будут назначены при необходимости]

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

Папка с материалами: [ссылка]. Если вы не готовы делиться в открытый доступ, то материалы будут закрыты и доступны только дирекции и кафедре.

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

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