Методы проектирования
Динамическое программирование, мемоизация и жадные алгоритмы. Парадигмы построения эффективных решений.
Методы проектирования
Разделяй и властвуй (Divide and Conquer)
Разбиение задачи на подзадачи, рекурсивное решение, объединение результатов. Примеры: QuickSort, MergeSort, бинарный поиск. Время T(n) = 2T(n/2) + O(n). Основная теорема рекуррентных соотношений.
Динамическое программирование (DP)
Разбиение на подзадачи с перекрытием, запоминание решений (memoization). Избегает повторных вычислений. Примеры: рюкзак, LCS, числа Фибоначчи. Подходы: top-down (рекурсия + memo), bottom-up (таблица).
Жадные алгоритмы (Greedy)
Локально оптимальный выбор на каждом шаге. Не гарантирует глобального оптимума, но быстр. Примеры: алгоритм Дейкстры, Хаффман, задача о размене монет. Требует доказательства корректности.
Метод возврата (Backtracking)
Систематический перебор с отсечением неперспективных ветвей. Построение решения шаг за шагом, откат при неудаче. Примеры: N ферзей, судоку, лабиринты. Экспоненциальная сложность, но с отсечениями.
Метод ветвей и границ (Branch and Bound)
Систематический перебор с оценкой границ для отсечения. Используется для задач оптимизации (минимизация/максимизация). Примеры: задача коммивояжёра, целочисленное программирование. Требует функции оценки.