Алгоритмы и структуры данных, часть 2
Санкт-Петербург / весна 2018, посмотреть все семестры

Продолжение курса Алгоритмы и структуры данных 1.

Узнаем алгоритмы для таких задач, как поиск образца в тексте, максимальный поток, линейное программирование, вычислительная геометрия. Разберёмся с понятием NP-трудности.

Оценка за курс

Оценка будет складываться из:

  • Обратная связь по онлайн-курсу: 10%
  • Теоретические задачи: 45%
  • Задачи на программирование (на курсере и на степике): 45%

Ваша оценка за курс будет посчитана следующим образом. Пусть \(F, T, P\) — число заданий по обратной связи, по теории и по программированию, соответственно, а \(f, t, p\) — число успешно выполненных вами заданий из этих категорий. Тогда ваш результат (число от 0 до 100) по курсу вычисляется так: \[10\cdot \frac{f}{F}+45\cdot \frac tT+45\cdot \frac pP \, .\] При выставлении оценки будут использоваться такие проходные значения: хотя 85 — отлично, хотя бы 75 — хорошо, хотя бы 65 — удовлетворительно (данные проходные баллы могут слегка поменяться в конце курса). Летучками можно будет закрыть пробелы по теоретическим задачам: 100% летучек — это 33% от теоретических задач (таким образом, если, например, по теоретическим задачам вы набрали 80% и решили при этом все летучки, то за теорию у вас будет 100%; если вы вообще ничего по теории не решили, но решили 50% летучек, то по теории у вас будет 16.5%).

Дата и время Название Место Материалы
15 февраля
18:30–19:50
Суффиксные деревья, лекция Таймс, ауд. с белыми досками Нет
15 февраля
20:00–21:20
Семинар 1, семинар Таймс Нет
22 февраля
18:30–19:50
Суффиксные массивы и преобразование Барроуза–Уиллера, лекция Таймс, ауд. с белыми досками Нет
22 февраля
20:00–21:20
Семинар 2, семинар Таймс Нет
01 марта
18:30–19:50
Алгоритм Кнута–Морриса–Пратта, алгоритмы построения суффиксного массива, лекция Таймс, ауд. с белыми досками Нет
01 марта
20:00–21:20
Семинар 3, семинар Таймс, ауд. с белыми досками Нет
15 марта
18:30–19:50
Конечные автоматы в задаче поиска подстрок, лекция Таймс, ауд. с белыми досками видео
15 марта
20:00–21:20
Семинар 4, семинар Таймс, ауд. с белыми досками Нет
22 марта
18:30–19:50
Потоки в сетях: алгоритмы, лекция Таймс, ауд. с белыми досками Нет
22 марта
20:00–21:20
Семинар 5, семинар Таймс, ауд. с белыми досками Нет
29 марта
18:30–19:50
Потоки в сетях: применения, лекция Таймс, ауд. с белыми досками Нет
29 марта
20:00–21:20
Семинар 6, семинар Таймс, ауд. с белыми досками Нет
05 апреля
18:30–19:50
Линейное программирование и симплекс-метод, лекция Таймс, ауд. с белыми досками Нет
05 апреля
20:00–21:20
Семинар, семинар Таймс, ауд. с белыми досками Нет
12 апреля
18:30–19:50
NP-трудные задачи, лекция Таймс, ауд. с белыми досками Нет
12 апреля
20:00–21:20
Семинар, семинар Таймс, ауд. с белыми досками Нет
19 апреля
18:30–19:50
Алгоритмы для NP-трудных задач, лекция Таймс, ауд. с белыми досками Нет
19 апреля
20:00–21:20
Семинар, семинар Таймс, ауд. с белыми досками Нет
26 апреля
18:30–19:50
Алгоритмы для NP-трудных задач, лекция Таймс, ауд. с белыми досками видео
26 апреля
20:00–21:20
Алгоритмы для NP-трудных задач (продолжение), лекция Таймс, ауд. с белыми досками видео
10 мая
18:30–19:50
Быстрое преобразование Фурье, лекция Таймс, ауд. с белыми досками Нет
10 мая
20:00–21:20
Семинар, семинар Таймс, ауд. с белыми досками Нет