Алгоритмы и структуры данных семинары 155-2 — различия между версиями
Melnichuk (обсуждение | вклад) (→Восьмой семинар 03.02.2016) |
Melnichuk (обсуждение | вклад) (→Первое домашнее задание) |
||
| Строка 49: | Строка 49: | ||
{| class="wikitable" | {| class="wikitable" | ||
|- | |- | ||
| − | ! Студенты !! Асимптотика – 1 !! Асимптотика – 2 !! Асимптотика – 3 !! Рекуррентности – 1 !! Рекуррентности – 2 | + | ! Студенты !! Сортировка-1 !! Сортировка-2 !! Асимптотика – 1 !! Асимптотика – 2 !! Асимптотика – 3 !! Рекуррентности – 1 !! Рекуррентности – 2 |
|- | |- | ||
| − | | Артемьев Максим || 2 || 4 || 1 || 7 || 8 | + | | Артемьев Максим || Перевертыш || Гармония || 2 || 4 || 1 || 7 || 8 |
|- | |- | ||
| − | | Богдашевская Мария || 4 || 1 || 2 || 7 || 6 | + | | Богдашевская Мария || Коллекционер Диего || Маляры || 4 || 1 || 2 || 7 || 6 |
|- | |- | ||
| − | | Бочкарева Мария || 3 || 8 || 4 || 3 || 1 | + | | Бочкарева Мария || Коллекционер Диего || Маляры || 3 || 8 || 4 || 3 || 1 |
|- | |- | ||
| − | | Додихудоев Бехзод || 2 || 8 || 4 || 5 || 6 | + | | Додихудоев Бехзод || Перевертыш || Гармония || 2 || 8 || 4 || 5 || 6 |
|- | |- | ||
| − | | Дурдыева Кумуш || 3 || 5 || 1 || 5 || 1 | + | | Дурдыева Кумуш || Коллекционер Диего || Гармония || 3 || 5 || 1 || 5 || 1 |
|- | |- | ||
| − | | Журавлев Виталий || 7 || 3 || 4 || 7 || 2 | + | | Журавлев Виталий || Коллекционер Диего || Гармония || 7 || 3 || 4 || 7 || 2 |
|- | |- | ||
| − | | Маркович Александр || 4 || 2 || 3 || 7 || 3 | + | | Маркович Александр || Коллекционер Диего || Маляры || 4 || 2 || 3 || 7 || 3 |
|- | |- | ||
| − | | Сердюков Иннокентий || 1 || 5 || 1 || 4 || 1 | + | | Сердюков Иннокентий || Перевертыш || Маляры || 1 || 5 || 1 || 4 || 1 |
|- | |- | ||
| − | | Соловьев Алексей || 7 || 1 || 4 || 8 || 5 | + | | Соловьев Алексей || Перевертыш || Гармония || 7 || 1 || 4 || 8 || 5 |
|- | |- | ||
| − | | Старков Александр || 8 || 5 || 1 || 7 || 3 | + | | Старков Александр || Перевертыш || Маляры || 8 || 5 || 1 || 7 || 3 |
|- | |- | ||
| − | | Третьяков Александр || 5 || 2 || 4 || 8 || 4 | + | | Третьяков Александр || Перевертыш || Гармония || 5 || 2 || 4 || 8 || 4 |
|- | |- | ||
| − | | Тумашова Анна || 7 || 1 || 3 || 8 || 4 | + | | Тумашова Анна || Коллекционер Диего || Маляры || 7 || 1 || 3 || 8 || 4 |
|- | |- | ||
| − | | Шибанкова Екатерина || 2 || 6 || 1 || 2 || 6 | + | | Шибанкова Екатерина || Перевертыш || Маляры || 2 || 6 || 1 || 2 || 6 |
|- | |- | ||
|} | |} | ||
Версия 23:57, 9 февраля 2016
Содержание
Первый семинар 11.01.2016
Рекурсия и ханойские башни. Другие применения рекурсии. Анализ сложности алгоритмов.
Второй семинар 13.01.2016
Основы амортизационного анализа: банковский метод, метод потенциалов. k-битовый счетчик. Вектор или массив переменного размера.
Третий семинар 18.01.2016
Понятие асимптотики. О-исчисление. Решение теоретических задач.
Четвертый семинар 20.01.2016
Merge, сортировка слиянием, partition, быстрая сортировка. Практика. Реализация сортировок. https://official.contest.yandex.ru/contest/2007/
Пятый семинар 25.01.2016
Порядковые статистики. Алгоритм и анализ сложности. Практика. Реализация сортировок. https://official.contest.yandex.ru/contest/2007/
Шестой семинар 27.01.2016
Основная теорема о рекуррентных асимптотических соотношениях. Маленькая самостоятельная работа на асимптотики.
Седьмой семинар 01.02.2016
Devide and conquer! Примеры применения: сортировки, выпуклая оболочка, бинарный поиск. Примеры невозможности решения задачи этим методом: остовное дерево. Анализ сложности полученных алгоритмов.
Восьмой семинар 03.02.2016
Динамическое программирование. Типы динамики: одномерная и многомерная, восходящая и нисходящая, ленивая и явная. Решение задачи максимального пути по таблице всеми возможными способами.
Девятый семинар 08.02.2016
Динамическое программирование. Общий подход к решению задач методом динамического программирования. Практика по решению задач. https://official.contest.yandex.ru/contest/2185/
Первое домашнее задание
Распределение задач:
| Студенты | Сортировка-1 | Сортировка-2 | Асимптотика – 1 | Асимптотика – 2 | Асимптотика – 3 | Рекуррентности – 1 | Рекуррентности – 2 |
|---|---|---|---|---|---|---|---|
| Артемьев Максим | Перевертыш | Гармония | 2 | 4 | 1 | 7 | 8 |
| Богдашевская Мария | Коллекционер Диего | Маляры | 4 | 1 | 2 | 7 | 6 |
| Бочкарева Мария | Коллекционер Диего | Маляры | 3 | 8 | 4 | 3 | 1 |
| Додихудоев Бехзод | Перевертыш | Гармония | 2 | 8 | 4 | 5 | 6 |
| Дурдыева Кумуш | Коллекционер Диего | Гармония | 3 | 5 | 1 | 5 | 1 |
| Журавлев Виталий | Коллекционер Диего | Гармония | 7 | 3 | 4 | 7 | 2 |
| Маркович Александр | Коллекционер Диего | Маляры | 4 | 2 | 3 | 7 | 3 |
| Сердюков Иннокентий | Перевертыш | Маляры | 1 | 5 | 1 | 4 | 1 |
| Соловьев Алексей | Перевертыш | Гармония | 7 | 1 | 4 | 8 | 5 |
| Старков Александр | Перевертыш | Маляры | 8 | 5 | 1 | 7 | 3 |
| Третьяков Александр | Перевертыш | Гармония | 5 | 2 | 4 | 8 | 4 |
| Тумашова Анна | Коллекционер Диего | Маляры | 7 | 1 | 3 | 8 | 4 |
| Шибанкова Екатерина | Перевертыш | Маляры | 2 | 6 | 1 | 2 | 6 |
О второй части домашнего задания будет сообщено дополнительно.
Сдавать домашние задания необходимо в AnyTask. Курс и задачи в нем вскоре появятся. Сдача происходит в формате PDF, так что изучайте основы LaTeX, они вам еще много раз пригодятся. Делайн по теории - 15 февраля.
