Алгоритмы и структуры данных
✨ Уровень | 🕗 Продолжительность | 💻 Практика |
Средний | 4-8 месяцев | 400+ упражнений по программированию |
Добро пожаловать в курс по алгоритмам и структурам данных. К окончанию курса вы обретёте достаточно знаний, чтобы значительно оптимизировать программы, научитесь понимать их эффективность и будете готовы к собеседованиям в ведущих IT-компаниях, таких как Google, Meta, Amazon и другие. В этом курсе мы начинаем с основ алгоритмов и структур данных и переходим к самым популярным темам в этой области.
Крупные технологические компании, такие как Google, Meta, Netflix и Amazon, проводят собеседования, уделяя особое внимание глубоким знаниям в области структур данных и алгоритмов. Освоив этот курс, вы будете готовы к таким интервью.
📚 Предварительные требования
Этот курс рассчитан на людей, которые уже владеют любым языком программирования общего назначения (например, Python, C++, Java или C#) и хотят углубиться в мир алгоритмов и структур данных. Перед началом желательно уверенно работать с циклами, уметь писать функции и использовать базовые структуры данных (такие как списки, множества или словари).
🤩 Результаты
По окончании этого курса вы научитесь эффективно использовать популярные структуры данных для написания алгоритмов, которые по скорости будут на порядок превосходить наивные решения. Мы рассмотрим лучшие практики написания кода и подготовки к алгоритмическим собеседованиям.
Этот курс ориентирован на действительно глубокое понимание каждого концепта. Вы будете изучать различные алгоритмы и реализовывать их вариации в многочисленных задачах, чтобы полностью овладеть каждым из них.
💻 Учитесь на практике
Цель изучения алгоритмов — не только теория.
Главное — научиться решать задачи.
В этом курсе процесс обучения — практический! Каждый новый материал сопровождается несколькими интерактивными заданиями, которые нужно пройти, чтобы двигаться дальше. Всего в курсе более 400 практических задач по программированию. Мы убеждены, что лучший способ получить глубокие знания — это практика. Здесь вы найдёте множество интересных и одновременно сложных упражнений, которые помогут развить навыки решения задач по каждой пройденной теме.
⚡ Учитесь в своём темпе
Вы можете заниматься в интенсивном режиме и завершать сразу несколько уровней за неделю или, наоборот, двигаться постепенно, уделяя больше времени каждому понятию. Темп обучения полностью зависит от вас. Единственное обязательное условие для успешного окончания курса — регулярные занятия. Практика по 1–2 часа каждый день даёт значительно больше результатов, чем однократное занятие раз в неделю на много часов подряд.
Чтобы вы не застряли на каком-то этапе, у нас есть форум для вопросов. Вы можете задавать свои вопросы и помогать другим участникам, отвечая на их вопросы под каждым заданием.
🎓 Учебный план
Курс ориентирован на фундаментальные знания о структурах данных и алгоритмах, с понятной и последовательной подачей материала. Чтобы учебный процесс был увлекательным, темы разделены на уровни, а прохождение каждого уровня означает, что вы полностью освоили очередную концепцию. Ниже перечислены основные разделы, которые мы будем разбирать:
Задачи на реализацию (Implementation problems)
- Алгоритм уже дан нам в условии задачи
- Работа с базовыми структурами данных (массивами, словарями, множествами и т.п.)
Побитовые операции (Bitwise operations)
- Двоичное представление чисел (int → bin, bin → int)
- Отрицательные числа в двоичной системе
- Побитовые операции OR, AND, XOR
- Представление чисел в различных системах счисления (base-10 → base-k, base-k → base-10)
Префиксные суммы (Prefix sums)
- Одномерные префиксные суммы
- Двумерные префиксные суммы
Скользящее окно / Два указателя (Sliding window / Two pointers)
- Поиск суммы с помощью скользящего окна
- Поиск уникальных значений с использованием скользящего окна
Теория чисел (Number theory)
- Проверка простоты: ,
- Решето Эратосфена
- Факторизация числа
- Наибольший общий делитель (GCD) и Наименьшее общее кратное (LCM)
- Модульная арифметика
Бинарный поиск (Binary Search)
- Линейный поиск против двоичного поиска
- Поиск значения в отсортированном массиве с помощью двоичного поиска
- Поиск вещественного числа с заданной точностью
- Особенности выбора левой и правой границ
- Двоичный поиск по ответу
Сортировка (Sorting)
- Bogosort
- Сортировка выбором
- Сортировка вставками
- Пузырьковая сортировка
Жадные алгоритмы (Greedy Algorithms)
- Использование жадного подхода
- Жадные эвристики
Динамическое программирование (Dynamic Programming)
- Одномерное динамическое программирование (например, Фибоначчи)
- Задача о монетах (минимальное число монет)
- Задача о монетах (количество способов)
Рекурсия (Recursion)
- Факторы ветвления
- Код Грея
- Задача о ханойских башнях
- Рекурсивное деление задачи на подзадачи
Разделяй и властвуй и продвинутая сортировка (Divide & Conquer & Advanced Sorting)
- Сортировка слиянием (Merge sort)
- Быстрая сортировка (Quick sort)
- Сортировка «на месте» (in-place)
- Сложность любой сортировки на сравнениях не может быть менее
Связанный список (Linked List)
- Узлы (Nodes) и рёбра
- Обход и поиск
- Удаление и вставка элементов
Очередь и стек (Queue & Stack)
- Порядок вставки и удаления
- Оптимизация поиска с помощью стека
Двоичное дерево и дерево бинарного поиска (Binary Tree & Binary Search Tree: BST)
- Построение бинарного дерева
- Поиск в бинарном дереве
- Обновление и удаление элементов в дереве
Куча (Heap)
- Heapify (приведение к куче)
- Пирамидальная сортировка (Heap sort)
Хеширование (Hashing)
- Хеш-функции
- Коллизии
Продвинутое динамическое программирование (Advanced Dynamic Programming)
- Расстояние редактирования (Edit Distance)
- Задача о рюкзаке (Knapsack problem)
- Наибольшая возрастающая подпоследовательность (Longest Increasing Subsequence)
- Эффективное умножение
nматриц
Представления графов (Graph Representations)
- Матрица смежности
- Список смежности
- Список рёбер
- Степени вершин
Поиск в ширину (Breadth-First Search: BFS)
- BFS (поиск в ширину) в графах
- Поиск кратчайшего пути
- BFS на сетке
- BFS в других структурах
Поиск в глубину (Depth-First Search: DFS)
- Проверка связности
- Поиск циклов
- Топологическая сортировка
- Проверка на двудольность (Bipartidness)
Префиксное дерево (Trie)
- Поиск подстрок в строках
Алгоритм Дейкстры (Dijkstra)
- Поиск кратчайшего пути в взвешенном графе
- Приёмы упрощения и оптимизации решения для различных типов задач
Бэктрекинг (Backtracking)
- Задача N ферзей
- Раскраска графа
- Заполнение таблиц числами
Дерево отрезков (Segment Tree)
- Базовое построение сегментного дерева (конструирование, получение значения, обновление)
- Запросы на диапазоне и обновление значений
- Двоичный поиск по префиксу
- Хранение нескольких значений в одной вершине
- Предварительная обработка входных данных и использование сегментного дерева
Сложность алгоритмов (Algorithm Complexity)
- Формальная запись Big
- P против NP
🚀 Welcome
Обучение на 80% состоит из самостоятельной работы. Завершение этого курса — это ваше собственное достижение, и мы будем поддерживать вас на каждом этапе!