В курсе подробно разобраны базовые алгоритмические методы: жадные алгоритмы, метод «разделяй и властвуй», динамическое программирование. Для всех алгоритмов математически строго доказаны корректность и оценки на время работы. Материал изложен так, чтобы были понятны и сами алгоритмы, и то, как можно было бы догадаться до их основных идей. Помимо теоретических основ, рассказаны тонкости реализации алгоритмов на языках программирования C++ и Python. В частности, рассказано, какие есть общие практики написания кода, позволяющие минимизировать вероятность ошибки, как писать и тестировать код, где стоит использовать стандартные методы, а не изобретать колесо.
1. Обзор
2. Введение: теория и задачи
2.1 Введение
2.2 Числа Фибоначчи
2.3 Наибольший общий делитель
2.4 О-символика
3. Жадные алгоритмы: теория и задачи
3.1 Введение
3.2 Коды Хаффмана
3.3 Очереди с приоритетами
4.Введение: практика и разбор задач
4.1 Практика на С++: Введение
4.2 Практика на С++: Числа Фибоначчи
4.3 Практика на С++: Наибольший общий делитель
4.4 Практика на Python: Введение
4.2 Практика на Python: Числа Фибоначчи
4.3 Практика на Python: Наибольший общий делитель
5. «Разделяй и властвуй»: теория и задачи
5.1 Двоичный поиск
5.2 Умножение чисел
5.3 Умножение матриц
5.4 Сортировка слиянием
5.5 Быстрая сортировка
5.6 Порядковые статистики
5.7 Сортировка кучей
5.8 Сортировки, основанные не на сравнениях
5.9 Рекуррентные соотношения
6. Жадные алгоритмы: практика и разбор задач
6.1 Практика на С++: Непрерывный рюкзак
6.2 Практика на С++: Коды Хаффмана
6.3 Практика на Python: Непрерывный рюкзак
6.4 Практика на Python: Коды Хаффмана
7. «Разделяй и властвуй»: практика и разбор задач
7.1 Практика на С++: Сортировки
7.2 Практика на Python: Сортировки
8. Динамическое программирование: теория и задачи
8.1 Введение
8.2 Наибольшая возрастающая подпоследовательность
8.3 Расстояние редактирования
8.4 Рюкзак
8.5 Перемножение последовательности матриц
8.6 Независимые множества во взвешенных деревьях
8.7 Обзор
9.Динамическое программирование: практика и разбор задач
9.1 Практика на С++: Расстояние редактирования
9.2 Практика на Python: Расстояние редактирования
Алгоритмы, жадные алгоритмы
Comments