[foxminded] Алгоритмы и структуры данных. 2022 (Александр Басалкевич)

[Акулкин]

Ссылка на картинку

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

Курс состоит из серии видеолекций и практических заданий для закрепления материала.

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

Умение работать с алгоритмами позволяет оценивать их эффективность, скорость и использование памяти. Кроме того, вы научитесь создавать алгоритмы с нуля и с их помощью оптимизировать производительность кода. А еще у вас выработается способность анализировать задачу и подбирать оптимальный алгоритм для ее решения, ведь код — это инструмент, а не самоцель.

Когда вы освоитесь с алгоритмами, вы будете увереннее решать обычные бытовые задачи и успешнее проходить собеседования. В крупных компаниях очень любят предложить соискателю выразить идею через алгоритм или через сравнение разных способов решения. Это считается базовым навыком хорошего инженера.

Практические задания на курсе:

1. Реализация структур данных (список, очередь, стек, хеш-таблица, бинарное дерево поиска)
2. Имплементация алгоритмов сортировки (Quick Sort, Heap Sort и др.)
3. Имплементация базовых алгоритмов на графе (обходы в глубину и в ширину, поиск компонент связности, поиск пути между двумя вершинами графа, поиск кратчайшего расстояния между двумя вершинами в неориентированном графе)
4. Реализация более сложных алгоритмов на графе (алгоритм Дейкстры, алгоритм Прима, поиск мостов и точек сочленения)
5. Нахождение площади произвольного многоугольника; реализация алгоритма построения выпуклой оболочки для набора точек на плоскости
6. Реализация алгоритмов Рабина-Карпа и Кнута-Морриса-Пратта для оптимального нахождения строки в тексте.

Содержание:

Модуль 1 - Асимптотическая сложность алгоритма

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

Модуль 2 - Структуры данных

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

Модуль 3 - Алгоритмы сортировки

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

Модуль 4 - Основы теории чисел

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

Модуль 5 - Алгоритмы на графах часть 1

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

Модуль 6 - Алгоритмы на графах часть 2

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

Модуль 7 - Геометрические задачи

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

Модуль 8 - поиск в тексте

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

Модуль 9 - Постскриптум

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