#Проектное решение
Download 98.68 Kb.
|
Тесты Проектирование алгоритмов HEMIS
|
====
#полинома некоторой степени ==== Экспоненты ==== Логарифма ==== полинома первой степени ++++ Полиномиальные алгоритмы обычно можно построить лишь тогда, когда ==== #удается найти решение без перебора всех допустимых вариантов данных ==== не удается найти решение без перебора всех допустимых вариантов данных ==== удается найти решение с перебором всех допустимых вариантов данных ==== удается найти решение с перебором половины и более всех допустимых вариантов данных ++++ Полиномиальным алгоритмом называется алгоритм, у которого временная сложность T(n), где n – размер задачи, есть ==== #T(n)=O(p(n)) где р(n) – полином от n ==== T(n)=O(p(n)) где р(n) экспонента от n ==== T(n) T(n)>O(p(n)) где р(n) – полином от n ++++ Проблема P = NP состоит в следующем: ==== #если положительный ответ на какой-то вопрос можно проверить за полиномиальное время, то и ответ на этот вопрос можно найти за полиномиальное время ==== если отрицательный ответ на какой-то вопрос можно проверить за полиномиальное время, то и ответ на этот вопрос можно найти за полиномиальное время ==== если положительный ответ на какой-то вопрос можно проверить за экспоненциальное время, то ответ на этот вопрос можно найти за полиномиальное время ==== если положительный ответ на какой-то вопрос можно проверить за полиномиальное время, то и ответ на этот вопрос можно найти за экспоненциальное время ++++ Проблема распознавания самоприменимости машины Тьюринга ==== #алгоритмически не разрешима ==== алгоритмически разрешима ==== относится к классу P задач ==== относится к классу NP задач ++++ Проблема самоприменимости машины Тьюринга формулируется так: Download 98.68 Kb. Do'stlaringiz bilan baham: 
|