Алгоритмы: теория и практика. Методы

Александр Куликов

Computer Science Center

В курсе подробно разобраны базовые алгоритмические методы: жадные алгоритмы, метод «разделяй и властвуй», динамическое программирование. Для всех алгоритмов математически строго доказаны корректность и оценки на время работы. Материал изложен так, чтобы были понятны и сами алгоритмы, и то, как можно было бы догадаться до их основных идей. Помимо теоретических основ, рассказаны тонкости реализации алгоритмов на языках программирования 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: Расстояние редактирования

Ключевые слова

Алгоритмы, жадные алгоритмы


Характеристики курса

Направление в конкурсе
Естественные и технические науки
Вид образования
Внеформальное
Язык обучения
Русский
Дисциплина
Естественные науки, математика и статистика
Авторы курса
Александр Куликов
Реквизиты авторов
Кандидат физико-математических наук. Научный сотрудник лаборатории математической логики ПОМИ РАН, координатор и преподаватель Computer Science центра и Computer Science клуба при ПОМИ РАН, преподаватель Академического университета. Научные интересы: алгоритмы для NP-трудных задач, схемная сложность.
Организация
Computer Science Center
Реквизиты организации
Computer Science Center – это совместная инициатива Computer Science клуба при ПОМИ РАН, компании JetBrains и Школы анализа данных. Основная цель Computer Science Center – дать возможность желающим получить востребованные современной наукой и промышленностью знания в дополнение к университетскому образованию. Сайт https://compscicenter.ru/
Входные требования по уровню знаний
Знание одного из распространённых языков программирования (C++, Java, Python, Octave, Haskell) на базовом уровне: циклы, массивы, списки, очереди. Базовые знания математики: доказательство от противного, доказательство по индукции, логарифм, экспонента.
Выходные знания, умения, навыки
Слушатели освоят основные алгоритмические методы: жадные алгоритмы, «разделяй и властвуй», динамическое программирование, а также поупражняются в реализации большинства разобранных в курсе алгоритмов.
Входной тест
Формирование групп по уровню подготовленности
Присутствие преподавателей
Присутствие тьюторов
Присутствие фасилитаторов
Форма представления учебных материалов
тексты, видеолекции, онлайн общение с преподавателем
Наличие обратной связи в материалах
Наличие совместного обучения
Наличие форумов, дискуссий
Наличие вебинаров, видеоконференций
Наличие неформального общения, meetup
Интеграция с LMS
Учебная аналитика
Наличие сертификации
Виды сертификации
Сертификат Stepic с подписью преподавателя
Наличие временных границ
Продолжительность
7 (недели)
Тип занятий (синхронность)
асинхронные
Количество модулей в курсе
9
Возможность формирования собственной траектории, индивидуализации на курсе
Поддерживаемые браузеры
Минимальные версии поддерживаемых браузеров: IE / Edge 10 Firefox 38 Chrome 31 Safari 8 Opera 30 iOS Safari 9 Android Browser 4.4 Chrome for Android 44
Поддержка лиц с ограниченными возможностями
Сайт курса

Комментарии