Алгоритмы и структуры данных, часть 2

Санкт-Петербург, весна 2021

Описание

О курсе

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

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

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

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

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

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

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

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

Оценка за все домашние задания:

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

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

Оценка домашних заданий на программирование

Всего будет как минимум 20 задач суммарно, они будут разбиты на контесты на сайте Codeforces. Каждая задача вносит одинаковый вклад в общую оценку заданий по программированию. Пусть \(S\) — число решенных задач во всех контестах, а \(P\) — суммарное число задач во всех контестах, тогда ваша оценка за домашние задания на программирования — это \(\frac{S}{P}\)

Преподаватели