Задач распознавания свойств (зрс)


Download 135 Kb.
bet1/3
Sana21.11.2023
Hajmi135 Kb.
#1792648
TuriРешение
  1   2   3
  • PNP?
  • Задачи распознавания свойств
  • Класс задач распознавания свойств (ЗРС) – множество проблем, решением которых является ответ «Да» или «Нет».
  • ГАМИЛЬТОНОВ ЦИКЛ (ГЦ).
  • Задан граф G = (V, E).
  • Спрашивается, содержит ли G гамильтонов цикл?
  • Opt задаче max{f(x) : x D} соответствует ЗРС:
  • « ли решение x D: f(x)  Q?», где Q – заданное число.
  • КОММИВОЯЖЕР (КМ). Дано:
  • N – список городов;
  • cijрасстояния между городами i,j N; B R.
  •  ли гамильтонов контур, длина которого  B?
  • Задачи
  • Под общей (массовой) задачей (проблемой) P понимается некоторый общий вопрос, требующий ответа.
  • Общая задача, как правило, содержит некоторые параметры. В задаче КМ, например, это расстояния между городами.
  • Если все параметры общей задачи принимают конкретные значения, то такую задачу называют индивидуальной.
  • Трудоёмкость алгоритма
  • Количество символов в стандартном (двоичном)
  • представлении данных инд. задачи XP наз. длиной входа
  • и обозначим L(X).
  • наз. трудоемкостью алг. A.
  • , где d – целое положительное число
  • Алг., трудоемкость которого не ограничена полиномом от длины входа, наз. экспоненциальным.
  1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling