Основы и методология программирования на ПМИ 2017/2018 (основной поток, 3 модуль)
Содержание
Основы и методология программирования, основной поток, 2018, 3-й модуль
Лектор: С.А. Объедков
Лекции: понедельник 13:40 – 15:00 и четверг 15:10 – 16:30.
Объявление
Те, кто пропустил по уважительной причине контрольную работу в конце февраля – начале марта, могут написать ее 22 марта в 12:10 – 13:30 в ауд. 311.
Лекции
- 12 февраля. Зачем изучать алгоритмы? Умножение целых чисел. "Разделяй и властвуй": алгоритм Карацубы.
- 15 февраля. Сортировка вставками и сортировка слиянием. Рекуррентные соотношения. Асимптотические обозначения.
- 22 февраля. Решение рекуррентных соотношений. Основная теорема.
- 26 февраля. Порядковые статистики: детерминированный и рандомизированный алгоритмы.
- 1 марта. Рандомизированные алгоритмы сортировки: Bogosort и Quicksort. Оценка времени работы рандомизированных алгоритмов.
- 5 марта. Устойчивость алгоритмов сортировки. Сортировка подсчетом, поразрядная и блочная сортировки.
- 12 марта. Нижняя оценка для сортировки сравнением в худшем случае. Двоичная куча: Heapsort и приоритетная очередь. K-ичная куча.
- 15 марта. Двоичные деревья поиска. Алгоритм построения двоичного дерева поиска. Сортировка при помощи двоичного дерева поиска и ее связь с быстрой сортировкой. Сложность вставки, удаления и поиска в двоичном дереве поиска. Сбалансированные деревья поиска. Красно-черные деревья: определение, доказательство сбалансированности.
- 19 марта. Вставка элемента в красно-черное дерево. Динамические порядковые статистики. Деревья отрезков.
- 23 марта. Хеш-таблицы. Разрешение коллизий при помощи цепочек. Открытая адресация. Универсальное хеширование.
Домашние задания
17. Контест №17.1 и Контест №17.2 — дедлайн 27.02.2018 в 00:00:01
18. Контест №18 — дедлайн 11.03.2018 в 23:59:59
19. Контест №19 — дедлайн 22.03.2018 в 23:59:59
Штрафы
| output-limit-exceeded | 1 |
| time-limit-exceeded | 2 |
| idleness-limit-exceeded | 2 |
| compilation-error | 0 |
| presentation-error | 1 |
| precompile-check-failed | 0 |
| runtime-error | 2 |
| memory-limit-exceeded | 2 |
| wrong-answer | 1 |
Экзамен
Экзамен пройдет 26 марта в 10:30 – 13:30 в ауд. 402 (группы 172, 174, 175) и ауд. 622 (группы 176, 177 и 178). Экзамен — письменный. С собой на экзамен можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается.
Показ работ — 29 марта в 10:30 – 11:50 в ауд. 317.
Формулы оценок
Накопленная оценка за II-III модули = 0,4 * домашние работы + 0,6 * контрольные контесты
Итоговая оценка за II-III модули = 0,4 * экзамен + 0,6 * накопленная оценка
Требования к оформлению кода программ
Мы используем cpplint для проверки стиля. Вот список требований.
Флаги для cpplint: --filter=-,+build/include,-build/include_order,+build/include_what_you_use,+build/storage_class,+readability/alt_tokens,+readability/braces,+readability/casting,+readability/inheritance,+runtime/casting,-runtime/explicit,+whitespace/blank_line,+whitespace/braces,+whitespace/comma,+whitespace/comments,+whitespace/empty_conditional_body,+whitespace/empty_loop_body,+whitespace/end_of_line,+whitespace/ending_newline,+whitespace/forcolon,+whitespace/indent,+whitespace/line_length,+whitespace/newline,+whitespace/operators,+whitespace/parens,+whitespace/semicolon,+whitespace/tab --linelength=100
Литература
Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. — М.: МЦНМО, 2014.
Клейнберг Дж., Тардос Е. Алгоритмы: разработка и применение. — СПб.: Питер, 2016.
Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. — 3-е издание — М.: Вильямс, 2013.
Преподаватели и ассистенты
| Подгруппа | Преподаватель | Учебные ассистенты |
|---|---|---|
| 172-1 | Сергей Абрамов | Игорь Минеев |
| 172-2 | Станислав Протасов | Игорь Минеев |
| 174-1 | Вильям Саакян | Ирина Понамарева |
| 174-2 | София Техажева | Ирина Понамарева |
| 175-1 | Сергей Объедков | Сергей Брагин |
| 175-2 | Алексей Умнов | Сергей Брагин |
| 176-1 | Иван Фефер | Вячеслав Пономарев |
| 176-2 | Михаил Густокашин | Вячеслав Пономарев, Валерия Стоева |
| 177-1 | Ярослав Кищенко | Александр Газарян |
| 177-2 | Ольга Абакумова | Александр Газарян |
| 178-1 | Мирон Левков | Анастасия Родигина |
| 178-2 | Федор Строк | Владимир Сухомлин |
