Алгоритмы и структуры данных на ПМИ (основной поток) — различия между версиями
Материал из Wiki - Факультет компьютерных наук
.obj (обсуждение | вклад) (→Лекции) |
.obj (обсуждение | вклад) |
||
Строка 18: | Строка 18: | ||
[https://official.contest.yandex.ru/contest/3855 Сортировки] — до 12 февраля. Для решения задачи F необязательно использовать именно алгоритм, реализованный в рамках решения задачи E. | [https://official.contest.yandex.ru/contest/3855 Сортировки] — до 12 февраля. Для решения задачи F необязательно использовать именно алгоритм, реализованный в рамках решения задачи E. | ||
+ | |||
+ | |||
+ | == Контрольные работы == | ||
+ | [https://www.dropbox.com/s/p3nlzn6fyhdi1ll/algo-quiz1-sample.pdf?dl=0 Тренировочный вариант] мартовской контрольной работы | ||
== Страницы семинаров == | == Страницы семинаров == | ||
[[АиСД_167-1|группа 167-1]] | [[АиСД_167-1|группа 167-1]] |
Версия 12:42, 27 февраля 2017
Лектор: С. Объедков
Расписание лекций:
четверг 12:10 – 13:30, ауд. 622
Содержание
Лекции
- 12 января. Постановка задачи поиска медианы. Простые решения этой задачи. Оценка сложности алгоритмов по времени и памяти. О-, o-, Ω-, ω-, Θ-обозначения. Время работы в худшем, лучшем и среднем случаях. Сортировка вставками.
- 19 января. Сортировка слиянием. Оценка времени работы алгоритма при помощи рекуррентного соотношения. Двоичный поиск. Примеры решения рекуррентных соотношений: решение с использованием дерева рекурсии и методом подстановки. Основная теорема.
- 26 января. Быстрая сортировка. Оптимальность сортировки слиянием.
- 2 февраля. Разделяй и властвуй: быстрое возведение в степень по модулю, выбор порядковой статистики за время O(n) — рандомизированный и детерминированный алгоритмы.
- 9 февраля. Структуры данных. Массив с операциями инициализации, чтения и записи, выполняемыми за время O(1). Структура данных для быстрого поиска и вставки на основе нескольких отсортированных массивов. Амортизационный анализ: групповой анализ и банковский метод (на примере двоичного счетчика).
- 16 февраля. Амортизационная стоимость операций в динамическом массиве. Реализация стека при помощи массива; извлечение максимального значения в стеке за константное время.
Домашние задания
Первое домашнее задание
Сортировки — до 12 февраля. Для решения задачи F необязательно использовать именно алгоритм, реализованный в рамках решения задачи E.
Контрольные работы
Тренировочный вариант мартовской контрольной работы