RUS ENG

Котов В. М. Дискретная математика

Котов В. М. Дискретная математика. Специальный курс : пособие для сту­дентов спец. 1-31 03 04 «Информатика» / В. М. Котов, В. А. Мощенский. - Минск : БГУ, 2010. - 115 с.

ISBN 978-985-518-157-7

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

Для студенов факультета прикладной математики и информатики БГУ.


Оглавление

ПРЕДИСЛОВИЕ

3

1. ПОРОЖДЕНИЕ СЛОВ

 

1.1. Пороэдение слов в исчислении высказываний

5

1.2. Канонические системы Поста

6

1.3. Соответствия Поста

7

   

1.3.1. Проблема соответствий Поста

8

1.3.2. Видоизмененная проблема соответствий Поста

8

2. ОСНОВНЫЕ АЛГОРИТМЫ

 

2.1. Машины Тьюринга

10

2.1.1. Определение машины Тьюринга

10

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

13

2.2. Вычислимые арифметические функции

16

2.2.1. Определение класса Ч

16

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

21

2.3. Универсальные машины Тьюринга

23

2.3.1. Коды машин Тьюринга

23

2.3.2. Универсальные машины и функции

24

2.4. ft- Ленточные машины Тьюринга (детерминированные и недетерминированные)

26

2.5. Нормальные алгоритмы Маркова

31

3. ДРУГИЕ АЛГОРИТМЫ

 

3.1. Варианты машин Тьюринга

36

3.1.1. Машины Тьюринга с ^-этажной лентой (к>1)

36

3.1.2. Машины Тьюринга с односторонней лентой

37

3.1.3. Машины Тьюринга со входом

38

3.1.4. Оракульные машины Тьюринга

38

3.1.5. Машины Тьюринга с двумя символами на ленте

40

   

3.2. Вероятностные машины

42

3.3. Альтернирующие машины

43

3.4. Равнодоступные адресные машины

44

3.5. Модели параллельных вычислений

47

3.6. Семейства схем

49

3.7. Конечные автоматы

53

3.7.1. Автоматы Мура и Мили

53

3.7.2. Эквивалентность автоматов Мура и Мили

54

3.7.3. Множества слов, вычислимые в реальное время

56

3.8. Приближенные (эвристические) алгоритмы

58

3.8.1. Оценки качества приближенных алгоритмов

59

3.8.2. Примеры приближенных алгоритмов

60

3.8.3. Задача fc -разбиения

62

4. ОСНОВНЫЕ КЛАССЫ СЛОЖНОСТЕЙ ВЫЧИСЛЕНИЙ

 

4.1. Временная и емкостная сложности вычислений

66

4.1.1. Соотношение между временной и емкостной сложностями вычислений

66

4.1.2. Одно свойство емкостной сложности вычислений

67

4.2. Некоторые классы сложностей вычислений

73

4.3. Классы Р и NP . Проблема P =? NP -полные и NP -трудные проблемы

75

4.3.1. Классы Р и NP . Проблема P =? NP

76

4.3.2. Некоторые NP -полные и NP -трудные проблемы

77

4.4. Р-полные проблемы

83

4.5. Вероятностные классы сложности вычислений

87

4.5.1. Два вероятностных класса

88

4.6. О машинно-независимой теории сложности вычислений

88

5. АНОМАЛИИ В ТЕОРИИ ВЫЧИСЛЕНИЙ

 

5.1. Теорема о пробелах

93

5.2. Одноместные предикаты и бесконечные последовательности булевых функций

95

5.3. Задача о камнях при различных способах задания их весов

98

5.4. Перечисление рекурсивно-перечислимых множеств

99

6. АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ

 

6.1. Проблемы самоприменимости, применимости и переводимости

101

6.2. Эквивалентность слов в ассоциативных исчислениях

103

6.3. Проблема соответствий Поста

106

6.4. Теорема Раиса

109

ЛИТЕРАТУРА

112

Другие сайты факультетаСтруктураОбразованиеМагистратураНаукаМеждународное сотрудничествоСтудентуНИРСАСовет молодых ученыхОлимпиадыАбитуриентуШкольникуЦентр
Компетенций
по ИТ
Microsoft
Imagine Premium
ИсторияИздания факультетаПрофбюро ФПМИПерсональные страницыФотогалереи Газета ФПМыНаши партнеры