Алгоритмы на Python

Профиль аудитории:

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

Предварительные требования:

• прохождение курса «Основы программирования на Python» или знания в объеме этого курса
• знание базового синтаксиса Python (переменные, циклы, функции)
• основы работы с списками, словарями и множествами
• желателен опыт решения простых алгоритмических задач

По окончании курса слушатели смогут:

• анализировать сложность алгоритмов с использованием O-нотации
• реализовывать и оптимизировать алгоритмы сортировки, поиска и работы с графами
• проектировать эффективные структуры данных для конкретных задач
• работать с данными в базах SQLite и формате JSON
• применять алгоритмы для решения практических задач (например, поиск пути, анализ данных)

Модуль 1. Основы алгоритмического мышления и анализ эффективности

• Алгоритмы как искусство: ключевые принципы и подходы к разработке;
• Асимптотический анализ: Big-O, Big-Θ, Big-Ω на примерах;
• Пространственная и временная сложность: как считать и оптимизировать;
• Базовые структуры данных Python: списки, словари, множества;
• Практикум: Профилирование кода — замер скорости стандартных операций Python.

Модуль 2. Классические алгоритмы сортировки: от теории к практике

• Сортировка пузырьком и вставками: понимание простых итеративных методов;
• Быстрая сортировка (QuickSort): выбор опорного элемента и рекурсия;
• Сортировка слиянием (MergeSort): разбиение, слияние, стабильность;
• Сравнение с встроенной timsort: когда использовать свои алгоритмы;
• Практикум: Реализация QuickSort и MergeSort с замером времени на больших данных.

Модуль 3. Алгоритмы поиска и хеширование: скорость и точность

• Линейный vs бинарный поиск: реализация и анализ на отсортированных данных;
• Хеш-таблицы: создание собственной реализации с обработкой коллизий;
• Алгоритм Кнута-Морриса-Пратта (KMP): поиск подстроки с префикс-функцией;
• Применение хеширования: подсчет уникальных элементов в потоке;
• Практикум: Поиск подстроки в тексте с KMP и хеширование для анализа частотности слов.

Модуль 4. Структуры данных: стеки, очереди и бинарные деревья

• Стеки: реализация через списки и решение задач (валидация скобок);
• Очереди: двусторонние очереди с collections.deque для симуляции процессов;
• Бинарные деревья поиска (BST): вставка, удаление, балансировка;
• Обход деревьев: рекурсивный и итеративный подходы;
• Практикум: Построение BST для поиска ближайшего значения и проверка выражений со скобками.

Модуль 5. Графы и алгоритмы поиска пути: от метро до сетей

• Представление графов: матрицы смежности vs списки ребер в Python;
• Поиск в ширину (BFS): нахождение кратчайшего пути в невзвешенном графе;
• Поиск в глубину (DFS): выявление циклов и компонент связности;
• Алгоритм Дейкстры: оптимизация маршрутов с учетом весов;
• Практикум: Построение графа московского метро и поиск оптимального маршрута с пересадками.

Модуль 6. Динамическое программирование и жадные стратегии

• Динамическое программирование: разложение задачи на подзадачи с мемоизацией;
• Классика DP: числа Фибоначчи, задача о рюкзаке (0/1 и дробный);
• Жадные алгоритмы: минимальное остовное дерево (Kruskal), выбор активности;
• Сравнение подходов: когда жадность проигрывает динамике;
• Практикум: Решение задачи о рюкзаке и планирование расписания с жадным алгоритмом.

Модуль 7. Интеграция алгоритмов с SQLite: данные в действии

• SQLite для алгоритмиста: создание схем для графов и деревьев;
• Эффективные запросы: индексы, оптимизация JOIN и WHERE;
• Хранение результатов: сериализация графов и путей в базу;
• Анализ больших данных: постраничная обработка и агрегация;
• Практикум: Сохранение графа метро в SQLite и поиск маршрутов с учетом времени поездки.

Модуль 8. JSON и финальный вызов: решатель головоломок

• JSON в Python: парсинг и генерация сложных структур данных;
• Алгоритмы обработки JSON: фильтрация, преобразование, сжатие;
• Разработка решателя судоку: рекурсия и backtracking;
• Оптимизация решателя: использование хеширования для проверки уникальности;
• Практикум: Создание решателя 100 сложнейших судоку с сохранением результатов в JSON.