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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Лекции)
Строка 9: Строка 9:
 
* '''19 января.''' Сортировка слиянием. Оценка времени работы алгоритма при помощи рекуррентного соотношения. Двоичный поиск. Примеры решения рекуррентных соотношений: решение с использованием дерева рекурсии и методом подстановки. Основная теорема.
 
* '''19 января.''' Сортировка слиянием. Оценка времени работы алгоритма при помощи рекуррентного соотношения. Двоичный поиск. Примеры решения рекуррентных соотношений: решение с использованием дерева рекурсии и методом подстановки. Основная теорема.
 
* '''26 января.''' Быстрая сортировка. Оптимальность сортировки слиянием.
 
* '''26 января.''' Быстрая сортировка. Оптимальность сортировки слиянием.
 
+
* '''3 февраля.''' Разделяй и властвуй: быстрое возведение в степень по модулю, выбор порядковой статистики за время ''O''(''n'') — рандомизированный и детерминированный алгоритмы.
  
 
== Домашние задания ==
 
== Домашние задания ==

Версия 16:58, 3 февраля 2017

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

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

Лекции

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

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

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

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

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

группа 167-1