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

1. О курсе

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

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

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

Неделя	Лекция	Семинар	Д/З	Контроль / событие	Дедлайн 1–3 - 4–6 - 7–11 - 12–16 } Детальное содержание программы 1. Основные понятия структур данных Концепция типа данных. Простейшие типы данных. Простейшие стандартные типы данных. Ограниченные типы (диапазоны). Массивы. Записи. Записи с вариантами. Множества. Представление массивов, записей и множеств. Последовательности (элементарные операции, буферизация, стандартные ввод и вывод). 2. Данные с динамической структурой Линейные списки: основные операции, упорядоченные списки и перестройка списков. Стеки, очереди, деки, нелинейные структуры данных, иерархические списки, мультисписки. Реализация перечисленных структур данных. Стандартные классы в ООП, поддерживающие динамические структуры. 3. Алгоритмы поиска Задачи поиска и кодирования (сжатия) данных. Кодовые деревья, оптимальные префиксные коды, исчерпывающий поиск. Линейный поиск. Поиск делением пополам (двоичный поиск). Поиск в таблице. Прямой поиск строки. Поиск в строке (алгоритмы Кнута, Мориса и Прата). Алгоритмы Боуэра-Мура. Алгоритмы Рабина-Карпа. 4. Алгоритмы сортировки Анализ сложности и эффективности алгоритмов поиска и сортировки. Оценка временной и пространственной сложности алгоритмов на основе асимптотических соотношений (О – и Ω-нотации). Порядковые статистики. Сортировка массивов: прямым включением, прямым выбором и прямым обменом. Улучшенные методы сортировки: включениями с уменьшающимися расстояниями, с помощью дерева, разделением. Нахождение медианы. Сравнение методов сортировки массивов. Файлы: организация и обработка. Сортировка файлов: прямое слияние, естественное слияние, сбалансированное многопутевое слияние, многофазная сортировка, распределение начальных серий. 5. Быстрый доступ к данным Хеширование данных. Способы вычисления хеш-функций. Разрешение коллизий. Линейное, квадратичное опробование. Метод цепочек, двойное хеширование. Оценка качества хеш-функций. Инвертированные индексы. Битовые карты. 3. План домашних заданий Недели 1–3: Реализация простейших типов данных и статических структур (массивы, записи, множества). Буферизация ввода-вывода. Дедлайн: [указать дату] Недели 4–6: Реализация линейных динамических структур (списки, стеки, очереди, деки). Использование стандартных классов ООП. Дедлайн: [указать дату] Недели 7–11: Реализация алгоритмов поиска (включая КМП — алгоритм Кнута-Мориса-Прата, Бойера-Мура, Рабина-Карпа). Построение оптимального префиксного кода. Дедлайн: [указать дату] Недели 12–16: Реализация различных видов сортировок и хеширования. Исследование временной сложности. Дедлайн: [указать дату] Другие виды активности: Устный опрос в начале занятия по теме прошлой лекции или в конце занятия по пройденной теме. Лабораторные работы по профилированию производительности (построение графиков зависимости количества операций от размера входных данных). Групповой проект по разработке программного модуля с использованием изученных архитектурных паттернов. Участие в командном соревновании по спортивному программированию (внутрисеместровое). Ведение технического дневника разработчика (лог принятых решений при реализации Д/З). 4. Коммуникация Чат курса (Telegram или другой мессенджер). Если создаете самостоятельно, присылайте ссылку после первого занятия в семестре. При необходимости помогу настроить. Форум для технических вопросов (например, ветка в LMS или отдельный канал), где ответы публикуются публично для всей группы. Еженедельные онлайн-консультации преподавателя (офлайн-часы). 5. Прогресс студентов Таблица с оценками, доступная студентам. Если создается самостоятельно, присылайте ссылку после первого занятия в семестре. Автоматический дашборд успеваемости в системе LMS (выполнение Д/З, накопленный балл). 6. Критерии оценивания и формы контроля успеваемости Итоговая оценка складывается из следующих компонентов: Накопленная оценка за домашние задания и практические задачи — 50%. Посещаемость и активность на семинарах (включая устные опросы) — 20% (бонусный компонент). Дифференцированный зачет (устная форма) — 30%. 6.1 Бонусы Рекомендуется учитывать посещаемость и активность (~20%). Дополнительные баллы могут начисляться за: досрочную сдачу работ; помощь одногруппникам в чате курса; выявление ошибок в методических материалах; участие во внешних хакатонах по профилю курса. 6.2 Дедлайны и штрафы Если используется система штрафов — важно её прописать. Пример стандартной политики: Задержка до 24 часов: штраф -10% от балла за работу. Задержка от 24 до 72 часов: штраф -30% от балла за работу. Более 72 часов без уважительной причины: работа не принимается (0 баллов). Правило «жизни»: одна работа может быть сдана без штрафа позже срока при условии предварительного уведомления. 7. Команда курса Руководитель курса: Дединский И.Р. Преподаватели: [ФИО будут добавлены] Ассистенты: [будут назначены при необходимости] 8. Материалы курса Папка с материалами: [ссылка]. Если вы не готовы делиться в открытый доступ, то материалы будут закрыты и доступны только дирекции и кафедре. Перечень типовых вопросов для промежуточной аттестации Моделирование абстрактных типов данных (АТД) для различных реализаций (табличное, списковое, комбинированное и т.д.). Поиск информации в различных структурах данных с использованием классических алгоритмов поиска в текстовой информации. Исследование эффективности алгоритмов сортировок для различных структур и размерностей данных. Реализация структур данных типа дерево и типовые алгоритмы их обработки. Реализация функций расстановки (хеширование) и различных методов разрешения коллизий. Реализовать алгоритмы поиска: КМП – алгоритм. Реализация алгоритма Боуэра-Мура. Алгоритм Рабина-Карпа. Построение графика зависимости количества операций сравнения от количества символов в массиве. Определение временной сложности алгоритма и сравнение с экспериментальными исследованиями.