Этап 5. Основы алгоритмов и структур данных
Время прохождения: 2 месяца
Введение в алгоритмы и структуры данных
Понятие алгоритмов: шаги, сложность выполнения, понятие «big O».
Основные типы структур данных и их применение
Создание, добавление, удаление элементов, индексация
Разбор временной и пространственной сложности
Сравнение массивов и списков, их преимущества и недостатки в различных задачах
Введение в хеширование, эффективность операций поиска и вставки
Применение словарей для быстрого поиска по ключам, уникальность данных в множествах
1. Проект 1: Консольное приложение «Система управления задачами» с приоритетами
2. Проект 2: Разработка интерактивной игры с использованием алгоритмов поиска пути.
20 домашних заданий для закрепления навыков
1. Освоение базовых алгоритмов и структур данных для эффективной обработки данных
2. Понимание, как выбирать подходящие структуры данных для решения различных задач
3. Умение реализовывать и оптимизировать алгоритмы
Очередь: принципы FIFO, реализация на списках и deque.
Продвинутые сортировки: быстрая сортировка (QuickSort), сортировка слиянием (MergeSort), пирамидальная сортировка (HeapSort).
Применение для управления данными в различных сценариях (например, стек вызовов функций).
Понимание и сравнение сложности алгоритмов сортировки
Применение для управления данными в различных сценариях (например, стек вызовов функций).
Очередь: принципы FIFO, реализация на списках и deque.
Линейный поиск: применение в простых структурах данных
Бинарный поиск: работа с отсортированными данными, сложность O(log n).
Поиск в строках: алгоритм Кнута-Морриса-Пратта (KMP) для эффективного поиска подстроки
Принципы работы рекурсивных функций, когда и как использовать рекурсию
Рекурсивные алгоритмы на примере алгоритма вычисления факториала и поиска чисел Фибоначчи
Проблемы рекурсии: переполнение стека, оптимизация через мемоизацию и динамическое программирование
Основы работы с деревьями: бинарные деревья поиска, операции вставки, удаления и поиска
Обходы дерева: в глубину (DFS), в ширину (BFS), рекурсивные и итеративные подходы
Введение в графы: представление графов (матрицы смежности, списки смежности), применение для задач на поиск кратчайшего пути и других
Жадные алгоритмы и динамическое программирование
Введение в жадные алгоритмы и примеры их применения (например, задача о рюкзаке).
Основы динамического программирования, решения сложных задач с минимальными вычислениями
Примеры использования для решения реальных задач