Лекции Технопарка. Курс «Алгоритмы и структуры данных»

Сегодня представляем вашему вниманию один из свежих курсов Технопарка — «Алгоритмы и структуры данных». Он представляет собой изучение базовых алгоритмов и структур данных, необходимых программистам для качественного решения ежедневных задач. В курсе представлены алгоритмы для работы с массивами, сортировки. Рассказывается об элементарных структурах данных: стек, очередь, списки, куча. Также в программу включены различные деревья поиска и хеш-таблицы. Курс дает представление о том, как оценивать эффективность алгоритмов, все алгоритмы курса оцениваются по времени работы и по количеству используемой дополнительной памяти. Вас ждут шесть лекций:

• «Введение. Исполнители. Абстракции интерфейсов. Рекурсия»;
• «Жадные алгоритмы»;
• «Сортировки»;
• «Поиск. Списки»;
• «Деревья»;
• «Хеш-таблицы».

Четыре лекции курса читает Степан Мацкевич, руководитель группы извлечения онтологической информации в компании ABBYY. Он был ведущим программистом при написании серверной части продукта ABBYY InfoExtractor на основе технологии ABBYY Compreno (анализ текстов и перевода).
Еще две лекции ведет Георгий Иванов, разработчик Поиска Mail.Ru, занимающийся задачами обработки поисковых запросов.

Лекция 1. «Введение. Массивы»

Введение в курс: дается определение алгоритма, структуры данных, эффективности алгоритма. Алгоритмы вычисления n-ого числа Фибоначчи. Решается задача проверки, является ли заданное натуральное число n простым. Рассказывается о быстром возведении числа в целую степень.
Рассматриваются массивы, однопроходные алгоритмы, линейный и бинарный поиск.
Часть лекции посвящена абстрактным типам данных, структуре данных «Динамический массив». В заключении речь пойдет об амортизированном времени добавления элемента.

Лекция 2. «Списки, стек, очередь, дек. Динамическое программирование и жадные алгоритмы»

Вторая лекция посвящена основным структурам данных: однонаправленным и двунаправленным спискам, абстрактным типам данных (стек, очередь, дек) и способам их реализации. Будут затронуты темы динамического программирования и жадных алгоритмов (размен монет, покрытие отрезками, задача о рюкзаке).

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

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

Лекция 4. «Сортировки (часть 2). Порядковые статистики».

Вторая часть лекции про сортировки от Георгия Иванова. Быстрая сортировка, сортировка Хоара, сортировка подсчетом. Кроме того, рассматривается алгоритм поиска медианы. Дается ответ на вопрос, как в реальных условиях ускоряют алгоритм быстрой сортировки. Приводится таблица сравнения сортировок. Георгий завершает лекцию рассказом про алгоритмы разрядной сортировки.

Лекция 5. «Хеш-таблицы и код Хаффмана»

Дается объяснение, что такое хеш-функции, что такое хеш-таблица и как ее строить. Как разрешать коллизии, возникающие при использовании хеш-функций, и каким методом (цепочками или открытой адресацией, в которой используется двойное хеширование). В конце рассматриваются динамическая хеш-таблица и таблица сравнения методов разрешения коллизий.

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

Последняя лекция по алгоритмам посвящена сразу нескольким разным видам деревьев: двоичным деревьям поиска (для создания ассоциативного массива) и проблемам их балансировки, декартовым деревьям, АВЛ-деревьям. Степан Мацкевич заканчивает лекцию на примерах реализации типа данных «Ассоциативный массив» с помощью деревьев и хеш-таблиц со сравнением преимуществ каждого варианта.
Плейлист всех лекций находится по ссылке. Напомним, что актуальные лекции и мастер-классы о программировании от наших IT-специалистов в проектах Технопарк, Техносфера и Технотрек по-прежнему публикуются на канале Технострим.