Алгоритмы и теория вычислений - ответы
Количество вопросов - 144
Суперпозиция - это
С синтаксической точки зрения все записанное в формальной системе
К особенностям программирования машин Тьюринга относятся:
Аббревиатура КНФ в контексте логических исчислений - это
Формулы в исчислении предикатов образуются с помощью
Машина Тьюринга состоит из:
Результатом конкатенации двух множеств М1 и М2 является множество М3, элементы которого получаются:
Два конечных автомата называются эквивалентными, если
Конечный автомат:
Множество правил в формальной грамматике
Примером формальной системы является
Головка машины Тьюринга имеет возможность:
Метод резолюций по своему смыслу более всего близок методу
В определении формальной грамматики отсутствует
Контрарная пара в методе резолюций - это
Предметная область называется моделью, если
К формулам конъюнктивного типа относятся
Если один и тот же язык выводим несколькими грамматиками, то такие грамматики называются:
Тезис Чорча гласит:
Неукорачивающая грамматика согласно классификации Хомского относится к классу
Свойство алгоритма, заключающееся в возможности его применения к бесконечно большому множеству данных, называется:
Если для любого произвольно взятого элемента можно определить, принадлежит он некоторому множеству или нет, то такое множество называется:
Утверждение об объектах исчисления предикатов, подлежащее доказательству, называется
Проверка истинности утверждения на первом шаге при n=1 в методе математической индукции называется
Выберите верное:
Множество степеней тройки является примером
Если А - это алфавит, то некоторое подмножество множества всех слов алфавита А называется
Синонимом названия операции импликации является
Машина Тьюринга может быть задана:
Машина Тьюринга, описывающая конечный автомат,
Некоторая процедура, состоящая из конечного числа шагов, строго определенных на конкретном наборе данных, называется:
Свойство алгоритма, заключающееся в том, что при одних и тех же данных получается один и тот же результат, называется:
Классификация алгоритмических моделей включает следующие группы:
Если машина Тьюринга зацикливается на некотором слове, это означает, что:
К операциям над машинами Тьюринга относятся:
Машина Тьюринга и машина Поста относятся к классу:
Примером примитивно-рекурсивной функции является:
Выберите верное:
Множество, которое может быть порождено некоторой вычислимой функцией, называется:
Множество корней некоторого уравнения является примером
Примером дискретного устройства является:
Автоматический железнодорожный переезд является примером
Отношение эквивалентности
Одним из способов определения эквивалентности конечных автоматов является:
При побитовом сложении двух чисел с помощью конечного автомата используемая память
Распознающий конечный автомат
Причиной, по которой конечный автомат не способен распознавать непериодичные последовательности, является:
Пусть М1 и М2 - некоторые множества, с соответствующими мощностями. Тогда мощность множества М3, полученного путем конкатенации множеств М1 и М2 будет
Множество, разрешимое конечным автоматом, характеризуется:
Сеть Петри - это двудольный граф, состоящий из:
Правила формальной системы имеют вид
Правила построения новых объектов в формальной системе называются
Формальность формальной системы означает
Формальная система определяется
Множество аксиом формальной системы
Может ли быть выводимым один и тот же язык в контексте формальной грамматики разными грамматиками?
В контексте формальной грамматики слова алфавита называются:
Согласно классификации Хомского все формальные грамматики делятся на:
Грамматика типа 2 согласно классификации грамматик Хомского называется:
Контекстная грамматика согласно классификации Хомского относится к классу
Традиционный набор операций в исчислении высказываний включает
Стандартное правило вывода обычно называют
Индукционный шаг в методе математической индукции - это
В исчисления предикатов существуют кванторы
Аксиомы исчисления предикатов формируются из
Утверждение о некоторой теореме исчисления предикатов, подлежащее доказательству, называется
Формула называется общезначимой, если она
Исчисление предикатов называется разрешимым, если
Аббревиатура ДНФ в контексте логических исчислений - это
Обязательным требованием метода резолюций является приведение исходной формулы к
К формулам дизъюнктивного типа относятся
Конечный автомат называется "конечным", потому что
Конечный автомат называется логическим, если
Типы данных в языках программирования введены для
Правило вывода в формальной системе - это
Множество распознаваемо конечным автоматом, если
Две грамматики эквивалентны, если
Литера в методе резолюций - это
Идея метода резолюций состоит в
Оператор суперпозиции функций является примером:
Грамматика типа 3 согласно классификации грамматик Хомского называется:
Говоря об абстрактных машинах, чаще всего имеют в виду машины Тьюринга, потому что:
Всякая формальная система задает
Добавление оператора неограниченной минимизации к классу примитивно-рекурсивных функций приводит к
Сходимость алгоритма означает, что
Сеть Петри в вычислительном плане:
Множество вида (010010010010...) является:
Формальная грамматика - это четверка, состоящая из
Правила вывода исчисления предикатов формируются из
Два конечных автомата называются эквивалентными, если
Существенность в формальной системе - это
Если переменная х не связана в формуле F, то она называется
Детерминированность в теории алгоритма означает:
Отличие тезиса от теоремы заключается в
Множество называется перечислимым, если
Свойствами алгоритма не являются:
Согласно определению конечный автомат состоит из
В определении конечный автомат присутствуют:
Двоичные наборы, являющиеся алфавитами логического автомата, представляют собой
При побитовом сложении двух чисел с помощью конечного автомата длина суммы по отношению в днинам слагаемых увеличится максимум на
Множество вида (01001000100001...) является:
Конечный автомат:
Объектами формальной системы могут быть
Наполнение формальной системы смыслом называется
В выводе в контексте формальной системы каждое слово - это либо
Язык, порождаемый формальной грамматикой - это
Синонимичное название грамматики типа 1 в классификации грамматик Хомского - это
Синонимом названия операции конъюнкции является
Стандартное правило вывода состоит из
Исчисления предикатов
Предметная область, соответствующая формальной системе, называется
Теорема Чёрча утверждает, что
Теорема Гёделя о полноте исчисления предикатов утверждает, что
Метатеорема - это
Конечный автомат, имеющий одно состояние, характеризуется следующими свойствами:
Характерными свойствами головки машины Тьюринга являются:
Тезис Тьюринга гласит:
Пустой дизъюнкт в методе резолюций обозначается
К формулам конъюнктивного типа не относится
Множество слов в произвольном алфавите, которое может быть получено из элементарных множеств путем конечного числа применений операций объединения, конкатенации, итерации, называется:
Метод аналитических таблиц в отличие от метода резолюций
Цифровая техника обрабатывает
Универсальным способом задания конечного автомата является:
Основными свойствами алгоритма являются:
Представителями класса моделей "Абстрактные машины" являются:
В определении конечного автомата не содержится
Машина Тьюринга:
Определение формальной системы включает в себя
Дискретность формальной системы означает, что
Регулярная грамматика согласно классификации Хомского относится к классу
Класс частично-рекурсивных функций образуют функции, которые
Множество слов в произвольном алфавите А называется регулярным, если оно может быть получено из элементарных множеств путем конечного числа применений операции
Принцип рассуждения от следствия к причине называется
Примером формальной системы является
Примером аналогового устройства является:
Схема определения понятия "Алгоритм" включает:
Контекстно-свободная грамматика согласно классификации Хомского относится к классу
Выберите верное:
Терм - это
Конечный автомат, осуществляющий побитовое сложение двух чисел
Граф,задающий машину Тьюринга, обладает следующими свойствами::
Вычисление или определение функции через нее саму в вычисленных или определенных ранее значениях называется
Пусть А - некоторый алфавит. Тогда языком алфавита А называется
Сеть Петри представляет собой: