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

Материал из CSC Wiki
Перейти к:навигация, поиск
(Лекции)
(Оценка за курс)
 
(не показано 16 промежуточных версий этого же участника)
Строка 7: Строка 7:
 
* (3) Олемская Александра ([mailto:alexandra.olemskaya@gmail.com alexandra.olemskaya@gmail.com], telegram:@SiERic)
 
* (3) Олемская Александра ([mailto:alexandra.olemskaya@gmail.com alexandra.olemskaya@gmail.com], telegram:@SiERic)
 
* (4) Сурков Максим ([mailto:surkovmax007@mail.ru surkovmax007@mail.ru], [mailto:maximsurkov980@gmail.com maximsurkov980@gmail.com], telegram:@maximumSHOOT)
 
* (4) Сурков Максим ([mailto:surkovmax007@mail.ru surkovmax007@mail.ru], [mailto:maximsurkov980@gmail.com maximsurkov980@gmail.com], telegram:@maximumSHOOT)
 +
 +
== Оценка за курс ==
 +
 +
'''Оценка за экзамены <math>s_{e,1}</math> и <math>s_{e,2}</math>'''
 +
 +
Оценки за экзамен после первого модуля («коллоквиум») <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>r</math> обозначает долю баллов от суммы баллов обязательных задач.
 +
 +
{| border="1" cellspacing="0" cellpadding="3"
 +
 +
|-
 +
!<math>s_p</math>
 +
!<math>r \geqslant \ldots</math>
 +
 +
|-
 +
!10
 +
|align=center|1.2
 +
 +
|-
 +
!9
 +
|align=center|1.0
 +
 +
|-
 +
!8
 +
|align=center|0.95
 +
 +
|-
 +
!7
 +
|align=center|0.88
 +
 +
|-
 +
!6
 +
|align=center|0.8
 +
 +
|-
 +
!5
 +
|align=center|0.72
 +
 +
|-
 +
!4
 +
|align=center|0.65
 +
 +
|}
 +
 +
'''Общая оценка за курс'''
 +
 +
В этом семестре ставится одна формальная оценка — в конце семестра.
 +
 +
Блокирующие элементы оценки:
 +
* Оба экзамена должны быть сданы: <math>s_{e, 1} \geqslant 4</math>, <math>s_{e, 2} \geqslant 4</math>.
 +
* По практике должен быть получен зачёт: <math>s_p \geqslant 4</math>.
 +
* В контестах должны быть сданы все задачи, помеченные как «must have».
 +
 +
Если блок пройден, оценка за курс вычисляется так:
 +
<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> --- округление к ближайшему целому.
 +
 +
Словами то же самое: при прохождении блока оценка за курс получается ''округлением к ближайшему целому'' средневзвешенного трёх оценок:
 +
* оценки за практику с коэффициентом 0.6;
 +
* оценки за экзамен после первого модуля («коллоквиум») с коэффициентом 0.2.
 +
* оценки за экзамен после второго модуля с коэффициентом 0.2.
  
 
== Информация ==
 
== Информация ==
Строка 31: Строка 98:
  
 
== Лекции ==
 
== Лекции ==
 +
'''[https://cdkrot.me/teaching/2020f-algo3/questions-exam1.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 линейная алгебра]
Строка 39: Строка 109:
 
* 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 Бинпоиск в суффиксном массиве, бор, алгоритм Ахо-Корасик]
 +
* 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 Потоки: алгоритмы Форда-Фалкерсона и Эдмондса-Карпа]
  
 
== Домашние задания ==
 
== Домашние задания ==
Строка 54: Строка 127:
  
 
* Базовые алгоритмы на строках: [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 теордз]
 
* Базовые алгоритмы на строках: [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 теордз]
 +
 +
* Суффиксный массив и хеши: [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 теордз]
 +
 +
* Бор, Ахо-Корасик и суфдерево: [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 теордз]
 +
 +
* Укконен и потоки: [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/201013.pdf теордз] (теордз до коллоквиума, контест уже после)
  
 
== ACM ==
 
== ACM ==

Текущая версия на 04:56, 30 октября 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 с дз появляется его разбор.

ACM