Институт №8 МАИ

6 день. Теоремы о сочетании алгоритмов

d1. Информация <–> d2. Системы счисления <–> d3. Обработка информации <–> d4. Дискретные сообщения
d4. Формальный алгоритм <–> d5. НАМ, т. Шеннона <–> d6. Сочетания алгоритмов <–> d7. УМТ <–> d8. Машина фон Неймана

Словарик программиста:

Тут больше о доказательствах, чем о терминах.

Но доказательства приемлемые для понимания!

Лирические отступления:

- 2 т. Шеннона гласит: маломощные буквы вполне выразительны! - Нормированно вычислимая машина — машина, которая ***обязана*** не зацикливаться и не отказывать, а не только машина, которая не мусорит! > - Вычислимый по Ричи = по С > - Вычислимый по Никлаусу Вирту = по Pascal ```yaml © Надо **блистать** знаниями на экзамене! ```

2.6 Теоремы о сочетании алгоритмов

Теоремы о сочетаниях алгоритмов обосновывают использование уже сконструированных МТ при конструировании новых МТ. Вместе © тем они определяют правила, которые нообходимо соблюдать при объединении нескольких МТ в одну, более сложную МТ.

2.6.1 Теорема о композиции (будет на зачёте)

Пусть f задана как функция h(g1, g2(u..)) и пусть она является композицией из более простых функций.

Тогда если все функции ВТ, то и композиция функций ВТ и может быть эффективно построена из МТ, вычисляющих функции g и h.

В частном случае, когда индексы для значений функции равны единице, функция f называется суперпозицией функций g и h.

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

Из теоремы 4.3.3 следует, что ВТ-функции g и h являются НВТ-функциями.
Тогда пусть машины для функций g и h (Tg и Th) могут реализовать нормированное вычисление этих функций.
Построим сложную машину Kn. Она будет копировать аргументы для следующей функции (аргументы функций одни и те же)
Степень машины K является циклом, при этом лента у нас бесконечная, и мы не пугаемся копий.
Любое изображение диаграммы автоматически доказывает, что она существует.
Наличие диаграммы и подробное соответствие заявленным функциям доказывает теорему.

Суть этой теоремы в одном предложении: вычислимая композиция вычислимых функций вычислима.

2.6.2 Теорема о ветвлении (будет на зачёте)

Пусть задана n-местная функция с несколькими ветвлениями.

Ветвление — это выражение функций через альтернативные ветки (способы).
При этом gi — ВТ-функция и p — предикат (алгоритм).
Если составные части ветвления ВТ, то и функция ВТ (диаграмма существует).

Недетерминированный выбор предиката не означает случайный выбор чисел!

По закону случайности, всё случайное закономерно!

Человек мыслит древовидно (влево/вправо).

Чтобы упростить мышление, прибегают к двузвенному ветвлению.
Двузвенное ветвление обслуживается одним предикатом (следствие из теоремы о ветвлении — частный случай теоремы).
Двузвенное ветвление никогда не отказывает!

2.6.3 Следствие из теоремы о ветвлении

Пусть функция определяется равенством системе из двух ВТ-функций g и h и одного ВТ-предиката p, который для g принимает значение Истины, для h значение Лжи.

Тогда f является ВТ-функцией, причем МТ для f может быть эффективно построена из МТ, вычисляющих две функции и предикат.

очень перекликается с теоремой о композиции.

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

Кратность — показатель степени.

Возведение в степень — машина умножения, мультипликации + предикат, возводящий умножение в степень (повторяющийся n раз)

Subtract — вычитание.

Возведение в степень сводится к умножению и зацикливанию в степень.

2.6.5 Теорема о цикле (будет на зачёте)

Пусть g — ВТ-функция, вычислимая Тg, а p — ВТ-предикат, вычислимый Tp.

Тогда функция f, определяемая процессом f = g, пока p принимает значение Истины, тоже является ВТ-функцией.
Причем МТ Tf может быть эффективно построена из Tg и Tp.

Доказательство: Машина Tf определяется сложной диаграммой. Мы считаем, что в простейшем случае цикл состоит из повторяемого тела — вычислимой функции — и вычислимого предиката, управляющего повторением.

Предикат является предусловием цикла (предшествует условию).
В частности, цикл с ложным предусловием не выполнится ни разу.
И наоборот: если предикат в конце цикла, то он выполнится хотя бы один раз.

- Цикл может не работать ни разу.
- Ветвление не может не работать!

2.6.6 Обобщённая теорема о цикле

Алгоритм Евклида вычисляет НОД! Это алгоритм путем взаимного вычитания чисел.
Цикл работает до последнего предиката и никогда не отказывает.