Алгоритмы и структуры данных II. Базовый поток весна 2026
Общие сведения о курсе
Второй семестр алгоритмов по системе и структуре не отличается от первого. Отличается лишь набор тем.
В семестре планируется 15 лекций и 30 семинаров (практических занятий). На лекциях разбираются различные модельные задачи и алгоритмы их решения, на семинарах студентам предлагается решать теоретические задачи, обсуждать их решения, реализовывать код избранных алгоритмов, а также сдавать домашние задания.
Во втором семестре разбираются, во-первых, задачи динамического программирования, во-вторых, множество задач и алгоритмов на графах. Вводная часть о динамическом программировании служит скорее подготовкой к графовым алгоритмам, поскольку многие из них по существу задействуют именно технику динамического программирования.
Приблизительную программу экзамена см. в pdf.
Лекции одного из прошлых потоков (весна 2023) см.: https://youtube.com/playlist?list=PL4_hYwCyhAvZSdTWba4rwTlmdMwqf0gEd&si=ZI7BbJZd2A25OEmn
Подробнее о правилах курса см.: https://docs.google.com/document/d/1TNoAMWFGZHsEigH9BlM_lGI4jdHxxR66Y3jHGtntQME/edit
За курс предусмотрены две оценки: за зачёт и за экзамен. Оценки независимы и никак не влияют друг на друга. Оценка за зачёт ставится за работу в семестре: за сдачу теоретических и практических домашних задач, а также за активность на семинарах и помощь в развитии курса (исправление опечаток в условиях, подготовка более сильных тестов к задачам, разработка собственных задач и пр.). Оценка за экзамен ставится исключительно исходя из качества устного ответа на экзамене.
В течение семестра планируются 4–5 домашних заданий, разбитых по темам: 1) динамическое программирование; 2) простейшие алгоритмы на графах; 3) кратчайшие пути в графах, остовы; 4) паросочетания и потоки; 5) продвинутые алгоритмы на деревьях (опционально). В каждой теме планируется большой контест и небольшое теоретическое задание. Чтобы заработать минимальную положительную оценку (уд. 3), нужно набрать примерно 50% баллов от максимума. Чтобы заработать наивысшую оценку (отл. 10), нужно приблизиться к идеальному студенту, решившему почти все задачи. Ожидаемый максимальный балл — 150. Оценка за семестр стремится зафиксировать уровень навыков студента в решении и реализации практических задач по алгоритмам.
Экзамен же рассчитан оценить уровень теоретической подготовки студента. На нём от студента ожидается знание доказательств изученных в течение курса алгоритмов, а также умение решать теоретические задачи. Обычно такие задачи более сложные, чем практические, что компенсируется отсутствием необходимости реализовывать их (имплементировать).
Литература. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – 1980. Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика. – 2010. С. Дасгупта, Х. Пападимитриу, У. Вазирани. Алгоритмы. Пер. с англ. под ред. А. Шеня. –– М.: МЦНМО, 2014. –– 320 с. Ахо А. Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. Москва. – 1979.
Руководитель курса
Илья Степанов
Преподаватели курса
- Смышляев Федор Витальевич
- Чубенко Полина Николаевна
- Кулешов Игорь Вячеславович
- Белков Иван Иванович
- Костров Максим Антонович
- Спицын Николай Антонович
- Подзорова Полина Владимировна
- Рубаненко Мария Александровна
- Чернецкий Аркадий Михайлович
- Цой Максим Вячеславович
- Утегенов Артем Маратович
- Халтурин Евгений Александрович
- Вашкевич Егор Сергеевич
- Степанов Илья Даниилович
