Одним из главных результатов теории алгоритмов является доказательство существования
(*ответ*) некоторых неразрешимых проблем
решения любой задачи
некоторых решаемых проблем
алгоритма Маркова решения любой задачи
Основным свойством конструктивного подхода к понятию алгоритма является то, что все множество функций строится
(*ответ*) из конечного числа исходных объектов - базиса с помощью простых операций, эффективная выполнимость которых очевидна
из бесконечного числа исходных объектов - базиса с помощью простых операций, эффективная выполнимость которых очевидна
из конечного числа исходных объектов - базиса с помощью простых операций, эффективная выполнимость которых не очевидна
из бесконечного числа исходных объектов - базиса с помощью простых операций, эффективная выполнимость которых не очевидна
Полиномиальная сложность алгоритма – это сложность алгоритма, у которого зависимость временной и емкостной сложности от размера задачи, имеет вид
(*ответ*) полинома некоторой степени
экспоненты
логарифма
полинома первой степени
Полиномиальные алгоритмы обычно можно построить лишь тогда, когда
(*ответ*) удается найти решение без перебора всех допустимых вариантов данных
не удается найти решение без перебора всех допустимых вариантов данных
удается найти решение с перебором всех допустимых вариантов данных
удается найти решение с перебором половины и более всех допустимых вариантов данных
Полиномиальным алгоритмом называется алгоритм, у которого временная сложность T(n), где n – размер задачи, есть
(*ответ*) T(n)=O(p(n)) где р(n) – полином от n
T(n)=O(p(n)) где р(n) экспонента от n
T(n)<O(p(n)) где р(n) – экспонента от n
T(n)>O(p(n)) где р(n) – полином от n
Проблема P = NP состоит в следующем:
(*ответ*) если положительный ответ на какой-то вопрос можно проверить за полиномиальное время, то и ответ на этот вопрос можно найти за полиномиальное время
если отрицательный ответ на какой-то вопрос можно проверить за полиномиальное время, то и ответ на этот вопрос можно найти за полиномиальное время
если положительный ответ на какой-то вопрос можно проверить за экспоненциальное время, то ответ на этот вопрос можно найти за полиномиальное время
если положительный ответ на какой-то вопрос можно проверить за полиномиальное время, то и ответ на этот вопрос можно найти за экспоненциальное время
Проблема распознавания самоприменимости машины Тьюринга
(*ответ*) алгоритмически не разрешима
алгоритмически разрешима
относится к классу P задач
относится к классу NP задач
Проблема самоприменимости машины Тьюринга формулируется так:
(*ответ*) машина Тьюринга применима с своему собственному коду
машина Тьюринга применима с любому слову внешнего алфавита
машина Тьюринга применима с любому слову внутреннего алфавита
машина Тьюринга применима с счетному множеству слов внешнего алфавита
Размером задачи является характеристика, которая определяет
(*ответ*) величину исходных данных или их количество
длину программы, реализующей алгоритм
время работы программы, реализующей алгоритм
количество циклов в программе, реализующей алгоритм
Свойство вычислимости алгоритма означает, что
(*ответ*) должен существовать вычислитель, способный выполнить указанные в алгоритме инструкции
алгоритм содержит конечное число инструкций
все инструкции алгоритма выполняются дискретно, т.е. без использования каких-либо аналоговых устройств непрерывного действия
на одних и тех же данных алгоритм всегда выполняется одинаково
Свойство дискретности алгоритма означает, что
(*ответ*) все инструкции алгоритма выполняются дискретно, т.е. без использования каких-либо аналоговых устройств непрерывного действия.
отдельные инструкции алгоритма выполняются с использованием аналоговых устройств непрерывного действия.
отдельные инструкции алгоритма выполняются непрерывно
алгоритм содержит конечное число инструкций
Свойство конечности алгоритма означает, что
(*ответ*) любой алгоритм задается последовательностью инструкций конечных размеров
любой алгоритм задается последовательностью инструкций бесконечных размеров
любой алгоритм должен завершаться
программа алгоритма не должна зацикливаться
Свойство результативности алгоритма означает, что
(*ответ*) алгоритм должен быть результативным, т.е. завершающимся с некоторым результатом после некоторого конечного числа шагов
алгоритм должен быть реализуемым
алгоритм должен содержать конечное число инструкций
программа алгоритма не должна содержать циклов
Трудно решаемыми являются задачи класса
(*ответ*) NP\P
NPÇP
NPÈP
NP
Частично-рекурсивной называется функция, построенная из простейших с помощью
(*ответ*) конечного числа операторов суперпозиции, примитивной рекурсии и минимизации
конечного числа операторов суперпозиции и минимизации
конечного числа операторов примитивной рекурсии и минимизации
бесконечного числа операторов суперпозиции, примитивной рекурсии и минимизации
Частично-рекурсивные фунции – это модель алгоритма, которая
(*ответ*) рассматривает понятие алгоритма с точки зрения того, что можно вычислить с помощью алгоритма
определяет область определения данной функции
определяет область изменения данной функции
определяет нули функции
Экспоненциальная сложность алгоритма – это сложность алгоритма, у которого зависимость временной и емкостной сложности от размера задачи, имеет вид
(*ответ*) экспоненты
полинома некоторой степени
полинома первой степени
полинома от экспоненты