Алгоритмы и структуры данных на ПМИ (основной поток) — различия между версиями
Материал из Wiki - Факультет компьютерных наук
.obj (обсуждение | вклад) |
.obj (обсуждение | вклад) м |
||
Строка 9: | Строка 9: | ||
# Клейнберг, Тардос. ''Алгоритмы. Разработка и применение'' | # Клейнберг, Тардос. ''Алгоритмы. Разработка и применение'' | ||
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ'' | # Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ'' | ||
− | # Также см. [https:// | + | # Также см. [https://www.dropbox.com/sh/5lxaheg89isd6h9/AACOa50ihgNiu46YqhguwmDBa/algo_16-17_1course_standart.pdf конспекты]. |
== Лекции == | == Лекции == |
Версия 00:20, 6 апреля 2017
Лектор: С. Объедков
Расписание лекций:
понедельник 10:30 – 11:50, ауд. 622
четверг 12:10 – 13:30, ауд. 622
Содержание
Рекомендуемая литература
- Дасгупта, Пападимитриу, Вазирани. Алгоритмы
- Клейнберг, Тардос. Алгоритмы. Разработка и применение
- Кормен, Лейзерсон, Ривест, Штайн. Алгоритмы: построение и анализ
- Также см. конспекты.
Лекции
Третий модуль
- 12 января. Постановка задачи поиска медианы. Простые решения этой задачи. Оценка сложности алгоритмов по времени и памяти. О-, o-, Ω-, ω-, Θ-обозначения. Время работы в худшем, лучшем и среднем случаях. Сортировка вставками.
- 19 января. Сортировка слиянием. Оценка времени работы алгоритма при помощи рекуррентного соотношения. Двоичный поиск. Примеры решения рекуррентных соотношений: решение с использованием дерева рекурсии и методом подстановки. Основная теорема.
- 26 января. Быстрая сортировка. Оптимальность сортировки слиянием.
- 2 февраля. Разделяй и властвуй: быстрое возведение в степень по модулю, выбор порядковой статистики за время O(n) — рандомизированный и детерминированный алгоритмы.
- 9 февраля. Структуры данных. Массив с операциями инициализации, чтения и записи, выполняемыми за время O(1). Структура данных для быстрого поиска и вставки на основе нескольких отсортированных массивов. Амортизационный анализ: групповой анализ и банковский метод (на примере двоичного счетчика).
- 16 февраля. Амортизационная стоимость операций в динамическом массиве. Реализация стека при помощи массива; нахождение максимального значения в стеке за константное время.
- 2 марта. Реализация очереди при помощи связного списка и при помощи массива; нахождение минимального элемента в очереди за константное время. Приоритетная очередь, ее реализация при помощи двоичной кучи. Сортировка кучей.
- 9 марта. Деревья поиска. Алгоритм построения двоичного дерева поиска. Сложность поиска в двоичном дереве поиска. Сортировка при помощи двоичного дерева поиска и ее связь с быстрой сортировкой. Сбалансированные деревья поиска. Определение красно-черного дерева.
- 16 марта. Красно-черные деревья. Удаление узла из двоичного дерева поиска.
- 23 марта. Деревья отрезков. Динамические порядковые статистики.
Четвертый модуль
- 3 апреля. Хеш-таблицы. Методы задания хеш-функций. Разрешение коллизий при помощи цепочек. Открытая адресация.
Домашние задания
Третий модуль
Сортировки — до 12 февраля. Для решения задачи F необязательно использовать именно алгоритм, реализованный в рамках решения задачи E.
Контрольные работы
Тренировочный вариант мартовской контрольной работы
В четвертом модуле контрольная работа пройдет в конце апреля.
Консультации к экзамену 31 марта
Консультации проводят указанные ниже учебные ассистенты. Аудитории будут объявлены позже.
25 марта 14:00, ауд. 205 — Дарья Вальтер — вопросы к консультации можно задать здесь
28 марта 13:40, ауд. 509 — Валерия Бубнова
28 марта 13:40, ауд. 317 — Максим Рябинин — вопросы к консультации можно задать здесь
29 марта 12:10, ауд. 509 — Арсений Турышев — вопросы к консультации можно задать здесь