Алгоритмы 3 2016/17 осень — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
(Планы лекций)
(Информация от 01.12.2016)
 
(не показано 16 промежуточных версий 2 участников)
Строка 3: Строка 3:
 
* Теоретический зачёт/экзамен в конце курса
 
* Теоретический зачёт/экзамен в конце курса
 
* Еженедельные задачи в контест на реализацию
 
* Еженедельные задачи в контест на реализацию
 +
 +
=== Информация от 01.12.2016 ===
 +
Взято из группы и немного переписано:
 +
 +
* Недифференцированный зачёт. При этом сдаём дифференцировано и 2-3 выражается в незачёт, а 4-5 в зачёт.
 +
* На зачёте сдаём теорию без конспекта.
 +
* 8-го последняя пара, 15-го утром консультация, 17-го в субботу зачёт.
 +
* Задачи из контеста можно будет сдавать до 22-го декабря 23:59.
 +
* 23-го по плану у вас должен стоять зачёт. Если зачёт сдан хотя бы на три и в контесте сдано строго больше половины, то до 29-го можно досдать практику и получить зачёт. Если условия не выполняются - результат получения зачёта неопределён.
  
 
== Контест ==
 
== Контест ==
  
 
* [http://acm.math.spbu.ru/tsweb/ Тестирующая система]
 
* [http://acm.math.spbu.ru/tsweb/ Тестирующая система]
* [http://acm.math.spbu.ru/trains/160901_au.pdf Условия задач]
+
* [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/160901_au.pdf Условия задач]
 
* [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160901_au.dat Результаты]
 
* [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160901_au.dat Результаты]
  
Строка 13: Строка 22:
  
 
[http://acm.math.spbu.ru/~sk1/courses/1617f_au3/program.pdf Программа курса]
 
[http://acm.math.spbu.ru/~sk1/courses/1617f_au3/program.pdf Программа курса]
 +
 +
[http://acm.math.spbu.ru/~sk1/courses/1617f_au3/questions-algo3-2016f-exam.pdf Вопросы к экзамену]
  
 
* 08.09 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/0908-FFT.html FFT и длинная арифметика] (конспект: Надя Бугакова)
 
* 08.09 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/0908-FFT.html FFT и длинная арифметика] (конспект: Надя Бугакова)
Строка 19: Строка 30:
 
* 29.09 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/0929-Matching.html Паросочетания в произвольном графе] (конспект: Дима Лапшин)
 
* 29.09 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/0929-Matching.html Паросочетания в произвольном графе] (конспект: Дима Лапшин)
 
* 06.10 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1006-LP.html Линейное программирование и симплекс метод] (конспект: Юра Ребрик)
 
* 06.10 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1006-LP.html Линейное программирование и симплекс метод] (конспект: Юра Ребрик)
* 13.10 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1013-LP.html Линейное программирование, продолжение] (конспект: Суворов Егор) [http://www-math.mit.edu/~goemans/18433S09/ellipsoid.pdf (Эллипсоиды)]
+
* 13.10 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1013-LP.html Линейное программирование, продолжение] (конспект: Суворов Егор)  
 
* 20.10 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1020-LP.html Линейное программирование, часть 3] (конспект: ?)  
 
* 20.10 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1020-LP.html Линейное программирование, часть 3] (конспект: ?)  
 +
* 01.11 (вт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1101-Planar.html Планарные графы] (конспект: Дима Лапшин)
 +
* 17.11 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1117-Planar-random.html Окончание планарных графов, рандомизированные алгоритмы] (конспект: Глеб Валин)
 +
* 24.11 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1124-Planes-random.html Полуплоскости, рандомизированные алгоритмы] (конспект: Лабутин Игорь)
 +
* 01.12 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1201-Polygons.html Выпуклые многоугольники, динамическая выпуклая оболочка] (конспект: Никонов Миша)
 +
* 08.12 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1208-Math.html  Диагарамма Вороного за <math>n^2</math>, корни многочленов в R, C, <math>F_p</math>, факторизация чисел Крайчиком] (конспект: Подгузов Никита)
 +
* 15.12 (чт) '''Консультация'''
 +
* 17.12 (сб) '''Теорзачёт'''
  
 +
== Литература, статьи ==
  
= Литература по LP =
+
=== Линейное программирование ===
  
 +
* [http://www-math.mit.edu/~goemans/18433S09/ellipsoid.pdf (Эллипсоиды)]
 
* [http://cs.brown.edu/courses/csci1490/notes/day9.pdf (Bland's rule proof)]  
 
* [http://cs.brown.edu/courses/csci1490/notes/day9.pdf (Bland's rule proof)]  
 
* [http://www-math.mit.edu/~goemans/notes-lp.ps (LP: Duality, Interior Point Ye's algorithm)]
 
* [http://www-math.mit.edu/~goemans/notes-lp.ps (LP: Duality, Interior Point Ye's algorithm)]
Строка 30: Строка 50:
 
* [http://old.compsciclub.ru/courses/linearprogramming (CS-Club, Максим Бабенко, видео)]
 
* [http://old.compsciclub.ru/courses/linearprogramming (CS-Club, Максим Бабенко, видео)]
 
* [https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture06.pdf (MaxFlow-MinCut duality)]
 
* [https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture06.pdf (MaxFlow-MinCut duality)]
 +
* [https://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube (Тест, на котором симплекс работает за экспоннету)]
 +
* [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture11.pdf (Взвешенное паросочетание в произвольном графе)]
 +
* [http://pub.ist.ac.at/~vnk/papers/BLOSSOM5.html (Реализация и подробное описание алгоритма поиска взвешенного паросочетания в произвольном графе)]
 +
 +
=== Планарные графы ===
 +
 +
* [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/papers/O(n)_new.pdf Ulrik Brandes'2011, алгоритм за O(n)]
 +
* [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/papers/demoucron-lucie-martinet.pdf Алгоритм Демукрона]
 +
* [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/papers/schnyder-grid-embedding.pdf Шнайдер'1989, укладка на гриде]

Текущая версия на 19:06, 25 декабря 2016

Отчётность

  • Теоретический зачёт/экзамен в конце курса
  • Еженедельные задачи в контест на реализацию

Информация от 01.12.2016

Взято из группы и немного переписано:

  • Недифференцированный зачёт. При этом сдаём дифференцировано и 2-3 выражается в незачёт, а 4-5 в зачёт.
  • На зачёте сдаём теорию без конспекта.
  • 8-го последняя пара, 15-го утром консультация, 17-го в субботу зачёт.
  • Задачи из контеста можно будет сдавать до 22-го декабря 23:59.
  • 23-го по плану у вас должен стоять зачёт. Если зачёт сдан хотя бы на три и в контесте сдано строго больше половины, то до 29-го можно досдать практику и получить зачёт. Если условия не выполняются - результат получения зачёта неопределён.

Контест

Планы лекций

Программа курса

Вопросы к экзамену

Литература, статьи

Линейное программирование

Планарные графы