Алгоритмы и теория вычислений

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

• результативностью
• однозначностью результата
• (Правильный ответ) массовостью

Отличие тезиса от теоремы заключается в

• (Правильный ответ) том, что в теореме все используемые понятия и термины строго определены, а в тезисе — нет
• написании — по сути это идентичные понятия
• том, что теорема доказывается, а тезис — нет

Сходимость алгоритма означает, что

• алгоритм не завершит работу через конечное число шагов
• (Правильный ответ) алгоритм завершит работу через конечное число шагов
• алгоритм применим для решения широкого круга задач

Выберите верное:

• (Правильный ответ) всякое разрешимое множество перечислимо
• (Правильный ответ) существует множество, которое перечислимо, но неразрешимо
• всякое перечислимое множество разрешимо

Класс частично-рекурсивных функций образуют функции, которые

• (Правильный ответ) определены не во всех точках
• невычислимы в рамках теории рекурсивных функций
• определены во всех точках

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

• (Правильный ответ) алгоритмом
• функцией
• графом переходов

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

• (Правильный ответ) однозначностью результата
• результативностью
• массовостью

Схема определения понятия «Алгоритм» включает:

• (Правильный ответ) память
• (Правильный ответ) элементарный шаг
• (Правильный ответ) данные

Распознающий конечный автомат

• способен распознавать все те же множества, что и машина Тьюринга
• (Правильный ответ) способен распознавать часть множеств, распознаваемых машиной Тьюринга
• не способен распознать ни одно множество, распознаваемое машиной Тьюринга

Множество слов в произвольном алфавите, которое может быть получено из элементарных множеств путем конечного числа применений операций объединения, конкатенации, итерации, называется:

• (Правильный ответ) регулярным
• перечислимым
• разрешимым

Множество вида (010010010010…) является:

• (Правильный ответ) бинарным
• (Правильный ответ) периодичным
• непериодичным

Причиной, по которой конечный автомат не способен распознавать непериодичные последовательности, является:

• конечное число символов во входном алфавите
• (Правильный ответ) конечное число его состояний
• конечное число символов в выходном алфавите

Два конечных автомата называются эквивалентными, если

• (Правильный ответ) они реализуют одно и то же автоматное отображение
• они состоят из одного и того же входного алфавита
• (Правильный ответ) по одной и той же входной последовательности они выдают одну и туже выходную последовательность

Одним из способов определения эквивалентности конечных автоматов является:

• процедура максимизации автоматов
• усреднение автоматов
• (Правильный ответ) процедура минимизации автоматов

Пусть М1 и М2 — некоторые множества, с соответствующими мощностями. Тогда мощность множества М3, полученного путем конкатенации множеств М1 и М2 будет

• равна произведению мощностей исходных множеств
• (Правильный ответ) не больше произведения мощностей исходных множеств
• равна сумме мощностей исходных множеств

Машина Тьюринга:

• неспособна распознавать непериодичные последовательности
• (Правильный ответ) способна распознавать периодичные последовательности
• неспособна распознавать периодичные последовательности
• (Правильный ответ) способна распознавать непериодичные последовательности

Множество вида (01001000100001…) является:

• (Правильный ответ) непериодичным
• (Правильный ответ) бинарным
• периодичным

Контекстно-свободная грамматика согласно классификации Хомского относится к классу

• 1
• (Правильный ответ) 2
• 3

Регулярная грамматика согласно классификации Хомского относится к классу

• (Правильный ответ) 3
• 1
• 2

В контексте формальной грамматики слова алфавита называются:

• (Правильный ответ) цепочками
• переменными
• константами

Наполнение формальной системы смыслом называется

• осмысление
• (Правильный ответ) интерпретация
• интерполяция

Формальность формальной системы означает

• (Правильный ответ) строгое соблюдение правил вывода
• (Правильный ответ) комбинаторность правил вывода
• (Правильный ответ) требование явного описания правил вывода
• (Правильный ответ) однозначность правил вывода

Пусть А — некоторый алфавит. Тогда языком алфавита А называется

• множество всех слов алфавита А
• (Правильный ответ) подмножество множества всех слов алфавита А
• подмножество алфавита А

Предметная область называется моделью, если

• ни одна из теорем формальной системы не является в этой области истинной
• (Правильный ответ) любая теорема формальной системы является в этой области истинной
• хотя бы одна теорема формальной системы является в этой области истинной

Теорема Чёрча утверждает, что

• исчисление предикатов полно
• исчисление предикатов разрешимо
• (Правильный ответ) исчисление предикатов неразрешимо

Аббревиатура КНФ в контексте логических исчислений — это

• конечная неполная форма
• конечная нормальная форма
• (Правильный ответ) конъюнктивной нормальная форма

Утверждение об объектах исчисления предикатов, подлежащее доказательству, называется

• леммой
• (Правильный ответ) теоремой
• аксиомой

Стандартное правило вывода обычно называют

• ponus modens
• (Правильный ответ) modus ponens
• modens ponus

Утверждение о некоторой теореме исчисления предикатов, подлежащее доказательству, называется

• метааксиомой
• (Правильный ответ) метатеоремой
• теоремой

Проверка истинности утверждения на первом шаге при n=1 в методе математической индукции называется

• (Правильный ответ) базисом индукции
• индукционным шагом
• леммой индукции

В исчисления предикатов существуют кванторы

• незначимости
• (Правильный ответ) существования
• (Правильный ответ) общности

Аксиомы исчисления предикатов формируются из

• (Правильный ответ) аксиом ИВ
• аксиом для логических операций
• (Правильный ответ) аксиом для кванторов общности и существования

Правила вывода исчисления предикатов формируются из

• (Правильный ответ) правило введения квантора общности
• (Правильный ответ) modus ponens
• (Правильный ответ) правило введения квантора существования

Аббревиатура ДНФ в контексте логических исчислений — это

• декомпозиционная неполная форма
• декомпозиция нормальной формы
• (Правильный ответ) дизъюнктивная нормальная форма

Сеть Петри — это двудольный граф, состоящий из:

• (Правильный ответ) переходов
• (Правильный ответ) дуг
• (Правильный ответ) позиций

Примером дискретного устройства является:

• (Правильный ответ) лифт
• радио
• (Правильный ответ) калькулятор
• (Правильный ответ) кодовый замок

Примером формальной системы является

• (Правильный ответ) машина Тьюринга
• (Правильный ответ) кулинарный рецепт

li>(Правильный ответ) шашки