- PVSM.RU - https://www.pvsm.ru -
Сегодня представляем вашему вниманию один из свежих курсов Технопарка — «Алгоритмы и структуры данных». Он представляет собой изучение базовых алгоритмов и структур данных, необходимых программистам для качественного решения ежедневных задач. В курсе представлены алгоритмы для работы с массивами, сортировки. Рассказывается об элементарных структурах данных: стек, очередь, списки, куча. Также в программу включены различные деревья поиска и хеш-таблицы. Курс дает представление о том, как оценивать эффективность алгоритмов, все алгоритмы курса оцениваются по времени работы и по количеству используемой дополнительной памяти. Вас ждут шесть лекций:
Четыре лекции курса читает Степан Мацкевич, руководитель группы извлечения онтологической информации в компании ABBYY. Он был ведущим программистом при написании серверной части продукта ABBYY InfoExtractor на основе технологии ABBYY Compreno (анализ текстов и перевода).
Еще две лекции ведет Георгий Иванов, разработчик Поиска Mail.Ru, занимающийся задачами обработки поисковых запросов.
Введение в курс: дается определение алгоритма, структуры данных, эффективности алгоритма. Алгоритмы вычисления n-ого числа Фибоначчи. Решается задача проверки, является ли заданное натуральное число n простым. Рассказывается о быстром возведении числа в целую степень.
Рассматриваются массивы, однопроходные алгоритмы, линейный и бинарный поиск.
Часть лекции посвящена абстрактным типам данных, структуре данных «Динамический массив». В заключении речь пойдет об амортизированном времени добавления элемента.
Вторая лекция посвящена основным структурам данных: однонаправленным и двунаправленным спискам, абстрактным типам данных (стек, очередь, дек) и способам их реализации. Будут затронуты темы динамического программирования и жадных алгоритмов (размен монет, покрытие отрезками, задача о рюкзаке).
Георгий Иванов читает лекцию про сортировки. Речь идет о разных простых типах сортировок (выбором, вставками, пузырьком и пирамидальной), методах их улучшения, оценке качества. Вторая половина этой лекции посвящена сортировке слиянием и быстрой сортировке, порядковой статистике, сортировкам без сравнений.
Вторая часть лекции про сортировки от Георгия Иванова. Быстрая сортировка, сортировка Хоара, сортировка подсчетом. Кроме того, рассматривается алгоритм поиска медианы. Дается ответ на вопрос, как в реальных условиях ускоряют алгоритм быстрой сортировки. Приводится таблица сравнения сортировок. Георгий завершает лекцию рассказом про алгоритмы разрядной сортировки.
Дается объяснение, что такое хеш-функции, что такое хеш-таблица и как ее строить. Как разрешать коллизии, возникающие при использовании хеш-функций, и каким методом (цепочками или открытой адресацией, в которой используется двойное хеширование). В конце рассматриваются динамическая хеш-таблица и таблица сравнения методов разрешения коллизий.
Последняя лекция по алгоритмам посвящена сразу нескольким разным видам деревьев: двоичным деревьям поиска (для создания ассоциативного массива) и проблемам их балансировки, декартовым деревьям, АВЛ-деревьям. Степан Мацкевич заканчивает лекцию на примерах реализации типа данных «Ассоциативный массив» с помощью деревьев и хеш-таблиц со сравнением преимуществ каждого варианта.
Плейлист всех лекций находится по ссылке [1]. Напомним, что актуальные лекции и мастер-классы о программировании от наших IT-специалистов в проектах Технопарк, Техносфера и Технотрек по-прежнему публикуются на канале Технострим [2].
Автор: Mail.Ru Group
Источник [3]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/razrabotka/249210
Ссылки в тексте:
[1] по ссылке: https://www.youtube.com/playlist?list=PLrCZzMib1e9rvDqeX2jRXrEWoTqUxrqUA
[2] Технострим: https://www.youtube.com/user/tpmgtu/videos
[3] Источник: https://habrahabr.ru/post/323696/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.