Вопрос: Одним из главных результатов теории алгоритмов является доказательство существования 
 (*ответ*) некоторых неразрешимых проблем
 решения любой задачи
 некоторых решаемых проблем
 алгоритма Маркова решения любой задачи
Основным свойством конструктивного подхода к понятию алгоритма является то, что все множество функций строится
 (*ответ*) из конечного числа исходных объектов - базиса с помощью простых операций, эффективная выполнимость которых очевидна
 из бесконечного числа исходных объектов - базиса с помощью простых операций, эффективная выполнимость которых очевидна
 из конечного числа исходных объектов - базиса с помощью простых операций, эффективная выполнимость которых не очевидна
 из бесконечного числа исходных объектов - базиса с помощью простых операций, эффективная выполнимость которых не очевидна
Полиномиальная сложность алгоритма – это сложность алгоритма, у которого зависимость временной и емкостной сложности от размера задачи, имеет вид
 (*ответ*) полинома некоторой степени
 экспоненты
 логарифма
 полинома первой степени
Полиномиальные алгоритмы обычно можно построить лишь тогда, когда 
 (*ответ*) удается найти решение без перебора всех допустимых вариантов данных
 не удается найти решение без перебора всех допустимых вариантов данных
 удается найти решение с перебором всех допустимых вариантов данных
 удается найти решение с перебором половины и более всех допустимых вариантов данных
Полиномиальным алгоритмом называется алгоритм, у которого временная сложность 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
Частично-рекурсивной называется функция, построенная из простейших с помощью
 (*ответ*) конечного числа операторов суперпозиции, примитивной рекурсии и минимизации
 конечного числа операторов суперпозиции и минимизации
 конечного числа операторов примитивной рекурсии и минимизации
 бесконечного числа операторов суперпозиции, примитивной рекурсии и минимизации
Частично-рекурсивные фунции – это модель алгоритма, которая
 (*ответ*) рассматривает понятие алгоритма с точки зрения того, что можно вычислить с помощью алгоритма
 определяет область определения данной функции 
 определяет область изменения данной функции 
 определяет нули функции
Экспоненциальная сложность алгоритма – это сложность алгоритма, у которого зависимость временной и емкостной сложности от размера задачи, имеет вид
 (*ответ*) экспоненты
 полинома некоторой степени
 полинома первой степени
 полинома от экспоненты
Категория: разное
Ответы:
тест прошел проверку
все верно по ответам)