Основы и методология программирования на ПМИ 2017/2018 (основной поток, 3 модуль) — различия между версиями

Версия 17:28, 6 марта 2018

Основы и методология программирования, основной поток, 2017, 3-й модуль

Материалы первого модуля

Материалы второго модуля

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

Лекции: понедельник 13:40 – 15:00 и четверг 15:10 – 16:30.

Лекции

1. 12 февраля. Зачем изучать алгоритмы? Умножение целых чисел. "Разделяй и властвуй": алгоритм Карацубы.
2. 15 февраля. Сортировка вставками и сортировка слиянием. Рекуррентные соотношения. Асимптотические обозначения.
3. 22 февраля. Решение рекуррентных соотношений. Основная теорема.
4. 26 февраля. Порядковые статистики: детерминированный и рандомизированный алгоритмы.
5. 1 марта. Рандомизированные алгоритмы сортировки: Bogosort и Quicksort. Оценка времени работы рандомизированных алгоритмов.
6. 5 марта. Устойчивость алгоритмов сортировки. Сортировка подсчетом, поразрядная и блочная сортировки.

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

17. Контест №17.1 и Контест №17.2 — дедлайн 27.02.2018 в 00:00:01
18. Контест №18 — дедлайн 11.03.2018 в 23:59:59

Штрафы

Формулы оценок

Накопленная оценка за 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.

Преподаватели и ассистенты