Учебно-методический комплекс

8Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Псковский государственный педагогический университет

имени

Физико-математический факультет

Кафедра алгебры и геометрии

УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС

учебной дисциплины

ДПП. Ф.10 Теория алгоритмов

032100.00 Математика с дополнительной специальностью

(код ОКСО 050201)

Физико-математический факультет

Форма обучения дневная

4 курс: 8 семестр

Псков

2006

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Псковский государственный педагогический университет

имени

Физико-математический факультет

Кафедра алгебры и геометрии

«Утверждаю»

Декан физико-математического факультета

_______________

«_____»______________200___г.

РАБОЧАЯ ПРОГРАММА

учебной дисциплины

ДПП. Ф.10 Теория алгоритмов

032100.00 Математика с дополнительной специальностью

(код ОКСО 050201)

Физико-математический факультет

Форма обучения дневная

4 курс: 8 семестр

Всего часов: 90

Лекции: 30

Практические занятия: 16

Лабораторные работы: 0

Самостоятельная работа: 44

Экзамен: 8 семестр

Псков

2007

Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности 032100.00 Математика с дополнительной специальностью.

Номер государственной регистрации

№ 000 пед/сп (новый)

31» января 2005 г.

ДПП. Ф.10 Теория алгоритмов

Рабочая программа принята на заседании кафедры алгебры и геометри.

Протокол № ____ заседания кафедры

«____»____________ 200 __ г.

Программа разработана доцентом кафедры информатики

__________________________

Заведующий кафедрой алгебры и геометрии

________________________

1. Пояснительная записка

1.1 Требования к содержанию учебной дисциплины из Государственного образовательного стандарта.

Введение. Алгоритмы в математике. Основные черты алгоритмов. Необходимость уточнения понятия алгоритма. Числовые функции и алгоритмы их вычисления. Понятие вычислимой функции, разрешимого множества.

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

Логические операции. Ограниченные кванторы. Подстановка функций в предикат. Кусочное задание функции.

Машины Тьюринга. Понятие машины Тьюринга Операции с машинами. Тезис Черча-Тьюринга.

Рекурсивные и рекурсивно-перечислимые множества. Рекурсивно-перечислимые предикаты, их свойства. Рекурсивно-перечислимые множества. Нумерация. Универсальная функция. Теорема Клини. Неразрешимые алгоритмические проблемы. Алгоритмическая сводимость.

1.2 Цели и задачи дисциплины.

Курс «Теория алгоритмов» должен способствовать развитию у будущего учителя школы достаточно широкого взгляда на методы и технологии программирования и вооружить его конкретными знаниями, дающими ему возможность преподавать курс математики в средней школе и квалифицированно вести факультативные занятия.

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

Требования к уровню подготовки по предмету

Студент, изучивший данную дисциплину, должен знать:

·  основные понятия теории формальных грамматик: классификацию Хомского, деревья вывода, принципы использования формальных грамматик для описания языков программирования;

·  требования к алгоритмам; определение и принцип функционирования машины Тьюринга;

·  понятие рекурсии, рекурсивной функции, оператора минимизации;

·  понятие алгоритмической неразрешимости; формулировку и доказательство теоремы о проблеме остановки;

·  определения разрешимого и перечислимого множества;

·  определение конечного автомата и способы его задания; определение алгебры регулярных выражений; понятие эквивалентности состояний и автоматов.

Студент, изучивший данную дисциплину, должен уметь:

·  строить дерево вывода для цепочек, выводимых в контекстно-свободных грамматиках;

·  строить простые машины Тьюринга и описывать протоколы их работы для конкретных данных;

·  строить разрешающие и перечисляющие процедуры для множеств, заданных словесными описаниями;

·  переходить от табличного задания конечного автомата к его графу переходов;

·  распознавать принадлежность слова данному регулярному выражению по источнику (графу регулярного выражения);

·  строить минимальный автомат, эквивалентный данному.

Студент, изучивший данную дисциплину, должен иметь представление:

·  о прикладных логических исчислениях - исчислении с равенством, формальной арифметике и теореме Геделя о ее неполноте;

·  об алгоритмических проблемах теории грамматик;

·  об операциях над машинами Тьюринга;

·  о существовании перечислимого множества, которое не является разрешимым;

·  о мерах сложности вычислений, полиномиальной сводимости, классах P и NP и о понятии NP-полной задачи.

1.3 Особенности построения дисциплины.

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

  Курс «Теории алгоритмов» изучается в 6-м семестре, по курсу предусмотрен  экзамен. В целом на изучение курса отведено 112 часов, из которых  56  часов аудиторных.

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

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

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

2. Структура учебной дисциплины.

Наименование тем	Всего часов	Аудиторные занятия	Самостоя-тельная работа
Лекции	Практики
Тема 1. Формальные системы	16	6	2	8
Тема 2. Частично рекурсивные функции и предикаты	30	10	6	14
Тема 3. Машина Тьюринга	24	8	4	12
Тема 4. Рекурсивные и рекурсивно перечислимые множества и предикаты	20	6	4	10
ИТОГО:	90	30	16	44

3. Содержание учебной дисциплины

Тема 1. Формальные системы и вычислимые функции.

Общее понятие формальной системы. Алгоритмы в математике. Основные черты алгоритмов. Необходимость уточнения понятия алгоритма. Числовые функции и алгоритмы их вычисления. Понятие вычислимой функции, разрешимого множества..

Тема 2. Частично рекурсивные функции и предикаты.

Частично рекурсивные функции и рекурсивные предикаты. Класс частично рекурсивных функций. Исходные функции. Операторы подстановки, примитивной рекурсии, минимизации. Рекурсивные предикаты. Логические операции. Ограниченные кванторы. Подстановка функций в предикат. Кусочное задание функции.

Тема 3. Машина Тьюринга.

Машины Тьюринга. Понятие машины Тьюринга Операции с машинами. Тезис Черча-Тьюринга.

Тема 4. Рекурсивные и рекурсивно перечислимые множества и предикаты.

Рекурсивные и рекурсивно-перечислимые множества. Рекурсивно-перечислимые предикаты, их свойства. Рекурсивно-перечислимые множества. Нумерация. Универсальная функция. Теорема Клини. Неразрешимые алгоритмические проблемы. Алгоритмическая сводимость.

4. Методические материалы и рекомендации для преподавателя

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

1.  Является ли разрешимым множество всех булевых формул, эквивалентных данной?

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

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

4.  Можно ли построить машину Тьюринга, которая для произвольной функции, заданной своим описанием, отвечает на вопрос "принимает ли эта функция на некоторых данных значение 0"?

5.  Может ли конечный автомат распознавать палиндромы произвольной длины?

6.  Может ли конечный автомат распознавать язык {0n1n}?

7.  Принадлежит ли данное слово a языку, заданному регулярным выражением А?

8.  Построить грамматику, порождающую язык {anbmambn}.

9.  Для данного арифметического выражения построить его дерево вывода в грамматике арифметических выражений.

10.  Построить машину Тьюринга, вычисляющую предикат "слово a в алфавите {0, 1} - палиндром" (т. е. справа налево читается так же, как и слева направо).

11.  a - слово в алфавите {a, b, c}. Построить одноленточную машину Тьюринга, которая сохраняет в a в том же порядке буквы a, b и удаляет c, не оставляя пробелов. Например, T(acbbca)=abba.

12.  Построить конечный автомат, который для произвольного слова a в алфавите {a, b, c} отвечает на вопрос: содержится ли в a фиксированное слово b?

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

4.2. Примерный перечень тем рефератов.

1.  Формальные грамматики. Классификация Хомского. Грамматики типа 2 и их использование при построении трансляторов.

2.  Понятие неоднозначности в теории грамматик. Привести примеры неоднозначных грамматик и неоднозначного вывода в них.

3.  Алгоритмические проблемы в теории грамматик.

4.  Основная идея доказательства существования универсальной машины Тьюринга и блок-схема ее построения.

5.  Общая схема доказательства эквивалентности машин Тьюринга и рекурсивных функций.

6.  Алгоритмические проблемы в теории автоматов. Что могут и что не могут конечные автоматы.

7.  Связь формальных грамматик и конечных автоматов.

8.  Сравнение сложности вычислений на одноленточной и многоленточной машинах Тьюринга на примере распознавания палиндромов в двухбуквенном алфавите.

4.3. Примерный перечень вопросов к экзамену по всей дисциплине.

1.  Интерпретации и модели.

2.  Семантическая и формальная непротиворечивость.

3.  Полнота. Непротиворечивость и семантическая полнота исчисления высказываний.

4.  Теорема Геделя о полноте исчисления предикатов.

5.  Общее понятие формальной системы. Примеры.

6.  Формальная арифметика. Теорема Геделя о неполноте формальной арифметики (формулировка).

7.  Формальные языки и формальные грамматики и классификация Хомского.

8.  Контекстно-свободные грамматики и деревья вывода.

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

10.  Формализация понятия алгоритма и универсальные алгоритмические модели.

11.  Машина Тьюринга - основные определения. Понятие вычислимости на машине Тьюринга.

12.  Операции над машинами Тьюринга. Универсальная машина Тьюринга.

13.  Понятие алгоритмической неразрешимости. Теорема Райса.

14.  Проблема остановки - формулировка теоремы и ее доказательство.

15.  Понятие рекурсии. Примитивно-рекурсивные функции. Примеры.

16.  Неограниченный оператор минимизации. Примеры. Определение частично-рекурсивной функции.

17.  Разрешимые и перечислимые множества и предикаты.

18.  Конечные автоматы. Основные определения. Способы задания автоматов.

19.  Алгоритмические возможности: что могут и что не могут вычислять автоматы. Примеры.

20.  Эквивалентность автоматов. Алгоритм минимизации автоматов.

21.  Автоматы и логические схемы. Программная реализация автоматов.

5. Формы и методы самостоятельной работы.

Реферат по указанной преподавателем теме согласно перечня 4.2.

6. Формы текущего, промежуточного и итогового контроля.

Контрольные работы, тестирование, экзамен.

7. Список литературы

Основная

1.  и др. Теория алгоритмов и дедуктивный вывод: Учеб. пособие. – М., 1999.

2.  Гладкий логика. - М.: Российск. гос. гуманит. ун-т, 1998.

3.  Иванищев в теорию алгоритмических сетей. – СПб, 2000.

4.  Информатика: Учебник /Под ред. . – М.: Финансы и статистика, 2002.

5.  , Максимова по теории множеств, математической логике и теории алгоритмов. - М.: Физматлит, 2001.

6.  Лексаченко . Множества. Вероятность. - М.: Вузовская книга, 2001.

7.  Лихтарников логика: Учеб. для вузов. – СПб.: Лань, 1999.

8.  Мальцев лекций по курсу "Теория алгоритмов".– СПб., 1999.

9.  Мальцев лекций по курсу “Теория алгоритмов”. – СПб, 1999.

10.  Хопкрофт Дж., Ульман Дж. Введение в теорию автоматов, языков и вычислений. – 2. изд./ Пер. с англ. - М.: Вильямс, 2002.

Дополнительная

1.  Булос Дж., Вычислимость и логика. - М.: Мир, 1994.

2.  , Сапоженко задач по дискретной математике. - М.: Наука, 1977.

3.  Алгоритмы: построение и анализ/ Пер. с английского под ред. А. Шеня. - М.: МЦМНО, 2002.

4.  , Адельсон-Вельский математика для инженера. - М.: Энергоатомиздат, 1988.

5.  Введение в математическую логику. - М.: Наука, 1984

6.  Столл. Множества. Логика. Аксиоматические теории. - М.: Просвещение, 1968.

Методические указания студентам по подготовке к практическим занятиям.

Контролирующие материалы для аттестации студентов по дисциплине.

1. Дополнение к области определения некоторой вычислимой функции _________ рекурсивно перечислимым

A) может не быть

B) разъединено с

C) не может быть

D) должно быть

2. В системе Пеано единственным неопределимым отношением является

A)

B)

C)

D)

3. Множество ________ тогда и только тогда, когда оно является _______ некоторой вычислимой функции

A) перечислимо, множеством значений

B) разрешимо, множеством значений

C) разрешимо, областью определения

D) перечислимо, областью определения

4. Фразы, соединяемые функтором, называются

A) аргументами

B) формульными

C) предложениями

D) регулярными

5. Если и рекурсия проводится по , то функция равна

A) 0

B)

C) x+z

D)

6. Любая непротиворечивая система арифметики с рекурсивной системой аксиом

A) совпадает с системой Пеано

B) является замкнутой

C) должна быть полной

D) не может быть полной

7. Утверждение арифметики Пеано называется неразрешенным, если оно

A) противоречит системе аксиом

B) и его отрицание опровержимы

C) истинно, но недоказуемо

D) и его отрицание w-противоречивы

8. Если , то функция в рекуррентной формуле равна

A) m+1

B) m(n+1)

C) m!

D) m+n+1

9. Если и рекурсия проводится по , то функция равна

A)

B) t+x

C) t+y

D)

10. Функция, полученная из вычислимой с помощью рекурсии, является

A) вычислимой

B) примитивно рекурсивной

C) дифференцируемой

D) частично рекурсивной

11. Если , то функция в рекуррентной формуле равна

A)

B)

C) 1

D)

12. Если , то функция (n, m) в рекуррентной формуле равна

A) m+n-1

B) 2m

C) (m+n)/2

D) m+n+1

13. Множество номеров несамоприменимых машин Тью­ринга

A) неразрешимо

B) рекурсивно перечислимо

C) неперечислимо

D) рекурсивно

14. Геделевский номер, равный , имеет функция

A)

B)

C)

D)

15. Множество истинных утверждений

A) носит название системы аксиом

B) перечисляет все системы аксиом

C) выводится из системы аксиом

D) не выводится из системы аксиом

16. Если и рекурсия проводится по переменной , то функция равна

A) m+x

B) 1

C) m+y

D)

17. Показал возможность существования универсальной вычислительной машины, способной выполнить любую эффективную процедуру

A) А. Тьюринг

B) Д. Гильберт

C) А. Марков

D) К. Гёдель

18. Машина Тьюринга есть совокупность компонент

A) пяти

B) двух

C) четырех

D) трех

19. Множество натуральных чисел является

A) только рекурсивным

B) только перечислимым

C) рекурсивным и перечислимым

D) простейшим

20. Полнота – это условие, что для любого утверждения s одно из утверждений s и Øs

A) ложно

B) доказуемо

C) опровержимо

D) истинно

21. Если и рекурсия проводится по , то функция равна

A)

B) zy

C)

D)

22. Существуют три основных класса фраз: имена, предложения и

A) дизъюнкты

B) функторы

C) предикаты

D) кванторы

23. Система Пеано содержит аксиом

A) 2

B) 3

C) 4

D) 5

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

A) автоматным языком

B) регулярным языком

C) метаязыком языком

D) алгоритмическим языком

25. Если множество не является множеством значений никакой функции, то оно

A) нерекурсивно, но рекурсивно перечислимо

B) рекурсивно, но не перечислимо

C) нерекурсивно и неперечислимо

D) рекурсивно, но не перечислимо

26. Выражение является

A) командой

B) элементом алфавита

C) исходной ситуацией

D) машиной Тьюринга

27. Если и рекурсия проводится по переменной , то функция равна

A) m+y

B) 2+m

C) m+1

D) m+x

28. Усеченная разность равна

A) 3

B) 0

C) -3

D) 5

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 и B – рекурсивные множества, то рекурсивны также множества I.
II.
III.

A) только I и III

B) только I и II

C) только II

D) I, II и III

35. Осмысленные конечные последовательности символов из алфавита L называются

A) программой

B) утверждениями

C) командами

D) словарем

36. Множество составных чисел является

A) только перечислимым

B) только рекурсивным

C) рекурсивным и перечислимым

37. порождающим Каждая п. р.ф имеет число номеров

A) ограниченное

B) небольшое

C) бесконечное

D) индивидуальное

38. Всякое непустое ______ множество является _________ некоторой всюду определенной вычислимой функции

A) продуктивное, множеством значений

B) креативное, областью определения

C) рекурсивно перечислимое, множеством значений

D) рекурсивное, областью определения

39. Язык, на котором описывается другой язык, называется

A) автоматным языком

B) формулой языка Ъ

C) формальной системой

D) метаязыком

40. Челночный алгоритм является алгоритмом

A) регулярным

B) нелинейным

C) дискретным

D) марковским

41. Если A и B – рекурсивные множества, то рекурсивны также множества I.
II.
III.

A) только I и II

B) I, II и III

C) только I и III

D) только II

42. Если и рекурсия проводится по переменной , то функция равна

A)

B) t+x+y+z

C)

D) ty

43. Показал возможность существования универсальной вычислительной машины, способной выполнить любую эффективную процедуру

A) А. Тьюринг

B) К. Гёдель

C) Д. Гильберт

D) А. Марков

44. Формальная грамматика, позволяющая построить любую правильную цепочку символов, называется грамматикой

A) регулярной

B) автоматной

C) нормальной

D) порождающей

45. Функция имеет гёделевский номер, равный

A) 9

B) 13

C) 19

D) 3

46. В любой рекурсивно аксиоматизированной формальной системе множество доказуемых утверждений

A) рекурсивно перечислимо

B) неперечислимо

C) разрешимо

D) нерекурсивно

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

A) вычислимым

B) рекурсивно перечислимым

C) рекурсивным

D) эффективным

48. Если и рекурсия проводится по , то функция равна

A) 0

B) x+z

C)

D)

49. Функция, определяемая как число шагов в вычислении машиной Тьюринга, называется

A) геделевским номером

B) длиной программы

C) характеристической

D) временным ресурсом

50. Внутреннее состояние машины Тьюринга обозначается

A)

B)

C)

D) П, Л, H

51. Если , то функция (n, m) в рекуррентной формуле равна

A) m+n+1

B) m+n-1

C) (m+n)/2

D) 2m

52. Если , то функция в рекуррентной формуле равна

A)

B) sin(πn)

C)

D) m+1

53. Множество натуральных чисел является

A) только рекурсивным

B) только перечислимым

C) рекурсивным и перечислимым

D) простейшим

54. Множество простых чисел является

A) только перечислимым

B) только рекурсивным

C) замкнутым

D) рекурсивным и перечислимым

55. Существуют три основных класса фраз: имена, предложения и

A) кванторы

B) дизъюнкты

C) предикаты

D) функторы

56. В рекурсивно аксиоматизированной формальной системе, в которой все доказуемые утверждения истинны, существует истинное утверждение s, так что: 1) s опровержимо; 2) Øs опровержимо

A) ни 1, ни 2

B) 2

C) 1 и 2

D) 1

57. Если и рекурсия проводится по , то функция равна

A)

B)

C)

D)

58. Пусть R – рекурсивность, а P – рекурсивная перечислимость. Тогда

A)

B)

C)

D)

59. Функция имеет гёделевский номер, равный

A) 4

B) 3

C) 5

D) 2

60. Функция имеет Гёделевский номер, равный

A) 1

B) 3

C) 4

D) 2

61. Имена и предложения называются фразами

A) замкнутыми

B) челночными

C) порождающими

D) простейшими

62. Существует команд машины Тьюринга

A) 2 типа

B) 3 типа

C) 8 типов

D) 4 типа

63. Осмысленные конечные последовательности символов из алфавита L называются

A) утверждениями

B) программой

C) командами

D) словарем

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

A) метаязыком языком

B) регулярным языком

C) автоматным языком

D) алгоритмическим языком

65. Если и рекурсия проводится по , то функция равна

A)

B)

C) zy

D)

66. Усеченная разность равна

A) -3

B) 0

C) 3

D) 5

67. Если и рекурсия проводится по переменной , то функция равна

A) y

B) x+1

C) x

D) y+1

68. Если и рекурсия проводится по , то функция равна

A)

B)

C) t+x

D) t+y

69. Теорема, связывающая рекурсивности множества с рекурсивной перечислимостью этого множества и его дополнения, называется теоремой

A) Клини

B) Поста

C) Тьюринга

D) Гёделя

70. Множество доказуемых утверждений формальной системы арифметики

A) разрешимо

B) замкнуто

C) неразрешимо

D) открыто

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

A) рекурсии

B) подстановки, рекурсии, минимизации

C) подстановки, минимизации

D) подстановки, рекурсии

72. Функция является примитивно рекурсивной, если она получается из набора исходных функций с помощью оператора: 1) рекурсии; 2) ограниченной минимизации; 3) подстановки – из перечисленного

A) 1 и 3

B) 1

C) 1, 2 и 3

73. 1 и 2 Существует команд машины Тьюринга

A) 4 типа

B) 3 типа

C) 8 типов

D) 2 типа

74. Теорема, связывающая рекурсивности множества с рекурсивной перечислимостью этого множества и его дополнения, называется теоремой

A) Клини

B) Поста

C) Гёделя

D) Тьюринга

75. Всякая вычислимая функция является вычислимой по Тьюрингу согласно

A) лемме Тьюринга

B) теореме Поста

C) тезису Чёрча

D) теореме Гёделя

76. В рекурсивно аксиоматизированной формальной системе, в которой все доказуемые утверждения истинны, существует истинное утверждение s, так что: 1) s опровержимо; 2) Øs опровержимо

A) 2

B) 1

C) 1 и 2

D) ни 1, ни 2

77. В любой рекурсивно аксиоматизированной формальной системе множество доказуемых утверждений

A) рекурсивно перечислимо

B) нерекурсивно

C) разрешимо

D) неперечислимо

78. Множество составных чисел является

A) рекурсивным и перечислимым

B) только рекурсивным

C) порождающим

D) только перечислимым

79. Если множество не является множеством значений никакой функции, то оно

A) нерекурсивно, но рекурсивно перечислимо

B) рекурсивно, но не перечислимо

C) нерекурсивно и неперечислимо

D) рекурсивно, но не перечислимо

80. Множество, если оно является множеством значений некоторой вы­числимой функции, называется

A) эффективным

B) разрешимым

C) вычислимым

D) рекурсивно перечислимым

81. Формальная грамматика, позволяющая построить любую правильную цепочку символов, называется грамматикой

A) нормальной

B) порождающей

C) автоматной

D) регулярной

82. Усеченная разность равна

A) 0

B) 3

C) 5

D) -3

83. Если множество рекурсивно, то оно является ______ всюду определенной вычислимой функции

A) ни множеством значений, ни областью определения

B) только множеством значений

C) только областью определения

D) множеством значений и областью определения

84. Входной алфавит определяется как

A)

B)

C)

D)

85. Если , то функция в рекуррентной формуле равна

A)

B)

C)

D) 1

86. Временные или пространственные характеристики процесса вычисления называются

A) представлением системы

B) классом сложности

C) интерпретацией системы

D) вычислительными ресурсами

87. Функция имеет Гёделевский номер, равный

A) 2

B) 1

C) 3

D) 4

88. Если и рекурсия проводится по , то функция равна

A)

B)

C) 0

D) 1

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

A) конечным

B) МП-автоматом

C) элементарным

D) дискретным

90. Функция имеет гёделевский номер, равный

A) 4

B) 1

C) 2

D) 5

91. Геделевский номер, равный 23, имеет функция

A) S(S(x))

B)

C)

D)

92. Система Пеано содержит аксиом

A) 3

B) 5

C) 4

D) 2

93. Множество доказуемых утверждений формальной системы арифметики

A) неразрешимо

B) открыто

C) разрешимо

D) замкнуто

94. Не существует формальной системы арифметики, удовлетворяющей условиям полноты и противоречивости согласно

A) тезису Черча

B) теории Гильберта

C) теореме Геделя

D) теореме Поста

95. Функция имеет гёделевский номер, равный

A) 3

B) 19

C) 9

D) 13

96. Если и рекурсия проводится по переменной , то функция равна

A) ty

B)

C) t+x+y+z

D)

97. Символы, которые машина Тьюринга читает и пишет на ленте, образуют

A) команды

B) конфигурацию

C) алфавит

D) выражения

98. Если множество неперечислимо, то оно _______ областью определения и ______ множеством значений всюду определенной вычислимой функции

A) может быть, может быть

B) не может быть, может быть

C) может быть, не может быть

D) не может быть, не может быть

99. Если A рекурсивно, а B – рекурсивно перечислимо, то _____ рекурсивно

A)

B)

C)

D)

100. Утверждение формально записывается как

A)

B)

C)

D)

101. w-непротиворечивая формальная система является

A) разрешимой

B) неполной

C) истинной

D) полной

102. Имена и предложения называются фразами

A) простейшими

B) челночными

C) замкнутыми

D) порождающими

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

A) подстановки, рекурсии, минимизации

B) подстановки, рекурсии

C) подстановки, минимизации

D) рекурсии

104. Конечному автомату соответствует грамматика, порождающая

A) машину Тьюринга

B) язык программирования

C) регулярный язык

D) словарь машины

105. Функция является: 1) частично вычислимой; 2) примитивно рекурсивной; 3) частично рекурсивной

A) 2 и 3

B) 1 и 2

C) 1

D) 1 и 3

106. Множество ________ тогда и только тогда, когда оно является _______ некоторой вычислимой функции

A) разрешимо, множеством значений

B) перечислимо, множеством значений

C) разрешимо, областью определения

D) перечислимо, областью определения

107. Если и рекурсия проводится по , то функция равна

A) t+x

B) t+y

C)

D)

108. Если , то функция в рекуррентной формуле равна

A) m(n+1)

B) m+1

C) m!

109. m+n+1 Не существует формальной системы арифметики, удовлетворяющей условиям полноты и противоречивости согласно

A) теореме Поста

B) тезису Черча

C) теореме Геделя

D) теории Гильберта

110. Если и рекурсия проводится по переменной , то функция равна

A)

B)

C) t+x+y+z

D) ty

111. Множество ________ тогда и только тогда, когда оно является _______ некоторой вычислимой функции

A) перечислимо, областью определения

B) разрешимо, областью определения

C) разрешимо, множеством значений

D) перечислимо, множеством значений

112. Марковский алгоритм – это алгоритм

A) стохастический

B) нормальный

C) недетерминированный

D) нелинейный

113. Функция, определяемая как число шагов в вычислении машиной Тьюринга, называется

A) длиной программы

B) временным ресурсом

C) геделевским номером

D) характеристической

114. Символы, которые машина Тьюринга читает и пишет на ленте, образуют

A) алфавит

B) конфигурацию

C) команды

D) выражения

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

A) эффективным

B) рекурсивно перечислимым

C) вычислимым

D) рекурсивным

116. Геделевский номер, равный 23, имеет функция

A)

B)

C) S(S(x))

D)

117. Если множество нерекурсивно, то оно _______ областью определения и ______ множеством значений всюду определенной вычислимой функции

A) не может быть, может быть

B) может быть, не может быть

C) может быть, может быть

D) не может быть, не может быть

118. Если и рекурсия проводится по переменной , то функция равна

A) 0

B) 1

C)

D)

119. Множество номеров самоприменимых машин Тьюринга

A) неперечислимо, но разрешимо

B) ни перечислимо, ни разрешимо

C) рекурсивно перечислимо и разрешимо

D) рекурсивно перечислимо, но не разрешимо

120. Любая неразрешимая алгоритмическая проблема дает пример множества

A) неперечислимого

B) несчетного

C) неразрешимого

D) невычислимого

121. Существует команд машины Тьюринга

A) 3 типа

B) 2 типа

C) 8 типов

D) 4 типа

122. Всякое непустое ______ множество является _________ некоторой всюду определенной вычислимой функции

A) продуктивное, множеством значений

B) рекурсивно перечислимое, множеством значений

C) рекурсивное, областью определения

D) креативное, областью определения

123. Если множество неперечислимо, то оно _______ областью определения и ______ множеством значений всюду определенной вычислимой функции

A) может быть, может быть

B) может быть, не может быть

C) не может быть, не может быть

D) не может быть, может быть

124. В любой рекурсивно аксиоматизированной формальной системе множество доказуемых утверждений

A) рекурсивно перечислимо

B) неперечислимо

C) нерекурсивно

D) разрешимо

125. Функция, вычислимая по Тьюрингу, является

A) примитивно рекурсивной

B) общерекурсивной

C) характеристической

D) частично рекурсивной

126. Функция имеет Гёделевский номер, равный

A) 2

B) 4

C) 3

D) 1

127. Функция является: 1) частично вычислимой; 2) примитивно рекурсивной; 3) частично рекурсивной

A) 1 и 2

B) 1

C) 1 и 3

D) 2 и 3

128. Частично вычислимая функция

A) может быть продолжена до вычислимой

B) это частный случай вычислимой

C) не везде совпадает с вычислимой

D) вычисляется с ограниченной точностью

129. Пусть R – рекурсивность, а P – рекурсивная перечислимость. Тогда

A)

B)

C)

D)

130. Входной алфавит определяется как

A)

B)

C)

D)

131. Если и рекурсия проводится по переменной , то функция равна

A) m+y

B) 1

C) m+x

D)

132. Команда машины Тьюринга состоит из элементарных действий

A) любого числа

B) двух

C) трех

D) конечного числа

133. Утверждение арифметики Пеано называется неразрешенным, если оно

A) и его отрицание w-противоречивы

B) истинно, но недоказуемо

C) и его отрицание опровержимы

D) противоречит системе аксиом

134. Теория алгоритмов является частью

A) математического анализа

B) численных методов

C) математической логики

D) теории чисел

135. Усеченная разность равна

A) 3

B) -3

C) 5

D) 0

136. Всякая вычислимая функция является вычислимой по Тьюрингу согласно

A) лемме Тьюринга

B) тезису Чёрча

C) теореме Поста

D) теореме Гёделя

137. Если множество не является множеством значений никакой функции, то оно

A) рекурсивно, но не перечислимо

B) нерекурсивно, но рекурсивно перечислимо

C) рекурсивно, но не перечислимо

D) нерекурсивно и неперечислимо

138. Если , то функция в рекуррентной формуле равна

A)

B) sin(πn)

C)

D) m+1

139. Если и рекурсия проводится по переменной , то функция равна

A) y+1

B) x

C) x+1

D) y

140. Функция является

A) частично вычислимой

B) рекурсивной

C) общерекурсивной

D) вычислимой

141. Теорема, связывающая рекурсивности множества с рекурсивной перечислимостью этого множества и его дополнения, называется теоремой

A) Тьюринга

B) Клини

C) Гёделя

D) Поста

142. Функция является примитивно рекурсивной, если она получается из набора исходных функций с помощью оператора: 1) рекурсии; 2) ограниченной минимизации; 3) подстановки – из перечисленного

A) 1

B) 1, 2 и 3

C) 1 и 2

D) 1 и 3

143. Каждая п. р.ф имеет число номеров

A) индивидуальное

B) бесконечное

C) ограниченное

D) небольшое

144. Дополнение к области определения некоторой вычислимой функции _________ рекурсивно перечислимым

A) разъединено с

B) должно быть

C) может не быть

145. не может быть Геделевский номер, равный 23, имеет функция

A) S(S(x))

B)

C)

D)

146. Осмысленные конечные последовательности символов из алфавита L называются

A) утверждениями

B) словарем

C) командами

D) программой

147. Множество составных чисел является

A) порождающим

B) рекурсивным и перечислимым

C) только перечислимым

D) только рекурсивным

148. Если и рекурсия проводится по переменной , то функция равна

A) m+y

B)

C) m+x

D) 1

149. В рекурсивно аксиоматизированной формальной системе, в которой все доказуемые утверждения истинны, существует истинное утверждение s, так что: 1) s опровержимо; 2) Øs опровержимо

A) 2

B) ни 1, ни 2

C) 1

D) 1 и 2

150. Утверждение формально записывается как

A)

B)

C)

D)

151. Если и рекурсия проводится по переменной , то функция равна

A) ty

B)

C)

D) t+x+y+z

152. Если и рекурсия проводится по , то функция равна

A)

B)

C)

D)

153. Не существует формальной системы арифметики, удовлетворяющей условиям полноты и противоречивости согласно

A) теореме Поста

B) тезису Черча

C) теории Гильберта

D) теореме Геделя

154. Марковский алгоритм – это алгоритм

A) недетерминированный

B) стохастический

C) нормальный

D) нелинейный

155. Формальная грамматика, позволяющая построить любую правильную цепочку символов, называется грамматикой

A) автоматной

B) порождающей

C) нормальной

D) регулярной

156. Функция, равная единице тогда и только тогда, когда предикат истинен, называется

A) характеристической

B) примитивно вычислимой

C) вычислимой

D) частично рекурсивной

157. Если и рекурсия проводится по , то функция равна

A) zy

B)

C)

D)

158. Функция вычисляется по формуле

A)

B)

C)

D)

159. Входят в алфавит формального логического языка символы

A)

B)

C)

D)

160. Класс примитивно рекурсивных функций

A) входит в класс вычислимых функций

B) совпадает с классом вычислимых функций

C) содержит в себе класс вычислимых функций

D) расширяет класс вычислимых функций

161. Каждая п. р.ф имеет число номеров

A) небольшое

B) бесконечное

C) индивидуальное

D) ограниченное

162. Символы, которые машина Тьюринга читает и пишет на ленте, образуют

A) выражения

B) алфавит

C) команды

D) конфигурацию

163. Функция, полученная из вычислимой с помощью рекурсии, является

A) примитивно рекурсивной

B) дифференцируемой

C) частично рекурсивной

D) вычислимой

164. Конечное множество команд, имеющих попарно различные начальные пары символов, называется

A) алгоритмом

B) машиной Тьюринга

C) программой

D) конфигурацией

165. Функция имеет Гёделевский номер, равный

A) 4

B) 2

C) 3

D) 1

166. Если множество рекурсивно, то оно является ______ всюду определенной вычислимой функции

A) только множеством значений

B) только областью определения

C) ни множеством значений, ни областью определения

D) множеством значений и областью определения

167. Если и рекурсия проводится по , то функция равна

A)

B) x+z

C) 0

D)

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

A) автоматным языком

B) алгоритмическим языком

C) регулярным языком

D) метаязыком языком

169. Пусть R – рекурсивность, а P – рекурсивная перечислимость. Тогда

A)

B)

C)

D)

170. Временные или пространственные характеристики процесса вычисления называются

A) классом сложности

B) интерпретацией системы

C) вычислительными ресурсами

D) представлением системы

171. Если и рекурсия проводится по , то функция равна

A)

B)

C)

D)

172. Машина Тьюринга есть совокупность компонент

A) трех

B) пяти

C) двух

D) четырех

173. Множество доказуемых утверждений формальной системы арифметики

A) открыто

B) разрешимо

C) замкнуто

D) неразрешимо

174. Композиция и равна

A)

B)

C)

D) 1

175. Всякое непустое ______ множество является _________ некоторой всюду определенной вычислимой функции

A) рекурсивно перечислимое, множеством значений

B) креативное, областью определения

C) рекурсивное, областью определения

D) продуктивное, множеством значений

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

A) подстановки, рекурсии

B) рекурсии

C) подстановки, рекурсии, минимизации

D) подстановки, минимизации

177. Установление соответствия между элементарными высказываниями формальной теории и содержательными высказываниями некоторой предметной области называется

A) интерпретацией теории

B) классом функторов

C) эффективной процедурой

D) порождающей грамматикой

178. Полнота – это условие, что для любого утверждения s одно из утверждений s и Øs

A) истинно

B) опровержимо

C) доказуемо

D) ложно

179. Множество истинных утверждений

A) носит название системы аксиом

B) не выводится из системы аксиом

C) перечисляет все системы аксиом

D) выводится из системы аксиом

180. Множество простых чисел является

A) рекурсивным и перечислимым

B) только перечислимым

C) только рекурсивным

181. замкнутым Если и рекурсия проводится по переменной , то функция равна

A)

B) t+x+y+z

C)

D) ty

182. Язык, на котором описывается другой язык, называется

A) формулой языка Ъ

B) формальной системой

C) автоматным языком

D) метаязыком

183. Показал возможность существования универсальной вычислительной машины, способной выполнить любую эффективную процедуру

A) А. Тьюринг

B) К. Гёдель

C) Д. Гильберт

D) А. Марков

184. Марковский алгоритм – это алгоритм

A) нормальный

B) стохастический

C) нелинейный

D) недетерминированный

185. Если и рекурсия проводится по переменной , то функция равна

A)

B)

C)

D)

186. Если , то функция в рекуррентной формуле равна

A) m+1

B) m+n+1

C) m(n+1)

D) m!

187. Множество номеров самоприменимых машин Тьюринга

A) рекурсивно перечислимо, но не разрешимо

B) неперечислимо, но разрешимо

C) рекурсивно перечислимо и разрешимо

D) ни перечислимо, ни разрешимо

188. Если и рекурсия проводится по , то функция равна

A) 1

B)

C) 0

D)

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

A) множество конфигураций машины

B) множеством состояний машины

C) множество команд машины

D) символы, записанные на ленте

190. Если A и B – рекурсивные множества, то рекурсивны также множества I. II.
III.

A) I, II и III

B) только I и III

C) только II

D) только I и II

191. Функция имеет гёделевский номер, равный

A) 9

B) 3

C) 13

D) 19

192. Функция является: 1) частично вычислимой; 2) примитивно рекурсивной; 3) частично рекурсивной

A) 1 и 2

B) 2 и 3

C) 1 и 3

D) 1

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

A) обратной

B) характеристической

C) вычислимой

D) рекурсивной

194. Конечному автомату соответствует грамматика, порождающая

A) регулярный язык

B) язык программирования

C) машину Тьюринга

D) словарь машины

195. Если множество нерекурсивно, то оно _______ областью определения и ______ множеством значений всюду определенной вычислимой функции

A) не может быть, может быть

B) не может быть, не может быть

C) может быть, не может быть

D) может быть, может быть

196. Если и рекурсия проводится по переменной , то функция равна

A) 2+m

B) m+1

C) m+y

D) m+x

197. Множество составных чисел является

A) только перечислимым

B) только рекурсивным

C) порождающим

D) рекурсивным и перечислимым

198. Теория алгоритмов является частью

A) численных методов

B) математической логики

C) математического анализа

D) теории чисел

199. Множество натуральных чисел является

A) рекурсивным и перечислимым

B) только перечислимым

C) простейшим

D) только рекурсивным

200. Если , то функция (n, m) в рекуррентной формуле равна

A) m+n+1

B) (m+n)/2

C) m+n-1

D) 2m

201. Функция является

A) вычислимой

B) частично вычислимой

C) общерекурсивной

D) рекурсивной

202. Если , то функция в рекуррентной формуле равна

A)

B)

C)

D) 1

203. Утверждение арифметики Пеано называется неразрешенным, если оно

A) противоречит системе аксиом

B) истинно, но недоказуемо

C) и его отрицание w-противоречивы

D) и его отрицание опровержимы

204. Символы, которые машина Тьюринга читает и пишет на ленте, образуют

A) алфавит

B) конфигурацию

C) команды

D) выражения

205. Конечное множество команд, имеющих попарно различные начальные пары символов, называется

A) конфигурацией

B) машиной Тьюринга

C) программой

D) алгоритмом

206. Функция, определяемая как число шагов в вычислении машиной Тьюринга, называется

A) характеристической

B) геделевским номером

C) длиной программы

D) временным ресурсом

207. Функция имеет гёделевский номер, равный

A) 2

B) 1

C) 4

D) 5

208. Геделевский номер, равный , имеет функция

A)

B)

C)

D)

209. Полнота – это условие, что для любого утверждения s одно из утверждений s и Øs

A) доказуемо

B) опровержимо

C) истинно

D) ложно

210. Функция равна

A) xyz

B) x+y

C) x+y+z

D) 3

211. Если и рекурсия проводится по , то функция равна

A)

B)

C) t+y

D) t+x

212. Множество всех истинных утверждений языка L является

A) разрешимым и перечислимым

B) неразрешимым, но перечислимым

C) неразрешимым и неперечислимым

D) разрешимым, но неперечислимым

213. В любой рекурсивно аксиоматизированной формальной системе множество доказуемых утверждений

A) рекурсивно перечислимо

B) разрешимо

C) нерекурсивно

D) неперечислимо

214. Композиция и равна

A)

B) 1

C)

D)

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

A) автоматным языком

B) алгоритмическим языком

C) метаязыком языком

D) регулярным языком

216. Функция имеет Гёделевский номер, равный

A) 4

B) 1

C) 3

D) 2