- •Программирование и алгоритмические языки. Курс за второй семестр. Абстрактные типы данных.
- •Задача о раскраске.
- •Перечисление последовательностей фиксированной длины.
- •Var I:tСтраны; c:tЦвет;
- •Два взгляда на диаграммы – графы и автоматы.
- •Деревья
- •Как сократить перебор с возвратом. Перечисление последовательностей переменной длины
- •Словарный порядок на последовательностях произвольной длины
- •Статическая реализация стеков.
- •Очереди. Статическая реализация.
- •Статическая реализация деревьев.
- •Автоматы как структуры данных
- •Статическая реализация графов. Проблема фрагментации памяти. Списочные структуры.
- •Общая схема реализации автомата как списка.
- •Обработка кучи.
- •Динамическая реализация абстрактных типов ссылками. Ссылочные типы Паскаля.
- •Ссылочные типы Паскаля. Синтаксис типов.
- •Объявление списочной структуры в Паскале.
- •Реализация стеков.
- •Реализация очередей.
- •Основные операции над списками.
- •Обработка деревьев. Деревья выражений.
- •Поиск атома.
- •Различные объединения типов. Записи типов с вариантами.
- •Создание дерева. Перевод из префиксной записи. Представление записи.
- •Анализ алгоритма вычисления. Дерево как последовательность ветвей.
- •Задача синтаксического анализа.
- •Графы-выражения.
- •Раздельное описание абстрактных типов. Модульное программирование.
- •Проблема с кратным использованием модулей.
- •Деревья как структуры данных.
- •Деревья поиска.
- •Поиск в дереве поиска.
- •Включение в дерево поиска.
- •Другие обходы дерева. Обход в ширину.
- •Рекурсивные процедуры и функции. Примеры применения.
- •Поиск в дереве.
- •Проблемы с семантикой рекурсии.
- •Введение в машинно-ориентированное (ссылочное) программирование. Оператор Goto.
- •Создание новых структурных операторов.
- •Формальная семантика goto и неструктурных программ.
- •Мини-Паскаль.
- •Представление сложных типов. Адресная арифметика.
- •Проблемы реализации ввода-вывода. Идея буферизации.
- •Реализация процедур read и write.
- •Реализация структур управления.
- •Путь наверх. Реализация процедур-подпрограмм.
- •Передача параметров.
- •Сохранение и восстановление значений. Соглашение о связях.
- •Введение в теоретическое программирование. Границы программирования. Принципиальная и практическая неразрешимость.
- •О формальной спецификации. Мир задачи как автомат.
- •Процедуры как функции на множестве состояний. Процедуры как преобразователи предикатов.
- •Универсальные методы решения задач.
Введение в машинно-ориентированное (ссылочное) программирование. Оператор Goto.
Синтаксис: goto k, где k – метка (имя, указатель) на некоторый оператор программы, соответствующее обозначение оператора. Выглядит как k:S.
В стандартном Паскале метками могут являться натуральные числа (не связаны с характером выполняемых действий). Все метки обязаны быть объявлены в программе в специальной области label. В стандартном Паскале это самая первая область объявлений, то есть до const.
Неформальная семантика: «Я нарушаю естественный ход выполнения программы, после меня выполняется не следующий оператор, а оператор, помеченный соответствующей меткой».
Создание новых структурных операторов.
Разбор случаев (нечто вроде case):
B1:S1;
…….
Bn:Sn
иначе Sn+1
где Bi – условие (предикат), Si – оператор.
S1
S2
Sn
Sn+1
if B1 then S1;
goto 1;
if B2 then S2;
goto 1;
…………..
if Bn then Sn
else Sn+1
1: {оператор}
Другой вариант: вложенный if.
c:char;
read(c);{чтение цифры}
if not c in [‘0’..’9’] then
begin
write(‘ожидалась цифра’);
goto 1;
end;
1:end;
Все подобные естественные использования goto в развитых языках программирования возлагаются на новые операторы с отличным синтаксисом.
Третий пример: программирование неструктурных алгоритмов.
while uslovie1 and uslovie2 do
begin
{что-то}
{проверка условия uslovie1}
if not uslovie1 then goto 1;{побочный выход из цикла}
{проверка условия uslovie2}
end;
В целом использование goto свидетельствует о плохом стиле программирования.
Формальная семантика goto и неструктурных программ.
Оператор goto не изменяет пользовательские переменные. В реальности goto изменяет системную переменную, счетчик команд, содержащую указатель (метку, имя, адрес) следующего в порядке выполнения оператора.
В терминах блок-схем goto – это просто стрелка.
Такая семантика даёт возможность точно определить семантику произвольных блок-схем. Пусть блок-схема B содержит n блоков S1,…,Sn. Неявно мы ввели нумерацию блоков (вместо индексов подошли бы любые иные указатели). Наша задача: построить структурную блок-схему, функционально эквивалентную данной.
Procedure StrucruredB ( );
var BlockName: tBlockName; {указатель на выполняемый блок}
bool:boolean;{значение текущего условного блока}
BlockEnd:tBlockName;{ещё один указатель на блок}
{этих переменных нет в исходной блок-схеме}
begin
BlockName:=cFirstBlockName;{указатель на кружок «Н»}
while BlockName<>cLastBlockName {указатель на кружок «К»}do
begin
{Разбор случаев – для каждого операторного блока два случая}
BlockName=ThisBlock : SThisBlock;
BlockName:=ThisBlockEnd;
BlockName=ThisBlockName : BlockName:=NextBlockName;
{метка оператора следующего блока}
{С каждым условным блоком связываем 3 случая}
BlockName=ThisBlock : Bool:=BThisBlock;
BlockName:=ThisBlockEnd;
BlockName=ThisBlockEnd and Bool=true : BlockName:=PlusBlockName;
{метка на блок, на который указывает стрелка + }
BlockName=ThisBlockName and Bool=false : BlockName:=MinusBlockName;
end;
end;
Данная программа пошагово эквивалентна исходной.
Наши рассуждения фактически доказывают более сильные утверждения:
1) Любая программа может быть записана с единственным циклом и единственным разбором случаев. Такая форма программы называется нормальной.
2) Этот переход можно осуществить алгоритмически – написать интерпретатор блок-схем, который по произвольной блок-схеме (для него – входные данные) исполняет алгоритм, описанный этой блок-схемой.
Procedure Structure(B:tFlowChart);
Упражнение*. Сделай это! ;)
В теории программирования этот результат называется теоремой об универсальной функции (теоремой о существовании компьютера).
Каковы же минимальные средства программирования? Сколько операторов, типов данных, переменных и так далее должен содержать язык программирования, чтобы на нём можно было написать любую программу?
Для прояснения этого вопроса создадим искусственный машинный язык с «паскалеобразным» синтаксисом.