Algo 2014 1 — различия между версиями
Материал из SEWiki
Burunduk (обсуждение | вклад) (→Результаты и условия контестов) |
Burunduk (обсуждение | вклад) (→Домашние задания по практике. Группа Копелиовича) |
||
| (не показаны 32 промежуточные версии 4 участников) | |||
| Строка 16: | Строка 16: | ||
* '''21 Октября''' [[Медиа:practice-bachelor-sluzhaev-141021.pdf | Домашнее задание по динамическому программированию]] | * '''21 Октября''' [[Медиа:practice-bachelor-sluzhaev-141021.pdf | Домашнее задание по динамическому программированию]] | ||
* '''28 Октября''' [[Медиа:practice-bachelor-sluzhaev-141028.pdf | Домашнее задание по динамическому программированию]] | * '''28 Октября''' [[Медиа:practice-bachelor-sluzhaev-141028.pdf | Домашнее задание по динамическому программированию]] | ||
| + | * '''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 Результаты] | ||
| Строка 73: | Строка 75: | ||
* '''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/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 Сентября''' [[Медиа: | + | * '''02 Сентября''' [[Медиа:14_x1.pdf|Асимптотика]] |
| − | * '''09 Cентября''' [[Медиа: | + | * '''09 Cентября''' [[Медиа:14_x2.pdf|Суммы и циклы for, время работы ]] |
| − | * '''16 Cентября''' [[Медиа: | + | * '''16 Cентября''' [[Медиа:14_x3.pdf|Линейные алгоритмы]] |
| − | * '''23 Cентября''' [[Медиа: | + | * '''23 Cентября''' [[Медиа:14_x4.pdf|Сортировки и кучи]] |
| − | * '''30 Cентября''' [[Медиа: | + | * '''30 Cентября''' [[Медиа:14_x5.pdf|Статистики и кучи]] |
| − | * '''7 Октября''' [[Медиа: | + | * '''7 Октября''' [[Медиа:14_x6.pdf|Бинарный поиск и поиск экстремальных точек]] |
| − | * '''14 Октября''' [[Медиа: | + | * '''14 Октября''' [[Медиа:14_x7.pdf|Динамика (ДЗ)]] [[Медиа:141014_classwork.pdf|Условие практики (было на паре)]] |
| − | * '''21 Октября''' [[Медиа: | + | * '''21 Октября''' [[Медиа:14_x8.pdf|Динамика++]] |
| − | * '''28 Октября''' [[Медиа: | + | * '''28 Октября''' [[Медиа:14_x9.pdf|Динамика по подмножествам]] |
| − | 4 ноября -- день народного единства | + | * '''4 ноября''' -- день народного единства |
| − | * '''11 ноября''' [[Медиа: | + | * '''11 ноября''' [[Медиа:14_xA.pdf|Графы: DFS]] |
| + | |||
| + | * '''18 ноября''' [[Медиа:14_xB.pdf|DFS и динамика]] | ||
| + | |||
| + | * '''25 ноября''' [[Медиа:14_xC.pdf|Кратчайшие пути]] | ||
| + | |||
| + | * '''2 декабря''' [[Медиа:14_xD.pdf|MST и DSU]] | ||
| + | |||
| + | * '''9 декабря''' [[Медиа:14_xE.pdf|MST и DSU]] | ||
| + | |||
| + | * '''16 декабря''' [[Медиа:14_xF.pdf|Разные задачи]] | ||
== Домашние задания по практике. Группа Опарина == | == Домашние задания по практике. Группа Опарина == | ||
| Строка 103: | Строка 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 ↔ add; get,build → add; find → 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) → add O(1), bootstrapping [add O(1) + merge O(logn) → 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)
Домашние задачи по практике. Группа Служаева
- 16 Cентября Линейные алгоритмы
- 23 Cентября Сортировки и бинарный поиск + дз
- 30 Cентября Сортировки и кучи + дз
- 7 Октября Динамическое программирование + дз
- 21 Октября Домашнее задание по динамическому программированию
- 28 Октября Домашнее задание по динамическому программированию
- 18 Ноября Домашнее задание по dfs
- 2 Декабря Домашнее задание по кратчайшим путям в графах
MIT
Практика - Копелиович Сергей (burunduk30@gmail.com), Опарин Всеволод
Деление на группы: <link>
Отчетность по курсу
- Одна глава электронного конспекта в TeX. Дедлайн 2 недели.
- Общий теорэкзамен: базовые и продвинутые лекции.
- Допуск к экзамену: зачет по практической части курса.
- Практическая часть: каждую неделю получаете контест и теорзадачи. Нужно сдать хотя бы 100% группа Копелиовича, текущие результаты
- Реализация и тестирование одного из описанных алгоритмов. С 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 сообщения "проверьте меня"
Домашние задания по практике. Группа Копелиовича
- 02 Сентября Асимптотика
- 09 Cентября Суммы и циклы for, время работы
- 16 Cентября Линейные алгоритмы
- 23 Cентября Сортировки и кучи
- 30 Cентября Статистики и кучи
- 14 Октября Динамика (ДЗ) Условие практики (было на паре)
- 21 Октября Динамика++
- 28 Октября Динамика по подмножествам
- 4 ноября -- день народного единства
- 11 ноября Графы: DFS
- 18 ноября DFS и динамика
- 25 ноября Кратчайшие пути
- 2 декабря MST и DSU
- 9 декабря MST и DSU
- 16 декабря Разные задачи
Домашние задания по практике. Группа Опарина
Лекции: конспект и экзамен
Конспекты лекций, сделанные силами студентов [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*, оценка скорости работы в графах с неравенством треугольника
