Основы теории алгоритмов

Конечному автомату соответствует грамматика, порождающая
машину Тьюринга
регулярный язык
язык программирования
словарь машины
Временные или пространственные характеристики процесса вычисления называются
интерпретацией системы
представлением системы
классом сложности
вычислительными ресурсами
Если A и B - рекурсивные множества, то рекурсивны также множества I.image029.gif II.image030.gif III.image031.gif
только I и III
только I и II
только II
I, II и III
В системе Пеано единственным неопределимым отношением является
image091.gif
image093.gif
image090.gif
image092.gif
Функция image017.gifявляется: 1) частично вычислимой; 2) примитивно рекурсивной; 3) частично рекурсивной
1 и 3
1
2 и 3
1 и 2
Язык, на котором описывается другой язык, называется
автоматным языком
метаязыком
формальной системой
формулой языка Ъ
Челночный алгоритм является алгоритмом
марковским
регулярным
дискретным
нелинейным
Функция image043.gifимеет Гёделевский номер, равный
4
3
2
1
Существуют три основных класса фраз: имена, предложения и
функторы
кванторы
предикаты
дизъюнкты
Функция, вычисляемая некоторой машиной Тьюринга с входным и выходным алфавитами, называется
обратной
вычислимой
характеристической
рекурсивной
Фразы, соединяемые функтором, называются
предложениями
формульными
регулярными
аргументами
Система Пеано содержит аксиом
3
4
2
5
Входной алфавит определяется как
image097.gif
image094.gif
image096.gif
image095.gif
Средство для соединения фраз для преобразования других фраз называется
метаязыком
функтором
конъюнкцией
грамматикой
Множество ________ тогда и только тогда, когда оно является _______ некоторой вычислимой функции
перечислимо, областью определения
разрешимо, областью определения
перечислимо, множеством значений
разрешимо, множеством значений
Марковский алгоритм - это алгоритм
стохастический
нелинейный
недетерминированный
нормальный
Входят в алфавит формального логического языка символы
image089.gif
image087.gif
image088.gif
image086.gif
Функция, полученная из вычислимой с помощью рекурсии, является
частично рекурсивной
дифференцируемой
примитивно рекурсивной
вычислимой
Множество всех истинных утверждений языка L является
разрешимым и перечислимым
разрешимым, но неперечислимым
неразрешимым и неперечислимым
неразрешимым, но перечислимым
Если множество неперечислимо, то оно _______ областью определения и ______ множеством значений всюду определенной вычислимой функции
может быть, может быть
не может быть, не может быть
не может быть, может быть
может быть, не может быть
Автомат, однократно считывающий входную строку слева направо, называется
дискретным
МП-автоматом
конечным
элементарным
Функция, вычислимая по Тьюрингу, является
частично рекурсивной
характеристической
общерекурсивной
примитивно рекурсивной
Полнота - это условие, что для любого утверждения s одно из утверждений s и Øs
истинно
ложно
опровержимо
доказуемо
Дополнение к области определения некоторой вычислимой функции _________ рекурсивно перечислимым
должно быть
разъединено с
не может быть
может не быть
Идея использования рекурсии для решения задач, связанных с основаниями математики, предложена
Аль Хорезми
Гильбертом
Тьюрингом
Пеано
Формальная грамматика, позволяющая построить любую правильную цепочку символов, называется грамматикой
автоматной
порождающей
нормальной
регулярной
Не существует формальной системы арифметики, удовлетворяющей условиям полноты и противоречивости согласно
тезису Черча
теореме Геделя
теории Гильберта
теореме Поста
Внутренним алфавитом машины Тьюринга называется
множество команд машины
множество конфигураций машины
множеством состояний машины
символы, записанные на ленте
Если image018.gifи рекурсия проводится по переменной image012.gif, то функция image020.gifравна
m+y
m+x
2+m
m+1
Если image021.gifи рекурсия проводится по переменной image022.gif, то функция image023.gifравна
image012.gif
image025.gif
image024.gif
image017.gif
Функция image068.gifимеет гёделевский номер, равный
5
3
2
4
Способ видения объектов формальных систем как конкретных объектов при условии, что содержательные объекты сохраняют структуру формальных, называется
изоморфизмом системы
трансформацией системы
представлением системы
интерпретацией системы
Если image001.gif, то функция image002.gifв рекуррентной формуле равна
image004.gif
1
image003.gif
image005.gif
Множество всевозможных осмысленных утверждений языка является
рекурсивно перечислимым
креативным
неперечислимым
рекурсивным
Утверждение image081.gifформально записывается как
image082.gif
image084.gif
image085.gif
image083.gif
Композиция image043.gifи image044.gifравна
image024.gif
image045.gif
image046.gif
1
Не сохраняет примитивную рекурсивность оператор
сдвига
минимизации
рекурсии
подстановки
Если image062.gifи рекурсия проводится по image012.gif, то функция image058.gifравна
image064.gif
image022.gif
zy
image065.gif
В любой рекурсивно аксиоматизированной формальной системе множество доказуемых утверждений
рекурсивно перечислимо
нерекурсивно
разрешимо
неперечислимо
Если image048.gifи рекурсия проводится по image012.gif, то функция image026.gifравна
image052.gif
image053.gif
t+y
t+x
Множество аксиом вместе с явным определением доказательства составляют
рекурсивное множество
формальную систему
теорию алгоритмов
машину Тьюринга
Множество истинных утверждений
не выводится из системы аксиом
выводится из системы аксиом
перечисляет все системы аксиом
носит название системы аксиом
Символы, которые машина Тьюринга читает и пишет на ленте, образуют
конфигурацию
выражения
команды
алфавит
В рекурсивно аксиоматизированной формальной системе, в которой все доказуемые утверждения истинны, существует истинное утверждение s, так что: 1) s опровержимо; 2) Øs опровержимо
1 и 2
1
2
ни 1, ни 2
Команда машины Тьюринга состоит из элементарных действий
конечного числа
трех
любого числа
двух
Если множество нерекурсивно, то оно _______ областью определения и ______ множеством значений всюду определенной вычислимой функции
не может быть, может быть
может быть, не может быть
не может быть, не может быть
может быть, может быть
Если image018.gifи рекурсия проводится по переменной image012.gif, то функция image019.gifравна
x+1
y+1
x
y
Всякое непустое ______ множество является _________ некоторой всюду определенной вычислимой функции
рекурсивное, областью определения
рекурсивно перечислимое, множеством значений
продуктивное, множеством значений
креативное, областью определения
Если image021.gifи рекурсия проводится по переменной image022.gif, то функция image026.gifравна
ty
t+x+y+z
image028.gif
image027.gif
Если image010.gif, то функция image002.gif(n,m) в рекуррентной формуле равна
(m+n)/2
m+n-1
m+n+1
2m