Алгоритмы и структуры данных 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	Контрольная работа	Разбор сложных тем семестра.

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

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

Активность	Срок / неделя	Формат
Контест №1	2–3 недели на выполнение	10–20 задач
Контест №2	2–3 недели на выполнение	10–20 задач
Контест №3	2–3 недели на выполнение	10–20 задач
Итоговая контрольная работа	Конец семестра	Письменный формат

Контесты

За семестр студент выполняет 3 контеста. В каждом контесте от 10 до 18 задач и выделены обязательные задачи, необходимые для получения удовлетворительной оценки.

• Выполнение обязательных задач соответствует оценке 3 из 10 за контест.
• Каждая следующая решённая задача добавляет 1 балл к оценке за контест.
• Максимальная оценка за контест — 10 баллов.
• Контесты проверяются ассистентами.

Итоговая контрольная работа

В конце семестра проводится контрольная работа. Она оценивается по 10-балльной шкале и учитывается при расчёте итоговой оценки с весом 30%.

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

чат курса

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

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

Таблица с оценками доступна студентам в канале дисциплины

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

Обязательное условие: если хотя бы один из трёх контестов выполнен на оценку ниже 3 баллов из 10, итоговая оценка за курс является неудовлетворительной.

Если обязательное условие выполнено, итоговая оценка рассчитывается по формуле:

Итог = 0,7 × средняя оценка за контесты + 0,3 × оценка за контрольную + бонус за активность

• Средняя оценка за контесты рассчитывается по трём контестам и имеет вес 70% в итоговой оценке.
• Оценка за итоговую контрольную работу имеет вес 30%.
• Семинарист может добавить до 1 балла за активность студента на семинарах.

Бонус за активность

Семинарист может добавить к итоговой оценке до 1 балла за активную работу на семинарах. Конкретный размер бонуса определяется семинаристом по итогам семестра.

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

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

Правила курса

1. Для получения положительной итоговой оценки каждый из трёх контестов должен быть выполнен минимум на 3 балла из 10.

1. В каждом контесте три обязательные задачи формируют минимальную удовлетворительную оценку; дополнительные задачи повышают оценку за контест.

1. После дедлайна обязательные задачи оцениваются с ограничением не более 50% от предусмотренных за них баллов.

1. Итоговая контрольная работа является частью итоговой оценки.

1. Активность на семинарах может дать до 1 дополнительного балла к итоговой оценке.

1. Актуальные дедлайны и организационные объявления публикуются в чате курса.

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

Папка с материалами: [ссылка будет добавлена]

• Презентации лекций, материалы семинаров и условия контестов.
• Материалы для подготовки к итоговой контрольной работе.