Алгоритмы и структуры данных 2018/2019 — различия между версиями
.obj (обсуждение | вклад) (→Домашние задания) |
.obj (обсуждение | вклад) (→Лекции) |
||
| Строка 14: | Строка 14: | ||
# '''7 ноября.''' Решение рекуррентных соотношений методом подстановки. Линейный алгоритм поиска k-ой порядковой статистики. | # '''7 ноября.''' Решение рекуррентных соотношений методом подстановки. Линейный алгоритм поиска k-ой порядковой статистики. | ||
# '''12 ноября.''' Нижние оценки для сортировки сравнениями. Сортировка подсчетом, блочная сортировка, поразрядная сортировка. | # '''12 ноября.''' Нижние оценки для сортировки сравнениями. Сортировка подсчетом, блочная сортировка, поразрядная сортировка. | ||
| + | # '''14 ноября.''' Рандомизированные алгоритмы. Лас-Вегас и Монте-Карло. Краткое введение в теорию вероятностей: вероятностные пространства, события, случайные переменные, математическое ожидание и его линейность, геометрические случайные переменные. Алгоритмы Bogosort и Quicksort. | ||
==Преподаватели и ассистенты== | ==Преподаватели и ассистенты== | ||
Версия 14:00, 15 ноября 2018
Лектор: С.А. Объедков
Содержание
Второй модуль
Лекции
понедельник 10:30 – 11:50, ауд. 622
среда 15:10 – 16:30, ауд. 622
- 29 октября. Задача сортировки. Сортировка вставками: анализ корректности с использованием инварианта цикла и времени работы. Асимптотические обозначения. Циклическая сортировка.
- 31 октября. Стратегия "Разделяй и властвуй". Сортировка слиянием. Доказательство корректности рекурсивных алгоритмов по индукции. Оценка времени работы рекурсивных алгоритмов при помощи рекуррентных соотношений: дерево рекурсии, итерационный метод, основная теорема.
- 7 ноября. Решение рекуррентных соотношений методом подстановки. Линейный алгоритм поиска k-ой порядковой статистики.
- 12 ноября. Нижние оценки для сортировки сравнениями. Сортировка подсчетом, блочная сортировка, поразрядная сортировка.
- 14 ноября. Рандомизированные алгоритмы. Лас-Вегас и Монте-Карло. Краткое введение в теорию вероятностей: вероятностные пространства, события, случайные переменные, математическое ожидание и его линейность, геометрические случайные переменные. Алгоритмы Bogosort и Quicksort.
Преподаватели и ассистенты
| Подгруппа | Преподаватель | Учебные ассистенты | Консультация |
|---|---|---|---|
| 182-1 | София Техажева | Александра Латышева | вт 10:30 – 11:50 |
| 182-2 | Сергей Брагин | Александра Латышева | вт 10:30 – 11:50 |
| 184-1 | Валерий Харитонов | Илья Погодаев | |
| 184-2 | Екатерина Гольцова | Илья Погодаев | |
| 185-1 | Илья Самоненко, (сайт для семинаров) |
Антон Родионов | |
| 185-2 | Сергей Объедков | Антон Родионов | |
| 186-1 | Антон Филиппов | Алия Хасанова | пн 13:40 – 15:00 |
| 186-2 | Святослав Фельдшеров | Алия Хасанова | пн 13:40 – 15:00 |
| 187-1 | Вильям Саакян | Андрей Чулков | |
| 187-2 | Михаил Густокашин | Андрей Чулков | |
| 188-1 | Владислав Вершинин | Агзамходжа Турсунходжаев | |
| 188-2 | Федор Строк | Агзамходжа Турсунходжаев | |
| 189-1 | Дмитрий Светличный | Алия Хасанова | пн 13:40 – 15:00 |
| 189-2 | Ярослав Кищенко | Андрей Чулков |
Домашние задания
Простые сортировки, бинарный поиск — с 29 октября по 4 ноября (со штрафом 50% — с 5 по 11 ноября).
Рекурсия, сортировка слиянием — с 5 по 13 ноября (со штрафом 50% — с 14 по 18 ноября).
Задачи на асимптотику и рекуррентные соотношения — с 7 по 20 ноября. UPDATE: Задание в пункте 4 несколько упрощено.
Сортировка подсчетом, поразрядная и др. — с 12 по 18 ноября (со штрафом 50% — с 19 по 25 ноября).
Литература
Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. — М.: МЦНМО, 2014.
Клейнберг Дж., Тардос Е. Алгоритмы: разработка и применение. — СПб.: Питер, 2016.
Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. — 3-е издание — М.: Вильямс, 2013.
Студенческие конспекты: 2015 г., 2016 г., 2017 г.
Оценки
Второй модуль
Текущая оценка: контрольная работа — 40%, домашние задания — 60%.
Промежуточная оценка: экзамен — 40%, текущая оценка — 60%.
Четвертый модуль
Накопленная оценка: контрольная работа — 50%, домашние задания — 50%.
Итог
Завершающая накопленная оценка: среднее промежуточной оценки за второй модуль и накопленной оценки за четвертый модуль.
Итоговая оценка: экзамен — 25%, завершающая накопленная оценка — 75%.
