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

Общие сведения

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

План занятий

• осенний семестр: 01 сентября – 14 декабря
• зачетная неделя: 15 – 21 декабря
• доп. выходные: 04 ноября 2025 г.

Руководитель курса

Илья Степанов

Регистрация на курс

[https:// ]

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

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

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

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

В каждом семестре по алгоритмам есть зачёт и экзамен. Оценка за зачёт ставится за работу в семестре (сдачу теоретических задач и контестов). Семинарист вправе выставлять дополнительные требования для сдачи зачёта. Оценка за экзамен ставится за устный ответ на экзамене и никак не зависит от работы в семестре (в том числе, нет такого понятия как «недопуск»). На семинарах повторяются пройденные на лекции алгоритмы, разбираются детали их реализации. Также разбираются теоретические задачи на соответствующую тему. Можно просить семинариста написать какой-то код, который вызывает затруднения, разобрать задачи с прошедших контестов или теоретических домашних работ. По умолчанию теоретические домашние задания сдаются устно семинаристу. Практические же задачи из контестов бывают двух видов: с код-ревью и без код-ревью. Чтобы задача с код-ревью была засчитана решённой, код решения нужно залить в репозиторий, который укажут семинарист и ассистент. Ассистент делает код-ревью, может отправить код на доработку. Когда все итерации ревью пройдены, за задачу проставляется балл в таблицу. Число итераций повторного ревью не ограничено, но ассистент имеет право отказать в ревью, если посчитает, что было предпринято слишком много попыток. Задачи без код-ревью не предполагают ревью, однако семинарист вправе выставить некоторые дополнительные задачи на ревью. Задачи с ревью помечены фразой «с ревью» в контесте, а также выделены красным цветом в таблице с оценками. Там же могут быть уточнены правила выставления баллов (например, какие-то решения могут получать меньше/больше баллов). Если возникают вопросы по решению задач из контеста, порядок действий следующий: если уместно, напишите стресс-тест (нужно, если программа получает WA, TL, RE на одном из неизвестных тестов); искать ошибку в программе станет легче, если у вас на руках есть контртест; если стресс-тестирование не помогло, можете попросить помощи у ассистента (для этого сообщите номер контеста, задачу, а также номер посылки в виде https://contest.yandex.ru/contest/67953/run-report/117944368/); если ассистент долго не отвечает или не может помочь, можете задать вопрос в общем чате курса (так же приложите контест, задачу и посылку). Если возникает вопрос по условию, можете задать его в общем чате, приложив собственно условие задачи (ссылку на нужную задачу в контесте или файл с теоретическими задачами). Так вам ответят быстрее. В общих чатах запрещено обсуждение решений и идей решений задач! Осуждается списывание в любом виде. Ближе к концу семестра будет проведена проверка на списывание (антиплагиат). Пойманные на списывании получат штраф к баллам за семестр. Списыванием может быть рассчитано и независимое использование одного и того же открытого кода. Поэтому пишите полностью свой код, не прибегая к помощи готовых библиотек. Исключение — код, приводимый на лекциях и семинарах. Оценка за семестр считается по формуле в общей табличке. Оценка тем выше, чем больше баллов набрано. Список задач будет окончально известен только ближе к концу семестра, поэтому заранее невозможно спрогнозировать, какие будут пороги на каждую оценку. В среднем правила такие: на отл10 нужно решить всё, на уд3 — набрать 50% баллов. Решить всё возможно: в семестре будет много бонусных задач, которые идут в зачёт, но не влияют на пороги. Если в течение семестра студент не набирает баллов на уд3, он получает пересдачу. На пересдачу можно сдавать те же самые практические (в первую очередь задачи без код-ревью) и теоретические задачи. Начать дорешивать можно сразу после зачётной недели и вплоть до пересдачи в начале следующего семестра. Семинарист может ставить небольшие бонусы за активность на семинарах. Уточняйте правила их выставления у семинаристов. В контестах встроена автоматическая проверка на кодстайл. См. кодстайл для C++ (https://docs.google.com/document/d/1HmFPnUPKfx8fXtU_rNm0lWzMwo7zr7RdCfAHbAMedjo/edit) и для Java (https://docs.google.com/document/d/12bd65gG03VLxVlYw7LCblBAVzbBsvoYPHhlqprkj6-E/edit). Если встречаете опечатки в условиях, пишите в общий чат, будем исправлять. Если понимаете, что в какой-то задаче очень слабые тесты (заходят решения, которые не должны), можете подготовить более сильные тесты. Их добавят в систему, а вам дадут бонусные баллы.

План домашних заданий с уточнением сроков сдачи

В течение семестра планируются 5–6 домашних заданий, разбитых по темам:

• 1) введение, бинарный поиск;
• 2) сортировки;
• 3) кучи, линейные контейнеры;
• 4) дерево отрезков, дерево Фенвика;
• 5) деревья поиска;
• 6) хеш-таблицы.

• В каждой теме планируется большой контест и небольшое теоретическое задание.

Критерии оценивания и формы контроля успеваемости (ДЗ, система бонусов, проект, зачет, экзамен)

Чтобы заработать минимальную положительную оценку (уд. 3), нужно набрать примерно 50% баллов от максимума. Чтобы заработать наивысшую оценку (отл. 10), нужно приблизиться к идеальному студенту, решившему почти все задачи. Оценка за семестр стремится зафиксировать уровень навыков студента в решении и реализации практических задач по алгоритмам.

Литература

Абрамов С. А. Лекции о сложности алгоритмов. – 2009.

Материалы занятий

Лекции одного из прошлых потоков (осень 2024)