Просмотр исходного текста страницы Алгоритмы и структуры данных 2016

== Лекции ==
'''13 января:''' Сортировка вставкой и слиянием. Использование инварианта цикла при доказательстве корректности сортировки вставкой.  Θ- и ''O''-обозначения. Оценка сложности алгоритмов. Рекуррентные соотношения.

'''16 января:''' ''О''-, ''o''-, Ω-, ω-, Θ-обозначения. Быстрая сортировка, время работы в худшем, лучшем и среднем случаях. Оптимальность сортировки слиянием. Сортировка при помощи двоичного дерева поиска и ее связь с быстрой сортировкой.

'''20 января:''' Примеры решения рекуррентных соотношений: решение с использованием дерева рекурсии и методом подстановки. Формулировка и интуитивное объяснение основной теоремы. [https://www.dropbox.com/s/6a0r410zjm9qwe7/algo-3-recurrences.pdf?dl=0 (Конспект.)]

'''23 января:''' Выбор порядковой статистики за время ''O''(''n''): [http://en.wikipedia.org/wiki/Quickselect рандомизированный] и [http://en.wikipedia.org/wiki/Median_of_medians детерминированный] алгоритмы.

'''27 января:''' Быстрое возведение в степень по модулю. Алгоритм Карацубы для умножения целых чисел. Алгоритм Штрассена для умножения матриц.

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

=== Задание 1 ===

Необходимо сдать все 6 задач в данном [https://official.contest.yandex.ru/contest/1002 контесте]. На выполнение задания дается 2 недели (см. точное время окончания в контесте). Условия ревью определяют семинаристы.

== Семинары ==
[[Алгоритмы и структуры данных. Подгруппа 101-1|Подгруппа 101-1.]]<br>
[[Алгоритмы и структуры данных. Подгруппы 102-1, 102-2, 107-2|Подгруппа 102-1.]]<br>
[[Алгоритмы и структуры данных. Подгруппы 102-1, 102-2, 107-2|Подгруппа 102-2.]]<br>
[[Алгоритмы и структуры данных. Подгруппа 105-1|Подгруппа 105-1.]]<br>
[[Алгоритмы и структуры данных. Подгруппа 106-1|Подгруппа 106-1.]]<br>
[[Алгоритмы и структуры данных. Подгруппа 107-1|Подгруппа 107-1.]]<br>
[[Алгоритмы и структуры данных. Подгруппы 102-1, 102-2, 107-2|Подгруппа 107-2.]]<br>

== Рекомендуемая литература ==
# [http://e-maxx.ru/bookz/files/cormen.pdf Кормен, Лейзерсон, Ривест, Штайн. Алгоритмы: построение и анализ]
# [https://dl.dropboxusercontent.com/u/829163/draft.pdf Дасгупта, Пападимитриу, Вазирани. Алгоритмы] ([http://beust.com/algorithms.pdf оригинал] | [http://biblio.mccme.ru/node/5066/shop купить])

== Полезные ссылки ==
# [[Reviewboard|Инструкция по использованию Review Board.]]