Алгоритмы и структуры данных на ПМИ (основной поток) — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Консультации к экзамену 31 марта)
(Консультации к экзамену 31 марта)
Строка 36: Строка 36:
 
28 марта 13:40, ауд. 509 — [mailto:lera-bubnova@yandex.ru Валерия Бубнова]
 
28 марта 13:40, ауд. 509 — [mailto:lera-bubnova@yandex.ru Валерия Бубнова]
  
28 марта 13:40, ауд. 317 — Максим Рябинин
+
28 марта 13:40, ауд. 317 — [mailto:mryabinin0@gmail.com Максим Рябинин] — вопросы к консультации можно задать [https://docs.google.com/forms/d/e/1FAIpQLSe01c3Bfdz3bQ1eRSlBgGwJ1NIlEagYHRfOuaTHqfIdxqJMkA/viewform здесь]
  
 
29 марта 12:10, ауд. 509 — [mailto:arture226@gmail.com Арсений Турышев] — вопросы к консультации можно задать [https://docs.google.com/forms/d/e/1FAIpQLScverCV5aXdKj_59mqs2KBxW6qx699Escu8bsYvR70OfVhztg/viewform здесь]
 
29 марта 12:10, ауд. 509 — [mailto:arture226@gmail.com Арсений Турышев] — вопросы к консультации можно задать [https://docs.google.com/forms/d/e/1FAIpQLScverCV5aXdKj_59mqs2KBxW6qx699Escu8bsYvR70OfVhztg/viewform здесь]

Версия 18:26, 27 марта 2017

Лектор: С. Объедков

Расписание лекций:
четверг 12:10 – 13:30, ауд. 622

Лекции

  • 12 января. Постановка задачи поиска медианы. Простые решения этой задачи. Оценка сложности алгоритмов по времени и памяти. О-, o-, Ω-, ω-, Θ-обозначения. Время работы в худшем, лучшем и среднем случаях. Сортировка вставками.
  • 19 января. Сортировка слиянием. Оценка времени работы алгоритма при помощи рекуррентного соотношения. Двоичный поиск. Примеры решения рекуррентных соотношений: решение с использованием дерева рекурсии и методом подстановки. Основная теорема.
  • 26 января. Быстрая сортировка. Оптимальность сортировки слиянием.
  • 2 февраля. Разделяй и властвуй: быстрое возведение в степень по модулю, выбор порядковой статистики за время O(n) — рандомизированный и детерминированный алгоритмы.
  • 9 февраля. Структуры данных. Массив с операциями инициализации, чтения и записи, выполняемыми за время O(1). Структура данных для быстрого поиска и вставки на основе нескольких отсортированных массивов. Амортизационный анализ: групповой анализ и банковский метод (на примере двоичного счетчика).
  • 16 февраля. Амортизационная стоимость операций в динамическом массиве. Реализация стека при помощи массива; нахождение максимального значения в стеке за константное время.
  • 2 марта. Реализация очереди при помощи связного списка и при помощи массива; нахождение минимального элемента в очереди за константное время. Приоритетная очередь, ее реализация при помощи двоичной кучи. Сортировка кучей.
  • 9 марта. Деревья поиска. Алгоритм построения двоичного дерева поиска. Сложность поиска в двоичном дереве поиска. Сортировка при помощи двоичного дерева поиска и ее связь с быстрой сортировкой. Сбалансированные деревья поиска. Определение красно-черного дерева.
  • 16 марта. Красно-черные деревья. Удаление узла из двоичного дерева поиска.
  • 23 марта. Деревья отрезков. Динамические порядковые статистики.

Также см. конспекты.

Домашние задания

Первое домашнее задание

Сортировки — до 12 февраля. Для решения задачи F необязательно использовать именно алгоритм, реализованный в рамках решения задачи E.

Контрольные работы

Тренировочный вариант мартовской контрольной работы

Консультации к экзамену 31 марта

Консультации проводят указанные ниже учебные ассистенты. Аудитории будут объявлены позже.

25 марта 14:00, ауд. 205 — Дарья Вальтер — вопросы к консультации можно задать здесь

28 марта 13:40, ауд. 509 — Валерия Бубнова

28 марта 13:40, ауд. 317 — Максим Рябинин — вопросы к консультации можно задать здесь

29 марта 12:10, ауд. 509 — Арсений Турышев — вопросы к консультации можно задать здесь

Страницы семинаров

группа 167-1