Самостоятельная работа №1 По предмету: Алгоритмы проектирования Статические и динамические меры сложности алгоритма

Теорема. РАМ с логарифмическим весом и многоленточные машины Тьюринга полиномиально связаны.


1.3 Язык Упрощенный Алгол.

Основные меры сложности выражаются в терминах определения1 для РАМ и машин Тьюринга, но вообще говоря, нет необходимости описывать алгоритмы в терминах столь простых машин. Для более наглядного описания алгоритмов мы введем некоторый язык высокого уровня, называемый Упрощенным Алголом. Программу на Упрощенном Алголе можно перевести непосредственно в программу для РАМ с помощью соответствующего транслятора. Однако нас не интересуют детали перевода Упрощенного Алгола в конкретную программу для РАМ. Для наших целей нужно рассматривать лишь время и память, необходимые для выполнения команд, составленных оператором на Упрощенном Алголе.

Упрощенный Алгол отличается от всех принятых языков программирования тем, что он разрешает использовать любой тип математических предписаний, если только их значения понятны, а перевод в команды РАМ очевиден. Этот язык не имеет также фиксированного набора типов данных. Переменные могут представлять целые числа, слова и массивы. Дополнительные типы данных - множества, списки, очереди и т.д. - можно вводить по мере необходимости. Формальное описание типов данных по возможности избегается. Тип данных какой-то переменной и ее область действия должны быть ясны по ее названию, либо по контексту.
В Упрощенном Алголе применяются традиционные конструкции математики и языков программирования, такие, как выражения, условия, операторы и процедуры.
Программа на Упрощенном Алголе - это оператор одного из следующих типов:
1) переменнаявыражение
2) if условие then оператор else оператор
3а) while условие do оператор
3б) repeat оператор until условие
4) for переменнаяисходное значение step размер шага
until заключительное значение do оператор
5) метка: оператор
6) goto метка
7) begin


блок