Лекция: ма→ра

Ра→па

Па→. ко

Результатом применения данного алгорифма к цепочке

Мама варит компот будет цепочка

(один ответ)

1)Алгорифм к данной цепочке неприменим

2)Копа варит компот

3)Кома варит компот

4)Коко варит компот

10.Команда машины Тьюринга состоит из

(один ответ)

1)Символа внешнего алфавита, символа внутреннего алфавита, сдвига

2)номера состояния ленты МТ, символа алфавита и сдвига

3)подстроки P, символа →, строки Q

4)номера команды, знака команды, номера следующей команды

11.Машина Тьюринга — это (несколько ответов)

(несколько ответов)

1)ЭВМ, предложенная Тьюрингом и не получившая широкого распространения

2)Виртуальная алгоритмическая машина

3)Язык программирования высокого уровня

4)Один из способов представления алгоритма

12.На каждом шаге алгорифм Маркова ищет подстановку

(один ответ)

1)начиная с первой

2)проверяет подстановку, следующую за последней успешной

3)проверяет последнюю успешную подстановку

13.Остановка МТ происходит, когда

(один ответ)

1)выполнена последняя подстановка

2)не изменяется символ внутреннего алфавита

3)в состоянии P0 машина остается на месте

4)не изменяется символ внешнего алфавита, состояние МТ остается неизменным, сдвиг — нулевой

14.Программа машины Тьюринга представляет собой

(один ответ)

1)Линейную последовательность инструкций

2)Таблицу команд

3)Графическое описание последовательности действий

4)описание алгоритма на естественном языке

15.Укажите неверное высказывание: Функция является вычислимой, если её алгоритм можно представить в виде

(один ответ)

1)Рекурсивной функции

2)Машины Тьюринга

3)Алгорифма Маркова

4)Экстраалгоритма

16.Фрагмент программы машины Поста

1. => 2

2. ?(1, 3)

Определяет

(один ответ)

1)Движение влево до первой метки

2)Движение влево до первой пустой ячейки

3)Движение вправо до первой метки

4)Нахождение метки и её удаление

17.Фрагмент программы машины Поста

1. <= 2

2. ?(3, 1)

Определяет

(один ответ)

1)Движение влево до первой метки

2)Движение влево до первой пустой ячейки

3)Движение вправо до первой метки

4)Нахождение метки и её удаление

18.Число п на ленте машины Поста записывается

(один ответ)

1)с помощью п меток

2)с помощью п+1 метки

3)с помощью п-1 метки

4)цифрами в десятичной системе

19.Грамматика, заданная метасимволами (1, 2, 3,…,9){( 0, 1, 2, 3,…,9)}определяет грамматику

(один ответ)

1)Натуральных чисел

2)Десятичных чисел

3)Целых чисел

4)Простую дробь

20.Грамматика, заданная метасимволами [(-,+)] (1, 2, 3,…,9){( 0, 1, 2, 3,…,9)}определяет грамматику

(один ответ)

1)Натуральных чисел

2)Десятичных чисел

3)Целых чисел

4)Простую дробь

21.Метасимвол ( ) означает, что последовательность символов может встречаться в данном месте грамматики

(один ответ)

1)ровно один раз

2)сколь угодно раз или ни разу

3)ровно один раз или ни разу

22.Метасимвол [ ] означает, что последовательность символов может встречаться в данном месте грамматики

(один ответ)

1)ровно один раз

2)сколь угодно раз или ни разу

3)ровно один раз или ни разу

23.Метасимвол { } означает, что последовательность символов может встречаться в данном месте грамматики

(один ответ)

1)ровно один раз

2)сколь угодно раз или ни разу

3)ровно один раз или ни разу

24.Множество нетерминальных символов обозначается как

(один ответ)

1)VT

2)S

3)VN

4)P

25.На каждом шаге алгорифм Маркова ищет подстановку

(один ответ)

1)начиная с первой

2)проверяет подстановку, следующую за последней успешной

3)проверяет последнюю успешную подстановку

26.Набор правил, определяющий допустимые конструкции языка называется

(один ответ)

1)Синтаксисом языка

2)Лексикой языка

3)Семантикой языка

4)Алфавитом языка

27.Операция объединения или сложения двух цепочек символов, это

(один ответ)

1)Конкатенация

2)Итерация

3)Обращение

4)Ассоциация

28.Целевой (начальный) символ грамматики всегда является символом

(один ответ)

1)Терминального алфавита

2)Внешнего алфавита

3)Нетерминального алфавита

4)Состоянием логического устройства

29.Остановка МТ происходит, когда

(один ответ)

1)выполнена последняя подстановка

2)не изменяется символ внутреннего алфавита

3)в состоянии P0 машина остается на месте

4)не изменяется символ внешнего алфавита, состояние МТ остается неизменным, сдвиг — нулевой

30.Повторение цепочки, это

(один ответ)

1)Конкатенация

2)Итерация

3)Обращение

4)Ассоциация

31.При графическом описании грамматики нетерминальный символ (или цепочка символов) обозначается

(один ответ)

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

2)жирной точкой или закрашенным кружком

3)овалом, кругом или прямоугольником с закругленными краями, внутрь которого вписана цепочка

4)никак не обозначается

32.При графическом описании грамматики терминальный символ обозначается

(один ответ)

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

2)жирной точкой или закрашенным кружком

3)овалом, кругом или прямоугольником с закругленными краями, внутрь которого вписана цепочка

4)никак не обозначается

33.Программа машины Тьюринга представляет собой

(один ответ)

1)Линейную последовательность инструкций

2)Таблицу команд

3)Графическое описание последовательности действий

4)описание алгоритма на естественном языке

34.Распознаватель языка

(один ответ)

1)Определяет какому языку принадлежит цепочка

2)Определяет, принадлежит ли цепочка заданному языку

3)Исправляет ошибочно заданные цепочки

4)выясняет с помощью каких правил грамматики создана цепочка

35.Укажите верное высказывание

(один ответ)

1)Длина цепочек языка бесконечна

2)Множество цепочек языка может быть бесконечным

3)Длина цепочек языка должна быть меньше некоторого числа, указываемого при задании языка

4)Мощность множества цепочек языка явно задается при описании языка

36.Укажите неверное высказывание: Функция является вычислимой, если её алгоритм можно представить в виде

(один ответ)

1)Рекурсивной функции

2)Машины Тьюринга

3)Алгорифма Маркова

4)Экстраалгоритма

37.Язык можно задать

(несколько вариантов ответа)

(несколько ответов)

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

2)Указанием способа порождения цепочек языка (заданием грамматики языка)

3)Определением семантики всех допустимых цепочек

4)Определением множества допустимых операций над цепочками

5)Определением метода распознавания цепочек языка

38.К какому типу принадлежит грамматика G2({0,1}.{A,S}, P, S) с.правила-ми-Р:

S 0A1

0A 00A1

(один ответ)

1)0

2)2

3)1

4)3

39.G(VT,VN,P,S), V = VN VT

где, .

Укажите тип грамматики

(один ответ)

1)0

2)2

3)1

4)3

40.Грамматика G(VT,VN,P,S), V = VN VT со структурой правил, где,. относятся к типу

(один ответ)

1)1. (Контекстно-зависимые грамматики)

2)3. Левосторонние грамматики

3)1. (Неукорачивающие грамматики)

4)0

41.Грамматика G(VT,VN,P,S), V = VN VT со структурой правил ,

где V+, | | |.

относятся к типу

(один ответ)

1)1. (Контекстно-зависимые грамматики)

2)3. Левосторонние грамматики

3)1. (Неукорачивающие грамматики)

4)0

42.Грамматика G(VT,VN,P,S), V = VN VT со структурой правил, где A VN, V+.

относятся к типу

(один ответ)

1)0

2)2. Конткстно-свободные неукорачивающие грамматики

3)1. (Неукорачивающие грамматики)

4)3. Левосторонние грамматики

43.Грамматика G(VT,VN,P,S), V = VN VT со структурой правил А В или А→у, где A, VN, VT*.

относятся к типу

(один ответ)

1)3. Правосторонние грамматики

2)2. Контекстно-свободные неукорачивающие грамматики

3)1. (Неукорачивающие грамматики)

4)3. Левосторонние грамматики

44.Грамматика G(VT,VN,P,S), V = VN VT со структурой правил А В или А, где A,B VN, VT.

относятся к типу

(один ответ)

1)3. Правосторонние грамматики

2)2. Контекстно-свободные неукорачивающие грамматики

3)1. (Неукорачивающие грамматики)

4)3. Левосторонние грамматики

47.Укажите правильную последовательность алгоритма Краскала

(на последовательность)

1)определяем в графе циклические ребра

2)определяется наибольшее циклическое ребро и удаляется

3)повторяем до полного исчезновения циклических ребер

48.Укажите правильную последовательность алгоритма Прима

(на последовательность)

1)строятся все вершины для графа без ребер

2)выбирается самое короткое ребро

3)добавляется только висячая вершина с ребром наименьшего веса

4)Процесс продолжается, пока не будут связаны все вершины

49.Задача коммивояжера состоит в том, чтобы …

(один ответ)

1)минимизировать длину гамильтонового цикла

2)минимизировать длину гамильтоновой цепи

3)найти остовное дерево минимального веса

4)найти кратчайший путь от одной вершины ко всем остальным

50.Выберите метод, с помощью которого нельзя решить задачу коммивояжера

(один ответ)

1)метод включения-исключения

2)жадный алгоритм

3)деревянный алгоритм

4)метод ветвей и границ

51.Повторение цепочки, это

(один ответ)

1)Конкатенация

2)Итерация

3)Обращение

4)Ассоциация

52.Какая проблема является основной для теории алгоритмов?

(один ответ)

1)Проблема поиска оптимального алгоритма.

2)Проблема существования или отсутствия алгоритма.

3)Исследование методов построения алгоритмов.

4)Проблема описания существующего алгоритма.

53.Какая из функций не является базовой рекурсивной функцией?

(один ответ)

1)f(x) = 1

2)f(x) = 0

3)f(x) = x

4)f(x) = x+1

54.Какой из тезисов создан для полностью рекурсивных функций?

(один ответ)

1)Тезис Клини

2)Тезис Тьюринга

3)Тезис Черча

4)Принцип нормализации

55.Какой из тезисов создан для «воображаемых» вычислительных машин?

(один ответ)

1)Тезис Клини

2)Тезис Тьюринга

3)Тезис Черча

4)Принцип нормализации

56.Какой из тезисов создан для частично рекурсивных функций?

(один ответ)

1)Тезис Клини

2)Тезис Тьюринга

3)Тезис Черча

4)Принцип нормализации

57.Операция получения рекурсивной функции при подстановке это ...

(один ответ)

1)Трансляция

2)Минимизация

3)Примитивная рекурсия

4)Суперпозиция

58.Какой из тезисов формулируется для алгорифмов Маркова?

(один ответ)

1)Тезис Клини

2)Тезис Тьюринга

3)Тезис Черча

4)Принцип нормализации

59.Какое из выражений относится к алгорифмам Маркова?

(один ответ)

1)A --> B

2)A(B)=B+1

3)<A> ::= B

4)A d0 P1

60.Какое из выражений относится к нотациям Бекуса?

(один ответ)

1)A --> B

2)A(B)=B+1

3)<A> ::= B

4)A d0 P1

61.Какое из выражений относится к нотациям Бекуса?

(один ответ)

1)A --> B

2)A(B)=B+1

3)<A> ::= B

4)A d0 P1

62.Какое из выражений отмечает конечную подстановку?

(один ответ)

1)A --> B

2)A --> .

3)<A> ::= B

4)A d0 P1

63.Какое из выражений обозначает Марковскую подстановку?

(один ответ)

1)A --> B

2)A(B)=B+1

3)<A> ::= B

4)A d0 P1

64.Какое из выражений означает «или»?

(один ответ)

1)A --> B

2)A(B)=B+1

3)<A> ::= B

4)|

65.Задача определения остовного дерева минимального веса в графе с заданными длинами ребер — это задача …

(один ответ)

1)Прима-Краскала

2)Дейкстры

3)сетевого планирования

4)Форда-Фолкерсона

66.Какое из выражений означает «по определению есть»?

(один ответ)

1)A --> B

2)A(B)=B+1

3)<A> ::= B

4)A d0 P1

67.Задача определения минимального расстояния от вершины до остальных это задача ...

(один ответ)

1)Прима-Краскала

2)Дейкстры

3)сетевого планирования

4)Форда-Фолкерсона

68.Задача определения максимального потока в сети это задача ...

(один ответ)

1)Прима-Краскала

2)Дейкстры

3)о назначениях

4)Форда-Фолкерсона

69.Задача о назнчениях решается с помощью

(один ответ)

1)двудольного графа

2)взвешенного графа

3)сетевого графа

4)ориентированного графа

70.Максимальным потоком для данной сети будет:

(один ответ)

1)11

2)5

3)10

4)7

71.Максимальным потоком для данной сети будет:

(один ответ)

1)7

2)5

3)13

4)2

72.Ре зультатом решения задачи о максимальном потоке для сети

будет сеть:

(один ответ)

73.Для решение основной задачи теории алгоритмов были предложены методы:

(несколько ответов)

1)Машина Тьюринга

2)Алгоритм Дейкстры

3)Алгоримы Маркова

4)Метод ветвей и границ

5)Рекурсивные функции

6)Жадный алгоритм

74.

(несколько ответов)

75.Решением задачи коммивояжера с исходной матрицей

		∞
		∞
С	=	∞
		∞
		∞

будет путь длиной:

(один ответ)

1)25

2)19

3)18

4)31

76.Шестеро девушек хотят выбрать партнера по танцам. Эллис нравятся Чарльз и Эдвард; Бетти нравятся Альберт и Дэн; Клара предпочитает Чарльза и Эдварда; Донна любит танцевать с Дэном; Элизабет нравятся Барт и Эдвард. Известно, что каждая девушка танцует с парнем, который ей нравится. С кем будет танцевать Дэн

(один ответ)

1)Донна

2)Элизабет

3)Бетти

4)Клара

77.Шестеро девушек хотят выбрать партнера по танцам. Эллис нравятся Чарльз и Эдвард; Бетти нравятся Альберт и Дэн; Клара предпочитает Чарльза и Эдварда; Донна любит танцевать с Дэном; Элизабет нравятся Барт и Эдвард. Известно, что каждая девушка танцует с парнем, который ей нравится. С кем танцует Бетти?

(один ответ)

1)Альберт

2)Барт

3)Дэн

4)Эдвард

78.Эмми входит в состав комитетов a и b. Брюс — комитетов a и c. Дэнис — член комитетов b, c и e. Эллен входит комитетов d и е. Чарльз член комитета b. Председатель студенческого совета планирует пригласить на совещание пятерых членов совета, входящих в различные комитеты. Поставьте в соответствие кто от каких комитетов будет присутствовать на собрании.

(на соответствие)

Левая часть(A):

1)Эмми

2)Брюс

3)Дэнис

4)Эллен

5)Чарльз

Правая часть(B):

1)a

2)b

3)c

4)d

5)e

79.Произвольное подмножество попарно несмежных рёбер двудольного графа (взятых вместе со своими вершинами) называется

(один ответ)

1)паросочетанием

2)разбиением

3)окружением

4)перестановкой

80.Граф, множество вершин которого можно разбить на два непересекающихся полмножества V1 и V2 таких, что любое ребро графа соединяет вершины разных подмножеств, — называется…

(один ответ)

1)двудольным

2)разбиением

3)окружением

4)паросочетанием

81.Множество ребер, которые из всех парасочетаний имеют большую мощность, называют…

(один ответ)

1)главным

2)эпицентрическим

3)наивероятнейшим

4)максимальным

82.С нахождением совершенного паросочетания связана задача ...