Соотнесите понятия теории алгоритмов и их содержание:
алгоритм < способ решения задачи, точно предписывающий как и в какой последовательности получить результат, однозначно определяемый исходными данными
нормальный алгоритм < ряд предписаний в форме подстановок в определенном алфавите
челночный алгоритм < модификация марковского алгоритма
примитивно рекурсивные функции < арифметические функции, которые сопоставляются по определенным правилам, примитивно рекурсивным описаниям
Соотнесите понятия теории конечных автоматов и их содержание:
конечный автомат < автомат, который однократно считывает символы строки слева направо, меняя каждый раз свое состояние
регулярный язык < язык, распознаваемый конечным автоматом
матрица переходов < один из способов описания работы конечного автомата
конечное состояние < состояние автомата, в которое он приходит после прочтения символов на ленте
Соотнесите понятия теории множеств и их содержание:
множество < объединение произвольного количества определенных отличных друг от друга объектов
подмножество < множество А есть подмножество множества В в том и только в том случае, если каждый элемент множества А есть также элемент множества В
мощность множества < критерий оценки размерности множества
пустое множество < множество, не содержащее элементов
Соотнесите понятия теории формальных грамматик и их содержание:
метаязык < язык, на котором описывается другой язык
грамматика < правила, определяющие предложения языка
фразы < комбинации символов, образующие грамматические единицы
функтор < средство соединения фраз для образования других фраз
Соотнесите понятия, характеризующие теорию формальных систем, и их содержание:
аксиоматический метод < способ построения научной теории, когда в основу кладутся исходные положения, называемые аксиомами
аксиома < исходное положение научной теории, принимаемое без доказательств
интерпретация теории < установление соответствия между высказываниями теории и содержательными высказываниями предметной области
представление системы < способ рассмотрения объектов формальной системы как конкретных объектов при условии, что конкретные объекты сохраняют структуру формальных
Соотнесите понятия, характеризующими машину Тьюринга, и их содержание:
машина Тьюринга < гипотетическая вычислительная машина, используемая для уточнения понятия алгоритма
внешний алфавит < алфавит символов, подаваемых на вход машины Тьюринга и выдаваемых на ее выходе
внутренний алфавит < алфавит символов, определяющих состояние машины Тьюринга
вычислимость по Тьюрингу < существование машины Тьюринга, вычисляющей заданную функцию
Соотнесите предикат и область истинности предиката:
x + 5 = 1 < –4
x2 < 0 < Æ
x2 – 1 = 0 < +1; –1
Соотнесите характеристики сложности алгоритмов и их содержание:
сложность < трудность решения задачи, измеренная в терминах некоторого ресурса, потребляемого в процессе вычислений
вычислительные ресурсы < временные или пространственные характеристики процесса вычислений
критерий сложности < средства измерения объема ресурсов, потребляемых в процессе вычислений
классы сложности < способ группировки алгоритмов в соответствии с их сложностью
Существуют следующие классы фраз:
(*ответ*) функторы
(*ответ*) предложения
(*ответ*) имена
кванторы
дизъюнкты
Существуют следующие типы конечных автоматов:
(*ответ*) детерминированные
(*ответ*) недетерминированные
рекурсивные
перечислимые
Существуют следующие формы записи работы конечного автомата:
(*ответ*) набор команд
(*ответ*) матрица переходов
(*ответ*) граф состояний
система алгебраических уравнений