Алгоритмы и структуры данных 2016: различия между версиями
Перейти к навигации
Перейти к поиску
Нет описания правки |
|||
| Строка 4: | Строка 4: | ||
'''16 января:''' ''О''-, ''o''-, Ω-, ω-, Θ-обозначения. Быстрая сортировка, время работы в худшем, лучшем и среднем случаях. Оптимальность сортировки слиянием. Сортировка при помощи двоичного дерева поиска и ее связь с быстрой сортировкой. | '''16 января:''' ''О''-, ''o''-, Ω-, ω-, Θ-обозначения. Быстрая сортировка, время работы в худшем, лучшем и среднем случаях. Оптимальность сортировки слиянием. Сортировка при помощи двоичного дерева поиска и ее связь с быстрой сортировкой. | ||
'''20 января:''' [https://www.dropbox.com/s/6a0r410zjm9qwe7/algo-3-recurrences.pdf?dl=0 | '''20 января:''' Примеры решения рекуррентных соотношений. Решение с использованием дерева рекурсии. Решение методом подстановки. Формулировка и интуитивное объяснение основной теоремы. [https://www.dropbox.com/s/6a0r410zjm9qwe7/algo-3-recurrences.pdf?dl=0 (Конспект.)] | ||
== Семинары == | == Семинары == | ||
Версия от 21:11, 20 января 2015
Лекции
13 января: Сортировка вставкой и слиянием. Использование инварианта цикла при доказательстве корректности сортировки вставкой. Θ- и O-обозначения. Оценка сложности алгоритмов. Рекуррентные соотношения.
16 января: О-, o-, Ω-, ω-, Θ-обозначения. Быстрая сортировка, время работы в худшем, лучшем и среднем случаях. Оптимальность сортировки слиянием. Сортировка при помощи двоичного дерева поиска и ее связь с быстрой сортировкой.
20 января: Примеры решения рекуррентных соотношений. Решение с использованием дерева рекурсии. Решение методом подстановки. Формулировка и интуитивное объяснение основной теоремы. (Конспект.)
Семинары
Подгруппа 101-1.
Подгруппа 105-1.
Подгруппа 106-1.