Главная / Алгоритмы и дискретные структуры / Алгоритмы и теория вычислений

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

Правильные ответы выделены зелёным цветом.
Все ответы: Курс посвящен знакомству с такими фундаментальными математическими понятиями, как вычисления и доказательство.

Смотрите также:

Программирование

Традиционный набор операций в исчислении высказываний включает

(1) дизъюнкцию

(2) конъюнкцию

(3) импликацию

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

(1) функцией

(2) алгоритмом

(3) графом переходов

Цифровая техника обрабатывает

(1) дискретные сигналы

(2) непрерывные сигналы

(3) аналоговые сигналы

Определение формальной системы включает в себя

(1) описание исходных объектов

(2) описание правил построения новых объектов на основе исходных и ранее построенных

(3) описание конечных автоматов

Стандартное правило вывода состоит из

(1) посылки

(2) заключения

(3) алфавита

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

(1) результативностью

(2) массовостью

(3) однозначностью результата

Конечный автомат:

(1) является общим случаем машины Тьюринга

(2) является частным случаем машины Тьюринга

(3) не имеет связи с машинами Тьюринга

Объектами формальной системы могут быть

(1) числа

(2) формулы

(3) графы

Метатеорема - это

(1) утверждение о свойствах некоторой теории

(2) утверждение о свойствах исчисления предикатов

(3) утверждение о свойствах конечных автоматов

Классификация алгоритмических моделей включает следующие группы:

(1) абстрактные машины

(2) вычислимые функции

(3) комбинаторные модели

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

(1) таблица переходов

(2) граф переходов

(3) функция переходов

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

(1) грамматика языка программирования

(2) шахматы

(3) конструктор "LEGO"

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

(1) общности

(2) существования

(3) незначимости

Если машина Тьюринга зацикливается на некотором слове, это означает, что:

(1) машина не имеет точки останова для этого слова

(2) машина работает с ошибками

(3) функция, вычисляемая машиной Тьюринга, на данном слове не определена

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

(1) его таблица переходов содержит одну строку

(2) его граф переходов имеет одну вершину

(3) его граф переходов не имеет вершин

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

(1) множество исходных объектов дискретно

(2) на каждом шаге работы системы применяется одно из конечного числа правил вывода

(3) на каждом шаге работы системы применяется конечное число правил вывода

Исчисления предикатов

(1) включает в себя ИВ

(2) включено в ИВ

(3) не связано с ИВ

К операциям над машинами Тьюринга относятся:

(1) суперпозиция машин Тьюринга

(2) операция условного перехода

(3) извлечение корня из машины Тьюринга

Отношение эквивалентности

(1) рефлексивно

(2) симметрично

(3) транзитивно

Существенность в формальной системе - это

(1) семантическое понятие

(2) синтаксическое понятие

(3) одно из правил вывода

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

(1) modus ponens

(2) правило введения квантора общности

(3) правило введения квантора существования

Головка машины Тьюринга имеет возможность:

(1) чтения информации с ленты

(2) записи информации на ленту

(3) перемещения по ленте только в одном направлении

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

(1) процедура минимизации автоматов

(2) процедура максимизации автоматов

(3) усреднение автоматов

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

(1) вычислимое отношение посылок и заключений

(2) логический автомат

(3) усреднение автоматов

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

(1) моделью формальной системы

(2) интерпретацией формальной системы

(3) областью значений формальной системы

Примером примитивно-рекурсивной функции является:

(1) константа ноль

(2) функция прибавления единицы

(3) функция тождества

Конечный автомат, осуществляющий побитовое сложение двух чисел

(1) является логическим автоматом

(2) при увеличении размерности складываемых чисел не требует увеличения оперативной памяти

(3) при сокращении размерности складываемых чисел освобождает неиспользуемую оперативную память

Если А - это алфавит, то некоторое подмножество множества всех слов алфавита А называется

(1) расширенным алфавитом

(2) языком алфавита А

(3) сокращением алфавита А

Теорема Гёделя о полноте исчисления предикатов утверждает, что

(1) исчисление предикатов является неполным

(2) исчисление предикатов является полным

(3) исчисление предикатов разрешимо

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

(1) выводу о несостоятельности теории рекурсивных функций

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

(3) выводу о тождественности операций суперпозиции и рекурсии

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

(1) способен распознавать все те же множества, что и машина Тьюринга

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

(3) не способен распознать ни одно множество, распознаваемое машиной Тьюринга

В определении формальной грамматики отсутствует

(1) терминальное множество

(2) теоретическое множество

(3) нетерминальное множество

Литера в методе резолюций - это

(1) буква

(2) отрицание буквы

(3) цифра

Тезис Тьюринга гласит:

(1) ни для одной вычислимой функции не существует машины Тьюринга, ее вычисляющей

(2) для каждой вычислимой функции существует машина Тьюринга, ее вычисляющая

(3) для любой произвольной функции существует машина Тьюринга, ее вычисляющая

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

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

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

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

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

Две грамматики эквивалентны, если

(1) языки, выводимые данными грамматиками, совпадают

(2) языки, выводимые данными грамматиками, не совпадают

(3) обе грамматики имеют один и тот же терминальный алфавит

(4) обе грамматики имеют один и тот же нетерминальный алфавит

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

(1) дизъюнктивная нормальная форма

(2) декомпозиция нормальной формы

(3) декомпозиционная неполная форма

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

(1) всякая функция, вычислимая по Тьюрингу, вычислима по Маркову

(2) всякая функция, вычислимая по Маркову, вычислима по Тьюрингу

(3) всякое произвольно взятое уравнение вычислимо по Тьюрингу

Результатом конкатенации двух множеств М1 и М2 является множество М3, элементы которого получаются:

(1) из исходных приписыванием элементов множества М2 к элементам множества М1 справа

(2) из исходных приписыванием элементов множества М2 к элементам множества М1 слева

(3) заменой элементов множества М1 элементами множества М2

Множество правил в формальной грамматике

(1) всегда конечно

(2) бесконечно

(3) необязательно конечно

Метод резолюций по своему смыслу более всего близок методу

(1) математической индукции

(2) доказательства от противного

(3) математической аппроксимации

Множество корней некоторого уравнения является примером

(1) перечислимого множества

(2) разрешимого множества

(3) рекурсивного множества

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

(1) перечислимым

(2) регулярным

(3) разрешимым

Грамматика типа 2 согласно классификации грамматик Хомского называется:

(1) контекстной

(2) контекстно-свободной

(3) укорачивающей

К формулам конъюнктивного типа относятся

(1) отрицание дизъюнкции

(2) отрицание имликации

(3) двойное отрицание

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

(1) всякое разрешимое множество перечислимо

(2) всякое перечислимое множество разрешимо

(3) существует множество, которое перечислимо, но неразрешимо

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

(1) дуг

(2) позиций

(3) переходов

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

(1) 1

(2) 2

(3) 3

Синонимом названия операции конъюнкции является

(1) логическое "или"

(2) логическое "и"

(3) логическое "если"

Основными свойствами алгоритма являются:

(1) массовость

(2) результативность

(3) однозначность результата

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

(1) кодовый замок

(2) радио

(3) лифт

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

(1) теоремой

(2) рекурсией

(3) аксиомой

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

(1) modus ponens

(2) modens ponus

(3) ponus modens

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

(1) данные

(2) память

(3) элементарный шаг

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

(1) входного алфавита

(2) выходного алфавита

(3) алфавита состояний

(4) функции переходов

(5) функции выходов

Правила построения новых объектов в формальной системе называются

(1) правилами вывода

(2) правилами ввода

(3) правилами выхода

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

(1) базисом индукции

(2) индукционным шагом

(3) леммой индукции

Представителями класса моделей "Абстрактные машины" являются:

(1) машина Тьюринга

(2) машина Поста

(3) машина Джексона

В определении конечный автомат присутствуют:

(1) три алфавита и две функции

(2) три функции и два алфавита

(3) три алфавита и три функции

Всякая формальная система задает

(1) перечислимое множество

(2) рекурсивное множество

(3) разрешимое множество

Если переменная х не связана в формуле F, то она называется

(1) чистой

(2) свободной

(3) несвязанной

Машина Тьюринга может быть задана:

(1) списком команд

(2) таблицей

(3) графом переходов

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

(1) они состоят из одного и того же входного алфавита

(2) они реализуют одно и то же автоматное отображение

(3) по одной и той же входной последовательности они выдают одну и туже выходную последовательность

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

(1) строгое соблюдение правил вывода

(2) требование явного описания правил вывода

(3) однозначность правил вывода

(4) комбинаторность правил вывода

Формулы в исчислении предикатов образуются с помощью

(1) переменных

(2) кванторов

(3) знаков логических операций

К особенностям программирования машин Тьюринга относятся:

(1) отсутствие доступа по адресу

(2) ограниченные возможности запоминания

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

Конечный автомат называется логическим, если

(1) его алфавиты - это двоичные наборы

(2) его функции - функции двух аргументов

(3) его алфавиты - упорядоченные тройки элементов

С синтаксической точки зрения все записанное в формальной системе

(1) существенно

(2) несущественно

(3) бессмысленно

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

(1) теоремой

(2) леммой

(3) аксиомой

Машина Тьюринга и машина Поста относятся к классу:

(1) легковых машин

(2) абстрактных машин

(3) комбинаторных моделей

Машина Тьюринга, описывающая конечный автомат,

(1) имеет головку, которая движется по ленте лишь в одном направлении

(2) не имеет возможности чтения записанного им на ленте

(3) имеет головку, которая движется по ленте в обоих направлениях

Множество аксиом формальной системы

(1) должно быть разрешимым

(2) должно быть конечным

(3) не должно быть конечным

(4) не должно быть разрешимым

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

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

(2) любая теорема формальной системы является в этой области истинной

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

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

(1) оператора языка программирования

(2) примитивно-рекурсивной функции

(3) алфавита языка программирования

При побитовом сложении двух чисел с помощью конечного автомата используемая память

(1) варьируется в зависимости от длин складываемых чисел

(2) постоянна и равна 1 бит на перенос разряда

(3) постоянна и равна памяти, выделенной под большее из слагаемых

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

(1) множество всех слов алфавита А

(2) подмножество множества всех слов алфавита А

(3) подмножество алфавита А

Исчисление предикатов называется разрешимым, если

(1) не существует такого алгоритма, который для любой формулы покажет, выводима она, или нет

(2) существует такой алгоритм, который для любой формулы покажет, выводима она, или нет

(3) оно полно

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

(1) определены во всех точках

(2) определены не во всех точках

(3) невычислимы в рамках теории рекурсивных функций

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

(1) непериодичным

(2) периодичным

(3) бинарным

Язык, порождаемый формальной грамматикой - это

(1) подмножество множества всех слов нетерминального алфавита

(2) множество всех слов в терминальном алфавите ФГ, выводимых из ее аксиомы

(3) подмножество множества всех слов терминального алфавита

Пустой дизъюнкт в методе резолюций обозначается

(1) квадратом

(2) треугольником

(3) кругом

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

(1) том, что теорема доказывается, а тезис - нет

(2) том, что в теореме все используемые понятия и термины строго определены, а в тезисе - нет

(3) написании - по сути это идентичные понятия

Конечный автомат:

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

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

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

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

Если один и тот же язык выводим несколькими грамматиками, то такие грамматики называются:

(1) эквивалентными

(2) похожими

(3) равными

Контрарная пара в методе резолюций - это

(1) операции конъюнкции и дизъюнкции

(2) операции отрицания и импликации

(3) литера и ее отрицание

Если для любого произвольно взятого элемента можно определить, принадлежит он некоторому множеству или нет, то такое множество называется:

(1) определимым

(2) элементарным

(3) разрешимым

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

(1) равна произведению мощностей исходных множеств

(2) равна сумме мощностей исходных множеств

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

Согласно классификации Хомского все формальные грамматики делятся на:

(1) 2 типа

(2) 3 типа

(3) 4 типа

Обязательным требованием метода резолюций является приведение исходной формулы к

(1) контрарной паре

(2) дизъюнктивная нормальная форма

(3) конъюнктивной нормальная форма

Множество степеней тройки является примером

(1) перечислимого множества

(2) рекурсивного множества

(3) разрешимого множества

Множество распознаваемо конечным автоматом, если

(1) оно перечислимо

(2) оно разрешимо

(3) и только если оно регулярно

Грамматика типа 3 согласно классификации грамматик Хомского называется:

(1) нерегулярной

(2) контекстно-свободной

(3) регулярной

К формулам дизъюнктивного типа относятся

(1) отрицание конъюнкции

(2) дизъюнкция

(3) импликация

Свойствами алгоритма не являются:

(1) узкая специализация

(2) неоднозначность результата

(3) нерезультативность

Сеть Петри представляет собой:

(1) дерево

(2) линейный протокол

(3) линейную последовательность

Неукорачивающая грамматика согласно классификации Хомского относится к классу

(1) 1

(2) 2

(3) 3

Синонимом названия операции импликации является

(1) логическое "и"

(2) логическое "если"

(3) логическое "не"

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

(1) результативностью

(2) массовостью

(3) однозначностью результата

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

(1) радио

(2) калькулятор

(3) кодовый замок

(4) лифт

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

(1) заключение-посылка

(2) условия-действия

(3) посылки-заключения

(4) действие-условие

Принцип рассуждения от следствия к причине называется

(1) дедукция

(2) абдукция

(3) редукция

Детерминированность в теории алгоритма означает:

(1) правило инициации

(2) определение следующего шага

(3) правило окончания

В определении конечного автомата не содержится

(1) функции выходов

(2) функции входов

(3) функции переходов

Типы данных в языках программирования введены для

(1) интереса

(2) устранения неоднозначностей и строгой формализации языка

(3) отличия одного языка программирования от другого

Индукционный шаг в методе математической индукции - это

(1) доказательство того, что утверждение верно для n=1

(2) доказательство того, что утверждение верно для n=k

(3) доказательство того, то утверждение верно для n=k+1 при доказанной истинности для n=k

Машина Тьюринга состоит из:

(1) бесконечной в обе стороны ленты

(2) управляющего устройства

(3) головки, которая может считывать символы с ленты и записывать их на ленту

Автоматический железнодорожный переезд является примером

(1) аналогового устройства

(2) цифрового устройства

(3) аналогово-цифрового устройства

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

(1) кулинарный рецепт

(2) шашки

(3) машина Тьюринга

Терм - это

(1) символ переменной

(2) n-арная функция нескольких переменных, где каждая переменная - это терм

(3) одно из правил вывода исчисления предикатов

Граф,задающий машину Тьюринга, обладает следующими свойствами::

(1) это ориентированный граф

(2) это мультиграф

(3) на ребрах графа записывается формула перехода машины из состояния в состояние

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

(1) ни для какого состояния одного автомата не найдется неотличимого от него состояния другого автомата

(2) для любого состояния одного автомата найдется неотличимое от него состояние другого автомата

(3) хотя бы для одного состояния одного автомата найдется неотличимое от него состояние другого автомата

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

(1) осмысление

(2) интерпретация

(3) интерполяция

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

(1) аксиом ИВ

(2) аксиом для кванторов общности и существования

(3) аксиом для логических операций

Характерными свойствами головки машины Тьюринга являются:

(1) возможность перемещения в обе стороны

(2) элементарное перемещение головки равно одной ячейке

(3) элементарное перемещение головки равно задаваемому оператором числу ячеек

Двоичные наборы, являющиеся алфавитами логического автомата, представляют собой

(1) наборы из нулей и единиц

(2) наборы двоек из нулей и единиц

(3) наборы троек из нулей и единиц

Формальная система определяется

(1) конечным алфавитом

(2) конечным набором исходных объектов

(3) множеством правил вывода

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

(1) метатеоремой

(2) теоремой

(3) метааксиомой

Говоря об абстрактных машинах, чаще всего имеют в виду машины Тьюринга, потому что:

(1) работы по ним были раньше других опубликованы

(2) у них благозвучное название

(3) других абстрактных машин не существует

Конечный автомат называется "конечным", потому что

(1) имеет конечное число состояний

(2) состоит из конечного числа алфавитов

(3) имеет конечное число описывающих его машин Тьюринга

В выводе в контексте формальной системы каждое слово - это либо

(1) аксиома

(2) выведенное слово из аксиомы

(3) выведенное слово из ранее выведенного слова

Формула называется общезначимой, если она

(1) истинна в любой предметной области

(2) истинна в некоторой предметной области

(3) она имеет интерпретацию

Суперпозиция - это

(1) общий случай рекурсии

(2) частный случай рекурсии

(3) то же самое, что и рекурсия

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

(1) один разряд

(2) два разряда

(3) три разряда

Формальная грамматика - это четверка, состоящая из

(1) терминального алфавита

(2) нетерминального алфавита

(3) множества правил

(4) множества исключений из правил

(5) аксиомы

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

(1) исчисление предикатов разрешимо

(2) исчисление предикатов неразрешимо

(3) исчисление предикатов полно

Тезис Чорча гласит:

(1) всякая частично-рекурсивная функция является вычислимой

(2) всякая вычислимая функция является частично-рекурсивной

(3) никакая вычислимая функция не является частично-рекурсивной

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

(1) периодичным

(2) непериодичным

(3) бинарным

Может ли быть выводимым один и тот же язык в контексте формальной грамматики разными грамматиками?

(1) да

(2) нет

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

(1) конъюнктивной нормальная форма

(2) конечная нормальная форма

(3) конечная неполная форма

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

(1) любая частично-рекурсивная функция вычислима по Тьюрингу

(2) всякая вычислимая по Тьюрингу функция является частично-рекурсивной

(3) определения понятия алгоритма по Тьюрингу и в терминах теории рекурсивных функций эквивалентны

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

(1) конечное число его состояний

(2) конечное число символов во входном алфавите

(3) конечное число символов в выходном алфавите

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

(1) цепочками

(2) переменными

(3) константами

Идея метода резолюций состоит в

(1) доказательстве тождественной ложности некоторой формулы

(2) доказательстве тождественной истинности некоторой формулы

(3) тождественных преобразованиях некоторой формулы с целью получения в итоге пустого дизъюнкта

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

(1) вычислимым

(2) перечислимым

(3) определимым

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

(1) обединения

(2) конкатенации

(3) итерации

Синонимичное название грамматики типа 1 в классификации грамматик Хомского - это

(1) контекстная

(2) неукорачивающая

(3) неукорачивающаяся

Метод аналитических таблиц в отличие от метода резолюций

(1) не требует приведения формулы к конъюнктивной нормальной форме

(2) требует приведение формулы к конъюнктивной нормальной форме

(3) требует приведения формулы к дизъюнктивной нормальной форме

Множество называется перечислимым, если

(1) оно является областью значений некоторой всюду определенной вычислимой функции

(2) оно является областью определения некоторой вычислимой функции

(3) существует алгоритм, определяющий для каждого произвольного элемента признак принадлежность данному множеству

Множество, разрешимое конечным автоматом, характеризуется:

(1) наличием автомата, который его распознает

(2) отсутствием автомата, который его распознает

(3) регулярностью

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

(1) 1

(2) 2

(3) 3

К формулам конъюнктивного типа не относится

(1) дизъюнкция

(2) отрицание дизъюнкции

(3) отрицание импликации

(4) импликация

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

(1) алгоритм завершит работу через конечное число шагов

(2) алгоритм не завершит работу через конечное число шагов

(3) алгоритм применим для решения широкого круга задач

Сеть Петри в вычислительном плане:

(1) сильнее конечного автомата

(2) слабее машины Тьюринга

(3) слабее конечного автомата

(4) сильнее машины Тьюринга

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

(1) 1

(2) 2

(3) 3