Алгоритмы ИВТ 2020 — различия между версиями
| (не показано 11 промежуточных версий 2 участников) | |||
| Строка 16: | Строка 16: | ||
|- | |- | ||
| 2 | | 2 | ||
| − | | [[ | + | | Сортировки |
| + | [[Quicksort]] | ||
| + | [[Сортировка слиянием]] | ||
| + | [[Цифровая сортировка]] | ||
| + | [[Сортировка подсчётом]] | ||
| + | |||
| + | [[QuickSelect]] | ||
| + | |||
| Екатерина Дробченко | | Екатерина Дробченко | ||
| [https://drive.google.com/file/d/13PsIUrDpRT51qPmHuS5xp-N_Y17Ujq2o/view?usp=sharing Сортировки, бинпоиск, сканлайн ] | | [https://drive.google.com/file/d/13PsIUrDpRT51qPmHuS5xp-N_Y17Ujq2o/view?usp=sharing Сортировки, бинпоиск, сканлайн ] | ||
| Строка 42: | Строка 49: | ||
| Михаил Воробьёв | | Михаил Воробьёв | ||
| [https://drive.google.com/open?id=1Bac6S7YXgKogKvZQglI23BIRRwg2TIBp Задачи на деревья поиска] | | [https://drive.google.com/open?id=1Bac6S7YXgKogKvZQglI23BIRRwg2TIBp Задачи на деревья поиска] | ||
| + | |- | ||
| + | | 6 | ||
| + | | Деревья поиска-3 | ||
| + | [[ Декартово дерево (Treap) ]] | ||
| + | [[ Декартово дерево по неявному ключу ]] | ||
| + | | Сергей Новиков | ||
| + | | [https://drive.google.com/open?id=1ftyGP8GgiDZ_lr_9XHCkK0HP_0RD1Fed Задачи на декартово дерево] | ||
| + | |- | ||
| + | | 7 | ||
| + | | [[Sparse table]], [[Дерево отрезков]] | ||
| + | | Алексей Кудринский | ||
| + | | [https://drive.google.com/open?id=1evEyPLk41fB4G4TeBBKZndFlqPin4CbM Задачи] | ||
| + | |- | ||
| + | | 8 | ||
| + | | Дерево Фенвика | ||
| + | [[Одномерное дерево Фенвика]] | ||
| + | [[Двумерное дерево Фенвика]] | ||
| + | [[Фенвик Фенвиков]] | ||
| + | | Эвелина Емельянова | ||
| + | | [https://drive.google.com/open?id=1GbH5nHWet05SWvo3LtnB_ux8nDUZsJjl Задачи на дерево Фенвика] | ||
| + | |- | ||
| + | | 9 | ||
| + | | Динамическое программирование-1 | ||
| + | [[Простые задачи на динамическое программирование]] | ||
| + | [[ДП на подотрезках]] | ||
| + | [[Задача НОП]] | ||
| + | [[Задача НВП]] | ||
| + | [[Задача о рюкзаке]] | ||
| + | | Данил Милько | ||
| + | | [https://drive.google.com/open?id=15Vj-wM7TrqV7YYIrgiaEvOJYNCf1bwLO Задачи на ДП-1] | ||
| + | |- | ||
| + | | 10 | ||
| + | | Динамическое програмирование-2 | ||
| + | [[ДП на подмножествах]] | ||
| + | [[Подсчёт ДП с помощью матричного умножения]] | ||
| + | | Анастас Беляев | ||
| + | | [https://drive.google.com/open?id=1WXJK7pFUzNL-C5yXNB1Yn289olaWDhtN Задачи на ДП-2] | ||
| + | |- | ||
| + | | 11 | ||
| + | | Графы-1, обход в глубину | ||
| + | [[DFS]] | ||
| + | [[Поиск компонент сильной связности]] | ||
| + | [[Поиск мостов, точек сочленения и компонент двусвязности]] | ||
| + | [[Задача 2-SAT]] | ||
| + | | Марина Коновалова | ||
| + | | | ||
| + | |- | ||
| + | | 12 | ||
| + | | Графы-2, Кратчайшие пути-1 | ||
| + | [[BFS]] | ||
| + | [[0-k BFS]] | ||
| + | [[Алгоритм Дейкстры]] | ||
| + | | Константин Драгун | ||
|- | |- | ||
|} | |} | ||
| Строка 61: | Строка 121: | ||
| [https://drive.google.com/open?id=1Pdn9bC0HEMvnyzC7bKqC6sXD1drYi2b- домашка моя домашка] | | [https://drive.google.com/open?id=1Pdn9bC0HEMvnyzC7bKqC6sXD1drYi2b- домашка моя домашка] | ||
|- | |- | ||
| + | | 3 | ||
| + | | Деревья поиска | ||
| + | | [https://codeforces.com/group/iMwjhG4D4C/contest/272242 коронаконтест] Обязательные задачи: A и D. STL разрешается использовать только в задачах E-G. | ||
| + | | [https://drive.google.com/open?id=1ftyGP8GgiDZ_lr_9XHCkK0HP_0RD1Fed коронадомашка] | ||
|} | |} | ||
| Строка 70: | Строка 134: | ||
* Баллы за семестр набираются за контесты и теор.домашки и конспекты лекций. Всего будет 5-7 контестов и 5-7 теор.домашек. | * Баллы за семестр набираются за контесты и теор.домашки и конспекты лекций. Всего будет 5-7 контестов и 5-7 теор.домашек. | ||
** Решённые полностью все контесты и задачи дают вам отл (14). Ваша оценка равна MIN(10, FLOOR((STUDENT_SCORE / MAX_SCORE) * 14)) - PENALTY . | ** Решённые полностью все контесты и задачи дают вам отл (14). Ваша оценка равна MIN(10, FLOOR((STUDENT_SCORE / MAX_SCORE) * 14)) - PENALTY . | ||
| − | ** В каждом контесте/листочке есть | + | ** В каждом контесте/листочке есть некоторое количество обязательных задач. Чтобы их сдать, надо получить OK в контесте и защитить решение перед семинаристом или ассистентом на очной сдаче. |
** Дедлайн на устную сдачу: 2 недели от дедлайна контеста/листочка. | ** Дедлайн на устную сдачу: 2 недели от дедлайна контеста/листочка. | ||
** За незащищённую обязательную задачу ваша итоговая оценка понижается на 1 балл. | ** За незащищённую обязательную задачу ваша итоговая оценка понижается на 1 балл. | ||
* Конспекты лекций ведутся в системе MediaWiki на этом сайте. Если вы хотите получить 10 бонусных баллов к STUDENT_SCORE и уважение от ваших однокурсников за конспектирование лекций, напишите об этом в телеграм Саше Гришутину (@rationalex). Заявляя своё желание, вы подтверждаете, что готовы законспектировать любую из лекций, на которой вы были (это нужно для того, чтобы равномерно распределить всех желающих по лекциям). При наличии нескольких желающих вести конспект, приоритет будет отдаваться тем, кто получил меньший бонусный балл за ведение конспектов. При равенстве всех пунктов, приоритет будет отдаваться тем, кто до этого сделал конспекты прилежнее и быстрее. | * Конспекты лекций ведутся в системе MediaWiki на этом сайте. Если вы хотите получить 10 бонусных баллов к STUDENT_SCORE и уважение от ваших однокурсников за конспектирование лекций, напишите об этом в телеграм Саше Гришутину (@rationalex). Заявляя своё желание, вы подтверждаете, что готовы законспектировать любую из лекций, на которой вы были (это нужно для того, чтобы равномерно распределить всех желающих по лекциям). При наличии нескольких желающих вести конспект, приоритет будет отдаваться тем, кто получил меньший бонусный балл за ведение конспектов. При равенстве всех пунктов, приоритет будет отдаваться тем, кто до этого сделал конспекты прилежнее и быстрее. | ||
*Если вы в какой-то момент поймёте, что курс вам неинтересен, то вы можете получить джентльменский уд(3), сдав и защитив все обязательные задачи и больше ничего. | *Если вы в какой-то момент поймёте, что курс вам неинтересен, то вы можете получить джентльменский уд(3), сдав и защитив все обязательные задачи и больше ничего. | ||
Текущая версия на 01:46, 12 мая 2020
Лекции и семинары
Домашки
| # | Тема | Контест | Листок |
|---|---|---|---|
| 1 | Базовые структуры, скиплисты, бинпоиск | тык Обязательные: C, I, J | пунь Обязательные: 2, 3, 9 |
| 2 | Кучи | контест мой контест Обязательная: A | домашка моя домашка |
| 3 | Деревья поиска | коронаконтест Обязательные задачи: A и D. STL разрешается использовать только в задачах E-G. | коронадомашка |
Правила игры
- Оценка за экзамен ставится следующим образом:
- Если вас устраивает накопленная оценка за семестр, то она и выставляется в качестве оценки за экзамен.
- Если вы хотите поднять итоговую оценку, то вы можете прийти на экзамен и получить за него оценку EXAM от 0 до 10, после чего ваша итоговая оценка будет равна ROUND(0.3*EXAM + 0.7*SEMESTER) .
- Баллы за семестр набираются за контесты и теор.домашки и конспекты лекций. Всего будет 5-7 контестов и 5-7 теор.домашек.
- Решённые полностью все контесты и задачи дают вам отл (14). Ваша оценка равна MIN(10, FLOOR((STUDENT_SCORE / MAX_SCORE) * 14)) - PENALTY .
- В каждом контесте/листочке есть некоторое количество обязательных задач. Чтобы их сдать, надо получить OK в контесте и защитить решение перед семинаристом или ассистентом на очной сдаче.
- Дедлайн на устную сдачу: 2 недели от дедлайна контеста/листочка.
- За незащищённую обязательную задачу ваша итоговая оценка понижается на 1 балл.
- Конспекты лекций ведутся в системе MediaWiki на этом сайте. Если вы хотите получить 10 бонусных баллов к STUDENT_SCORE и уважение от ваших однокурсников за конспектирование лекций, напишите об этом в телеграм Саше Гришутину (@rationalex). Заявляя своё желание, вы подтверждаете, что готовы законспектировать любую из лекций, на которой вы были (это нужно для того, чтобы равномерно распределить всех желающих по лекциям). При наличии нескольких желающих вести конспект, приоритет будет отдаваться тем, кто получил меньший бонусный балл за ведение конспектов. При равенстве всех пунктов, приоритет будет отдаваться тем, кто до этого сделал конспекты прилежнее и быстрее.
- Если вы в какой-то момент поймёте, что курс вам неинтересен, то вы можете получить джентльменский уд(3), сдав и защитив все обязательные задачи и больше ничего.
