Контрольные по математике | Интуитивное понятие алгоритма. алгоритмы в математике

Интуитивное понятие алгоритма. Алгоритмы в математике.

1. Термин «алгоритм» появился в связи с…

A. – разработкой программ для ЭВМ

B. + обозначением процесса цифровых вычислений десятичной позиционной арифметики

C. – поиском решений задач математической логики

D. – изучением проблемы сложности вычислений

2. Термин «алгоритм» происходит от …

A. + имени средневекового узбекского математика Мухаммад ибн Муса аль-Хорезми

B. – описанной Евклидом последовательности действий для нахождения наибольшего общего делителя двух чисел

C. – понятии «нормальный алгорифм», введенного А. А. Марковым

D. – первого языка программирования

3. Термин «алгоритм» появился в …

A. – VIII веке

B. + IX веке

C. – XVIII веке

D. – XIX веке

4. Задача формального определения понятия алгоритма решена в …

A. – 1830-х годах

B. + 1930-х годах

C. – 1940-х годах

D. – 1950-х годах

5. Развитие прикладного направления теории алгоритмов началось в …

A. – 1830-х годах

B. – 1930-х годах

C. + 1940-х годах

D. – 1950-х годах

6. Выберите наиболее правильное интуитивное определение алгоритма

A. + Алгоритм – это точное и полное предписание о последовательности выполнения конечного числа действий, необходимых для решения любой задачи из некоторого класса

B. – Под алгоритмом понимается всякое предписание, которое задаёт вычислительный процесс

C. – Алгоритм – это инструкция для выполнения последовательности действий, которая задается исходным набором данных

D. – Под алгоритмом понимается любая совокупность правил

7. Алгоритмы, в соответствии с которыми решение поставленных задач сводится к арифметическим действиям, называются (численными) алгоритмами.

8. Алгоритмы, в соответствии с которыми решение поставленных задач сводится к логическим действиям, называются (логическими) алгоритмами.

9. Примерами численных алгоритмов являются алгоритмы

A. + нахождения НОД

B. + решения систем линейных уравнений методом Гаусса

C. – поиска минимального числа

D. – поиска пути из вершины хо в вершину хn для графа

10. Примерами логических алгоритмов являются алгоритмы

A. – умножения матрицы на вектор

B. – алгоритм вычисления членов последовательности

C. + поиска равных чисел в последовательности

D. + поиска пути в лабиринте

Свойства алгоритма.

11. Разбиение выполнения алгоритмана на последовательность законченных действий называется свойством…

A. + дискретности

B. – детерминированности

C. – конечности

D. – результативности

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

A. – дискретность

B. – детерминированности

C. + понятность

D. – результативности

13. Свойство, недопускающее произвола действий исполнителя и требующее, чтобы команда могла быть понята и выполнена однозначно называют свойством…

A. – дискретности

B. – детерминированности

C. – понятности

D. + определенности

14. Требование, чтобы закон получения последующей системы величин из предыдущей был простым и локальным называется…

A. + элементарность команд

B. – понятность

C. – определенность

D. – конечность

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

A. – дискретности

B. – детерминированности

C. – понятности

D. + результативности

16. Свойство алгоритма быть применимым для решения любой задачи из некоторого класса называется свойством…

A. – определенности

B. + массовости

C. – результативности

D. – детерминированности

Способы записи алгоритма.

17. Способ записи алгоритмов, представляющий собой описание на естественном языке последовательных этапов обработки данных, называется…

A. — табличным

B. + словесным

C. — логичным

D. — простым

18. Способ записи алгоритмов, представляющий собой описание последовательных этапов обработки данных в виде таблицы, называется …

A. +табличным

B. -словесным

C. -схематичным

D. -красивым

19. Способ записи алгоритмов, представляющий совокупность буквенных обозначений, чисел, знаков арифметических операций, элементарных функций и знака "равно", называется…

A. — знаковым

B. — буквенным

C. — алгоритмическим

D. +формульным

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

A. + алгоритмическим

B. — правильным

C. — формульным

D. — знаковым

21. Способ записи алгоритмов, представленный в виде последовательности связанных между собой изображений (функциональных блоков), каждое из которых соответствует выполнению одного или нескольких действий, называется …

A. — формульным

B. — посталгоритмическим

C. — алгоритмическим

D. + графическим

22. Ориентированный граф, указывающий порядок исполнения команд алгоритма, изображенных специальными блоками в виде геометрических фигур, называется…

A. — геометрическим

B. + блок-схема

C. — фигурным

D. — схематическим

23. Блочный символ используемый в блок-схеме для обозначения начала или конца алгоритма.

A. –

B. –

C. –

D. +

24. Блочный символ используемый в блок-схеме для обозначения вычислительных действий.

A. +

B. –

C. –

D. –

25. Блочный символ используемый в блок-схеме для обозначения проверки условий.

A. –

B. +

C. –

D. –

26. Блочный символ используемый в блок-схеме для обозначения для обозначения ввода и вывода данных.

A. –

B. –

C. +

D. –

27. Выберите блок-схемы соответствующие алгоритмической конструкции "ветвлению".

A. +

B. +

C. –

D. –

28. Выберите блок-схемы соответствующие алгоритмической конструкции "цикл".

A. –

B. +

C. +

D. –

29. Выберите блок-схему соответствующую алгоритмической конструкции "следование"

A. –

B. –

C. –

D. +

Необходимость уточнения понятия алгоритма. Алгоритмические модели

30. Алгоритмическая модель, связывающая понятие алгоритма с процедурами вычисления значений числовых функций построена…

A. – Э. Постом

B. – А. Тьюрингом

C. – А. А. Марковым

D. + С. К. Клини

31. Алгоритмическая модель, связывающая понятие алгоритма с описанием точно очерченных процессов, выполняемых неким устройством построена …

A. – С. К. Клини

B. + А. Тьюрингом

C. – А. А. Марковым

D. – А. Чёрчем

32. Как особое соответствие между словами в том или ином абстрактном алфавите алгоритм определяется в модели …

A. – Э. Поста

B. – А. Тьюринга

C. + А. А. Маркова

D. – А. Чёрча

33. Формальное определение алгоритма необходимо при …

A. – вычислении числовых функций и исчислении предикатов

B. – доказательстве возможности его построения

C. + доказательстве неразрешимости задач

D. – определении эффективности конкретного алгоритма

Понятие вычислимой функции.

34. Частичной функцией называется закон, устанавливающий в соответствие …

A. + некоторым или всем элементам множества X однозначно определенные элементы множества Y

B. – каждому элементу множества X однозначно определенные элементы множества Y

C. – некоторым элементам множества X элементы множества Y

D. – каждому элементу множества X все элементы множества Y

35. Всюду определенной функцией называется закон, устанавливающий в соответствие …

A. – некоторым или всем элементам множества X однозначно определенные элементы множества Y

B. + каждому элементу множества X однозначно определенные элементы множества Y

C. – некоторым элементам множества X элементы множества Y

D. – каждому элементу множества X все элементы множества Y

36. Пусть даны два множества X, Y и частичная функция <D(f), f > из X в Y, где D(f) Í X, f : D(f)→Y и f(x) – значение f на данном x. Тогда D(f) называется …

A. + областью определения f

B. – множеством значений f

C. – образом множества X при функции f

D. + прообразом множества X при функции f

37. Пусть даны два множества X, Y и частичная функция <D(f), f > из X в Y, где D(f) Í X, f : D(f)→Y и f(x) – значение f на данном x. Тогда множество {f(x) / xÎD(f)} называется …

A. – областью определения f

B. + множеством значений f

C. + образом множества X при функции f

D. – прообразом множества X при функции f

38. Пусть даны два множества X, Y и частичная функция <D(f), f > из X в Y, где D(f) Í X, f : D(f)→Y. Если D(f) пустое, то f называется …

A. – частичной

B. – всюдуопределенной

C. + нигде не определенной

D. – инъективной

39. Частичная функция <D(f), f > из (N0)m в (N0)n, где D(f) Í (N0)m, f : D(f)→ (N0)n называется вычислимой (интуитивно вычислимой), если существует такая «программа» (алгоритм), что …

A. + при подаче на ее вход вектора х Î (N0)m мы получим на выходе f(x), если х Î D (f), а иначе некоторое c Ï (N0)n

B. – при подаче на ее вход вектора х Î (N0)m мы получим на выходе f(x), если х Î D (f), а если х Ï D (f), то на выходе получим некоторое c Ï (N0)n или же программа работает бесконечно долго

C. – печатает все элементы множества (N0)m и только их, через равные промежутки времени.

D. – по любому n из (N0)m определяет, принадлежит ли f(n) множеству (N0)n и выводит сообщение о принадлежности данного элемента.

40. Частичная функция <D(f), f > из (N0)m в (N0)n, где D(f) Í (N0)m, f : D(f)→ (N0)n называется полувычислимой, если существует такая «программа» (алгоритм), что …

A. – при подаче на ее вход вектора х Î (N0)m мы получим на выходе f(x), если х Î D (f), а иначе некоторое c Ï (N0)n

B. + при подаче на ее вход вектора х Î (N0)m мы получим на выходе f(x), если х Î D (f), а если х Ï D (f), то на выходе получим некоторое c Ï (N0)n или же программа работает бесконечно долго

C. – печатает все элементы множества (N0)m и только их, через равные промежутки времени.

41. Отметьте истинные высказывания:

A. + вычислимые функции полувычислимы

B. – полувычислимые функции вычислимы

C. + всюду определенные полувычислимые функции вычислимы

D. + нигде не определенные функции вычислимы

42. Отметьте все истинные высказывания о вычислимой функции:

A. + функция вычислима <=> ее D(f) является перечислимым множеством

B. + существуют невычислимые функции

C. – частично определенная функция не вычислима

D. – функция вычислима <=> она всюду определена

43. Пусть X Í Y – два множества. Характеристической функцией подмножества X в У называется такая функция c x что …

A. c x (n)=( if n Î Y then 0 else c Ï X)

B. c x (n)=( if n Î X then 0 else не определено)

C. + c x (n)=( if n Î X then 0 else 1)

D. – c x (n)=( if n Î X then f(x) else не определено)

44. Пусть X Í Y – два множества. Полуарактеристической функцией подмножества X в У называется такая функция c x что …

A.– c x (n)=( if n Î Y then 0 else c Ï X)

B.+ c x (n)=( if n Î X then 0 else не определено)

C.– c x (n)=( if n Î X then 0 else 1)

D.- c x (n)=( if n Î X then f(x) else не определено)

45. Если существует синтаксическое выражение и соответствующая интерпретация его как функции f, и если это выражение определяет алгоритм, которй реализуют данную функцию, то функцию f называют …

A. – интуитивно вычислимой

B. – полувычислимой

C. + эффективно вычислимой

D. – невычислимой

Понятие разрешимого множества.

46. Множество X называется разрешимым, если существует такая «программа» (алгоритм), что …

A. – при подаче на ее вход вектора х Î X мы получим на выходе f(x), если х Î D (f), а иначе некоторое c Ï X

B. – при подаче на ее вход вектора х Î X мы получим на выходе f(x), если х Î D (f), а если х Ï D (f), то на выходе получим некоторое c Ï X или же программа работает бесконечно долго

C. – печатает все элементы множества X и только их, через различные промежутки времени

D. + по любому n из (N0)m определяет, принадлежит ли n множеству X и выводит сообщение о принадлежности данного элемента

47. Отметьте все истинные высказывания о разрешимом множестве:

A. + пересечение разрешимых множеств – разрешимо

B. + разность разрешимых множеств – разрешимое множество

C. – множество X разрешимо тогда и только тогда, когда оно конечно

D. + объединение разрешимых множеств – разрешимо

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

A. + Всякое разрешимое множество – перечислимо. Если множество X и его дополнение до множества N перечислимы, то X разрешимо.

B. – Всякое перечислимое множество – разрешимо. Если множество X и его дополнение до множества N разрешимы, то X перечислимо.

C. – Если множество X перечислимо, то X разрешимо.

D. – Всякое перечислимое множество – разрешимо и всякое разрешимое множество –перечеслимо.

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

A. + существует разрешимое неперечислимое множество

B. – существует перечислимое разрешимое множество

C. – существует разрешимое перечислимое множество

D. – существует перечислимое неразрешимое множество

Понятие перечислимого множества.

50. Множество X называется перечеслимым, если существует такая «программа» (алгоритм), что …

A. – при подаче на ее вход вектора х Î X мы получим на выходе f(x), если х Î D (f), а иначе некоторое c Ï X

C. + печатает все элементы множества X и только их, через различные промежутки времени

D. – по любому n из (N0)m определяет, принадлежит ли n множеству X и выводит сообщение о принадлежности данного элемента

51. Отметьте все истинные высказывания о перечислимом множестве:

A. + множество перечислимо <=> оно является областью определения вычислимой функции

B. – разность перечислимых множеств – перечислима

C. + пересечение перечислимых множеств – перечислимо

D. + объединение перечислимых множеств – перечислимо

Частично рекурсивные функции и рекурсивные предикаты. Класс частично рекурсивных функций. Исходные функции.

52. Рекурсией называется …

A. + способ задания функции, при котором значение определяемой функции для произвольных значений аргументов выражается известным образом через значения определяемой функции для меньших значений аргументов

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

C. – вычисление функции через базовые функции с помощью известных алгоритмов

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

53. Отметьте все элементарные (исходные, базовые) функции для построения класса частично рекурсивных функций:

A. + нуль-функция: O(x)=0;

B. + функция следования: S(x)=x+1;

C. + функция проецирования (выбора): Inm(x1,x2,…,xn)=xm, 1£m£n.

D. – функция – константа Cqn(x1,x2,…,xn)=q, nÎN, qÎ N

54. Укажите истинные высказывания:

A. + множество частично рекурсивных функций – счетно

B. + классы частично рекурсивных функций, функций вычислимых по Тьюрингу и по Маркову эквивалентны

C. – не существует нигде не определенной вычислимой функции

D. – множество функций счетно

55. Выберите истинное всказывание:

A. – класс примитивно-рекурсивных функций шире класса частично рекурсивных функций

B. + класс частично рекурсивных функций включает класс примитивно-рекурсивных функций

C. – класс частично рекурсивных функций совпадает с классом примитивно-рекурсивных функций

D. – пересечение класса частично рекурсивных функций и класса примитивно-рекурсивных функций пусто

56. Функция f называется частично рекурсивной относительно множества простейших функций из базового набора, если она строится

A. + из простейших вычислимых функций конечным числом применения операторов суперпозиции, примитивной рекурсии и минимизации

B. – из простейших вычислимых функций конечным числом применения оператора суперпозиции

C. – из простейших вычислимых функций конечным числом применения операторов суперпозиции и примитивной рекурсии

D. – из нуль-функции и функции следования конечным числом применения операторов суперпозиции, примитивной рекурсии и минимизации

57. Функция f называется примитивно-рекурсивной относительно множества простейших функций из базового набора, если она строится

A. – из простейших вычислимых функций конечным числом применения операторов суперпозиции, примитивной рекурсии и минимизации

B. – из простейших вычислимых функций конечным числом применения оператора примитивной рекурсии

C. + из простейших вычислимых функций конечным числом применения операторов суперпозиции и примитивной рекурсии

58. Выберите истинные всказывания:

A. + всякая примитивно-рекурсивная функция всюду определена

B. + если функция f получена из примитивно-рекурсивных функций с применением операций подстановки или примитивной рекурсии, то функция f является примитивно-рекурсивной функцией

C. + все примитивно-рекурсивные функции интуитивно вычислимы

D. – все частично рекурсивные функции являются примитивно-рекурсивными

59. Возвратной рекурсией (рекурсией пробега) называется такая рекурсия, при которой

A. + значение f(x1,…,xn, y+1) зависит от x1, …, xn, y, а также от некоторых и возможно всех f(x1,…,xn, u), где u£y

B. – значение f(x1,…,xn, y+1) зависит от x1, …, xn, y, а также от f(x1,…,xn, y)

C. – значение f(x1,…,xn, y+1) зависит от f(x1,…,xn, y)

D. – значение f(x1,…,xn, y+1) зависит от x1, …, xn, y, а также от некоторых и возможно всех f(x1,…,xn, u), где u³y

60. Функции f1n+1,…,fkn+1 определены с помощью совместной рекурсии, если для всех 1£i£k имеет место следующая система равенств:

A. –

B. +

C. –

D. –

61. n-местным предикатом Pn, заданным на множестве M, называется …

A. – отображение Pn: Mn® N0

B. – отображение Pn:M ®{0,1}

C. – логическое высказывание

D. + отображение Pn:Mn®{0,1}

62. Характеристической (представляющей) функцией предиката Pn называется такая функция c Pn что …

A. cPn ()=( if Pn() – истинно then 0 else Pn())

B. – c Pn ()=( if Pn()– истинно then 0 else не определено)

C. + c Pn ()=( if Pn()– истинно then 0 else 1)

D. – c Pn ()=( if Pn()– истинно then Pn() else не определено)

63. Предикат Pn называется примитивно-рекурсивным, если …

A. + его характеристическая функция примитивно-рекурсивна

B. – его характеристическая функция частично рекурсивна

C. – его характеристическая функция вычислима

D. – существует алгоритм его вычисляющий

Оператор суперпозиции (подстановки).

64. Из совокупностей функциональных термов выберите ту, которая представляет операцию суперпозиции

A. +

B. –

C. –

65. Суперпозиция σ(S, 0) равна …

A. + 1

B. – 0

C. – x

D. – x+1

66. Суперпозиция σ(S, σ(S, x)) равна …

A. – x+1

B. – 2

C. + x+2

D. – 1

67. Суперпозиция σ(S, σ(S, 0)) равна …

A. – 1

B. – x+1

C. – x+2

D. + 2

68. Суперпозиция σ(0, σ(S, 0)) равна

A. + 0

B. – 1

C. – x+1

D. – x

69. Суперпозиция σ(S, σ(S, I22)) равна

A. + x2 + 2

B. – x2

C. – x1+1

D. – x1+2

70. Функция fn(x1, x2, …, xn) получена из функций fm0, fn1, fn2, …, fnm с помощью операции суперпозиции (подстановки), если …

A. – fn(x1, x2, …, xn)=fn1(fm0(x1, x2, …, xn), …, fnm(x1, x2, …, xn))

B. –

C. + fn(x1, x2, …, xn)=fm0(fn1(x1, x2, …, xn), …, fnm(x1, x2, …, xn))

D. –

Оператор примитивной рекурсии.

71. Из совокупностей функциональных термов выберите ту, которая представляет операцию примитивной рекурсии

A. –

B. +

C. –

72. Функция задана схемой примитивной рекурсии с помощю функций g(x)=2x и h(x,y,z)=zx. Задайте функцию аналитически.

A. –

B. –

C. –

D. +

73. Функция заданя соотношениями

f(x,0)=0;

f(x,y+1)=f(x,y)+x.

Вычислите f(5,2)

A. – 5

B. – 7

C. – 25

D. + 10

74. Выберите из предложенных функций, функцию f, полученную с помощью примитивной рекурсии из g и h, где g(x)=1, h(x, y,z)=z+x

A.+ f(x, y)=xy+1

B.– f(x, y)=1+x

C.– f(x, y)=x+y

D.– f(x, y)=1+y

75. Выберите из предложенных функций, функцию f, полученную с помощью примитивной рекурсии из g и h, где g(x)=x, h(x, y,z)=zx.

A.– f(x, y)=xy

B.– f(x, y)=zx

C.+ f(x, y)=xy+1

D.– f(x, y)=xy

76. Выберите из предложенных функций, функцию f, полученную с помощью примитивной рекурсии из g и h, где g(x)=x, h(x, y,z)=yz.

A.– f(x, y)=y×x!

B.+ f(x, y)=y! ×x

C.– f(x, y)=у×z

D.- f(x, y)=x×y

77. Функция f(x) получается из функции g(x) с помощью итерации если выполняется схема …

A. +

B. –

C. –

D. –

78. Функция f(x, y) получается из функции g(x) с помощью примитивной рекурсии если выполняется схема …

A. –

B. –

C. –

D. +

Оператор минимизации.

79. Из совокупностей функциональных термов выберите ту, которая представляет операцию минимизации

A. –

B. –

C. +

80. Найдите g-1(x), если известно, что g(x)=Sg и D(g)=N0

A. – g-1(x)=x

B. + g-1(x)=x при x=0 и x=1, иначе не определена

C. – g-1(x)=x при x=0, иначе не определена

D. – g-1(x)=x при x=1, иначе не определена

81. Найдите m x[Sg x=1]

A. – x

B. – 0

C. – не определено

D. + 1

82. Минимизируйте функцию f(x1,x2)= x1 — x2, по переменной x1, учитывая D(f)ÍN02

A. – x1+ x2

B. – x2 – x1

C. + 0 при x1 =0 и x2=0, иначе не определено

D. – x1 + x2 при x1 ³ x2, иначе не определено

83. Минимизируйте по x функцию f(x)= 10

A. – 10

B. + 0 при x=10, иначе не определено

C. – 10 при x=10, иначе не определено

D. – x

84. f(x1,…,xn) получена из функции g(x1,…,xn, y) в результате применения операции минимизации (m-операции) по y, если …

A. +

B. +

C. –

D. –

85. Будем говорить, что функция f(x) получена из функции g(x) в результате операции обращения, и обозначать f(x)«g-1(x), если …

A. f(x)=my[g(y)=0]

B. g(x)=my[f(y)=x]

C. + f(x)=my[g(y)=x]

D. f(x)=1/g(x)

86. Минимизируйте функцию f(x)= x1 + x2, по переменной x2, учитывая D(f)ÍN02

A. – x1 – x2 при x1 ³ x2, иначе не определено

B. + x2 – x1 при x2 ³ x1, иначе не определено

C. – 0 при x1 =0 и x2=0, иначе не определено

D. – x1 + x2 при x1 ³ x2, иначе не определено

Машины Тьюринга. Тезис Черча-Тьюринга.

87. За начальное состояние машины Тьюринга отвечает символ внутреннего алфавита …

A. – qn

B. – R

C. – q0

D. + q1

88. За конечное состояние машины Тьюринга отвечает символ внутреннего алфавита …

A. – qn

B. – S

C. + q0

D. – q1

89. Внешним алфавитом машины Тьюринга является …

A.+ A={ a0,a1,…,an}

B.– Q={q0,q1,…,qn}

C.– {R, L,S}

D.– {a, b, …}

90. Работа машины Тьюринга продолжается до тех пор, …

A. – пока команда сдвига не будет обозначать отсутствие сдвига – S

B. + пока машина Тьюринга не придёт в состояние q0

C. – не будет получен результат вычисления

D. – не будут пройдены все непустые ячейки ленты

91. Лента машины Тьюринга …

A. – ограничена слева

B. – ограничена справа

C. – ограничена с обеих сторон

D. – не ограничена ни с одной стороны

92. Внутренним для машины Тьюринга является алфавит

A. A={ a0,a1,…,an}

B. + Q={q0,q1,…,qn}

C. – {R, L,S}

D. – {a, b, …}

93. Алфавитом сдвигов для машины Тьюринга является алфавит

A. A={ a0,a1,…,an}

B. Q={q0,q1,…,qn}

C. + {R, L,S}

D. – {a, b, …}

94. Минимальным элементом памяти машины Тьюринга является (ячейка)

95. В ячейке ленты машины Тьюринга может храниться…

A. + только одна буква внешнего алфавита

B. – только одна буква внутреннего алфавита

C. – произвольное количество букв внешнего алфавита

D. – произвольное количество букв внутреннего алфавита

96. Управляющая головка Машины тьюринга в каждый момент времени "умеет" …

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

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

C. – обозревать и записывать символ в одной ячейке ленты

D. – обозревать и считывать символ в одной ячейке ленты

97. Дана функциональная схема. На ленте машины Тьюринга изначально записано слово 10100. Головка машины находится в конфигурации стандартного начала (первый символ слова). Укажите, что будет записано на ленте после выполнения данной функциональной схемы.

A. – 10101

B. – 10110

C. + 10011

D. – 11001

98. Дана функциональная схема. На ленте записано слово 1011. Головка машины Тьюринга находится в конфигурации стандартного начала (первый символ слова). Укажите первое действие, которое выполнит головка машины Тьюринга.

A. – сдвинется вправо на ноль в состоянии q1, заменив 1 на 0

B. – сдвинется влево, изменит состояние на q2 и заменит 1 на 0

C. + сдвинется вправо на ноль в состоянии q1, ничего не меняя

D. – сдвинется влево, изменит состояние на q2 и сотрет 1

99. Дана функциональная схема машины Тьюринга. На ленте записано слово 13201. При выполнении функциональной схемы головка на ленте машины дошла до конца вправо и встала на пустой символ. Укажите следующее действие, которое выполнит головка.

A. – поставит вместо пустого символа единицу, сдвинется влево и перейдет в состояние q3

B. + сдвинется влево не внося изменений в ячейку и встанет на последний символ слова (1), перейдя в состояние q2

C. – сдвинется вправо в состояние q0, стерев последний символ

D. – не произведя сдвига на ячейку поставит вместо пустого символа единицу и перейдет в состояние q0

100. Укажите, какую функцию вычисляет данная функциональная схема машины Тьюринга в четверичной системе счисления.

A. – x-4

B. – 3*x

C. – x+y

D. + x+4

101. Укажите, какую функцию вычисляет данная функциональная схема машины Тьюринга

A. –

B. +

C. –

D. –

102. Укажите, какую функцию вычисляет данная функциональная схема машины Тьюринга.

A. f(x, y)=x+y

B. + f(x)=1+x

C. f(x)=x-1

D. – f(x, y)=x-y

103. Дана функциональная схема машины Тьюринга. Головка машины находится в конфигурации стандартного начала. На ленте записано слово 3210221. Введите слово, которое будет записано на ленте машины после выполнения работы (ответ вводится с клавиатуры без пробела).

(ответ: 1)

104. Дана функциональная схема машины Тьюринга. На ленте записано слово 30121. Головка машины Тьюринга находится на последнем символе слова (1). Введите, слово, которое будет записано на ленте машины после выполнения следующего шага работы (ответ вводится с клавиатуры без пробела).

(ответ: 30123)

105. Дана функциональная схема машины Тьюринга. Головка машины находится в конфигурации стандартного начала (первый символ слова). На ленте записано слово 1231. Введите, слово, которое будет записано на ленте машины после выполнения работы (ответ вводится с клавиатуры без пробела).

(ответ: 1301)

106. В модели машины Тьюринга внешняя память представлена в виде…, разделенной на секции одинакового размера – ячейки памяти.

A. – конечной ленты

B. – бесконечной вправо ленты

C. + есконечной в обе стороны ленты

D. – конечной влево ленты

107. Конечное число символов, с помощью которых кодируется информация, подаваемая в машину, и информация, которая вырабатывается в процессе её работы, называется…

A. + внешним алфавитом

B. – внутренним алфавитом

C. – совокупностью

D. – алфавитом

108. В модели машины Тьюринга нет элементарной команды …

A. + B (Назад)

B. – R (Вправо)

C. – L (Влево)

D. – S (На месте)

109. Унарная запись натурального числа n — это набор, состоящий из…

A. – (n-1)-ого символа "|"

B. + (n+1)-ого символа "|"

C. – n символов "|"

D. – (n+1)-ого символа "1"

110. Необходимо построить программу, реализующую алгоритм перевода слова из X палочек в слово из X+1 палочки. Каретка машины находится над крайней слева палочкой.
Какая из приведённых программ реализует этот алгоритм?

A.– Q0| —> |LQ1; Q1| —> |SQ1

B.– Q1| —> |RQ1; Q1| —> |SQ0

C.– Q1| —> |LQ1; Q1| —> |SQ1

D.+ Q1| —> |LQ1; Q1| —> |SQ0

111. Начальная конфигурация машины Тьюринга имеет вид: 110Q11.
После выполнения программы

Q10 —> 1LQ2

Q11 —> 0LQ1

Q21 —> 0LQ3

Q20 —> 0RQ3

Q2^ —> 1SQ1

Q3^ —> ^RQ0

Q3 0—> 0LQ3

Q31 —> 1LQ3

будет получено слово…

A. – 1011

B. + 1010

C. – 1111

D. – 1000

113. На ленте имеется два набора символов "|", разделённых двумя пустыми ячейками. Каретка машины находится под крайним справа символом "|" в первом наборе. Машина работает в соответствии с программой:

Q1| —> |LQ1

Q1^ —> |LQ2

Q2 ^ —> |LQ3

Q3| —> |LQ3

Q3 ^ —> ^RQ4

Q4| —> ^RQ5

Q5| —> ^RQ6

Q6| —> ^RQ0

Какой алгоритм реализует данная машина Тьюринга?

A. + сложения двух унарных чисел

B. – вычитания двух унарных чисел

C. – сложения двух унарных чисел и вычитания из результата тройки

D. – вычитания тройки из первого числа

Нормальные алгорифмы Маркова

114. Пусть m принадлежит N, A={а0,а1,…,аm} — алфавит, не содержащий в качестве букв символов "—>" и ".". P, Q принадлежат A*. Простой формулой подстановок (или простой продукцией) в алфавите A называется слово вида: …

A. – P —> .Q

B. + P —> Q

C. – P. —> Q

D. – P. —> .Q

115. Пусть S — нормальная схема в алфавите A, а Р, R принадлежат A*. Факт того, что нормальная схема S заключительно переводит слово P в слово R, обозначается…

A. S:Р|-.R

B. S:Р|=> R

C. S:Р|- R

D. + S:Р|=>.R

116. Пусть A, B — конечные алфавиты, не содержащие в качестве букв символов "—>" и ".", причём A содержится в B. Нормальный алгорифм над алфавитом A задаётся…

A.
– алфавитом A и нормальной схемой в алфавите A

B. + алфавитом B и нормальной схемой в алфавите B

C. – алфавитом A и нормальной схемой в алфавите B

D. – алфавитом B и нормальной схемой в алфавите A

117. Пусть дано слово P в алфавите A={a, b,c} и задана нормальная схема в алфавите A.

ab —> c

cb —> a

a —>.^

Результатом применения данного нормального алгорифма к слову P=abbcb будет слово…

A. – bbcb

B. – aa

C. + a

D. – cb

118. Пусть дан нормальный алгорифм в алфавите {|,*}, заданный нормальной схемой

*|| —> |

*| —> .|

^—> *

Среди данных слов выберите то, к которому не применим указанный нормальный алгорифм.

A. – |||

B. + **

C. – ||*

D. – |*|

119. Пусть дан нормальный алгорифм в алфавите {|,*}, заданный нормальной схемой

* —> *

| —> .||

^ —> *

Среди данных слов выберите то, к которому применим указанный нормальный алгорифм.

A. – |||*|

B. – **

C. – |*|*|

D. + |||||

120. Среди предложенных нормальных алгорифмов выберите тот, который не применим ни к одному непустому слову в алфавите {a, b}.

A. a —> c c —> a

B. b —> c c —> b

C. + a —> b b —> a

D. – a —> b b —> c

121. Необходимо записать кортеж <1,2> в унарной форме. Выберите верную запись.

A. – ||*|||

B. + ||^|||

C. – |*||

D. – |^||

122. Задана нормальная схема

* —>^

#|| —> +

+| —> |||+

+ —> .|

^—>#

Указанный нормальный алгорифм, преобразует унарное число m*n в…

A. + число 3(m+n)

B. – целую часть числа 3(m+n)

C. – целую часть числа (3m-n)/2

D. – число 3(m-n)

123. Пусть для слова в алфавите А={a, b,c, d} задана следующая схема подстановок

dac->acd

cb->ad

Результатом применения ее к слову dacacbabc будет…

A. + acacdbabc

B. – acdaadabc

C. – acdacbabc

D. – acdaadabc

124. Пусть m принадлежит N, A={а0,а1, …, аm} — алфавит, не содержащий в качестве букв символов "—>" и ".". P, Q принадлежат A*. Заключительной формулой подстановок в алфавите A называется слово вида: …

A. – P —> Q

B. + P —> .Q

C. – P. —> Q

D. – P. —>. Q

Нумерация.

125. Множество X счетно, если …

A. + существует биекция f: X —> N

B. – существует инъекция f: X —> N

C. – существует сюръекция f: X —> N

D. – установлено соответствие f между X и N

126. Множество X эффективно счетно, если существует …

A. – биекция f: X—>N

B. – инъекция f: X —> N, такая, что функции f и f-1 эффективно вычислимы

C. – сюръекция f: X —> N, такая, что функции f и f-1 эффективно вычислимы

D. + биекция f: X—>N, такая, что функции f и f-1 эффективно вычислимы

127. Перечислением (нумерацией) множества X называется …

A. – отображение g: N —> X

B. + сюръективное отображение g: N —> X

C. – сюръективное отображение g: X —> N

D. – инъективное отображение g: X —> N

128. Говорят о перечислении (нумерации) множества X без повторений, если задано …

A. + биективное отображение g: N —> X

B. – сюръективное отображение g: N —> X

C. – инъективное отображение g: N —> X

D. – инъективное отображение g: X —> N

129. Не является эффективно счетным множество …

A. – N x N

B. – N0 x N0 x N0

C. – Uk>0Nk, множество всех конечных последовательностей натуральных чисел

D. + N0 x R

130. Не является эффективно счетным множество …

A. – вычислимых n-местных функций

B. – программ

C. + всех функций

D. – всюду определенных вычислимых функций

Логика предикатов

131. Чем отличается логика предикатов от логики высказываний.

A. — ничем

B. + язык логики предикатов вводит рассмотрение утверждения, отнесённые к предметам, т. е. производится более детальный анализ предложений.

C. – только названием

D. – нет правильного варианта ответа.

132.

Найдите квантор всеобщности

A. + forall

B. — ∃

C. — X

D. – F

133.

Найдите квантор существования

A. — forall

B. + ∃

C. — X

D. – F

134.

Квантор существования называется … к квантору всеобщности

— соседским

— двойным

— обратным

+ двойственным

135.

Формула называется … в данной интерпретации, если она принимает значение И для всех возможных значений её свободных переменных (если они есть)

A. — Бинарной

B. — Ложной

C. + Истинной

D. — Существующей

136.

Формула называется … в данной интерпретации, если она принимает значение Л для всех возможных значений её свободных переменных (если они есть)

A. — Бинарной

B. + Ложной

C. — Истинной

D. — Существующей

137.

Формула А логически ведет формулу В тогда и только тогда, когда формула … логически общезначима.

A. + А→В

B. – А+В

C. — ┐А

D. — ┐В

138.

Формулы А и В … тогда и только тогда, когда формула АВ логически общезначима

A. + Равносильны

B. — неравны

C. — противоположны

D. — нет правильного варианта ответа

139.

Формула А логически ведет формулу В и А истинно в данной интерпретации, то В в данной интерпретации …

A. — Бинарно

B. — Ложно

C. + Истинно

D. — Существует

140.

Отрицание формулы, начинающейся с кванторов, … формуле, полученной заменой каждого квантора на двойственной и перенесением знака за кванторы.

A. + Равносильно

B. — неравно

C. — противоположно

D. — нет правильного варианта ответа

Интуитивное понятие алгоритма. алгоритмы в математике

Наташа

Узнать стоимость за 15 минут

Распродажа дипломных

Подпишись на наш паблик в ВК

Нужна работа?