Алгоритмы и структуры данных 2MIT осень 2020 — различия между версиями

Материал из CSC Wiki
Перейти к:навигация, поиск
(Домашние задания)
(Лекции)
 
(не показано 18 промежуточных версий этого же участника)
Строка 9: Строка 9:
  
 
== Оценка за курс ==
 
== Оценка за курс ==
 +
 +
[https://docs.google.com/spreadsheets/d/1iTgGCXVpxItYdftfYJ1oMcCZJQD2mCDAdzt4Iyn6Ikk/edit Оценки]
  
 
'''Оценка за экзамены <math>s_{e,1}</math> и <math>s_{e,2}</math>'''
 
'''Оценка за экзамены <math>s_{e,1}</math> и <math>s_{e,2}</math>'''
  
 
Оценки за экзамен после первого модуля («коллоквиум») <math>s_{e, 1}</math> и за экзамен после второго модуля <math>s_{e, 2}</math> — числа от 3 до 10.
 
Оценки за экзамен после первого модуля («коллоквиум») <math>s_{e, 1}</math> и за экзамен после второго модуля <math>s_{e, 2}</math> — числа от 3 до 10.
 
[https://docs.google.com/spreadsheets/d/1iTgGCXVpxItYdftfYJ1oMcCZJQD2mCDAdzt4Iyn6Ikk/edit Оценки за коллоквиум]
 
  
 
'''Оценка за практику <math>s_p</math>'''
 
'''Оценка за практику <math>s_p</math>'''
Строка 68: Строка 68:
 
Если блок пройден, оценка за курс вычисляется так:
 
Если блок пройден, оценка за курс вычисляется так:
 
<math>s = \lfloor 0.6\cdot s_p + 0.2 \cdot s_{e, 1} + 0.2\cdot s_{e, 2}\rceil</math>,
 
<math>s = \lfloor 0.6\cdot s_p + 0.2 \cdot s_{e, 1} + 0.2\cdot s_{e, 2}\rceil</math>,
где <math>\lfloor \cdot \rceil</math> --- округление к ближайшему целому.
+
где <math>\lfloor \cdot \rceil</math> округление к ближайшему целому.
  
 
Словами то же самое: при прохождении блока оценка за курс получается ''округлением к ближайшему целому'' средневзвешенного трёх оценок:
 
Словами то же самое: при прохождении блока оценка за курс получается ''округлением к ближайшему целому'' средневзвешенного трёх оценок:
Строка 98: Строка 98:
  
 
== Лекции ==
 
== Лекции ==
'''[https://cdkrot.me/teaching/2020f-algo3/questions-exam1.pdf Вопросы к экзамену за первый модуль]'''
+
[https://cdkrot.me/teaching/2020f-algo3/questions-exam1.pdf Вопросы к экзамену за первый модуль]
 +
 
 +
[https://cdkrot.me/teaching/2020f-algo3/questions-exam2.pdf Вопросы к экзамену за второй модуль]
  
 
[https://cdkrot.me/teaching/2020f-algo3/conspect.pdf Конспект]
 
[https://cdkrot.me/teaching/2020f-algo3/conspect.pdf Конспект]
  
 
«Доски» с лекций:
 
«Доски» с лекций:
* 1 сентября<!-- (1.25 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-09-01_numbers.pdf теория чисел]
+
* 1 сентября<!--(1.25 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-09-01_numbers.pdf теория чисел]
* 3 сентября<!-- (1.5 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-09-03_algebra.pdf линейная алгебра]
+
* 3 сентября<!--(1.5 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-09-03_algebra.pdf линейная алгебра]
* 10 сентября<!-- (1.5 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-09-10_FFT.pdf FFT] и длинная арифметика
+
* 10 сентября<!--(1.5 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-09-10_FFT.pdf FFT] и длинная арифметика
* 17 сентября<!-- (1.5 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-09-17_Division_4Rus.pdf Деление, метод четырёх русских] и [https://cdkrot.me/teaching/2020f-algo3/notes/2020-09-17_Strings.pdf строки (префикс-функция)]
+
* 17 сентября<!--(1.5 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-09-17_Division_4Rus.pdf Деление, метод четырёх русских] и [https://cdkrot.me/teaching/2020f-algo3/notes/2020-09-17_Strings.pdf строки (префикс-функция)]
* 22 сентября<!-- (0.6 пары)-->: Z-функция, полиномиальный хеш [оффлайн]
+
* 22 сентября<!--(0.6 пары)-->: Z-функция, полиномиальный хеш [оффлайн]
* 24 сентября<!-- (1.75 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-09-24_SuffixArray.pdf Полиномиальный хеш, алгоритм Бойера-Мура, суффиксный массив]
+
* 24 сентября<!--(1.75 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-09-24_SuffixArray.pdf Полиномиальный хеш, алгоритм Бойера-Мура, суффиксный массив]
* 1 октября<!-- (1.5 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-10-01_AhoCorasick.pdf Бинпоиск в суффиксном массиве, бор, алгоритм Ахо-Корасик]
+
* 1 октября<!--(1.5 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-10-01_AhoCorasick.pdf Бинпоиск в суффиксном массиве, бор, алгоритм Ахо-Корасик]
* 10 октября<!-- (1.5 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-10-10_Ukkonen1.pdf Алгоритм Укконена], [https://cdkrot.me/teaching/2020f-algo3/notes/2020-10-10_Ukkonen2.pdf его реализация и доказательство]; [https://cdkrot.me/teaching/2020f-algo3/notes/2020-10-10_Flows.pdf потоки]
+
* 10 октября<!--(1.5 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-10-10_Ukkonen1.pdf Алгоритм Укконена], [https://cdkrot.me/teaching/2020f-algo3/notes/2020-10-10_Ukkonen2.pdf его реализация и доказательство]; [https://cdkrot.me/teaching/2020f-algo3/notes/2020-10-10_Flows.pdf потоки]
* 17 октября<!-- (1.5 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-10-17_Flows_FF_EK.pdf Потоки: алгоритмы Форда-Фалкерсона и Эдмондса-Карпа]
+
* 15 октября<!--(1.5 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-10-15_Flows_FF_EK.pdf Потоки: алгоритмы Форда-Фалкерсона и Эдмондса-Карпа]
* 5 ноября<!-- (1 пара)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-11-05_Dinic.pdf Потоки: алгоритм Диница, теоремы Карзанова]
+
* 5 ноября<!--(1 пара)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-11-05_Dinic.pdf Потоки: алгоритм Диница, теоремы Карзанова]
* 12 ноября<!-- (1 пара)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-11-12_GlobalCut.pdf Глобальный разрез: алгоритм Каргера-Штейна], [https://cdkrot.me/teaching/2020f-algo3/notes/2020-11-12_MincostFlow.pdf поток минимальной стоимости]
+
* 12 ноября<!--(1 пара)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-11-12_GlobalCut.pdf Глобальный разрез: алгоритм Каргера-Штейна], [https://cdkrot.me/teaching/2020f-algo3/notes/2020-11-12_MincostFlow.pdf поток минимальной стоимости]
* 19 ноября<!-- (1 пара)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-11-19_MincostCirculation.pdf Циркуляция минимальной стоимости], [https://cdkrot.me/teaching/2020f-algo3/notes/2020-11-19_Matchings.pdf паросочетания]
+
* 19 ноября<!--(1 пара)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-11-19_MincostCirculation.pdf Циркуляция минимальной стоимости], [https://cdkrot.me/teaching/2020f-algo3/notes/2020-11-19_Matchings.pdf паросочетания]
* [доп] 25 ноября<!-- (45 минут)-->: проталкивание предпотока: [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/conspect/0925-preflow-push-3.pdf конспект], [https://yadi.sk/d/JWKsMWzAl1f8-g код с лекции]
+
* [доп] 25 ноября<!--(45 минут)-->: проталкивание предпотока: [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/conspect/0925-preflow-push-3.pdf конспект], [https://yadi.sk/d/JWKsMWzAl1f8-g код с лекции]
 +
* 26 ноября<!--(1 пара)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-11-26_Matchings2.pdf паросочетания-2]
 +
* [доп] 2 декабря<!--(40 минут)-->: хеширование кукушки, совершенное хеширование (двухуровневая и графовая схемы), суффиксный массив за O(n) (алгоритм Карккайнена-Сандерса) [https://yadi.sk/d/za24fi155P-NCA материалы лекции]
 +
* 3 декабря: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-12-03_Games.pdf игры на графах]
 +
* [доп] 9 декабря<!--(40 минут)-->: количество простых до n, [https://yadi.sk/d/c7zA4gdSN_OcLg материалы лекции]
 +
* 10 декабря<!--(1.4 пары)-->: [https://cdkrot.me/teaching/2020f-algo3/notes/2020-12-10_UniHash_BloomFilter_GeneralMatchings.pdf универсальное хеширование, фильтр Блума, паросочетания в недвудольных графах]
  
 
== Домашние задания ==
 
== Домашние задания ==
Строка 124: Строка 131:
 
Домашнее задание разбирается в начале практики. В этот момент удобно спросить о всём, что не получилось. И про контест тоже. После разбора в pdf с дз появляется его разбор.
 
Домашнее задание разбирается в начале практики. В этот момент удобно спросить о всём, что не получилось. И про контест тоже. После разбора в pdf с дз появляется его разбор.
  
* Теория чисел: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m200903_hse.dat результаты] [https://cdkrot.me/teaching/2020f-algo3/statements/200903_hse.pdf условия] [https://cdkrot.me/teaching/2020f-algo3/practice/200901.pdf теордз]
+
{| border="1" cellspacing="0" cellpadding="3"
  
* Линейная алгебра: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m200909_hse2.dat результаты] [https://cdkrot.me/teaching/2020f-algo3/statements/200909_hse2.pdf условия] [https://cdkrot.me/teaching/2020f-algo3/practice/200908.pdf теордз]
+
|-
 +
!Тема
 +
!Условия
 +
!Результаты
 +
!Теордз
 +
 
 +
|-
 +
!Теория чисел
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/statements/200903_hse.pdf №1]
 +
|align=center|[http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m200903_hse.dat №1]
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/practice/200901.pdf №1]
 +
 
 +
|-
 +
!Линейная алгебра
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/statements/200909_hse2.pdf №2]
 +
|align=center|[http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m200909_hse2.dat №2]
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/practice/200908.pdf №2]
 +
 
 +
|-
 +
!FFT и длинная арифметика
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/statements/200912_hse2.pdf №3]
 +
|align=center|[http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m200912_hse2.dat №3]
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/practice/200915.pdf №3]
  
* FFT и длинная арифметика: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m200912_hse2.dat результаты] [https://cdkrot.me/teaching/2020f-algo3/statements/200912_hse2.pdf условия] [https://cdkrot.me/teaching/2020f-algo3/practice/200915.pdf теордз]
+
|-
 +
!Базовые алгоритмы на строках
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/statements/200922_hse2.pdf №4]
 +
|align=center|[http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m200922_hse2.dat №4]
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/practice/200922.pdf №4]
  
* Базовые алгоритмы на строках: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m200922_hse2.dat результаты] [https://cdkrot.me/teaching/2020f-algo3/statements/200922_hse2.pdf условия] [https://cdkrot.me/teaching/2020f-algo3/practice/200922.pdf теордз]
+
|-
 +
!Суффиксный массив и хеши
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/statements/200925_hse2.pdf №5]
 +
|align=center|[http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m200925_hse2.dat №5]
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/practice/200929.pdf №5]
  
* Суффиксный массив и хеши: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m200925_hse2.dat результаты] [https://cdkrot.me/teaching/2020f-algo3/statements/200925_hse2.pdf условия] [https://cdkrot.me/teaching/2020f-algo3/practice/200929.pdf теордз]
+
|-
 +
!Бор, Ахо-Корасик и суфдерево
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/statements/201009_hse2.pdf №6]
 +
|align=center|[http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m201009_hse2.dat №6]
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/practice/201006.pdf №6]
  
* Бор, Ахо-Корасик и суфдерево: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m201009_hse2.dat результаты] [https://cdkrot.me/teaching/2020f-algo3/statements/201009_hse2.pdf условия] [https://cdkrot.me/teaching/2020f-algo3/practice/201006.pdf теордз]
+
|-
 +
!Укконен и потоки
 +
|align=center|—
 +
|align=center|—
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/practice/201013.pdf №7]
  
* Укконен и потоки: [https://cdkrot.me/teaching/2020f-algo3/practice/201013.pdf теордз]
+
|-
 +
!Потоки и разрезы
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/statements/201027_hse2.pdf №7]
 +
|align=center|[http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m201027_hse2.dat №7]
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/practice/201103.pdf №8]
  
* Потоки и разрезы: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m201027_hse2.dat результаты] [https://cdkrot.me/teaching/2020f-algo3/statements/201027_hse2.pdf условия] [https://cdkrot.me/teaching/2020f-algo3/practice/201103.pdf теордз]
+
|-
 +
!Быстрые потоки
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/statements/201107_hse2.pdf №8]
 +
|align=center|[http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m201107_hse2.dat №8]
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/practice/201110.pdf №9]
  
* Быстрые потоки: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m201107_hse2.dat результаты] [https://cdkrot.me/teaching/2020f-algo3/statements/201107_hse2.pdf условия] [https://cdkrot.me/teaching/2020f-algo3/practice/201110.pdf теордз]
+
|-
 +
!Потоки и разрезы
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/statements/201112_hse2.pdf №9]
 +
|align=center|[http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m201112_hse2.dat №9]
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/practice/201117.pdf №10]
  
* Mincost: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m201112_hse2.dat результаты] [https://cdkrot.me/teaching/2020f-algo3/statements/201112_hse2.pdf условия] [https://cdkrot.me/teaching/2020f-algo3/practice/201117.pdf теордз]
+
|-
 +
!Паросочетания
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/statements/201120_hse2.pdf №10]
 +
|align=center|[http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m201120_hse2.dat №10]
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/practice/201124.pdf №11]
  
* Паросочетания: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m201120_hse2.dat результаты] [https://cdkrot.me/teaching/2020f-algo3/statements/201120_hse2.pdf условия] [https://cdkrot.me/teaching/2020f-algo3/practice/201124.pdf теордз]
+
|-
 +
!Паросочетания-2
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/statements/201127_hse2.pdf №11]
 +
|align=center|[http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m201127_hse2.dat №11]
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/practice/201201.pdf №12]
  
* Паросочетания-2: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m201127_hse2.dat результаты] [https://cdkrot.me/teaching/2020f-algo3/statements/201127_hse2.pdf условия] (3 балла за задачу) [теордз]
+
|-
 +
!Игры на графах
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/statements/201203_hse2.pdf №12]
 +
|align=center|[http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m201203_hse2.dat №12]
 +
|align=center|[https://cdkrot.me/teaching/2020f-algo3/practice/201208.pdf №13]
 +
|}
  
 
== ACM ==
 
== ACM ==

Текущая версия на 18:44, 29 декабря 2020

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

Лектор: Пётр Смирнов

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

Оценки

Оценка за экзамены и

Оценки за экзамен после первого модуля («коллоквиум») и за экзамен после второго модуля — числа от 3 до 10.

Оценка за практику

В этой части учитываются баллы за контесты и теоретические домашние задания. обозначает долю баллов от суммы баллов обязательных задач.

10 1.2
9 1.0
8 0.95
7 0.88
6 0.8
5 0.72
4 0.65

Общая оценка за курс

В этом семестре ставится одна формальная оценка — в конце семестра.

Блокирующие элементы оценки:

  • Оба экзамена должны быть сданы: , .
  • По практике должен быть получен зачёт: .
  • В контестах должны быть сданы все задачи, помеченные как «must have».

Если блок пройден, оценка за курс вычисляется так: , где — округление к ближайшему целому.

Словами то же самое: при прохождении блока оценка за курс получается округлением к ближайшему целому средневзвешенного трёх оценок:

  • оценки за практику с коэффициентом 0.6;
  • оценки за экзамен после первого модуля («коллоквиум») с коэффициентом 0.2.
  • оценки за экзамен после второго модуля с коэффициентом 0.2.

Информация

Деление на группы, осень 2020

Результаты практик

svn-репозиторий для сдачи дз (логин тот же, что и в прошлом году)

Тестирующая система

Дедлайны

  • Практика, контест: дедлайн в субботу в 23:59
  • Теория в tex, дедлайн в субботу в 23:59
  • Исправления и только исправления (не новые задачи!) можно отправлять до 11:10 вторника.
  • Отношения к дедлайнам: их нельзя продалбывать. Еcли заболели/внезапная контрольная/опаздываете -- всегда предупредите. Если у вас проблемы, и вам жизненно необходим именно на этой неделе разовый сдвиг дедлайна, не постесняйтесь попросить об этом (заранее, не за полчаса до).

Все домашние задания отправляем в svn

Лекции

Вопросы к экзамену за первый модуль

Вопросы к экзамену за второй модуль

Конспект

«Доски» с лекций:

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

Результаты контестов

В pdf с домашним заданием также лежат задачи практики и их разбор. Как вы догадываетесь, ими полезно пользоваться при решении дз. Конспект прочесть тоже полезно.
Домашнее задание разбирается в начале практики. В этот момент удобно спросить о всём, что не получилось. И про контест тоже. После разбора в pdf с дз появляется его разбор.

Тема Условия Результаты Теордз
Теория чисел №1 №1 №1
Линейная алгебра №2 №2 №2
FFT и длинная арифметика №3 №3 №3
Базовые алгоритмы на строках №4 №4 №4
Суффиксный массив и хеши №5 №5 №5
Бор, Ахо-Корасик и суфдерево №6 №6 №6
Укконен и потоки №7
Потоки и разрезы №7 №7 №8
Быстрые потоки №8 №8 №9
Потоки и разрезы №9 №9 №10
Паросочетания №10 №10 №11
Паросочетания-2 №11 №11 №12
Игры на графах №12 №12 №13

ACM