chapter_10.py

"""Сложные вычислительные задачи."""

# Функция f(n) называется полиномиально возрастающей, если она растет растёт пропорционально полиному (многочлену) от размера входных данных.
#
# **Полиномиально возрастающие функции** (примеры):
# * f(n) = 3n + 2 → линейный рост O(n)
# * f(n) = n^2 → квадратичный рост O(n^2)
# * f(n) = 5n^3 + 10n → кубический рост O(n^3)
#
# **Не является полиномиальным ростом**:
# Эти функции растут быстрее любого полинома.
#
# * Экспоненциальный рост: f(n) = 2^n, f(n) = e^n
# * Факториальный рост: f(n) = n!
# * Суперполиномиальный рост: f(n) = n * log n
#
# **Полиномиальный** означает, что «растёт как какая-то степень n»
#
# **Полиномиально возрастающий** — значит растущий как многочлен от n , например n, n^2, n^10, но не как 2^n или n!

# **P-задача** – это класс задач, которые можно решить быстро (за полиномиальное время) на обычном компьютере (время работы алгоритма растёт как многочлен от размера входа: например, O(n), O(n^2), O(n^3) — это всё полиномиально)
#
# **NP-задача** — это класс задач, для которых решение можно проверить быстро (за полиномиальное время), если оно уже дано.

# #  NP-полнота

# NР - недетерминированное полиномиальное время
#
# NР относится к группе вычислительных задач, которые решаются за время, полиномиально возрастающее по мере увеличения размера задачи. У этих задач есть отличительная черта: если решение предложено, то его точность может быть подтверждена или опровергнута за полиномиальное время.
#
# Задача считается NP-полной, если принадлежит классу NP и является такой же трудной, как и любая другая задача NP. Другими словами, NP-полные задачи — одни из самых сложных в информатике.

# Редукция – преобразование известной задачи, которая, как доказано, является NР-полной, в другую. Успешно выполнив это преобразование, мы устанавливаем, что вторая задача также является NР-полной.

# # NР-трудность

# В теории сложности вычислений задача называется NР-трудной, если ее решение за полиномиальное время означает, что любая задача из класса NР может быть решена за аналогичное время.
#
# NР-трудные задачи имеют характерную черту: они могут быть, а могут и не быть частью класса NР. То есть, несмотря на то что они трудноразрешимы, могут существовать решения, проверяемые за полиномиальное время. Отсутствие такого решения не исключает возможности его существования.
#
# Примеры:
# * Задача о коммивояжере.
# * Задача о наполнении рюкзака наиболее ценными предметами и пр.
#
# NP-трудные задачи обычно решаются с помощью **эвристических и аппроксимирующих алгоритмов**. То есть эти алгоритмы неидеальны, но **достаточно** эффективны для получения результата.

# Изучение и решение NР-трудных и NP-пoлныx задач позволяют находить алгоритмы, которые обеспечивают равновесие между точностью и эффективностью использования времени и ресурсов.

# * **P** – задачу легко решить.
# * **NP** – задачу сложно решить быстро, но если есть решение, его можно быстро проверить.
# * **NP-полная (NP-complete)** – самые трудные из NP.
# * **NP-трудные (NP-hard)** – еще труднее (или не из NP вообще). И проверить её правильность тоже невозможно, но если ты это решишь, то и все головоломки из NP тоже решишь.