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

Упражнение 1:

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

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

(2) радио

(3) лифт

Номер 3

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

Ответ:

(1) радио

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

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

(4) лифт

Упражнение 2:

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

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

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

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

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

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

Номер 3

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

Ответ:

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

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

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

Упражнение 3:

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

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

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

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

Номер 3

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

Ответ:

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

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

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

Упражнение 4:

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

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

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

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

Номер 3

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

Ответ:

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

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

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

Упражнение 5:

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

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

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

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

Номер 3

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

Ответ:

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

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

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

Упражнение 6:

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

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

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

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

Номер 3

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

Ответ:

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

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

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

Упражнение 7:

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

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

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

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

Номер 3

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

Ответ:

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

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

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

Упражнение 8:

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

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

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

(3) бинарным

Номер 3

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

Ответ:

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

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

(3) бинарным

Упражнение 9:

Номер 1

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

Ответ:

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

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

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

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

Номер 2

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

Ответ:

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

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

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

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

Номер 3

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

Ответ:

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

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

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

Упражнение 10:

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

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

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

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

Номер 3

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

Ответ:

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

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

(3) итерации

Упражнение 11:

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

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

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

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

Номер 3

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

Ответ:

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

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

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

Упражнение 12:

Номер 1

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

Ответ:

(1) дуг

(2) позиций

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

Номер 2

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

Ответ:

(1) дерево

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

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

Номер 3

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

Ответ:

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

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

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

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

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