Теория алгоритмов, информатика, математика, экзамены, 3курс, 5 сем

Теория алгоритмов, информатика, математика, экзамены, 3курс, 5 сем

1.Вычислительный процесс - это

(один ответ)

1) последовательность действий, выполняемых исполнителем

2) последовательность шагов алгоритма

3) порядок выполнения алгоритма в применении к исходным данным

4) совокупность промежуточных значений переменных

Правильные ответы

1.

2.Исходные данные - это

(один ответ)

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

2) множество возможных значений переменных

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

4) набор всех переменных алгоритма и их значений

Правильные ответы

1.

3.Состоянием вычислительного процесса, порожденного алгоритмом А называют

(один ответ)

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

2) множество возможных значений переменных

3) точно определенное множество значений, с которых начинается выполнение алгоритма

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

Правильные ответы

1.

4.Терминальным состоянием вычислительного процесса является

(один ответ)

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

2) множество возможных значений переменных

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

4) переход из одного состояния в другое

Правильные ответы

1.

5.Результат - это

(один ответ)

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

2) значения выходных переменных в данный момент времени

3) состояние, на множестве значений которого выполняется определенное условие - правило окончания алгоритма

4) множество возможных значений результирующих переменных

Правильные ответы

1.

6.Сложностью алгоритма является

(один ответ)

1) количество действий в вычислительном процессе алгоритма

2) количество операций присваивания в алгоритме

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

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

Правильные ответы

1.

7.Какие из перечисленных свойств алгоритма являются необходимыми

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

1) дискретность

2) рекурсивность

3) результативность

4) формальность и простота

5) массовость

6) эффективность

7) детерменированность

Правильные ответы

1.3.7.

8.Какие из перечисленных свойств алгоритма являются сравнительными

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

1) дискретность

2) рекурсивность

3) результативность

4) формальность и простота

5) массовость

6) эффективность

7) детерменированность

Правильные ответы

2.4.5.6.

9.Какие из функций являются базовыми рекурсивными

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

1) функции любого числа независимых переменных, тождественно равные нулю

2) функция, полученная с помощью оператора суперпозиции

3) функции любого числа независимых переменных, тождественно равные одному из аргументов

4) функция, полученная с помощью оператора минимизации

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

6) любые всюду вычислимые функции

Правильные ответы

1.3.5.

10.Какие функции не являются общерекурсивными

(один ответ)

1) функции любого числа независимых переменных, тождественно равные нулю

2) функции получения последователя одного независимого переменного

3) функции любого числа независимых переменных, тождественно равные одному из аргументов

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

5) функция, полученная с помощью оператора минимизации из рекурсивных функций

6) функции, полученные с помощью оператора примитивной рекурсии из рекурсивных функций

Правильные ответы

5.

11.Алгоритм построения суперпозиции двух функций

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

1) Выбираются две функции f, g

2) Определяется аргумент x_k первой функции f, для которой будем осуществлять подстановку

3) Подставляем значение аргумента в g и вычисляем её значение g₀

4) x_k=g₀

5) f₀=f(x₁, …, x_k,…, x_m)

Варианты ответов выставленны внужном порятке

12.Алгоритм построения примитивной рекурсии

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

1) Выбираем две функции ц и ш, у которых количество аргументов n-1 и n+1 соответственно

2) Определяем значение для n-1 аргумента и фиксируем значение x_n (n-го аргумента), это будет y

3) Выбираем значение y=0

4) Вычисляем ; Увеличиваем y на 1 и получаем функцию =

Варианты ответов выставленны внужном порятке

13.Алгоритм оператора построения по первому нулю

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

1) фиксируем значение переменных

2) строим некую функцию f, к которой будет добавлена переменная

3) определяем, имеет ли относительно этой переменной функция f натуральный корень. Если корней нет, то при данных значениях функция g не определена. Если корни есть, то находим минимальный корень у. Этот корень и есть искомое значение функции g, g=y

Варианты ответов выставленны внужном порятке

14.В блок-схеме

описана команда

(один ответ)

1) цикла с предусловием

2) полного ветвления

3) цикла с параметром

4) неполного ветвления

Правильные ответы

2.

15.В блок-схеме

Описана команда

(один ответ)

1) цикла с предусловием

2) полного ветвления

3) цикла с параметром

4) неполного ветвления

Правильные ответы

1.

16.В блок-схеме

Описана команда

(один ответ)

1) цикла с предусловием

2) полного ветвления

3) цикла с параметром

4) неполного ветвления

Правильные ответы

4.

17.В блок-схеме

Описана команда

(один ответ)

1) цикла с предусловием

2) полного ветвления

3) цикла с параметром

4) неполного ветвления

Правильные ответы

3.

18.В блок-схеме

Описана команда

(один ответ)

1) цикла с предусловием

2) цикла с постусловием

3) цикла с параметром

4) неполного ветвления

Правильные ответы

2.

19.Алгоритм - это

(один ответ)

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

2) последовательность действий, применяемая к некоторым исходным данным

3) пошаговое описание процесса решения какой-либо задачи

Правильные ответы

1.

20.Свойство, означающее, что процесс решения задачи, определяемый алгоритмом, расчленен на отдельные элементарные шаги, соответствует

(один ответ)

1) дискретности

2) результативности

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

4) массовости

Правильные ответы

1.

21.Существование на каждом шаге алгоритма однозначного выбора и отсутствие неоднозначных конструкций соответствует свойству

(один ответ)

1) дискретности

2) результативности

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

4) массовости

Правильные ответы

3.

22.Свойство, означающее, что алгоритм всегда приводит к результату через конечное число шагов, соответствует

(один ответ)

1) результативности

2) определенности

3) дискретности

4) массовости

Правильные ответы

1.

23.ψ_3,4(x,y,z)=

(один ответ)

1) x

2) z

3) y

4) значение не определено

Правильные ответы

4.

24.λ (λ(λ(х)))=

(один ответ)

1) х+3

2) х+1

3) х+х+х

Правильные ответы

1.

25.Класс данных, к которым применим данный алгоритм, определяет

(один ответ)

1) массовость

2) эффективность

3) результативность

4) рекурсивность

Правильные ответы

1.

26.В ячейках ленты машины Тьюринга записываются

(один ответ)

1) Команды

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

3) Символы внешнего алфавита

4) Информация о сдвиге каретки

Правильные ответы

3.

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

(один ответ)

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

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

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

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

Правильные ответы

1.

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

(один ответ)

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

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

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

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

Правильные ответы

3.

29.Задан фрагмент алгорифма Маркова

ра→па

па→. ко

ма→ра

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

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

(один ответ)

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

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

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

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

Правильные ответы

3.

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

(один ответ)

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

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

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

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

Правильные ответы

1.

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

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

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

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

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

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

Правильные ответы

2.4.

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

(один ответ)

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

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

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

Правильные ответы

1.

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

(один ответ)

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

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

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

Правильные ответы

3.

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

(один ответ)

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

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

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

Правильные ответы

2.

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

(один ответ)

1) VT

2) S

3) VN

4) P

Правильные ответы

3.

36.Множество правил грамматики обозначается:

(один ответ)

1) VT

2) S

3) VN

4) P

Правильные ответы

4.

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

(один ответ)

1) VT

2) S

3) VN

4) P

Правильные ответы

1.

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

(один ответ)

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

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

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

Правильные ответы

1.

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

(один ответ)

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

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

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

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

Правильные ответы

1.

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

(один ответ)

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

2) Итерация

3) Обращение

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

Правильные ответы

1.

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

(один ответ)

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

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

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

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

Правильные ответы

3.

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

(один ответ)

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

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

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

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

Правильные ответы

4.

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

(один ответ)

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

2) Итерация

3) Обращение

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

Правильные ответы

2.

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

(один ответ)

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

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

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

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

Правильные ответы

1.

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

(один ответ)

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

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

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

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

Правильные ответы

3.

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

(один ответ)

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

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

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

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

Правильные ответы

2.

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

(один ответ)

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

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

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

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

Правильные ответы

2.

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

(один ответ)

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

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

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

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

Правильные ответы

2.

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

(один ответ)

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

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

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

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

Правильные ответы

4.

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

(один ответ)

1) Никакую NP-полную задачу нельзя решить никаким известным алгоритмом полиномиальной сложности

2) Задача коммивояжера является NP полной задачей

3) Если будет найден полиномиальный алгоритм для какой-нибудь NP-полной задачи, то существуют полиномиальные алгоритмы для всех NP-полных задач

4) Существует точный алгоритм решения задачи коммивояжера линейной временной сложности

Правильные ответы

4.

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

1. => 2

2.?(1, 3)

Определяет

(один ответ)

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

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

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

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

Правильные ответы

3.

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

1. <= 2

2.?(3, 1)

Определяет

(один ответ)

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

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

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

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

Правильные ответы

2.

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

(один ответ)

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

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

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

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

Правильные ответы

2.

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

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

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

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

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

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

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

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

Правильные ответы

1.2.5.

55.Команда машины Поста состоит из

(один ответ)

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

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

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

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

Правильные ответы

4.

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

S 0A1

0A 00A1

A

(один ответ)

1) 0

2) 2

3) 1

4) 3

Правильные ответы

1.

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

:

,

где , .

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

(один ответ)

1) 0

2) 2

3) 1

4) 3

Правильные ответы

3.

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

(один ответ)

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

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

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

4) 0

Правильные ответы

1.

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

где V⁺, | | |.

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

(один ответ)

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

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

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

4) 0

Правильные ответы

3.

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

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

(один ответ)

1) 0

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

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

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

Правильные ответы

2.

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

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

(один ответ)

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

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

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

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

Правильные ответы

4.

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

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

(один ответ)

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

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

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

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

Правильные ответы

1.

Итого: 62

Дата добавления: 2015-11-04