Алгоритмы 1MIT осень2017 — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
(→‎Лекции)
 
(не показаны 43 промежуточные версии 3 участников)
Строка 17: Строка 17:
 
* [[help_g++_install | g++ для всех]]
 
* [[help_g++_install | g++ для всех]]
  
−
* [[help_algosvn | svn для сдачи теордз]] (актуальная версия)
+
* [[help_algosvn | svn для сдачи теордз]] (для 1-й и 3-й группы)
 +
 
 +
* [http://mit.spbau.ru/sewiki/index.php/Algo17-gitlab help по gitlab] (только для 2-й группы)
  
 
* Чтение [http://acm.math.spbu.ru/~sk1/examples/c++/base/ примеров по C++] сделают знакомство с ним проще
 
* Чтение [http://acm.math.spbu.ru/~sk1/examples/c++/base/ примеров по C++] сделают знакомство с ним проще
Строка 27: Строка 29:
 
[[algo_2017_1_groups_fall | Деление на группы]]
 
[[algo_2017_1_groups_fall | Деление на группы]]
  
−
[https://docs.google.com/spreadsheets/d/18mTcy8ykJgOhLHStBvwxZOlAOWFT7YA9LNkpGinCJ1g/edit#gid=0 Результаты практики]
+
[https://docs.google.com/spreadsheets/d/18mTcy8ykJgOhLHStBvwxZOlAOWFT7YA9LNkpGinCJ1g/edit#gid=0 Результаты проверки домашних заданий]
  
 
Дедлайны (окончательная версия):
 
Дедлайны (окончательная версия):
Строка 41: Строка 43:
 
[http://acm.math.spbu.ru/~sk1/courses/1718f_au/lections Краткие планы лекций]
 
[http://acm.math.spbu.ru/~sk1/courses/1718f_au/lections Краткие планы лекций]
  
−
* 04.09 (ср) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au/lections/2017-09-04-Asymptotic-1.html Асимптотика]: определения, Карацуба, мастер-теорема)
+
* 04.09 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au/lections/2017-09-04-Asymptotic-1.html Асимптотика]: определения, Карацуба, мастер-теорема)
  
−
* 11.09 (ср) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au/lections/2017-09-11-DataStructures.html Базовые структуры данных]: неасимптотические оптимизации, вектор, список, стек/дек/очередь)
+
* 11.09 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au/lections/2017-09-11-DataStructures.html Базовые структуры данных]: неасимптотические оптимизации, вектор, список, стек/дек/очередь)
 +
 
 +
* 18.09 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au/lections/2017-09-18-BS-HashTable.html Базовые структуры данных]: амортизация, бинпоиски, хеш-таблицы, хранение множеств и два указателя)
 +
 
 +
* 25.09 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au/lections/2017-09-25-DataStructures.html Базовые структуры данных]: избавление от амортизации, куча, Heap-Sort, аллокация памяти, пополняемые структуры)
 +
 
 +
* 02.10 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au/lections/2017-10-02-Sort.html Сортировки]: квадратичные, Merge-Sort, Quick-Sort)
 +
 
 +
* 09.10 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au/lections/2017-10-09-Sort.html Сортировки и статистики]: Quick-Sort, статистики за линейное время, Radix-Sort, Bucket-Sort, Kirkpatrick-Sort)
 +
 
 +
* 16.10 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au/lections/2017-10-16-Heap.html Кучи]: V.E.B., Leftist, Skew, MinMax)
 +
 
 +
* 23.10 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au/lections/2017-10-23-Heap.html Кучи]: нижняя оценка на время построения, Биномиальные кучи, кучи Фибоначчи)
 +
 
 +
'''Коллоквиум'''
 +
 
 +
6.11 -- не учебный день...
 +
 
 +
* 8.11 (пн) (Динамика: база, графовый вид, восстановление ответа, рюкзак, НОП)
 +
 
 +
* 13.11 (пн) (Динамика: bitset, Хиршберг, НВП за nlogn, измельчение перехода, возведение матриц в степень)
  
 
== Домашние задания ==
 
== Домашние задания ==
Строка 58: Строка 80:
  
 
* '''6 сентября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m170906_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=170906_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/solutions/170906 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/statements/170906_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice/170906.pdf Асимптотика] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice-src/170906/ TeX:src]
 
* '''6 сентября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m170906_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=170906_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/solutions/170906 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/statements/170906_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice/170906.pdf Асимптотика] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice-src/170906/ TeX:src]
 +
 +
* '''13 сентября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m170913_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=170913_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/solutions/170913 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/statements/170913_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice/170913.pdf Асимптотика, неасимптотические оптимизации] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice-src/170913/ TeX:src]
 +
 +
* '''20 сентября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m170920_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=170920_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/solutions/170920 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/statements/170920_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice/170920.pdf Базовые структуры данных] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice-src/170920/ TeX:src]
 +
 +
* '''27 сентября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m170927_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=170927_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/solutions/170927 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/statements/170927_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice/170927.pdf Амортизация, бинпоиск] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice-src/170927/ TeX:src]
 +
 +
* '''4 октября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m171004_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=171004_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/solutions/171004 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/statements/171004_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice/171004.pdf Бинпоиск, сортировки] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice-src/171004/ TeX:src]
 +
 +
* '''11 октября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m171011_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=171011_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/solutions/171011 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/statements/171011_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice/171011.pdf Сортировки и точки] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice-src/171011/ TeX:src]
 +
 +
* '''18 октября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m171018_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=171018_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/solutions/171018 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/statements/171018_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice/171018.pdf Кучи] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice-src/171018/ TeX:src]
 +
 +
* '''25 октября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m171025_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=171025_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/solutions/171025 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/statements/171025_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice/171025.pdf Кучи] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice-src/171025/ TeX:src]
 +
 +
* '''15 ноября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m171115_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=171115_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/solutions/171115 решения] [https://yadi.sk/i/8jht2tc53PmBar условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice/171115.pdf Динамика] [https://yadi.sk/d/8dWrOsHd3PkgbF TeX:src]
 +
 +
* '''22 ноября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m171122_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=171122_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/solutions/171122 решения] [https://yadi.sk/i/y18mShwR3Q3sUH условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice/171122.pdf Динамика] [https://yadi.sk/d/lxpSLhpH3Pygjw TeX:src]
 +
 +
* '''29 ноября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m171129_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=171129_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/solutions/171129 решения] [https://yadi.sk/i/wFsjPs-e3QAPgk условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice/171129.pdf Динамика] [https://yadi.sk/d/_IyzvWKU3QAEmu TeX:src]
 +
 +
* '''13 декабря.''' Практика (дз не было): [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice/171213.pdf dfs]
 +
 +
* '''20 декабря.''' Контест: [https://yadi.sk/i/5Vj66YlR3Qo684 условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice/171220.pdf dfs, динамика по подмножествам] [https://yadi.sk/d/wvK9m8ct3Qnc3a TeX:src]
 +
 +
<!--
 +
 +
== Новый семестр ==
 +
 +
[http://acm.math.spbu.ru/~sk1/courses/1718s_au/conspect/conspect.pdf Конспект]
 +
 +
[http://acm.math.spbu.ru/~sk1/courses/1718s_au/lections Краткие планы лекций]
 +
 +
* 02.12 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718s_au/lections/2018-02-12-complexity.html Сложность]: NP-hard, сведения, гипотезы)
 +
 +
[http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice-src/ TeX исходники практик]
 +
 +
[http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice/ Условия теорзадачек]
 +
 +
[http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/ Условия контестов]
 +
 +
* '''10 февраля.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m180210_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=180210_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/solutions/180210 решения] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180210_au.pdf условия] Сложная задача по сложности
 +
 +
* '''14 февраля.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m180214_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=180214_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/solutions/180214 решения] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180214_au.pdf условия (прошлый семестр)] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice/180214.pdf Сложность] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice-src/180214/ TeX:src]
 +
 +
-->

Текущая версия на 17:54, 4 июня 2018

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

  • Копелиович Сергей Владимирович (burunduk30@gmail.com, vk.com/burunduk1)
  • Гардер Антон Владимирович (algo-au17@garder.me, t.me/avgarder)
  • Колганов Роман Александрович (roman.kolganov@gmail.com, vk.com/rokolgan, аналогичный телеграм)

Софт, примеры, справка

Информация

Деление на группы

Результаты проверки домашних заданий

Дедлайны (окончательная версия):

  • практика, контест: среда 24:00
  • теория в tex: суббота 24:00, исправления -- понедельник до 24:00

Лекции

Конспект

Краткие планы лекций

  • 16.10 (пн) (Кучи: V.E.B., Leftist, Skew, MinMax)
  • 23.10 (пн) (Кучи: нижняя оценка на время построения, Биномиальные кучи, кучи Фибоначчи)

Коллоквиум

6.11 -- не учебный день...

  • 8.11 (пн) (Динамика: база, графовый вид, восстановление ответа, рюкзак, НОП)
  • 13.11 (пн) (Динамика: bitset, Хиршберг, НВП за nlogn, измельчение перехода, возведение матриц в степень)

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

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

TeX исходники практик

Условия теорзадачек

Условия контестов

  • 13 декабря. Практика (дз не было): dfs


Источник — «http://mit.spbau.ru/sewiki/index.php?title=Алгоритмы_1MIT_осень2017&oldid=15819»