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

4 день. Дискретные сообщения, теория алгоритмов

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

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

Аналоговый — непрерывный, неделимый на части.
Дискретный — прерывистый, состоящий из отдельных частей.
Алгоритм — точно заданная последовательность шагов, указывающая, как за конечное число шагов получить требуемый результат.
Пространственная сложность — объём памяти, необходимый алгоритму для обработки сообщения длины n.
Формализация задачи — чёткое описание модели, на которой задача ставится, и формулировка теории этой задачи.
Сигнатура — перечень знаков R (имён) отношений r. Обозначается Ω.
Теория — перечень названий отношений и их свойств. T = (Ω, A).
Модель — множество, на котором заданы отношения и выполнены требуемые свойства. M = {M, {r1, r2, …, rk} }.

1.9 Конструктивное описание процесса обработки дискретных сообщений

Любое сообщение будем считать дискретным, а не аналоговым.
Дискретный — прерывистый, состоящий из отдельных частей.
Аналоговый — непрерывный, неделимый на части. Обработка сообщений состоит в применении правила обработки V

вспомним V = C * P * Q
Чтобы P - перевод сообщения в другое состояние - был основой автоматизации сообщения (как того требует условие), должен быть задан способ построения сообщения.
Если сообщение D конечно, то P может быть задано таблицей (это применимо для информации на одном листе бумаги).

Пример - таблица умножения.

К слову, таблица умножения умножает цифры (!)

Если D бесконечно, то таблица непрактична. Тогда мы разбиваем P на такты (представляем в виде элементарных шагов обработки).

Такты состоят в выполнении нескольких простых отображений, называемых операциями: P = P1 * P2 * … * Pk

Примеры операций: копирование буквы, приписывание буквы/слова.

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

Лексико-графический порядок:

Он используется для упорядочивания слов. Это словарный порядок (по 1 и далее буквам).

Алфавит не бывает пустым.

Слово бывает пустым (в нем 0 букв, но есть пробелы)

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

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

Рассматривают 5 свойств алгоритма:

Всегда актуальна задача поиска наиболее эффективного алгоритма, работающего за меньшее время.
Пространственная сложность — объём памяти, необходимый алгоритму для обработки сообщения длины n.
Для обозначения класса сложности используется O-нотация.

При решении задач важно описывать сложность алгоритма решения! Без этого будет скидка на экзамене — алгоритм не обоснован научно.

Об этом подробнее в статье с консультацией к экзамену.

Схема Горнера ( или O(n) ):

1.10 Интерпретация дискретных сообщений

Одно и то же сообщение можно интерпретировать по-разному. Это зависит от восприятия человека и его представлений о внешнем мире.

Если книгу по воровству можно купить, а само воровство можно осуществить, то наличие книги воровство не гарантирует.

Именно сам процесс воровства гарантирует воровство — такая логика.

Но там была другая притча, которую мы опустим.

Интерпретация дискретного сообщения при наличии модели сводится к тому, что каждому знаку ставится в соответствие объект, представляемый этим знаком.

Модель (реляционная система) — это множество М с заданным на нём набором отношений. Понятие модели не указывает на то, что она моделирует. Для этого введём понятия теории и сигнатуры.
Сигнатура — перечень знаков R (имён) отношений r. Обозначается Ω.
Теория — упорядоченная пара сигнатуры и множества высказываний о свойствах сигнатуры (аксиом A).

Теория — перечень названий отношений и их свойств.

Модель — множество, на котором заданы отношения и выполнены требуемые свойства.

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

Любая задача обработки/автоматизации информации ставится на соответствующей модели. Перед постановкой задачи необходимо её формализовать.

Формализация задачи — чёткое описание модели, на которой задача ставится, и формулировка теории этой задачи.

Формализация. Полный вариант:

Модель М называется моделью теории Т, если М и Т имеют одинаковую сигнатуру Ω и если после интерпретации каждого имени отношения теории, как одноименного отношения в модели, каждая аксиома теории становится истинным высказыванием.