Algo 2014 1 — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
(→‎Домашние задания по практике. Группа Копелиовича)
(→‎Домашние задания по практике. Группа Копелиовича)
 
(не показано 27 промежуточных версий 4 участников)
Строка 17: Строка 17:
 
* '''28 Октября''' [[Медиа:practice-bachelor-sluzhaev-141028.pdf | Домашнее задание по динамическому программированию]]
 
* '''28 Октября''' [[Медиа:practice-bachelor-sluzhaev-141028.pdf | Домашнее задание по динамическому программированию]]
 
* '''18 Ноября''' [[Медиа:practice-bachelor-sluzhaev-141118.pdf | Домашнее задание по dfs]]
 
* '''18 Ноября''' [[Медиа:practice-bachelor-sluzhaev-141118.pdf | Домашнее задание по dfs]]
 +
* '''2 Декабря''' [[Медиа:practice-bachelor-sluzhaev-141202.pdf | Домашнее задание по кратчайшим путям в графах]]
 
[https://docs.google.com/spreadsheets/d/1gLUwgo8fQQdr6mA60KIV5ynb-oUaZeOlYkOQRV15Yd8/edit#gid=0 Результаты]
 
[https://docs.google.com/spreadsheets/d/1gLUwgo8fQQdr6mA60KIV5ynb-oUaZeOlYkOQRV15Yd8/edit#gid=0 Результаты]
  
Строка 75: Строка 76:
 
* '''17 ноября''' [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m141117_au.dat дз #11] [http://acm.math.spbu.ru/trains/141117_au.pdf условия] DFS, DP, trees
 
* '''17 ноября''' [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m141117_au.dat дз #11] [http://acm.math.spbu.ru/trains/141117_au.pdf условия] DFS, DP, trees
  
−
* '''24 ноября''' [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m141124_au.dat дз #12] [http://acm.math.spbu.ru/trains/141123_au.pdf условия] Кратчайшие пути
+
* '''24 ноября''' [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m141124_au.dat дз #12] [http://acm.math.spbu.ru/trains/141124_au.pdf условия] Кратчайшие пути
 +
 
 +
* '''1 декабря''' [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m141201_au.dat дз #13] [http://acm.math.spbu.ru/trains/141201_au.pdf условия] MST и DSU
 +
 
 +
* '''8 декабря''' [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m141208_au.dat дз #14] [http://acm.math.spbu.ru/trains/141208_au.pdf условия] деревья
 +
 
 +
== Персональные домашние задания ==
 +
 
 +
Таблица распределения персональных ДЗ по алгоритмам:
 +
 
 +
https://docs.google.com/spreadsheets/d/1V9HVo-wmDeF5w3gNBHCYjTFWzumBMsnmZR1d5h5ddRI/edit#gid=0
 +
 
 +
С персональным домашним заданием не должно быть проблем с теорией, с пониманием, как и что писать, нужно сесть и написать. Если есть пробелы в теории, вопросы по заданию, обращайтесь к Сергею Копелиовичу.
 +
'''До 15-го декабря 01:00''' (ночь с вс на пн) нужно прислать первую версию. '''До 22-го декабря 01:00''' (ночь с вс на пн) прислать готовую с вашей точки зрения версию, к которой я придерусь. Придирки нужно будет исправить до Нового Года.
 +
Для тех, кто делает учебные задачи выложен пример: http://acm.math.spbu.ru/~sk1/problems/sample.7z
 +
 
 +
Коммитить готовое ДЗ сюда: http://mit.spbau.ru/svn/algo14b/логин
 +
 
 +
Чтобы ДЗ проверили, нужно написать на почту Burunduk30@gmail.com письмо с просьбой проверить, в теме письма на забудьте подстроку [AU].
 +
 
 +
P.S. Пример использования svn:
 +
 
 +
* svn co http://mit.spbau.ru/svn/algo14b/kravchenko.jurij (создали себе копию)
 +
* svn add <файлы> <папки> (добавили файлы у себя локально)
 +
* svn ci -m "comment to this commit" (добавили изменения на сервер)
 +
* После коммита можно писать на Burunduk30@gmail.com сообщения "проверьте меня"
  
 
== Домашние задания по практике. Группа Копелиовича ==
 
== Домашние задания по практике. Группа Копелиовича ==
  
−
* '''02 Сентября''' [[Медиа:140902.pdf|Асимптотика]] [[Файл:140902.pdf|Асимптотика]]
+
* '''02 Сентября''' [[Медиа:14_x1.pdf|Асимптотика]]  
  
−
* '''09 Cентября''' [[Медиа:140909.pdf|Суммы и циклы for, время работы ]]
+
* '''09 Cентября''' [[Медиа:14_x2.pdf|Суммы и циклы for, время работы ]]
  
−
* '''16 Cентября''' [[Медиа:140916.pdf|Линейные алгоритмы]]
+
* '''16 Cентября''' [[Медиа:14_x3.pdf|Линейные алгоритмы]]
  
−
* '''23 Cентября''' [[Медиа:140923.pdf|Сортировки и кучи]]
+
* '''23 Cентября''' [[Медиа:14_x4.pdf|Сортировки и кучи]]
  
−
* '''30 Cентября''' [[Медиа:140930.pdf|Статистики и кучи]]
+
* '''30 Cентября''' [[Медиа:14_x5.pdf|Статистики и кучи]]
  
−
* '''7 Октября''' [[Медиа:141007.pdf|Бинарный поиск и поиск экстремальных точек]]
+
* '''7 Октября''' [[Медиа:14_x6.pdf|Бинарный поиск и поиск экстремальных точек]]
  
−
* '''14 Октября''' [[Медиа:141014.pdf|Динамика (ДЗ)]] [[Медиа:141014_classwork.pdf|Условие практики (было на паре)]]
+
* '''14 Октября''' [[Медиа:14_x7.pdf|Динамика (ДЗ)]] [[Медиа:141014_classwork.pdf|Условие практики (было на паре)]]
  
−
* '''21 Октября''' [[Медиа:141021.pdf|Динамика++]]
+
* '''21 Октября''' [[Медиа:14_x8.pdf|Динамика++]]
  
−
* '''28 Октября''' [[Медиа:141028.pdf|Динамика по подмножествам]]
+
* '''28 Октября''' [[Медиа:14_x9.pdf|Динамика по подмножествам]]
  
 
* '''4 ноября''' -- день народного единства
 
* '''4 ноября''' -- день народного единства
  
−
* '''11 ноября''' [[Медиа:141111.pdf|Графы: DFS]]
+
* '''11 ноября''' [[Медиа:14_xA.pdf|Графы: DFS]]
  
−
* '''18 ноября''' [[Медиа:141118.pdf|DFS и динамика]]
+
* '''18 ноября''' [[Медиа:14_xB.pdf|DFS и динамика]]
  
−
* '''25 ноября''' [[Медиа:141125.pdf|Кратчайшие пути]]
+
* '''25 ноября''' [[Медиа:14_xC.pdf|Кратчайшие пути]]
 +
 
 +
* '''2 декабря''' [[Медиа:14_xD.pdf|MST и DSU]]
 +
 
 +
* '''9 декабря''' [[Медиа:14_xE.pdf|MST и DSU]]
 +
 
 +
* '''16 декабря''' [[Медиа:14_xF.pdf|Разные задачи]]
  
 
== Домашние задания по практике. Группа Опарина ==
 
== Домашние задания по практике. Группа Опарина ==
Строка 110: Строка 142:
  
 
* [https://docs.google.com/spreadsheets/d/14S8Dx-MwCD_lwKOcJmsIxPNnTL_46lS9n26QnWdmzxA/edit?usp=sharing| Результаты]
 
* [https://docs.google.com/spreadsheets/d/14S8Dx-MwCD_lwKOcJmsIxPNnTL_46lS9n26QnWdmzxA/edit?usp=sharing| Результаты]
 +
 +
== Лекции: конспект и экзамен ==
 +
 +
* [[Медиа:questions-hard.pdf|Вопросы к экзамену]]
 +
 +
Конспекты лекций, сделанные силами студентов [https://www.dropbox.com/sh/m7eyz7ou9ndh5f7/AAA6_alB1kHUF0Mw8Mz3tr7Xa?dl=0]
 +
 +
* [[Медиа:program.tex|Список авторов]]
 +
 +
* [[Медиа:2014-09-02-Intro.pdf|2014-09-02-Intro.pdf]]            : общие слова, разбор вступительного теста
 +
* [[Медиа:2014-09-09-DataStrucutre.pdf|2014-09-09-DataStrucutre.pdf]]    : стек, дек, очередь, вектор с удвоением и без амортизации, хеш-таблица на списках, частичные суммы, бинарный поиск, аллокация памяти
 +
* [[Медиа:2014-09-17-conspect.pdf|2014-09-17-conspect.pdf]]        : нижняя оценка на сортировку, разбор выражений со стеком, преобразование операци: merge &harr; add; get,build &rarr; add; find &rarr; delete, хеш-таблица с открытой адресацией
 +
* [[Медиа:2014-09-23-Sorts-2.pdf|2014-09-23-Sorts-2.pdf]]          : квадратичные сортировки, radix sort, bucket sort, Kirkpatrick's sort, adaptive heap sort, историческая справка
 +
* [[Медиа:2014-09-30-Heaps.pdf|2014-09-30-Heaps.pdf]]            : интерфейс "куча", k-heap, leftist heap, skew heap, merge O(logn) + build O(n) &rarr; add O(1), bootstrapping [add O(1) + merge O(logn) &rarr; merge O(1)]
 +
* [[Медиа:2014-10-07-Heaps-And-Merge.pdf|2014-10-07-Heaps-And-Merge.pdf]]  : inplace stable merge, minmax heap, нижняя оценка на построение бинарной кучи, pairing heap
 +
* [[Медиа:2014-10-14-Heaps.pdf|2014-10-14-Heaps.pdf]]            : доказательство оценки O(sqrt(n)) в pairing heap, биномиальные деревья и кучи, реклама кучи Фибоначчи
 +
* [[Медиа:2014-10-21-DP.pdf|2014-10-21-DP.pdf]]              : задачи на диниамку: погрузка грузов на корабль за O(n<sup>2</sup>) времени и O(n) памяти, кратчайший путь на гриде при перемещении по трём направлениям, наибольший по площади красный многоугольник
 +
* [[Медиа:2014-10-21-Fib.pdf|2014-10-21-Fib.pdf]]              : куча Фибоначчи -- полное описание и доказательство
 +
* [[Медиа:2014-10-28-DP.pdf|2014-10-28-DP.pdf]]              : динамика по подмножествам: операции с множествами, старший/младший/число бит, vertex coloring за O(3^n), гамильтонов путь/цикл за O(2^n*n), set cover за O(2^m), is_independent за O(2^n)
 +
* [[Медиа:2014-11-11-DFS.pdf|2014-11-11-DFS.pdf]]              : мосты, точки сочленения, компоненты вершинной двусвязности, рёберной двусвязности, эйлеров путь/цикл
 +
* [[Медиа:2014-11-18-graphs.pdf|2014-11-18-graphs.pdf]]          : цикл Де Брюина, задача про ориентацию графа, два указателя: профессор с яйцами; обобщение метода с временем работы sqrt(n) на запрос; задача про точки на прямой (одна, две, k)
 +
* [[Медиа:2014-11-25-bfs-upgraded.pdf|2014-11-25-bfs-upgraded.pdf]]    : поиск в ширину, алгоритм Dial-а, кратчайший путь за O(m + nsqrt(k)), O((m+n)logk), radix heap, реализация dijkstra за O(m + nlogk), двухуровневая radix heap
 +
* [[Медиа:2014-12-02-DP-proof-SK.pdf|2014-12-02-DP-proof-SK.pdf]]      : доказательство корректности решения за O(n<sup>2</sup>) для поиска k точек на прямой (часть от Серёжи Копелиовича)
 +
* [[Медиа:2014-12-02-DP-proof-olga.pdf|2014-12-02-DP-proof-olga.pdf]]    : доказательство корректности решения за O(n<sup>2</sup>) для поиска k точек на прямой (часть от Оли Черниковой)
 +
* [[Медиа:2014-12-02-FB-and-DP-proof.pdf|2014-12-02-FB-and-DP-proof.pdf]]  : доказательство корректности решения за O(n<sup>2</sup>) для поиска k точек на прямой, кратчайшие пути: историческая справка, Форд-Беллман, оптимизации к Форд-Беллман, поиск отрицательного цикла
 +
* [[Медиа:2014-12-09-Goldberg.pdf|2014-12-09-Goldberg.pdf]]        : алгоритм Гольдберга поиска кратчайшего пути за O(msqrtnlogN)
 +
* [[Медиа:2014-12-16-Karp.pdf|2014-12-16-Karp.pdf]]            : поиск цикла минимального среднего веса: решение бинарным поиском, алгоритм Карпа за O(nm) с доказательством
 +
* [[Медиа:2014-12-16-Yen-AStar.pdf|2014-12-16-Yen-AStar.pdf]]        : алгоритм Йена поиска k-го кратчайшего пути, алгоритм A<sup>*</sup>, оценка скорости работы в графах с неравенством треугольника
 +
 +
[[Category:1 курс. Осень 2014]]

Текущая версия на 14:17, 29 февраля 2016

Общие лекторы

Лектор #1 - Куликов Александр

Лектор #2 - Копелиович Сергей

Физики

Практика - Фондаратов Валентин, Служаев Евгений (evgentu@gmail.com)

Домашние задачи по практике. Группа Служаева

Результаты

MIT

Практика - Копелиович Сергей (burunduk30@gmail.com), Опарин Всеволод

Деление на группы: <link>

Материалы курса в dropbox

Результаты сдачи практики

Отчетность по курсу

  • Одна глава электронного конспекта в TeX. Дедлайн 2 недели.
  • Общий теорэкзамен: базовые и продвинутые лекции.
  • Допуск к экзамену: зачет по практической части курса.
  • Реализация и тестирование одного из описанных алгоритмов. С codereview, c промежуточным дедлайном 2 недели и окончательным дедлайном 1 месяц. Выдача ДЗ персональная, старт синхронный.

Формат сдачи ДЗ

Дедлайны теорзадач: мягкий в вс. 01:00, далее стоимость уменьшается в 2 раза, жесткий в вс. 23:59.

Дедлайн контеста: в вс. в 23:59 (через 11 суток после начала).

Задачи контеста сдавать в систему.

Теорзадачи отсылать по email преподавателю группы. Тема письма должна содержать подстроку [AU].

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

Персональные домашние задания

Таблица распределения персональных ДЗ по алгоритмам:

https://docs.google.com/spreadsheets/d/1V9HVo-wmDeF5w3gNBHCYjTFWzumBMsnmZR1d5h5ddRI/edit#gid=0

С персональным домашним заданием не должно быть проблем с теорией, с пониманием, как и что писать, нужно сесть и написать. Если есть пробелы в теории, вопросы по заданию, обращайтесь к Сергею Копелиовичу. До 15-го декабря 01:00 (ночь с вс на пн) нужно прислать первую версию. До 22-го декабря 01:00 (ночь с вс на пн) прислать готовую с вашей точки зрения версию, к которой я придерусь. Придирки нужно будет исправить до Нового Года. Для тех, кто делает учебные задачи выложен пример: http://acm.math.spbu.ru/~sk1/problems/sample.7z

Коммитить готовое ДЗ сюда: http://mit.spbau.ru/svn/algo14b/логин

Чтобы ДЗ проверили, нужно написать на почту Burunduk30@gmail.com письмо с просьбой проверить, в теме письма на забудьте подстроку [AU].

P.S. Пример использования svn:

  • svn co http://mit.spbau.ru/svn/algo14b/kravchenko.jurij (создали себе копию)
  • svn add <файлы> <папки> (добавили файлы у себя локально)
  • svn ci -m "comment to this commit" (добавили изменения на сервер)
  • После коммита можно писать на Burunduk30@gmail.com сообщения "проверьте меня"

Домашние задания по практике. Группа Копелиовича

  • 4 ноября -- день народного единства

Домашние задания по практике. Группа Опарина

Лекции: конспект и экзамен

Конспекты лекций, сделанные силами студентов [1]

  • 2014-09-02-Intro.pdf  : общие слова, разбор вступительного теста
  • 2014-09-09-DataStrucutre.pdf  : стек, дек, очередь, вектор с удвоением и без амортизации, хеш-таблица на списках, частичные суммы, бинарный поиск, аллокация памяти
  • 2014-09-17-conspect.pdf  : нижняя оценка на сортировку, разбор выражений со стеком, преобразование операци: merge ↔ add; get,build → add; find → delete, хеш-таблица с открытой адресацией
  • 2014-09-23-Sorts-2.pdf  : квадратичные сортировки, radix sort, bucket sort, Kirkpatrick's sort, adaptive heap sort, историческая справка
  • 2014-09-30-Heaps.pdf  : интерфейс "куча", k-heap, leftist heap, skew heap, merge O(logn) + build O(n) → add O(1), bootstrapping [add O(1) + merge O(logn) → merge O(1)]
  • 2014-10-07-Heaps-And-Merge.pdf  : inplace stable merge, minmax heap, нижняя оценка на построение бинарной кучи, pairing heap
  • 2014-10-14-Heaps.pdf  : доказательство оценки O(sqrt(n)) в pairing heap, биномиальные деревья и кучи, реклама кучи Фибоначчи
  • 2014-10-21-DP.pdf  : задачи на диниамку: погрузка грузов на корабль за O(n2) времени и O(n) памяти, кратчайший путь на гриде при перемещении по трём направлениям, наибольший по площади красный многоугольник
  • 2014-10-21-Fib.pdf  : куча Фибоначчи -- полное описание и доказательство
  • 2014-10-28-DP.pdf  : динамика по подмножествам: операции с множествами, старший/младший/число бит, vertex coloring за O(3^n), гамильтонов путь/цикл за O(2^n*n), set cover за O(2^m), is_independent за O(2^n)
  • 2014-11-11-DFS.pdf  : мосты, точки сочленения, компоненты вершинной двусвязности, рёберной двусвязности, эйлеров путь/цикл
  • 2014-11-18-graphs.pdf  : цикл Де Брюина, задача про ориентацию графа, два указателя: профессор с яйцами; обобщение метода с временем работы sqrt(n) на запрос; задача про точки на прямой (одна, две, k)
  • 2014-11-25-bfs-upgraded.pdf  : поиск в ширину, алгоритм Dial-а, кратчайший путь за O(m + nsqrt(k)), O((m+n)logk), radix heap, реализация dijkstra за O(m + nlogk), двухуровневая radix heap
  • 2014-12-02-DP-proof-SK.pdf  : доказательство корректности решения за O(n2) для поиска k точек на прямой (часть от Серёжи Копелиовича)
  • 2014-12-02-DP-proof-olga.pdf  : доказательство корректности решения за O(n2) для поиска k точек на прямой (часть от Оли Черниковой)
  • 2014-12-02-FB-and-DP-proof.pdf  : доказательство корректности решения за O(n2) для поиска k точек на прямой, кратчайшие пути: историческая справка, Форд-Беллман, оптимизации к Форд-Беллман, поиск отрицательного цикла
  • 2014-12-09-Goldberg.pdf  : алгоритм Гольдберга поиска кратчайшего пути за O(msqrtnlogN)
  • 2014-12-16-Karp.pdf  : поиск цикла минимального среднего веса: решение бинарным поиском, алгоритм Карпа за O(nm) с доказательством
  • 2014-12-16-Yen-AStar.pdf  : алгоритм Йена поиска k-го кратчайшего пути, алгоритм A*, оценка скорости работы в графах с неравенством треугольника
Источник — «http://mit.spbau.ru/sewiki/index.php?title=Algo_2014_1&oldid=7491»