![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Числовые функции, значения которых можно вычислить посредством применения некоторого алгоритма, называются эффективно вычислимыми (или просто вычислимыми) функциями.
Функция называется всюду определенной, если область ее определения, т.е. множество значений ее аргумента и область
значений функций, каждому из которых сопоставлено некотороезначение аргумента, совпадают.
Функции, определенные не для всех значений аргументов, называются частичными (не всюду определенными) функциями.
Частично-рекурсивные функции – это функции, определяемые особым образом с достаточной математической строгостью. А именно: если функция может быть получена за конечное число шагов из некоторых простейших функций с помощью операций суперпозиции, примитивной рекурсии и операции минимизации.
С.К. Клини (американский логик и математик) высказал гипотезу о том, что класс алгоритмически вычислимых частичных функций совпадает с классом всех частично рекурсивных функций. Ранее аналогичную гипотезу относительно всюду определенных вычислимых функций выдвинул А Чёрч (американский логик и математик). Гипотезы Чёрча и Клини обычно объединяют в виде тезиса Чёрча.
19. Понятие о труднорешаемых, NP, P и NP-полных задачах. Взаимоотношение классов P, NP и NP-полных задач.
Широкое распространение получило соглашение о том, что задача не считается эффективно решаемой до тех пор, пока для нее не будет получен полиномиальный алгоритм. В связи с этим вводят термин труднорешаемой задачи, если для нее не существует полиномиального алгоритма.
Аббревиатура NP происходит от английских слов nondeterministic (N) и polinomial (P) и означает класс всех задач распознавания, которые могут быть решены НДВУ за полиномиальное время. В отличие от этих задач класс задач, полиномиально разрешимых на детерминированной одноленточной машине Тьюринга (ДМТ), стали называть классом P (от слова polinomial).
После того как было введено понятие класса задач NP,было доказано, что многие хорошо известные комбинаторные задачи, будучи сформулированы как задачи распознавания, оказываются эквивалентными по трудности задаче о выполнимости. Этот класс эквивалентности, состоящий из “самых трудных” задач, принадлежащих к классу NP, получил название класса NP - полных задач. Иногда его называют классом универсальных задач, которые упрощенно понимают как задачи, для которых не найдены полиномиальные алгоритмы. Однако и не доказано, что таких алгоритмов вообще не существует.
Дата публикования: 2015-03-26; Прочитано: 4454 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!