Просмотр исходного текста страницы Алгоритмы 1MIT осень2017

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

* Копелиович Сергей Владимирович (burunduk30@gmail.com, [https://vk.com/burunduk1 vk.com/burunduk1])

* Гардер Антон Владимирович (algo-au17@garder.me, [https://t.me/avgarder t.me/avgarder])

* Колганов Роман Александрович (roman.kolganov@gmail.com, [https://vk.com/rokolgan vk.com/rokolgan], аналогичный телеграм)

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

* [http://acm.math.spbu.ru/~sk1/help/testsys/ help по TestSys]

* [[help_tex_windows | TeX]]

* [[help_bash_windows | Bash для windows]]

* [[help_g++_install | g++ для всех]]

* [[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++] сделают знакомство с ним проще

* [[help_sublime_dict | Sublime: настройка правописания]]

== Информация ==

[[algo_2017_1_groups_fall | Деление на группы]]

[https://docs.google.com/spreadsheets/d/18mTcy8ykJgOhLHStBvwxZOlAOWFT7YA9LNkpGinCJ1g/edit#gid=0 Результаты проверки домашних заданий]

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

* практика, контест: среда 24:00

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

== Лекции ==

[https://yadi.sk/d/_y_oxvJI3PeCVS Конспект]

[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 Асимптотика]: определения, Карацуба, мастер-теорема)

* 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, измельчение перехода, возведение матриц в степень)

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

[http://acm.math.spbu.ru/cgi-bin/monitor_au.pl Результаты контестов]

[http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice-src/ TeX исходники практик]

[http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice/ Условия теорзадачек]

[http://acm.math.spbu.ru/~sk1/courses/1718f_au/statements/ Условия контестов]

* Вступительный контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m170903_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=170903_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/solutions/170903 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/statements/170903_au.pdf условия] 

* '''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 условия] Теорзадачи: [https://yadi.sk/i/XRdg2NJ03PPW59 Кучи] [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 условия] Теорзадачи: [https://yadi.sk/i/bhVPiImo3PkYfS Динамика] [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 условия] Теорзадачи: [https://yadi.sk/d/9neikNMC3Pygjr Динамика] [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 условия] Теорзадачи: [https://yadi.sk/d/2itEbuiU3QAEcS Динамика] [https://yadi.sk/d/_IyzvWKU3QAEmu TeX:src]

* '''13 декабря.''' Практика (дз не было): [https://yadi.sk/i/MvVeElfz3Qnbus dfs]

* '''20 декабря.''' Контест: [https://yadi.sk/i/5Vj66YlR3Qo684 условия] Теорзадачи: [https://yadi.sk/i/DnYf2mlG3QnbwA 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/ Условия контестов]

* '''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/1718f_au/solutions/180214 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/statements/180214_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice/180214.pdf Асимптотика] [http://acm.math.spbu.ru/~sk1/courses/1718f_au/practice-src/180214/ TeX:src]