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