Пять типичных задач
Задача устойчивых паросочетаний служит превосходным примером процесса проектирования алгоритма.
Для многих задач этот процесс состоит из нескольких ключевых шагов: постановка задачи с математической точностью, достаточной для того, чтобы сформулировать конкретный вопрос и начать продумывать алгоритмы ее решения; планирование алгоритма для задачи; и анализ алгоритма, который доказывает его точность и позволяет получить граничное время выполнения для оценки эффективности.
Для практической реализации этой высокоуровневой стратегии применяются фундаментальные приемы проектирования, чрезвычайно полезные для оценки присущей ей сложности и формулирования алгоритма для ее решения.
Освоение этой темы будет полезно начать с некоторых типичных ключевых точек, которые встретились нам в процессе нашего изучения алгоритмов: четко сформулированных задач, похожих друг на друга на общем уровне, но значительно различающихся по сложности и методам, которые будут задействованы для их решения.
Первые три задачи могут быть эффективно решены последовательностью алгоритмических приемов нарастающей сложности; четвертая задача станет поворотной точкой в нашем обсуждении — в настоящее время считается, что эффективного алгоритма для ее решения не существует. Наконец, пятая задача дает представление о классе задач, которые считаются еще более сложными.
Все эти задачи самодостаточны, а побудительные причины для их изучения лежат в области вычислительных приложений. Тем не менее для описания некоторых из них будет удобно воспользоваться терминологией графов. Графы — достаточно стандартная тема на ранней стадии изучения вычислительных технологий, но в главе 3 они будут рассматриваться на довольно глубоком уровне; кроме того, ввиду огромной выразительной силы графов они будут широко использоваться в книге.
В контексте текущего обсуждения граф G достаточно рассматривать просто как способ представления попарных отношений в группе объектов. Таким образом, G состоит из пары множеств (V, E) — набора узлов V и набора ребер E, каждое из которых связывает два узла. Таким образом, ребро e Ѯ E представляет двухэлементное подмножество V: e = {u, v} для некоторых u, v Ѯ V; при этом u и v называются концами e.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу