Алгоритмы на дискретных структурах данных (ШАД) 2025

Правила сдачи курса алгоритмов от ШАД

• Курс сложный! Трезво оценивайте свои силы.
• Курс состоит из лекций и семинаров в онлайн-формате.
• Для сдачи курса необходимо сдать 1) контесты, 2) ревью и теории к ревью 3) очный письменный теорминимум в конце семестра.
• Контесты проводятся в Яндекс.Контесте. Для сдачи задания необходимо отправить готовый код решения в контест и получить вердикт OK. За посылки с ошибками начисляется от 0 до 2 штрафных баллов в зависимости от ошибки.
• Внимательно следите за тем, с какого аккаунта отправляете задачи в контест. Владельцы нескольких аккаунтов попадают под санкции ШАД.
• Ревью и теории к ревью сдаются через ЛМС ШАД.
• Студенты, не зарегистрировавшиеся вовремя в ЛМС, автоматически идут на пересдачу.

Дедлайны

• Необходимо соблюдать дедлайны отправки заданий, устанавливаемые ШАД.
• Обратите внимание на мидтерм!
• Дорешивать задачи контестов можно в любое время, даже сразу после закрытия контестов. После окончания семестра в ШАД контесты официально открываются на дорешивание. Обычно семестр ШАД заканчивается раньше, чем наступает зачетная неделя, поэтому ваши дорешивания будут учтены без штрафа при выставлении оценки.
• Тем не менее, крайне не рекомендуется оставлять все контесты на конец семестра. Задачи сложные и трудоемкие, сдать их за одну ночь не получится.
• После финального дедлайна по курсу никакие правки не принимаются!

Сдача ревью

• Ревью сдаются через ЛМС ШАД. Перед сдачей кода нужно обязательно сдать теоретическое решение. Ревью без теории не засчитывается!
• Не путать теорию к ревью и теоретические задачи! Это разные задания. Теоретические задачи сдавать не нужно.
• Требования к ревью либо присылаются в ЛМС после успешной сдачи теории в срок, либо выкладываются в общий доступ после дедлайна по теории к ревью.
• Первую версию ревью и теории нужно прислать в срок. При опоздании задание не засчитывается.
• Сдача ревью проводится в несколько итераций. Вам необходимо исправлять замечания. Исправленные решения сдаются так же через ЛМС. Доделывание происходит в свободном режиме либо до соответствующего дедлайна, либо до конца семестра. Дополнительный дедлайн объявляется по усмотрению проверяющего в случае, если участники курса массово откладывают исправления.

Система оценивания

Система выставления оценки за курс отличается от систем ШАДа, поскольку порядок сдачи курса не совпадает ни с общим, ни с порядком для вольнослушателей.

Отл 10: 1450 баллов и 2 ревью
Отл 9: 1400 баллов и 2 ревью
Отл 8: 1350 баллов и 2 ревью
Хор 7: 1250 баллов и 2 ревью
Хор 6: 1200 баллов и 2 ревью
Хор 5: 1150 баллов и 2 ревью
Уд 4: 950 баллов, 2 ревью
Уд 3: 900 баллов, 2 ревью

Перезачет курса

• Замена курса на другой производится через Учебное управление в начале семестра.
• Перезачесть курс можно, только если вы уже прошли его как студент ШАД.
• Перезачет курса педагогической практикой происходит только по предварительной договоренности с кафедрой.
• Вы не можете использовать правила перезачета в ШАД, в частности, вы не можете перезачесть курс алгоритмов из бакалавриата.
• Перезачет ранее пройденного курса при восстановлении из академического отпуска происходит автоматически, если оценка за курс была "хор" или "отл". В противном случае возможен перезачет только отдельных заданий курса по согласованию с преподавателем.

Порядок пересдач

• На пересдаче необходимо сдать теорминимум.
• К пересдаче студент может доделывать ревью и контесты. Если заработанных баллов хватает на желаемую оценку, она выставляется в ведомость.
• Если студент не зарегистрировался в ЛМС или же был по каким-либо причинам удалён из системы, для получения оценки требуется сдать устный экзамен в традиционном формате (по билетам).

Контакты

Чат важных объявлений ШАД https://t.me/joinchat/AAAAAEJ2hkBm1zv3pdCenw

Примерная программа теорминимума (за два семестра)

Примечание. Для алгоритмов нужно знать постановку задачи, основные шаги и асимптотику.

Асимптотики: определения O(), o(), Θ(), Ω(). Понятие амортизированной сложности. Понятие вероятностной сложности. Процедура Merge в MergeSort. Итеративный и рекурсивный варианты. Варианты выбора pivot-элемента в QuickSort (фиксированно, случайно, медиана медиан). Метод потенциалов. Определение кучи. Основные операции. Асимптотика б/д. Определения односвязного и двусвязного списков, стека, дека, очереди. Основные операции. Асимптотика б/д. Определение хеш-функции. Определение коллизии, методы разрешения. Основные операции с хеш-таблицей. Асимптотика б/д. Постановка задачи идеального хеширования (fixed set). Определение декартова дерева. Основные операции. Асимптотика б/д. Определения ориентированного и неориентированного графов, дерева. Алгоритмы BFS и DFS б/д. Асимптотика б/д. Определения моста, точки сочленения, компоненты связности, компоненты сильной связности, остовного дерева. Алгоритм Косарайю б/д. Асимптотика б/д. Алгоритм Крускала б/д. Асимптотика б/д. Постановки задач LCA и RMQ. Сведение друг к другу б/д. Алгоритм Форда-Беллмана б/д. Асимптотика б/д. Алгоритм Дейкстры б/д. Асимптотика б/д. Определения зет и префикс функций. Алгоритм КМП б/д. Определение структуры данных бор. Определение суффиксного дерева. Алгоритм Ахо-Корасик б/д. Определение суффиксного массива. Определение регулярного выражения. Определение конечного автомата, детерминированного и недетерминированного. Определение потока в сети. Определение предпотока. Алгоритм Диница б/д. Асимптотика б/д. Определения разреза, веса разреза, минимального разреза (min cut). Алгоритм Штор-Вагнера б/д. Асимптотика б/д. Определение двудольного графа. Определения паросочетания и максимального паросочетания в двудольном графе. Сведение паросочетания к потоку. Определения вершинного и реберного покрытий. Алгоритм FFT б/д.