Курс Алгоритмы и структуры данных

На этом этапе вы узнаете, почему нельзя использовать стандартное понимание времени для оценки скорости работы алгоритма. Мы рассмотрим понятие асимптотической сложности алгоритма и научимся определять ее на многочисленных примерах.

Познакомимся с основными и наиболее используемыми структурами данных: массив, список, стек, очередь, хеш-таблица, дерево, бинарное дерево поиска.

Разберем большое количество алгоритмов сортировки, среди которых быстрая сортировка, heap-sort, сортировка подсчетом и др. Поскольку алгоритм быстрой сортировки пользуется популярностью на собеседованиях, рассмотрим его очень подробно (Какой элемент выбрать опорным и почему? Какие есть схемы разбиения, их преимущества и недостатки?)

Поговорим о делителях числа, простых числах, факторизации. Рассмотрим алгоритм Евклида для нахождения наибольшего общего делителя и наименьшего общего кратного. Познакомимся с алгоритмом «решето Эратосфена» для нахождения простых чисел.

Узнаем, что представляет собой структура данных граф. Рассмотрим сферы ее применения. Научимся реализовывать простые алгоритмы на графах, такие как поиск в глубину и в ширину, нахождение компонент связности и др.

Разберемся, как работают более сложные алгоритмы на графах: алгоритм Дейкстры и алгоритм Прима. Научимся находить мосты и точки сочленения для заданного графа.

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

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

Рассмотрим принципы балансировки AVL-дерева. Решим несколько популярных задач, а также проверим полученные знания с помощью викторины.