Алгоритмы и структуры данных на ПМИ (основной поток) — различия между версиями
Материал из Wiki - Факультет компьютерных наук
.obj (обсуждение | вклад) (→Лекции) |
.obj (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
* '''19 января.''' Сортировка слиянием. Оценка времени работы алгоритма при помощи рекуррентного соотношения. Двоичный поиск. Примеры решения рекуррентных соотношений: решение с использованием дерева рекурсии и методом подстановки. Основная теорема. | * '''19 января.''' Сортировка слиянием. Оценка времени работы алгоритма при помощи рекуррентного соотношения. Двоичный поиск. Примеры решения рекуррентных соотношений: решение с использованием дерева рекурсии и методом подстановки. Основная теорема. | ||
* '''26 января.''' Быстрая сортировка. Оптимальность сортировки слиянием. | * '''26 января.''' Быстрая сортировка. Оптимальность сортировки слиянием. | ||
| − | * ''' | + | * '''2 февраля.''' Разделяй и властвуй: быстрое возведение в степень по модулю, выбор порядковой статистики за время ''O''(''n'') — рандомизированный и детерминированный алгоритмы. |
| + | * '''9 февраля.''' Структуры данных. Массив с операциями инициализации, чтения и записи, выполняемыми за время ''O''(1). 2. Амортизационный анализ: групповой анализ и банковский метод (на примере двоичного счетчика). | ||
== Домашние задания == | == Домашние задания == | ||
Версия 14:17, 9 февраля 2017
Лектор: С. Объедков
Расписание лекций:
четверг 12:10 – 13:30, ауд. 622
Лекции
- 12 января. Постановка задачи поиска медианы. Простые решения этой задачи. Оценка сложности алгоритмов по времени и памяти. О-, o-, Ω-, ω-, Θ-обозначения. Время работы в худшем, лучшем и среднем случаях. Сортировка вставками.
- 19 января. Сортировка слиянием. Оценка времени работы алгоритма при помощи рекуррентного соотношения. Двоичный поиск. Примеры решения рекуррентных соотношений: решение с использованием дерева рекурсии и методом подстановки. Основная теорема.
- 26 января. Быстрая сортировка. Оптимальность сортировки слиянием.
- 2 февраля. Разделяй и властвуй: быстрое возведение в степень по модулю, выбор порядковой статистики за время O(n) — рандомизированный и детерминированный алгоритмы.
- 9 февраля. Структуры данных. Массив с операциями инициализации, чтения и записи, выполняемыми за время O(1). 2. Амортизационный анализ: групповой анализ и банковский метод (на примере двоичного счетчика).
Домашние задания
Первое домашнее задание
Сортировки — до 12 февраля. Для решения задачи F необязательно использовать именно алгоритм, реализованный в рамках решения задачи E.
