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

О курсе

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

1 курс, осенний семестр

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

Пререквизиты

• Базовые знания математики.
• Базовые знания и навыки работы с алгоритмами.

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

Лектор курса: Никулов Сергей.

Семинаристы: Мусаев Садык, Середа Андрей, Якушева София, Старокожко Иван, Бунин Лев.

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

Неделя	Лекция	Семинар
1	Асимптотика. Анализ алгоритмов. O-, Ω- и Θ-нотации. Временная сложность алгоритма. Модель вычисления.	Практика и задачи по теме лекции.
2	Рекурренты. Алгоритм Евклида. Бинарный поиск. Рекуррентные соотношения и способы их решения: метод подстановки, деревья рекурсии, Мастер-теорема (б/д). Алгоритм Евклида. Бинарный поиск по ответу. Примеры задач.	Практика и задачи по теме лекции.
3	Квадратичные сортировки. Сортировки выбором, вставками и пузырьком. Реализация, время работы и доказательство.	Практика и задачи по теме лекции.
4	Merge sort (сортировка слиянием). Сортировка слиянием с дополнительной памятью и Inplace. Реализация и анализ времени работы.	Практика и задачи по теме лекции.
5	Быстрая сортировка (Quicksort). Реализация. Разбиение Ломуто и Хоара. Доказательство времени работы. Барьер Ω(n log n) (б/д).	Практика и задачи по теме лекции.
6	Пирамидная сортировка (HeapSort). Бинарная пирамида. SiftUp и SiftDown. Построение пирамиды, пирамидальная сортировка и анализ времени работы.	Практика и задачи по теме лекции.
7	Лист. Стек. Очередь. Односвязные и двусвязные списки. Стек и очередь. Реализация на списках.	Практика и задачи по теме лекции.
8	Бинарное дерево поиска. Способы обхода. Поиск, вставка и удаление элемента. Анализ времени работы.	Практика и задачи по теме лекции.
9	AVL-дерево. Анализ высоты AVL-дерева. Balance-фактор. Повороты. Поиск, вставка и удаление элементов. Анализ времени работы.	Практика и задачи по теме лекции.
10	Амортизационный анализ. Методы подсчёта, банковский метод и метод потенциалов. Очередь на двух стеках. Двоичный счётчик.	Практика и задачи по теме лекции.
11	Splay-дерево. Повороты. Splay, Split и Merge. Поиск, вставка и удаление элементов. Анализ времени работы.	Практика и задачи по теме лекции.
12	Динамическое программирование. Критерии применимости, порядки пересчёта, одномерная и двумерная динамика. Задача о рюкзаке: дискретная и непрерывная постановки, реализация и анализ времени работы.	Практика и задачи по теме лекции.
13	НОП и НВП. Наибольшая общая подпоследовательность: оптимальная подструктура, реализация и анализ времени. Наибольшая возрастающая подпоследовательность: решения за O(n²) и O(n log n), реализация и анализ времени.	Практика и задачи по теме лекции.
14	Контрольная работа	Разбор сложных тем семестра.

Контрольные активности

В течение семестра предусмотрены три контеста и итоговая контрольная работа. Точные недели публикации контестов и дедлайны будут объявлены отдельно в чате курса.

Активность	Срок / неделя																		Контесты За семестр студент выполняет 3 контеста. В каждом контесте от 10 до 18 задач и выделены обязательные задачи, необходимые для получения удовлетворительной оценки. Выполнение обязательных задач соответствует оценке 3 из 10 за контест. Каждая следующая решённая задача добавляет 1 балл к оценке за контест. Максимальная оценка за контест — 10 баллов. Контесты проверяются ассистентами. Итоговая контрольная работа В конце семестра проводится контрольная работа. Она оценивается по 10-балльной шкале и учитывается при расчёте итоговой оценки с весом 30%. 4. Коммуникация Чат курса: [ссылка будет добавлена ближе к старту семестра] В чате публикуются организационные объявления, информация о контестах и дедлайнах, уточнения по контрольной работе и изменения в расписании. 5. Прогресс студентов Таблица с оценками: [ссылка будет добавлена ближе к старту семестра] В таблице фиксируются результаты трёх контестов, итоговой контрольной работы и бонус за активность на семинарах. 6. Критерии оценивания и формы контроля успеваемости Обязательное условие: если хотя бы один из трёх контестов выполнен на оценку ниже 3 баллов из 10, итоговая оценка за курс является неудовлетворительной. Если обязательное условие выполнено, итоговая оценка рассчитывается по формуле: Итог = 0,7 × средняя оценка за контесты + 0,3 × оценка за контрольную + бонус за активность Средняя оценка за контесты рассчитывается по трём контестам и имеет вес 70% в итоговой оценке. Оценка за итоговую контрольную работу имеет вес 30%. Семинарист может добавить до 1 балла за активность студента на семинарах. Бонус за активность Семинарист может добавить к итоговой оценке до 1 балла за активную работу на семинарах. Конкретный размер бонуса определяется семинаристом по итогам семестра. Дедлайны и штрафы Для каждого контеста устанавливается дедлайн. После дедлайна задачи могут быть оценены максимум в 50% от количества баллов, предусмотренных за них в соответствующем домашнем задании. Правила курса Для получения положительной итоговой оценки каждый из трёх контестов должен быть выполнен минимум на 3 балла из 10. В каждом контесте три обязательные задачи формируют минимальную удовлетворительную оценку; дополнительные задачи повышают оценку за контест. После дедлайна обязательные задачи оцениваются с ограничением не более 50% от предусмотренных за них баллов. Итоговая контрольная работа является частью итоговой оценки. Активность на семинарах может дать до 1 дополнительного балла к итоговой оценке. Актуальные дедлайны и организационные объявления публикуются в чате курса. Материалы курса Папка с материалами: [ссылка будет добавлена] Презентации лекций, материалы семинаров и условия контестов. Материалы для подготовки к итоговой контрольной работе.