Алгоритмы и структуры данных семинары 155-2 — различия между версиями
Melnichuk (обсуждение | вклад) (→Первое домашнее задание) |
Melnichuk (обсуждение | вклад) (→Первое домашнее задание) |
||
| Строка 1: | Строка 1: | ||
| + | ===Первый семинар 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=== | ||
| + | Динамическое программирование. | ||
| + | Типы динамики: одномерная и многомерная, восходящая и нисходящая, ленивая и явная. | ||
| + | Решение задачи максимального пути по таблице всеми возможными способами. | ||
| + | |||
===Первое домашнее задание=== | ===Первое домашнее задание=== | ||
Версия 14:11, 3 февраля 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
Динамическое программирование. Типы динамики: одномерная и многомерная, восходящая и нисходящая, ленивая и явная. Решение задачи максимального пути по таблице всеми возможными способами.
Первое домашнее задание
Распределение задач:
| Студенты | Асимптотика – 1 | Асимптотика – 2 | Асимптотика – 3 | Рекуррентности – 1 | Рекуррентности – 2 |
|---|---|---|---|---|---|
| Бочкарева Мария | 3 | 8 | 1 | 3 | 4 |
| Додихудоев Бехзод | 2 | 8 | 6 | 5 | 4 |
| Дурдыева Кумуш | 3 | 5 | 1 | 5 | 1 |
| Журавлев Виталий | 7 | 3 | 2 | 7 | 4 |
| Маркович Александр | 4 | 2 | 3 | 7 | 3 |
| Сердюков Иннокентий | 1 | 5 | 1 | 4 | 1 |
| Соловьев Алексей | 7 | 1 | 5 | 8 | 4 |
| Старков Александр | 8 | 5 | 3 | 7 | 1 |
| Третьяков Александр | 5 | 2 | 4 | 8 | 4 |
| Тумашова Анна | 7 | 1 | 4 | 8 | 3 |
| Фурсов Глеб | 6 | 1 | 4 | 4 | 4 |
| Шибанкова Екатерина | 2 | 6 | 6 | 2 | 1 |
О второй части домашнего задания будет сообщено дополнительно.
Сдавать домашние задания необходимо в AnyTask. Курс и задачи в нем вскоре появятся. Сдача происходит в формате PDF, так что изучайте основы LaTeX, они вам еще много раз пригодятся.
