Алгоритмы и структуры данных семинары 155-2

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

Первый семинар 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
Артемьев Максим 2 4 8 7 1
Богдашевская Мария 4 1 6 7 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, они вам еще много раз пригодятся. Делайн по теории - 15 февраля.