Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

С О Д Е Р Ж А Н ИЕ

Предисловие

3

Введение

5

ЧАСТЬ

I . Алгоритмы

11

§ 1 .

Численные алгоритмы

11

1.1.

Арифметические

действия; алгоритм Евклида . .

11

1.2.

Численные

алгоритмы

13

1.3.

Диофантовы

уравнения

Ц

§ 2.

Алгоритмы игр

15

2.1. Одиннадцать предметов

16

2.2.

Побеждает

чет

17

2.3.

Дерево игры

17

2.4.

Существование

выигрышной

стратегии . . . .

20

§ 3 .

Алгоритмы поиска

пути в лабиринте

25

3.1.

Лабиринты

:

25

3.2.

Алгоритм

поиска .

26

3.3.

Обоснование

алгоритма поиска

29

§ 4.

Проблема слов

33

4.1. Ассоциативные исчисления

33

4.2.

Проблема

эквивалентности слов

34

4.3.

Проблема

слов

и лабиринты

36

. 4.4.

Построение алгоритмов

37

4.5.

Самосовмещення

квадрата

42

*

4.6.

Уравнения

в

словах

46

§

5.

Вычислительная машина с автоматическим управле­

нием

46

5.4.

Человек-вычислитель

46

5.2.

Вычислительные

машины

48

5.3.

Машинные

команды

50

§ 6.

Программа (машинный алгоритм)

52

. 6 . 1 . Программа для линейных уравнений

53

6.2.

Повторение

54

6.3.

Программирование алгоритма

Ев.клида

^57

ЧАСТЬ П. Машины Тьюринга

60

§ 7. Необходимость

уточнения понятия алгоритма . .

60

7.1. Существование

алгоритмов

60

7.2.

Распознавание

выводимости

63

7.3.

Формулировка

определения

«алгоритма» . . .

65

§ 8. Машина Тьюринга

68

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

68

8.2.

Функционирование

машины

Тьюринга

73

§ 9. Реализация алгоритма

в машине Тьюринга (тыорин-

гово

вычисление)

76

9.1\

Переход от пк

п

+ '

1 в'десятичной

системе

счис-

-

ления

76

9.2.

Перевод унарной записи в десятичную

79

9.3.

Сложение

. 8 1

9.4-. Повторное суммирование и умножение

82

9.5.

Нахождение общего

наибольшего делителя

. ,

84

§ 10.

Программирующие алгоритмы

88

10.1. Стандартные

программы

и формальные

операции

над программами

88

10.2.

Последовательная композиция . . . .

. . .

. .

91

10.-3. • Параллельная

композиция

93

10.4.

Разветвление

алгоритмов

94

10.5.

Повторное применение алгоритма

96

10.6.

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

98

§ 11.

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

и функции,

вычислимые по

Тьюрингу

99

11.1. Вычисление функций

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

пробле­

мы . .

99

*

11.2.

Простейшие операторы

102

• 1-1.3. Примитивная рекурсия

.

103

*

11.4.

ц.-оператор

107

*

11.5.

Рекурсивные

описания

и

их

тыорингово

про­

граммирование

108

* 11.6.

Рекурсивное

программирование

функций,

вы­

числимых по

Тьюрингу

112

§ 12. -Варианты внешней памяти

: . .

115

+

12.1. Полуленты и

параллельная

композиция . .

. .

116

•

12.2.

Доказательство

теоремы

о

полуленте

117

•

12.3.

Многоэтажные

и многомерные

ленты

119

§ 13. Основная гипотеза теории алгоритмов

120

13.1. Гипотеза и ее значение

120

13.2.

Обоснование

гипотезы

123

ЧАСТЬ

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

-.

125

§ 14.

Универсальная

машина

Тьюринга

125

14.1. Алгоритм подражания

125

14.2.

Универсальная

машина . . .

127

§ 15.

Алгоритмически

неразрешимые

проблемы .

. . .

131

15.1. Теорема

Черча

131

15.2.

Распознавание

самоприменимости

и

переводи­

мости

132

15.3.

Краткий

исторический обзор

134

§ 16.

Невозможность

алгоритма

для

проблемы

эквива­

лентности

слов

138

16.1. Невозможность алгоритма распознавания

перево­

димости

слов

.

.138

16.2.

Неразрешимость проблемы

эквивалентности

. . .

143

§ J 7 .

Качество

алгоритмов

и вычислений

144

17.1. Сигнализирующие

функции

144

17.2.

Оценки

для

примеров § 9

145

17.3.

Поиск лучшего

алгоритма

146

17.4.

Распознавание

симметрии

148

§ 18.

Следы тыоринговых вычислений

150