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

10 день. Элементы дейкстровской нотации

d10. Нотация Дейкстры <–> d11. Типы данных <–> d12. Файлы, блоки <–> d13. Критика фон Неймана, рекурсия
d1. Раскладки клавиатур, кодировки <–> d6. Системы программирования <–> d9. Железки (1-12) <–> d14. Железки (13-35) <–> d15. Железки (36-74)

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

Принстон — программы и данные на одном устройстве памяти. Небезопасно.
Гарвард — раздельная реализации памяти для программ и для данных, что безопаснее.
Программа — текст, включающий в себя инструкции описания объектов, ввода, обработки, вывода данных.
Недетерминированность ветвления — выбор истинного ветвления не определяется порядком записи.
Ветвление — разбиение на альтернативные ветки.
Альтернативные — когда другие ветки не рассматриваются в случае успеха одной.
Массив — структурный тип данных, совокупность компонентов одного и того же скалярного типа.
Компоненты массива обозначены явно и доступны по индексам.
Индекс — функция, которая по значениям количества компонентов определяет их адрес.

© У нас форма распространения знаний устная!

Глава 3. Элементы дейкстровской нотации

3.1.1 Требования к структуре программ для машины фон Неймана

Машина фон Неймана состоит из управляющего устройства, памяти и регистров.

Для работы в её памяти должны быть объекты:

программа
таблица имён
все данные, которые надо обработать

Объекты связаны с адресами памяти специальными ячейками.

Правильность работы программы зависит от программиста, поскольку память — хранилище слов без какой-либо интерпретации.

Принстонская архитектура названа в честь института, в котором преподавал фон Нейман. Она отличается совместным размещением программы и данных в памяти, лишь на регистре процессора их можно различить. Такая реализация хорошо своей скоростью выполнения сгенерированной в памяти программы, но её недостаток — уязвимость к вирусам.
Гарвардская архитектура основана на раздельной реализации памяти для программ и для данных, что безопаснее (ценой аппаратурных затрат).

Составление таблицы имён можно автоматизировать правками текста программы, а для полной автоматизации процесса надо указать тип процессора обработки данных.

Для упрощения помещаем таблицу имён в начало программы.

Для обработки объект должен иметь значение, отличное от боттом _|_ (знак неопределённости — перевёрнутая Т).

Паскаль и Си требуют обязательного описания всех объектов, кроме предопределённых.

int i, j, k;

Данные в памяти недоступны для восприятия человеком, т.е. представлены внутренне. Их надо преобразовать во внешнее представление на доступном человеку носителе — произвести вывод данных.

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

Программа машины фон Неймана — текст, включающий в себя инструкции описания объектов, ввода, обработки, вывода данных.

3.1.2 Обобщённая инструкция присваивания

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

Основная инструкция обработки данных любого ЯП — инструкция присваивания.

x = a

x — имя объекта, a — действие над операндами, = — знак присваивания.

Всё, что в левой границе присваивания — lvalue.

Значение переменной копируется на свободный регистр, а с регистра — в ячейку памяти, сопоставленную с lvalue. На практике проверка на неопределённость значения переменно не выполняется — это замедляет исполнение программы.

Операнды в выражении выражаются словами одного типа, иначе — согласуются, что происходит перед отправкой копии в ячейку lvalue.

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

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

Одновременное присваивание аналогично обычному.

На Pascal символ присваивания составной: :=, а в Си — атомарный =

На языке СИ нельзя присваивать массивы или структуры! Есть лишь константный указатель на память, который должен быть в левой части присваивания.

А также в Си есть условное присваивание, в Pascal его нет:

3.1.3 Обобщенная инструкция композиции

Композиция — составная инструкция, при которой значения одной функции используются как аргументы для другой.

Для минимизации вычислений процесс разбивают на ряд последовательных подвыражений, разделённых точкой с запятой. В Си композиция инструкций скрепляется знаками { }

При параллельной композиции знаком разделения ветвей будет ||.

3.1.4 Охраняемые инструкции

Охраняемую инструкцию используют для возможности разрешать/запрещать выполнение инструкции в зависимости от выполнения условий.

Она снабжена предохранителем.

Предохранитель используют в ветвлении и цикле.

Это обычно называют тернарным оператором

Подробнее почитать здесь

3.1.5 Обобщённое ветвление

Правила выполнения ветвления (инструкции IF-FI):

1) Предохранители и предикаты одновременно и независимо вычисляются.

2) Чтобы ветвление разветвилось, должна быть хотя бы одна истинная ветка, иначе аварийный отказ. Ошибка при планировании ветвления лежит на плечах программиста.

3) Допустимо наличие более чем 1 истинного предиката.

Выбор истинного ветвления не определяется порядком записи — предохранители не упорядочены. Это называют недетерминированностью ветвления.

Но это не является случайностью! Случайность подчинена законам вероятности, что противоречит недетерминированности.

У них свои наборы регистров и переменных, не влияющие друг на друга.

Но компилятор вряд ли может обнаружить ошибку, поскольку она проявляется лишь в процессе runtime.

© Клянусь мамой, программа работает!
- Ставлю печать!

Программист должен страдать над ветками ветвления.

Составляя их, он должен думать, чтобы ветвление анализировало предикаты.

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

Выбрать и выполнить ветку — одно из основных назначений ветвления.

Если отдых, то отправляемся в Сочи.
- Если неважно,
- самолётом или на поезде,
- тогда проявляется 
- недетерминированнось.

При неалгоритмическом ветвлении ветка выбирается не случайно!

И не по весу, не по цене!

Случайная ветка не является детерминированной.

Недетерминированное программирование облегчает выполнение задач.

Ветвление на 2 ветки выполняется одним предикатом и никогда не отказывает (двузвенное ветвление). Ветвление выбирает одну из двух альтернативных ветвей.

© Язык СИ — это птичий,
- более лаконичный язык.
- В нём больше скобочек, значков.

Что в нём плохого:

break — показатель американского грубого языка!
в СИ нет встроенного стека!

© Нужны бойцовские качества! Надо уметь ругать языки — тогда вы выплывете на любом собеседовании!

Когда попадает к вам язык, необходимо узнать его с точки зрения Дейкстры (ветвлений), что в нём роскошного.

3.1.6 Обобщённая инструкция цикла

Цикл — средство организации многократного выполнения вычислений до момента превышения заданного значения.
Цикл содержит условие завершения в форме предиката.

Правила выполнения цикла:

1) Ветка выполняется, если предохранитель истинный.

2) Количество истинных предохранителей может быть более 1.

3) При отсутствии истинных веток цикл может не работать.

4) Выполнение каждой охраняемой инструкции приводит к изменению аргументов.

Ветки при выполнении влияют на переменные и немного на предикаты.
Цикл работает до последнего предиката и имеет внутри будто бы обобщённое ветвление.
Обобщённый цикл работает до последнего предиката!
Цикл работает много раз, пока одна ветка выполняется.

Предохранитель в IF FI обеспечивает более защитное программирование, отказ обнаруживается раньше.

Цикл с предусловием может не работать.

do while — постусловие

while do — предусловие

Pascal — untill not (двойное отрицание, использовалось, чтобы формулировка цикла была точной. При отрицании условия — просто Untill, при согласии — двойное отрицание).

3.2 Типы данных

3.2.1 Определение типа данных

Данные — сообщения в машинно-читаемом операбельном виде.

Тип данных — множество слов алфавита с правилом интерпретации для сопоставления значений слов с атрибутами другого или того же типа.
Атрибуты данных — отношения и функции над значениями этого типа.

Атрибуты данных:

операции
функции
отношения
константы

Эффективные способы задания типов:

1) Перечислением множества изображений. Сводятся к начальному отрезку натурального ряда.

Перечислимый тип “паразитирует” на целом типе и его реализация нецелесообразна.

2) Заданием характеристической функции (предиката), истинного, когда изображение относится к данному типу.

Этот тип тоже не может быть первичным, т.к. базируется на некотором надмножестве изображений.

3) С помощью системы аксиом, содержащих свойства изображений.

Способ математически красив, но неконструктивен, т.к. не позволяет порождать значения в явном виде.

Первая отечественная ЭВМ БЭСМ.

Она также представляла собой МТ и была неудобной: на ней также приходилось моделировать числа вещественного типа.

Первый компьютер — американский!
Второй — британский!
Но первый континентальный — отечественный!

Всего было 4 пришествия МТ:

Первой МТ была она сама;

Второй МТ — первые компьютеры;

Третья МТ — бортовые компьютеры;

Четвёртая МТ — первое появление микроархитектуры.

И всё это делали умные люди, с математическим подходом!

Они знали матанализ!

Перечислимый тип основан на задании слов, пронумерованных в порядке описания и несущих смысловую нагрузку.

Соответствующий тип может быть задан отрезком, или диапазоном.

Массив — структурный тип данных, совокупность компонентов одного и того же скалярного типа. Компоненты массива обозначены явно и доступны по индексам.
Индекс — функция, которая по значениям количества компонентов определяет их адрес.

3.2.2 Тип логический

bottom _ | _ это знак неопределённости. Он описывает класс ситуаций, когда результат не имеет осмысленной интерпретации.

На языках СУБД _ | _ обозначается как NULL
SQL читается как Сиквел.

Если в машинном слове хотя бы одна единица, то истина.

3.2.3 Тип целый

Из курса алгебры знаем — это множество целых чисел вида 0-+1+-2, образующих алгебраическое кольцо относительно сложения и умножения (деление разрывает кольцо — 7/2 не является целым числом).

Эффективная вычислимость требует замены бесконечного числа чисел на конечный отрезок (множество), в который войдут числа между MIN MAX.

Пример диапазона: [-32768; 32767].
0 входит в положительную часть, поэтому диапазон несимметричен.
Т — переопределённое значение, депутат. Вместе с неопределённым значением _ | _ они войдут в целый тип.
Отношение в целом типе размыкает целый тип и переходит в булевский (введён в C99).
Раз отношения размыкают логический тип, то они не являются операциями (3/5).

Отношения являются операциями если в результате получается тот же тип данных. А рациональные числа - размыкание целого типа.

Деление - медленная операция.

Алгоритм деления - не алгоритм. В нём есть элемент прикидки, эвристического подбора. Деление сводится к вычитанию с эвристическим подбором.