Цель этого курса — познакомить слушателей с основными алгоритмами, применяемыми для разработки программного обеспечения. Вы научитесь выбирать подходящие структуры данных и алгоритмы для реализации возникающих задач, и узнаете, как использовать языки С/С++ для реализации алгоритмов.

Курс ведет Сергей Бабичев, доцент кафедр информатики и вычислительной математики, а также теоретической и прикладной информатики в МФТИ. Под катом вас ждет восемь лекций:

• Лекция 1. «Введение. Исполнители. Абстракции интерфейсов. Рекурсия»
• Лекция 2. «Жадные алгоритмы»
• Лекция 3. «Сортировки»
• Лекция 4. «Поиск. Списки»
• Лекция 5. «Деревья»
• Лекция 6. «Хеш-таблицы»
• Лекция 7. «Динамическое программирование»
• Лекция 8. «Алгоритмы на графах»

Лекция 1. «Введение. Исполнители. Абстракции интерфейсов. Рекурсия»



На первой лекции вспомним основы алгоритмов и посмотрим, как их можно использовать на практике. Поговорим о свойствах алгоритмов, исполнителях, нотациях, параметрах и классах сложности. Разберем неполиномиальную задачу (сколько поместится предметов в рюкзак). Кроме того, поговорим об абстракциях (массив, стек, множество) и рекурсии (основная теорема).

Лекция 2. «Жадные алгоритмы»



Лекция посвящена разным алгоритмам нахождения оптимальных (или близких к оптимальным) решений для самых разнообразных задач. Посмотрим на приближенное решение задачи нахождения оптимальных значений. Разберем абстракцию строки символов, префиксную функцию, динамические структуры данных.

Лекция 3. «Сортировки»



Сведения про разные сортировки и около сортировочную деятельность. Будут рассмотрены несколько технологий сортировок: сравнением, быстрая, с использованием свойств элементов, внешняя и другие. Также дается сравнение сортировок, когда и какой метод нужно применять.

Лекция 4. «Поиск. Списки»



Занимаемся поиском, работой с динамическими структурами данных, работой со списками и деревьями. Проводим сравнительный анализ методов поиска: простой последовательный поиск, распределяющий поиск, поиск с сужением зоны. Кроме того, поговорим о структуре данных «список», который тоже используется для поиска, и структуре данных «дерево», который считается обобщением «списка».

Лекция 5. «Деревья»



Продолжение темы «деревьев», затронутой еще на второй лекции. Рассматриваются две абстракции (множество и отображение), от них перейдем к сбалансированным деревьям поиска, красно-черным деревьям (двоичное дерево поиска), после чего коснемся интерфейса абстракции приоритетной очереди (основанной на деревьях).

Лекция 6. «Хеш-таблицы»



Как производить внешний поиск (на внешних носителях) с использованием B-деревьев, что такое обобщенный быстрый поиск, хеш-функции, разные виды хеш-таблиц. Также вы узнаете об еще одном виде поиска, который хорошо подходит к параллельным алгоритмам — списки с пропусками. Напоследок рассматривается пример решения задачи, которая требует нескольких разных структур данных.

Лекция 7. «Динамическое программирование»



Тут мы поговорим о способах решения больших задач, которые сами по себе делятся на подзадачи. Узнаете, как с помощью структур данных можно решать своеобразные задачи (о количестве маршрутов, о возрастающей подпоследовательности наибольшей длины), метод решения которых мы попробуем обобщить. Пойдет разбор этапов решения задачи методом динамического программирования.

Лекция 8. «Алгоритмы на графах»



Последняя лекция, в которой будут разные виды представления граф, понятие релаксации, несколько режимов поиска (BFS, DFS), топологическая сортировка, поиск остовных деревьев в графе, алгоритм Дейкстры (его связь с жадными алгоритмами) и алгоритм Флойда-Уоршалла (и его связь с динамическим программированием).

По завершению курса вы узнаете основные понятия: исполнитель, абстракция, объекты, методы, итерация, рекурсия, жадные алгоритмы, динамическое программирование, сортировка, поиск, графы. Получите навык анализировать основные свойства алгоритмов, научитесь выбирать необходимые структуры данных для решения задач и обосновывать свой выбор. Сможете эффективно реализовывать алгоритмы на языках С и С++.

Плейлист всех лекций находится по ссылке. Напомним, что актуальные лекции и мастер-классы о программировании от наших IT-специалистов в проектах Технопарк, Техносфера и Технотрек по-прежнему публикуются на канале Технострим.