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

Количество вопросов - 144

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Терм - это

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

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

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

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

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