О курсе

На курсе поговорим об алгоритмах на графах (кратчайшие пути, остовные деревья, потоки в сетях), линейном программировании, алгоритмах на строках и о полиномиальных классах задач.

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

Домашние задания

Будут состоять из двух типов задач: Задачи на программирование будут приниматься в автоматическом режиме на системе для контестов. Задачи на доказательство будет приниматься через сайт центра.

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

Оценка будет выставляться по результатам решения домашних заданий и летучек. Летучки составляют 10% 0% от общей оценки, теоретические домашние задания - 40% 45%, задачи на программирование - 50% 55%. За 85% решённых задач выставляется оценка отлично, за 75% - хорошо, за 60% - зачёт.

Оценка теоретических домашних заданий

Всего будет \(n\) домашних заданий (предполагаем, что \(n\) будет равно 6 4). За каждое домашнее задание можно набрать 1 балл максимум. В каждом домашнем задании есть несколько задач. Решение каждой задачи вносит одинаковый вклад в оценку этого домашнего задания. В каждом домашнем задании указано, сколько задач нужно решить, чтобы получить максимальный балл. Получить больше максимального балла нельзя. Например, если в одном домашнем задании есть 4 задачи, но для максимального балла нужно решить 3, то если вы полностью решаете любые 3 из 4, то получаете 1 балл. Либо если же вы решаете две задачи правильно, а две задачи наполовину, то тоже получите 1 балл за домашнее задание. Оценка за все домашние задания:

• Взять \(n - 2\) лучших домашних задания студента, \(S\) — это сумма баллов по этим домашним заданиям.
• Оценка за теоретические домашние задания — это \(\frac{S}{n - 2}\).
• Взять \(n - 1\) лучших домашних задания студента, \(S\) — это сумма баллов по этим домашним заданиям.
• Оценка за теоретические домашние задания — это \(\frac{S}{n - 1}\).

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

Оценка летучек

Летучек не будет.

В начале лекции будут летучки, это несколько тестовых заданий на несколько минут. В этом семестре летучки будут реже. У вас есть ровно одна попытка ответить на каждый вопрос. Для тех, кто не сможет ходить на лекции, будет отдельный большой тест в конце на тему летучек, на котором можно будет набрать те 10% от общего балла. Оценка за летучки:

• За каждую летучку вы получаете \(\frac{C}{Q}\), где C — число правильных ответов, а Q — число вопросов.
• Всего будет \(n\) летучек, из них выбираются лучшие \(n - 2\) для студента, и суммируются полученные по ним баллы в число \(S\).