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

5 день. НАМ, т. Шеннона

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

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

Термины с лекции:

Высокоуровневая модель — более удобная в использовании модель в сравнении с элементарной за счёт введения абстракции.
Абстракция — смысловая конструкция, описывающая длинные на машинном коде операции.
Алгоритм с человеческим лицом — понятный человеку!
Язык Рефал — теоретический язык, написанный Турчиным для бортового компьютера “Бурана”.
Основная алгоритмическая модель — модель Тьюринга.
Инкремент числа — увеличение числа на 1.
Операнд — аргумент операции; данные, которые обрабатываются командой (a+b, ‘a’ и ‘b’ — операнды).
Предикат определяется как функция на множестве отношений {И,Л}. ***
Аналоговый — непрерывный, относящийся к физическим величинам (в сравнении с цифровым).
Цифровой — описанный технически, с помощью цифр.
pdp11 — машина, на которой впервые появился язык C.

Все примеры НАМ — кликни здесь

Термины с лабораторки:

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

Алгоритмы Маркова в оригинале называны алгорифмами. Они были предложены в 1950г. академиком Андреем Марковым (мл.). На их концепции физиком Турчиным основан язык Рефал.

Компилятор на Рефале был написан за несколько недель (!) Турчиным для бортового компьютера “Бурана”.

Алгоритм прибавления 1 к десятичному числу:

Входные сообщения (у Маркова) = входное слово, даже если в сообщении много букв.

У Маркова нет пробелов (как в понимании Тьюринга).

Звёздочка — это, по сути, маркер движения.

В конце алгоритма съедается звёздочка (с костылём), и работа завершается.

С помощью этого трюка можно решить разные задачи.

Достаточно ли одного маркера для сообщения (?)

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

Присоединяющие алгоритмы Маркова:

Высокий уровень НАМ в сравнении с МТ особенно ярко проявляется в рекурсивных правилах вычисления выражений.

Все примеры НАМ — кликни здесь

Радиомикрофон фонит — аналоговый (аналоговый и цифровой - разница ?)

Аналоговый — непрерывный, относящийся к физическим величинам (в сравнении с цифровым).

Цифровой — описанный технически, с помощью цифр.

Марков - элементарная, но высокоуровневая модель (абстрактная).
В ней нет явных состояний, поэтому это алгоритм с человеческим лицом

Вычислить значение выражения, состоящего из цифр (операнда) (!)

Цифры хороши тем, что их можно до конца вычислять.

© Обратимся к нашим воронам на Воробьёвых горах.

Натуральная С/С не работает с пустыми словами.
Если нулём считать пустое слово, то всё работает.
В бедных натуральных с/с (без отрицательных чисел) выдаётся модуль разности (© Алгоритм обладает высокой математической культурой)
pdp11 машина, на которой впервые появился язык C

НАМ - культовая вещь, раз она есть в учебниках разных стран.

Марков - математик, а Турчин - физик.

Марков работает с цифрами, как и Тьюринг.

Марков не делит многочлены, но по признакам делимости выводит отстатки от деления (нет арифметики).

По сути вычитает палочки и оставляет неполные.

Число - полином.

При делении уголком присутствует эвристика.

Если в Маркове пишет лямбду или пробелом — иностранный шпион!

© Марков - ортогональная альтернативная алгоритмическая схема.

Выжимка из книги “Теория алгорифмов” Маркова — ознакомиться

Напиши диаграмму своей задачи в Маркове

Мы решили, что Основная алгоритмическая модель — модель Тьюринга.

2.4 Исследование алгоритмической модели Тьюринга

доказательства этих теорем просто не поместились сюда…
2.4.1 Теоремы Шеннона

Клод Шеннон — 1956 г.

Результаты доказательств теорем довольно громоздки.

Но они позволили выяснить, какой смысл имеют состояния головки машины Тьюринга.

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

У Шеннона много теорем, даже из физики!

Теорема 2.4.1 (про два состояния) Первая т. Шеннона

Для любой МТ T с множеством состояний Q можно эффективным образом построить МТ T', моделирующую машину Тьюринга и имеющую всего два состояния: a и b.

Рабочий алфавит содержит: r = 3 * (p+1) * (s+1) + p букв.

Произведение (p+1) * (s+1) — одна из характеристик эффективности алгоритма.
Алгоритм тем эффективнее, чем меньше значение произведения.
Из этого следует, что смоделированные машины определяют менее эффективные алгоритмы, чем моделирующая машина Т.
А ещё эти алгоритмы выполняются за большее число тактов.

Откуда берётся тройка в формуле? 3 буквы: движемся налево, направо или никуда не движемся

Смысл теоремы в том, что если алфавит большой, то можно построить короткое сообщение.

Теорема 2.4.2 (про одну букву) Вторая т. Шеннона

Для любой машины Тьюринга T можно эффективным образом построить МТ T'', моделирующую машину Т и имеющую однобуквенный алфавит.

Смысл в том, любой алгоритм может быть записан на очень бедном алфавите.

Это себя оправдывает на слабом железе!

МТ с малым числом состояний не может нормально закончить свою работу.
Из-за технических искажений возникла морзянка — раньше звук передавался с трудом.

По т. Шеннона использование доп.букв не нужно => когда мы используем их, показываем нежелание разобраться в теореме.

Состояния и буквы перетекают друг в друга.

© Путаница сразу выдаёт шпиона!

Когда строим диаграмму, постепенно получаем доказательство.

алгоритм из 2 состояний - самая простая семантика (да или нет?) (да! 2 состояния и 5 букв)

2.5 Вычислимые функции

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

В матане обычно имеют дело с числовыми функциями.
Но есть и абстрактные функции на произвольных множествах.

2.5.1 Понятие функции на множестве слов

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

2.5.2 Понятие вычислимости (только заголовок)

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

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

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

С точки зрения математики, алгоритм - вычислимая функция.

Невычислимые можно построить, нарушая алгоритмические методы.

Найди примеры невычислимых функций (?)

Для невычислимых функций невозможно построение алгоритма!

2.5.4 Нормированные вычисления

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

1) никогда не может остановиться после применения

2) перечисляет значения функции и останавливается (на правильных словах МТ отказать и остановиться не может!)

При нормированных вычислениях головка не должна заходить левее λ.

- Выкинь '#' и ставь пометки.
- Согласно теореме, диез - преступление!
- © 6$!

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

Теорема 2.5.5 Для любой МТ можно эффективным образом построить машину Тn, которая имеет полубесконечную ленту и моделирует машину Tn.

Кондовый способ = надёжный! Ограничение ленты не нарушает общности МТ. Внутри ленты раздвигается лента, часть слева с мусором отображается вправо, но вычисления идут на нечётной части (1, 3, 5, 7) Т.е. внутрь одной полубесконечной ленты засунули другую.

2.5.5 Предикаты, вычислимые по Тьюрингу

Предикат определяется как функция на множестве отношений {И,Л}. В случае n = 1 предикат называют свойством, а если n > 1, то n-арным отношением (бинарным, например).
Предикаты используются при описании алгоритмов, при этом необходимо, чтобы они сами были вычислимыми.

Определение 2.5.6