CourseOn
Back

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

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

Computer Science Center

В курсе подробно разобраны базовые алгоритмические методы: жадные алгоритмы, метод «разделяй и властвуй», динамическое программирование. Для всех алгоритмов математически строго доказаны корректность и оценки на время работы. Материал изложен так, чтобы были понятны и сами алгоритмы, и то, как можно было бы догадаться до их основных идей. Помимо теоретических основ, рассказаны тонкости реализации алгоритмов на языках программирования C++ и Python. В частности, рассказано, какие есть общие практики написания кода, позволяющие минимизировать вероятность ошибки, как писать и тестировать код, где стоит использовать стандартные методы, а не изобретать колесо.

Syllabus

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: Расстояние редактирования

key words, tags

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


Course properties

Competition track
Science and engineering
Form of education
Informal
Learning language
Russian
Discipline
Natural sciences, mathematics and statistics
Course authors
Александр Куликов
Author’s characterization
Кандидат физико-математических наук. Научный сотрудник лаборатории математической логики ПОМИ РАН, координатор и преподаватель Computer Science центра и Computer Science клуба при ПОМИ РАН, преподаватель Академического университета. Научные интересы: алгоритмы для NP-трудных задач, схемная сложность.
Organization
Computer Science Center
Organization characterization
Computer Science Center – это совместная инициатива Computer Science клуба при ПОМИ РАН, компании JetBrains и Школы анализа данных. Основная цель Computer Science Center – дать возможность желающим получить востребованные современной наукой и промышленностью знания в дополнение к университетскому образованию. Сайт https://compscicenter.ru/
Knowledge level entrance requirements
Знание одного из распространённых языков программирования (C++, Java, Python, Octave, Haskell) на базовом уровне: циклы, массивы, списки, очереди. Базовые знания математики: доказательство от противного, доказательство по индукции, логарифм, экспонента.
Output knowledge, abilities, skills
Слушатели освоят основные алгоритмические методы: жадные алгоритмы, «разделяй и властвуй», динамическое программирование, а также поупражняются в реализации большинства разобранных в курсе алгоритмов.
Entrance test
Groups formation by readiness level
Teachers presence
Tutors presence
Facilitators presence
Training materials forms
texts, video lecture, synchronous video
Interactivity in training materials
Collaborative learning presence
Discussions, forums presence
Webinars, video conferences presence
meetup presence
LMS integration
Learning Analytics
Certification presence
Certification types
Сертификат Stepic с подписью преподавателя
Course time limits
Duration
7 (weeks)
Learning types (sync/async)
asynchronous
Course modules number
9
Personal learning path possibility, course individualization
Supported browsers
Минимальные версии поддерживаемых браузеров: IE / Edge 10 Firefox 38 Chrome 31 Safari 8 Opera 30 iOS Safari 9 Android Browser 4.4 Chrome for Android 44
Special needs support
Course site
https://stepic.org/course/217

Comments