Лекции Техносферы. Подготовительный курс «Алгоритмы и структуры данных»

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

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

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

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

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

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

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

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