Список вопросов базы знаний

Множество М называется разрешимым, если для него существует алгоритм, решающий проблему

Множество М называется эффективно перечислимым, если для него существует алгоритм, позволяющий

Можно выделить следующие основные типы универсальных алгоритмических моделей

Недетерминированность алгоритма Т означает, что при запуске многих экземпляров этого алгоритма

Недетерминированный алгоритм всегда должен выдавать на выходе одно из двух сообщений:

Необходимость формального определения алгоритма определяется тем, что необходимо иметь математически точный инструмент

Необходимость формального определения алгоритма определяется тем, что только при наличии формального определения алгоритма можно

Одним из главных результатов теории алгоритмов является доказательство существования

Оператор суперпозиции из функций и имеет вид

Основным свойством конструктивного подхода к понятию алгоритма является то, что все множество функций строится

Полиномиальная сложность алгоритма – это сложность алгоритма, у которого зависимость временной и емкостной сложности от размера задачи, имеет вид

Полиномиальные алгоритмы обычно можно построить лишь тогда, когда

Полиномиальным алгоритмом называется алгоритм, у которого временная сложность T(n), где n – размер задачи, есть

Применение оператора суперпозиции к функциям и дает следующие функции

Проблема P = NP состоит в следующем:

Проблема равенства классов P и NP можно сформулировать как: является ли

Проблема распознавания самоприменимости машины Тьюринга

Проблема самоприменимости машины Тьюринга формулируется так:

Размером задачи является характеристика, которая определяет

Свойство вычислимости алгоритма означает, что

Свойство дискретности алгоритма означает, что

Свойство конечности алгоритма означает, что

Свойство результативности алгоритма означает, что

Функция f(n) ecть О(g(n)), если

Частично-рекурсивной называется функция, построенная из простейших с помощью

Частично-рекурсивные фунции – это модель алгоритма, которая

Число 2, выраженное с помощью оператора суперпозиции через нуль-функцию и функцию следования имеет вид

Экспоненциальная сложность алгоритма – это сложность алгоритма, у которого зависимость временной и емкостной сложности от размера задачи, имеет вид

Алгоритм "быстрая сортировка" в общем случае более быстрый, чем сортировка вставками:

В терминах машин Тьюринга детерминированность отражается в том, что программа МТ является отображением:

Детерминированность алгоритма заключается в том, что на каждом шаге имеется лишь одно допустимое действие, зависящее от входных данных и от текущего внутреннего состояния:

Для недетерминированных алгоритмов обычно рассматривают только одну форму задач - задачи распознавания языков:

Для списка общего вида вычислительная сложность "быстрой" сортировки равна O(n):

Емкостная сложность алгоритма - объем памяти, требуемый для решения задачи:

Множество всех слов над алфавитом A обозначается как A*:

Наихудшим сценарием для "быстрой" сортировки будет тот, при котором центральный элемент все время попадает в одноэлементный подсписок, а все прочие элементы остаются во втором подсписке:

Недетерминированная машина Тьюринга является чисто теоретическим понятием:

НМТ допускает входное слово x, если только одна последовательность конфигураций приводит к допускающему состоянию:

Операция умножения требует большего времени, чем операция сложения:

При оценке сложности алгоритма обычно рассматривают его сложность в лучшем случае:

Существуют задачи, для которых не существует самого быстрого алгоритма:

Теорема Блюма утверждает, что ускорение возможно для любой задачи:

Формальная система записи алгоритма адекватна реальной системе команд процессора:

Алгоритмическую сложность можно определить как зависимость времени исполнения алгоритма от длины входных данных:

В Гамильтоновом цикле нужно выйти из какой-то вершины и вернуться в нее таким образом, чтобы ни в какой промежуточной вершине не побывать дважды:

В параметрически-зависимых по трудоемкости алгоритмах трудоемкость определяется размерностью входа:

Для всех функций f(n) = 1/n, f(n) = 7, f(n) = 2 · n + 12, f(n) = n · ln (n) будет справедлива оценка О(n):

Задача о коммивояжере относится к задачам класса Р:

Задача поиска нужной фамилии в телефонном справочнике имеет логарифмическую сложность:

Запись O(g(n)) обозначает класс функций таких, что все они растут не быстрее, чем функция g(n) с точностью до постоянного множителя: