Алгоритмы на дискретных структурах данных (ШАД) 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 ревью

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

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

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

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

Контакты

Свежий чат курса https://t.me/+-DyDJhjRKvoyNDFi

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

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

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