Язык Паскаль (Основные понятия и определения)

Размещено на http://www.allbest.ru/

Министерство образования и науки Украины

Национальный технический университет Украины "КПИ"

Факультет Информатики и вычислительной техники

ЯЗЫК ПАСКАЛЬ (Основные понятия и определения)

Киев 2011

Содержание

1. Понятие алгоритма

2. Структура ЭВМ неймановского типа

3. Принцип программного управления

4. Формы представления чисел в памяти ЭВМ

5. Эволюция средств программирования

6. Формализованное определение понятия "язык"

7. Стандарт языка Паскаль

8. Упражнения

1. Понятие алгоритма

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

Для записи алгоритмов можно использовать обычный разговорный язык. В этом случае, например, алгоритм возведения числа X в целую положительную степень Y, т.е. вычисления по формуле S = X^Y можно записать в виде следующей системы последовательно выполняемых правил или указаний:

Присвоить переменной S значение "единица". Перейти к пункту 2.

Присвоить переменной i значение "единица". Перейти к пункту 3.

Если i Y, то перейти к пункту 4, иначе - к пункту 6.

Присвоить переменной S ее предыдущее значение, умноженное на величину X. Перейти к пункту 5.

Увеличить значение i на единицу. Перейти к пункту 3.

Считать значение S результатом. Вычисления прекратить.

Другой пример алгоритма - поиск минимального числа x в последовательности из n чисел a₁,a₂, ...,a_n. Пусть в качестве минимального числа x принимается а₁, после чего x сравнивается с последующими числами, начиная с а₂. Если x<a₂, то x сравнивается с а₃ и т. д., пока не найдется число a_i<х. Если a_i<x, то x присваивается значение a_i и продолжается сравнение x со следующими числами, начиная с a_i+1. Процесс продолжается до тех пор, пока не будут просмотрены все n чисел. В результате x будет иметь значение, равное наименьшему в последовательности числу. Этот процесс может быть записан в виде следующей системы последовательных указаний:

Положить x = a₁. Перейти к пункту 2.

Положить i = 2. Перейти к пункту 3.

Если i n, то перейти к пункту 4, иначе - к пункту 6.

Если a_i < x, то положить x= a_i. Перейти к пункту 5.

Увеличить i на единицу. Перейти к пункту 3.

Считать значение x результатом. Прекратить просмотр.

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

Концепции алгоритмов в математических терминах были впервые описаны в 1930 - 1940 г.г., когда велись поиски условий, с помощью которых возможно доказательство проблемы разрешимости задач или, в общем случае, автоматическое доказательство математических теорем. Существуют три основных типа алгоритмических моделей [2]. В первом понятие алгоритм связывается с вычислимыми числовыми функциями. Во втором алгоритм представляется как некоторое универсальное устройство, способное выполнять набор простейших операций (например, машина Тьюринга). Третий тип основывается на ниже определяемых понятиях абстрактного алфавита и соответствия между словами в таком алфавите, что позволяет формально описывать процессы преобразования информации.

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

Абстрактным алфавитом называется любая конечная совокупность объектов, называемых буквами или символами данного алфавита. Иными словами алфавит - это конечное множество различимых символов (слово "абстрактный" для краткости здесь и далее опускается). Алфавит, как и любое другое множество, может быть задан перечислением его элементов. Например, алфавит A есть A={a, bc}, алфавит B есть B={x, y}.

Под словом или строкой в алфавите понимают любую конечную последовательность символов. В последовательности (цепочке) между символами стоит операция сцепки или конкатенации, т.е. менять местами символы в последовательности нельзя. Например, в алфавите A словами являются любые последовательности: aac cbacb bb, а в алфавите B: x, y, yx, xx и т. п.

Число символов в слове называется длиной этого слова. Так слова в алфавите A, приведенные в примере, имеют длину соответственно 1, 2, 2, 3, 2. Различают также пустые слова, не содержащие ни одного символа. Слово p называется подсловом слова q, если слово q можно представить в виде q=pr, где r - любое слово, в том числе и пустое. Очевидно, что такое понятие слова будет отличаться от аналогичного в разговорных языках. Здесь под словом можно понимать любую последовательность символов, даже бессмысленную.

При расширении алфавита понятие слова может существенно меняться. Так, например, в алфавите A={0,1,2,3,4,5,6,7,8,9} цепочка символов 69+73 представляет собой два слова, соединенные знаком суммы, а в алфавите B={+,0,1,2,3,4,5,6,7,8,9} это будет одно слово. В общем случае, в качестве символов могут использоваться не только одиночные символы, но и отдельные слова, фразы, абзацы и, даже, целые тексты.

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

Пусть заданы слова в алфавитах X и Y и заданы соответствия между этими словами. Если x_i- слово в алфавите X, а y_j - слово в алфавите Y, то алфавитный оператор Гx_i=y_j преобразует входное слово x_i в выходное слово y_j. Символ Г в алфавитном операторе означает отображение.

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

Совокупность всех слов, на которых алфавитный оператор определен, называется областью его определения. Алфавитный оператор, не сопоставляющий данному входному слову a_i никакого выходного слова b_j (в том числе и пустого), на этом слове не определен.

К наиболее простым алфавитным операторам относятся так называемые посимвольные отображения. Последнее состоит в том, что каждый символ входного слова алфавита A заменяется некоторым символом выходного алфавита B. Более сложными являются так называемые кодирующие отображения. Под кодирующим отображением понимается соответствие, сопоставляющее каждому символу входного алфавита некоторую конечную последовательность символов в выходном алфавите, называемую кодом.

Рис.1.1 Кодирующее отображение

Пусть заданы алфавиты: A={p,r,s,t} - входной и B={a,b,c,d,f,g,h} - выходной. Тогда отображение символов А символами В, т.е. кодом (Рис.1.1), является примером кодирующего отображения. Для построения искомого отображения достаточно заменить все символы любого слова a_i в алфавите А соответствующими кодами алфавита В. Так, если слово x=sstr, то Гx=fghfghabcceg есть код исходного слова x.

Процесс, обратный кодированию, т.е. замена в слове b_j кодов алфавита В символами из А, называется декодированием и обозначается как Г^-1b_j=a_i. Например, для слова b=fghfghabcceg в алфавите В декодирование Г^-1b дает слово a=sstr.

Если при кодировании слова a_i получается некоторое слово b_j и декодирование дает исходное слово a_i (Гa_i=b_j, Г^-1b_j=a_i), то имеет место обратимость кодирования. Условие обратимости кодирования иначе называется условием взаимной однозначности соответствующего кодирующего отображения. В приведенном выше примере обратимость существует. Но, если зданы A={a,b,c}, B={r,s}, Га=r, Гb=s, Гс=rs и слово aabca в алфавите А, то обратимость отсутствует, так как Гaabca=rrsrsr, а Г^-1rrsrsr=aababa (либо одно из слов acaba, aabca, acca).

Для обратимости кодирования должны выполняться следующие условия:

коды разных символов исходного алфавита А должны быть различны;

код любого символа алфавита А не может совпадать ни с каким из начальных подслов кодов других символов этого алфавита.

Пояснение этих утверждений сводится к следующему. Пусть слово q=b₁,b₂, ...,b_n является кодом слова p=a₁,a₂, ...,a_m в алфавите А. Тогда по коду q можно однозначно восстановить слово р. В силу второго условия только одно начальное подслово слова q будет совпадать с каким-либо символом алфавита А. Ясно, что таким подсловом является символ а₁. Применяя аналогичные рассуждения к оставшемуся отрезку слова q, можно однозначно восстановить один за другим все символы слова р. Следовательно, любому данному коду может соответствовать только одно слово в А, что доказывает обратимость кодирующего отображения.

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

Кодирование позволяет сводить изучение произвольных алфавитных отображений к алфавитным отображениям в некотором стандартном алфавите. Наиболее часто в качестве стандартного алфавита выбирается двоичный алфавит, состоящий из двух символов. В качестве таких символов обычно используются цифры 0 и 1, т.е. С={0,1}. Подавляющее большинство современных ЭВМ обрабатывают информацию, закодированную именно в двоичном стандартном алфавите.

Пусть А - произвольный, а С - стандартный алфавиты и n - число символов в алфавите А, а m - число символов в алфавите С. В этом случае всегда можно выбрать длину слова L, удовлетворяющую условию m^Ln и закодировать все символы в алфавите А словами длины l в алфавите С так, чтобы коды различных букв были разными (действительно, число различных слов длины L в m-символьном алфавите равно m^L). Любое такое кодирование будет нормальным и порождает обратимое кодирующее отображение слов в алфавите А в слова в алфавите С (см. ниже диапазон представления чисел в машине).

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

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

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

Формальное определение алгоритма

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

Свойства алгоритма. Всякий алгоритм любому входному слову ставит в соответствие только одно выходное слово. Это одно из основных свойств алгоритма - формальность. Иначе это свойство называют детерминированностью или однозначностью.

К числу других свойств алгоритма относятся массовость и результативность.

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

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

Тогда массовость алгоритма - это применимость ко всей области его определения.

В этом случае эквивалентность алгоритмов может быть определена следующим образом: два алгоритма эквивалентны, если совпадают их области применимости и результаты переработки любого слова из этой области. Если области применимости совпадают частично, алгоритмы называют слабо эквивалентными.

Оценка сложности алгоритмов

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

А - алгоритм решения некоторого класса задач и n-размерность одной задачи из этого класса (в частном случае n может быть, например длинной последовательности в рассмотренном выше алгоритме, количеством слов в анализируемом тексте и т.п.);

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

Тогда алгоритм называется полиномиальным, если f_A(n) растет не быстрее чем полином от n. В противном случае алгоритм А называется экспоненциальным. Так, функции типа kn, kn²,kn³,..., где k - коэффициент, могут рассматриваться как полиномиальные, а функции типа 2ⁿ, nⁿ, n!... как экспоненциальные. Для достаточно больших n значение экспоненциальной функции всегда превышает значение полиномиальной функции. Для малых n это не всегда справедливо, но всегда есть такое n, для которого значение экспоненциальной функции превышает аналогичное для полиномиальной.

Время, затраченное на реализацию алгоритма, как функция размерности задачи называется временной сложностью алгоритма и обозначается как O[f_A(n)]. Применительно к решению задачи на ЭВМ это время является в большинстве случаев свойством самого алгоритма и слабо зависит от машины, на которой решается соответствующая алгоритму программа.

Кроме временной сложности алгоритмов существуют и другие меры сложности. Так, сложность можно характеризовать числом операций N (применительно к конкретной ЭВМ) и общим объемом информации Р, т.е общим количеством слов, используемых при выполнении алгоритма. Тогда время его выполнения на конкретной ЭВМ связано с числом операций, а объем информации связан с объемом памяти, необходимой машине для реализации соответствующей программы. Следовательно, время реализации алгоритма есть функция T=f(N). При таком подходе значения Т и Р называют соответственно вычислительной и емкостной сложностью алгоритма.

Блок-схемы алгоритмов

Среди универсальных форм представления или записи алгоритмов можно выделить так называемые блок-схемы алгоритмов. Универсальность этой формы обусловлена тем, что в ней заранее не определяются абстракции, которые могут специфицироваться в блоках даже с применением обычного разговорного языка. Блоки являются всего лишь шаблоном для описания действий в процессе решения задачи, а связи между блоками определяют последовательность этих действий.

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

Операторный блок - это прямоугольник, в который вписывается некоторое действие или выражение (Рис.1.2.а). Этот блок может иметь несколько входов и только один выход, что обеспечивает однозначность в определении последовательности выполняемых действий. Исключение составляют начальный и конечный блоки. Первый не имеет входов, второй - выхода.

Рис.1.2 Элементы блок-схем алгоритмов

Условный блок обозначается ромбом, в который вписывается некоторое условие. Поскольку результатом проверки условия может быть либо "да", либо "нет" ("истина" или "ложь", "0" или "1"), блок имеет два соответствующих этим ответам выхода (Рис 1.2.б).

Если операторный или условный блоки имеют более одного входа, то изображение входов совмещается (Рис 1.2.в). На связях, определяющих последовательность выполнения блоков, стрелки не обязательны, если их направление соответствует продвижению "сверху-вниз" и "слева-направо". Ограничения на геометрические размеры блоков в этом случае не вводятся.

Рис.1.3 Варианты блок-схем алгоритмов вычисления степенной функции

Такая форма представления алгоритмов очень удобна в тех случаях, когда рассматриваются верхние уровни в иерархической структуре процесса проектирования программ и даже на нижних уровнях, если по каким-то причинам не определены средства их описания. Кроме того, блок-схемы наиболее удобны для записи алгоритмов на начальных стадиях обучения программированию. Блок-схемы алгоритмов вычисления степенной функции и решения квадратного уравнения иллюстрируется соответственно рисунками Рис.1.3.а,б и 1.4.

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

Рис.1.4 Блок-схема алгоритма решения квадратного уравнения

2. Структура ЭВМ неймановского типа

Традиционная структура, предложенная Дж. Нейманом для однопроцессорных ЭВМ в 1947г., до настоящего времени не претерпела принципиальных изменений. В качестве основных устройств ЭВМ можно выделить Оперативную Память (ОП), Арифметико-Логическое Устройство (АЛУ) и Устройство Управления (УУ), назначение которых сводится к следующему.

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

ОП структурирована, т.е. в простейшем случае содержит n ячеек, каждой из которых ставится в соответствие номер от нуля до n-1. Этот номер называется адресом ячейки.

Число, хранящееся в ячейке - это ее значение или содержимое. Если в i-й ячейке, например, находится число m, то принято говорить "содержимое ячейки с адресом i есть m". Если это значение не было туда принудительно записано, считается, что значение ячейки не определено (его нельзя принимать равным нулю, поскольку в ячейке может быть любое число, оставшееся там после предыдущей записи или число, случайно сформированное при включении машины).

Подавляющее большинство современных типов памяти относится к так называемой памяти с неразрушающим чтением, т.е. при чтении содержимого ячейки оно не изменяется. Для его изменения необходимо записать в эту ячейку новое значение или, иначе говоря, присвоить ячейке новое значение (операция присваивания далее обозначается как :=).

Понятию адреса в полной мере соответствует понятие переменной в алгебре. Действительно, адрес соответствует уникальному имени переменной и как ячейке с некоторым адресом, так и переменной можно присвоить определенное значение. Например, присваивание i := i+1, следует понимать как присваивание содержимому ячейки с адресом "i" ее предыдущего значения, увеличенного на единицу.

Арифметико-логическое устройство позволяет выполнять некоторое (заранее заданное) множество инструкций и настраивается на выполнение конкретной инструкции управляющими сигналами, поступающими из устройства управления. Как правило, АЛУ сохраняет результат выполненной инструкции до выполнения очередной, что позволяет использовать и одноадресные команды (см. ниже).

Устройство управления обеспечивает чтение и запись информации в ячейки с заданным адресом и формирование управляющих сигналов, необходимых для управления АЛУ и Устройствами Ввода-Вывода (УВВ) в процессе выполнения команд. Устройства ввода-вывода информации иначе называют внешними устройствами, назначение которых - обеспечить взаимодействие человека с машиной.

Команда представляет собой число, разделенное на группы цифр, первая из которых содержит код операции, а следующие - адреса ячеек памяти. Например, трехадресная команда соответствует обычному представлению двухместных алгебраических операций вида x := y * z, которая читается как выполнить операцию * над переменными y и z (содержимым ячеек c адресами y и z) и результат присвоить переменной x (ячейке с адресом х), а при выполнении одноместных операций значение "лишних" адресов не используется.

В общем случае команда может содержать один, два, три или даже четыре адреса. Например, одноадресная команда - удобная инструкция для таких действий, как передача значения переменной из устройства ввода в ячейку памяти с заданным адресом, передача содержимого ячейки с заданным адресом в АЛУ, сложение содержимого АЛУ с содержимым заданной ячейки и т.п. Одноадресные команды удобны тем, что не содержат "лишних" адресных полей, но приводят к увеличению необходимого для решения задачи количества инструкций. В четырехадресных командах четвертый адрес обычно используется для указания места, где расположена следующая выполняемая инструкция. Выбор структуры команд осуществляется на этапе проектирования самой ЭВМ и к рассматриваемой предметной области прямого отношения не имеет.

Для временного хранения инструкции в процессе ее выполнения (цикла выполнения команды) используется один из узлов УУ, который называют регистром команд. Этот узел обеспечивает разделение кода команды на код операции и коды адресов на физическом (схемном) уровне.

Для формирования и временного хранения адреса выполняемой команды используется узел УУ, называемый СЧетчиком Адреса Команды (СЧАК) или регистром-указателем номера команды (Pointer Instruction - PI). Понятие адреса команды и назначение СЧАК (PI) определяется ниже.

3. Принцип программного управления

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

Чтобы обеспечить возможность размещения программы в памяти, команды должны быть обязательно представлены в числовом виде, так как в памяти (об этом уже упоминалось) можно хранить только числа. Для представления команд в виде чисел необходимо иметь две кодирующие таблицы.

Фрагмент первой таблицы (Таблица 1.а) позволяет поставить в соответствие операциям некоторые коды. Так из этой таблицы следует, что операции записи в ячейку памяти с адресом, указанным в первом из адресов команды - А1, некоторого значения соответствует код 01 (операция ввода числа), чтения числа из ячейки с адресом А1 с выдачей результата на УВВ - код 02 (операция вывода), сложению - код 03 и т. д. Такого типа таблица является принадлежностью конкретного типа ЭВМ, т.е. "заложена" в нее при проектировании.

Таблица 1.а Фрагмент системы команд абстрактной ЭВМ

Действия, выполнямые командой	Код команды
Ввод (запись) числа из УВВ в [А1]	01
Вывод [А1] на УВВ	02
Сложить [А1} с [А2] и результат поместить в [А3]	03
Вычесть из [А1] [A2] и результат поместить в [A3]	04
Умножить [А1] на [А2] и результат поместить в [А3]	05
Разделить [А1] на [А2] и результат поместить в [А3]	06
. . .	. . .
Закончить выполнение программы	00

Количество строк в таблице соответствует мощности множества команд, составляющих систему команд этой ЭВМ (для современных ЭВМ система команд может содержать более тысячи инструкций; коды операций, также как и структура команды, выбираются при проектировании ЭВМ).

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

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

а = ((b+c) d² - e) / f

при условии, что свободной является память ЭВМ, начиная с 100 ячейки. Тогда под переменные можно "распределить память", например, таким образом (выбор в общем случае произволен): переменной а поставить в соответствие ячейку с адресом 100, переменной b - ячейку с адресом 101; и т.д. (Таблица 1.б), в которой переменная r предназначена для хранения промежуточных результатов.

Таблица 1.б Пример распределения памяти

При записи кодов команд, т.е. команд, приведенных к виду чисел, которые обеспечивают вычисление величины а, ниже применяется специальная форма записи (Таблица 2).

Таблица 2. Программа вычисления выражения а=((b+c)d² - e)/f.

No	КОП	А1	А2	А3	Примечание (коментарий)
1	01	101	000	000	ввод значения b
2	01	102	000	000	ввод значения c
3	01	103	000	000	ввод значения d
4	01	104	000	000	ввод значения e
5	01	105	000	000	ввод значения f
6	03	101	102	106	r := b+c(сложение b и c, результат в r)
7	05	103	103	103	d := d x d (вычисление величины d2)
8	05	106	103	106	r := r + d (b + c) x d2
9	04	106	104	106	r := r - e ((b + c) x d2) - e
10	05	106	105	100	a := r : f (((b + c) x d2) - e) / f
11	02	100	000	000	вывод а
12	00	000	000	000	конец вычислений (адреса не нужны)

Форма таблицы соответствует бланкам, которые использовали программисты в начале-середине 50-ых годов. Правила составления такой таблицы очевидны при условии, что А1 является адресом первого операнда, А2 - адресом второго операнда и А3 - адресом результата, а вычисление выражения "разложено" (структурировано) на двухместные и одноместные операции. Пример тех же самых вычислений, но с использованием одноадресных команд иллюстрируется программой, которая приведена в Таблице 3. Здесь используются дополнительно введенные коды операций: 07, предписывающий передачу содержимого ячейки памяти с адресом А в АЛУ, 08 - обратные действия, а коды 03-06 определяют выполнение соответствующих операций над переменными, одна из которых находится в АЛУ, другая - в ячейке с адресом А, и сохранением результата в АЛУ.

Таблица 3. Программа с использованием одноадресных команд

No	КОП	А	Примечание	No	КОП	А	Примечание
1	01	101	ввод b	8	05	103	(b+c) x d
2	01	102	ввод c	9	05	103	(b+c) x d2
3	01	103	ввод d	10	04	104	(b+c) x d2-e
4	01	104	ввод e	11	06	105	((b+c) x d2-e)/f
5	01	105	ввод f	12	08	100	АЛУ заслать в a
6	07	101	b заслать в АЛУ	13	02	100	вывести a
7	03	102	b+c	14	00	00	конец вычислений

Как следует из таблицы, программа относительно предыдущей "удлинилась" всего на две команды, но при этом не имеет "лишних" адресных полей (за исключением последней команды). Записанная таким образом последовательность команд или программа представляет собой последовательность чисел, которые можно разместить в памяти ЭВМ.

Пусть программа размещена в свободной зоне памяти начиная, например, с ячейки 501 (такое размещение обычно осуществляется с помощью сложения номера команды с константой или так называемым смещением, которое в рассматриваемом случае равно 500). Тогда для автоматического выполнения программы достаточно занести в СЧАК (РI) число 501 (так называемый пусковой адрес) и включить режим автоматического выполнения программы.

При этом всегда будут производится одни и тот же набор действий - цикл выполнения команды:

1. Содержимое ячейки памяти, адрес которой определяется значением СЧАК (PI), т.е. первой команды программы, передается в регистр команд устройства управления.

2. Если код операции команды не предписывает прекращение вычислений, то выполняется пункт 3, иначе пункт 7.

3. С помощью дешифрованного кода операции АЛУ настраивается на выполнение заданной операции.

4. Числа, которые хранятся в ячейках, указанных адресами команды, передаются в АЛУ в качестве операндов.

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

6. Содержимое СЧАК (PI) модифицируется (в простейшем случае к содержимому СЧАК (PI) прибавляется единица, т.е. выполняется присваивание СЧАК := СЧАК+1) и происходит возврат в начало цикла (к пункту 1).

7. Вычисления заканчиваются, т.е. прекращается автоматическое выполнение программы.

Таким образом, принцип программного управления в упрощенном виде основывается на том, что программа должна быть представлена в числовом виде, размещена в памяти ЭВМ, а сама ЭВМ должна выполнять некоторую процедуру автоматической выборки и исполнения очередной команды вплоть до окончания программы. При этом следует еще раз подчеркнуть, что для представления программы в числовом виде необходимо предварительно распределить память, а также то, что подавляющее большинство современных ЭВМ построено на основе принципа Неймана и любая исполняемая ими программа в конечном счете должна быть приведена к виду, аналогичному рассмотренному выше.

4. Формы представления чисел в памяти ЭВМ

При составлении таблицы распределения памяти под ячейкой понималась так называемая логическая ячейка памяти, которая может отличаться от физической ячейки, т.е. состоять из одной, двух и более физических ячеек. Логическая ячейка обеспечивает хранение и возможность чтения или записи чисел фиксированной длины (иначе n-разрядных чисел) в определенной системе счисления.

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

Наиболее широко распространенной системой счисления, используемой для представления чисел в памяти ЭВМ, является позиционная однородная система счисления с основанием р=2 (двоичная система счисления).

В общем случае число в позиционной однородной системе счисления с основанием р определяется степенным рядом:

a_npⁿ + a_n-1p^n-1 +... + a_ipⁱ +...+ a₂p² + a₁p¹ + a₀p⁰,

где a_i ={0,1, ..., p-1}- цифры системы, p - основание системы.

Сокращенная и обычно применяемая форма записи числа представляет собой последовательность цифр: a_n a_n-1 ... a_i ... a₂ a₁ a₀ .

Система собственно и называется однородной позиционной потому, что от позиции, которую занимает цифра в сокращенной форме записи числа, зависит ее "вес" и этот вес пропорционален степени одного и того же основания. Кроме того, для позиционных систем счисления обязательна цифра "0", которая используется для обозначения "пустых" позиций.

Так при основании "десять" для обозначения чисел используются десять арабских цифр, a_i ={0, 1, ..., 9}, а сокращенная запись вида 1263951 соответствует степенному ряду:

1*10⁶ + 2*10⁵ + 6*10⁴ + 3*10³ + 9*10² + 5*10¹ + 1*10⁰

При основании "два" для записи чисел используются только две цифры, т.е. a_i ={0, 1} и, например, число 1110101 соответствует ряду:

1*2⁶ + 1*2⁵ +1*2⁴ + 0*2³ + 1*2² + 0*2¹ +1*2⁰

и, если подсчитать сумму членов ряда, то десятичному числу 54.

Ниже Таблицей 1.5. иллюстрируется изображение первых восемнадцати чисел в позиционных однородных системах счисления с основаниями 2, 4, 8, 16 и 10 (основания систем в первой строке таблицы записаны в десятичной системе). При этом для изображения цифр в системах с различным основанием использованы символы цифр десятичной системы, а для недостающих цифр шестнадцатеричной - первые шесть букв латинского алфавита.

Таблица 1.5 Представление чисел в позиционных однородных системах счисления

Основание системы счисления	Основание системы счисления
10	16	8	4	2	10	16	8	4	2
0	0	0	0	0	9	9	11	21	1001
1	1	1	1	1	10	a	12	22	1010
2	2	2	2	10	11	b	13	23	1011
3	3	3	3	11	12	c	14	30	1100
4	4	4	10	100	13	d	15	31	1101
5	5	5	11	101	14	e	16	32	1110
6	6	6	12	110	15	f	17	33	1111
7	7	7	13	111	16	10	20	100	10000
8	8	10	20	1000	17	11	21	101	10001

Как видно из таблицы, основание любой системы счисления в этой же системе обозначается сочетанием цифр 10, поэтому если нет ссылок на то, что рассматриваемая система является десятичной, число "10" следует читать как "один, ноль" и оно не является числом "десять".

Рассматриваемая форма представления чисел называется естественной формой или формой с фиксированной точкой (запятой). Точка используется для разделения числа на целую и дробную части. Это разделение условно, поскольку определяется единицей измерения соответствующей величины, и оказывается существенным только при выполнении арифметических операций. Так, например, мера 3.5 см. может быть заменена числом 0.35 м. или целым числом 35 мм.

При определении количества неделимых объектов (счете) дробные числа вообще не имеют смысла, хотя и в этом случае можно ввести масштабный коэффициент на единицу измерения (сто объектов, тысяча и т.п.). При этом следует отметить, что положение точки при представлении данных не должно меняться для всей задачи или совокупности связанных задач. В памяти ЭВМ, например, все числа обычно представлены дробями, но при программировании с использованием языков высокого уровня интерпретируются как целые (integer), а масштабирование осуществляется в процессе ввода чисел автоматически. Масштабный коэффициент в этом случае задан неявно. Ячейка памяти для хранения чисел в естественной форме иллюстрируется Рис.1.6 Знаковый разряд позволяет определить знак числа, а n-разрядная мантисса хранит его значащую часть.

Вторая из известных и широко используемых форм представления чисел предполагает явное задание масштабного коэффициента и называется формой с плавающей точкой (запятой).

Так десятичное число 625.324 может быть представлено в виде 0.625324 * 10³ , 6.25324 * 10² или 625324 * 10^-3 и т. п. Для записи чисел с плавающей точкой в памяти машины кроме знакового разряда числа и мантиссы требуются разряды для отображения знака порядка (показателя степени во втором сомножителе) и значения самого порядка.

Такие числа в языках высокого уровня чаще всего называются вещественными (real) и записываются в виде 0.625324 Е+3 или 625324 Е-3 и т. п., где Е разделяет мантиссу и порядок.

Минимальным числом, которое можно представить в n-разрядной мантиссе ячейки с фиксированной точкой, будет число А_min=0.000 . . .001 или А_min=2^-n. Числа меньше этого должны были бы размещаться в несуществующих разрядах и поэтому воспринимаются как "0". Такие числа называют машинным нулем. Последний определяет погрешность вычислений.

Максимальное число, которое можно представить в ячейке памяти с фиксированной точкой, есть величина А_max= 0.111 . . . 111 или А_max=1-2^-n. В этом нетрудно убедиться, если из числа 1,000 . . . 000 в двоичной системе счисления вычесть единицу младшего разряда, т.е. 2^-n.

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

Диапазон представления в общем случае есть отношение A_max/A_min. Это отношение позволяет в свою очередь определить кардинальное число card(А) (card - сокращенное от cardinaliti, т.е. мощность множества значений (чисел), которые могут быть представлены в ячейке памяти). Понятие диапазона представления иллюстрируется Таблица 1.6, на котором числа представлены в десятичной системе счисления.

Таблица 1.6 Диапазон представимых чисел в ячейке с фиксированной точкой.

	Переполнение разрядной сетки
Amax	9	9	.	.	.	9	.	.	.	9	9
	9	9	.	.	.	9	.	.	.	9	8
	Область представимых в мантиссе чисел
	0	0	.	.	.	0	.	.	.	0	2
Amin	0	0	.	.	.	0	.	.	.	0	1
	0	0	.	Машинный ноль	.	0	0

Для n-разрядной ячейки с фиксированной точкой диапазон представления D есть величина D=2^-n/(1- 2^-n)=2ⁿ-1.

У современных ЭВМ длина физической ячейки, как правило, равна одному байту, т.е. восьми двоичным разрядам При длине ячейки в один байт D=255. С учетом возможности представления в такой ячейке и числа "0" ее кардинальное число равно 256, т.е. card(байт)=256. Естественно, что такое кардинальное число слишком мало для представления чисел. Поэтому реально числа представляются в логических ячейках, длина которых соответствует нескольким физическим ячейкам (байтам) и, соответственно, таким образом увеличивается их диапазон представления.

Если длина логической ячейки, например, равна двум байтам, то реальный диапазон представления есть величина D =2¹⁵-1=32767 (показатель степени равен 15, поскольку шестнадцатый разряд - знаковый), а кардинальное число - card =2¹⁶ (с учетом возможности представления отрицательных чисел и нуля). Для оценки погрешности вычислений при определенном представлении чисел можно использовать традиционные меры - абсолютную и относительную погрешности.

Абсолютная погрешность A есть среднее арифметическое между максимальным и минимальным значениями "отбрасываемой" части числа, т.е. той части, которая соответствует машинному нулю. Максимальное значение для n-разрядной мантиссы в пределе равно 2^-n (единице младшего разряда), а минимальное - нулю. Таким образом A=2^-(n+1).

Относительная погрешность есть величина, определяемая отношением абсолютной погрешности к самому числу, т.е. лежит в интервале [_min, _max]. При этом _min,= A /A_max , а _max=A/A_min. Таким образом, относительная погрешность вычислений при представлении чисел, например, в форме с фиксированной точкой может колебаться в пределах от 0 до 100%.

При желании определить диапазон и точность представления чисел с плавающей точкой лучше предварительно ознакомиться с соответствующей литературой, например, [16], поскольку числа в ячейке машины обычно представляются в нормализованной нормальной форме, т.е. у мантиссы первый разряд всегда значащий (не равен нулю).

5. Эволюция средств программирования

При написании фрагментов программ ранее использовались числовые коды операций и числовые значения адресов памяти. Такой способ написания программ называется программированием в числовых кодах. Его трудоемкость очевидна. Нормой для квалифицированного программиста, пишущего такие программы, считалось оформление 4-8 отлаженных относительно всей программы команд в рабочую смену, а сложность реальных программ характеризовалась несколькими сотнями команд. При большей сложности программист попадал в фазу "панической отладки", когда устранение ошибок приводило к внесению новых и т. д. Поэтому естественным оказалось стремление облегчить труд программиста, частично возложив его на саму машину, т.е. автоматизировать процесс написания программ.

Первым шагом в этой области можно считать разработку программ, которые "переводили" (транслировали) более привычную для человека символьную форму пошагового описания вычислений в программу, написанную в числовых кодах. Примером такой пошаговой формы может служить левая часть комментария таблицы 2, выделенная жирным шрифтом. Таким образом в средства программирования вводится абстракции (понятие переменной, символьное изображение операций), которые позволяет программисту отвлечься от проблем, связанных с формой представления чисел, кодированием операций и распределением памяти. Однако, в этом случае перед программой-транслятором (точнее перед разработчиком этой программы) возникает не простая задача: каким образом выбрать форму представления чисел и размер логической ячейки при формировании таблицы распределения памяти. Простейший способ ее решения - выбрать для всех переменных один и тот же размер логической ячейки "с запасом". Такое решение мало пригодно потому, что почти всегда приведет к лишним затратам памяти. Кроме того остается неясным выбор формы представления чисел. Более эффективное решение заключается в том, что транслятору в тексте программы необходимая для этих целей информация сообщается дополнительно, т.е. в программу некоторым образом вводится спецификация типов переменных и на основании этой спецификации строится таблица распределения памяти.

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

Подобные описанному выше языки программирования назывались языками символического кодирования, а системы программирования - системами символического кодирования (ССК). Сегодня такие языки превратились в достаточно мощные средства программирования, называемые Ассемблерами.

Дальнейшими шагами в этом направлении явилось расширение палитры средств языков (дополнительных абстракций) и параллельное совершенствование трансляторов. Здесь можно упомянуть язык FORTRAN (аббревиатура от FORmula TRANsaction). Эти языки (языки высокого уровня) позволяли записывать формулы в принятом для алгебраических выражений виде, управлять форматами чисел, вводом-выводом, организовать ветвящийся и циклический вычислительный процесс, работать с простейшими структурами данных и др., причем язык FORTRAN используется и совершенствуется по сей день.

По мере усложнения языков программирования создавать и анализировать программы становилось проще и удобнее, но в то же время задача перевода программ на язык числовых кодов команд, выполняемых машиной, становилась все труднее. Эти трудности компенсировались с помощью ступенчатой трансляции (на жаргоне - метода "раскрутки" программного обеспечения), при которой использовались уже имеющиеся трансляторы, или сам транслятор программировался на языке достаточно высокого уровня. Например, в первом случае для трансляции FORTRAN-программы достаточно "привести" ее в текст на языке АССЕМБЛЕР, а остальное завершит транслятор с АССЕМБЛЕРА.

В общем случае, если программа на языке высокого уровня написана без ошибок, можно условно представлять транслятор и ЭВМ единой машиной, которая может непосредственно выполнять программы, т.е. не принимать во внимание процесс трансляции. Сочетание транслятора и ЭВМ иногда называют виртуальной машиной. На рисунке (Рис.1.5) показана структура такой машины. Ее процессором является ЭВМ, которая используется дважды. На первом этапе программа, выполняемая виртуальной машиной - это транслятор, а исходные данные - текст программы на языке высокого уровня. Результатом будет перевод такой программы в машинные коды. Далее ЭВМ будет использована еще раз при выполнении рабочей программы, данными для которой послужат исходные данные самой задачи, а результатом - данные, определяющие ее решение.



Рис.1.5 Структура виртуальной машины

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

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

2. Ошибки, обнаруживаемые при выполнении рабочей программы. Такие ошибки могут возникать, например, при переполнении разрядной сетки, попытке извлечь квадратный корень из отрицательного числа и т.п. Такой тип ошибок называется ошибками времени выполнения (run time error).

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

Однако ошибки могут быть не только в программе, они могут появляться и в данных. Примером ошибки в исходных данных является ввод значения переменной x вместо y или числа 5 - вместо числа 15. Некоторые языки высокого уровня строятся таким образом, что ошибки этого типа можно частично обнаружить.

Начала современной трактовки концепций разработки универсальных языков программирования высокого уровня были заложены в языке АЛГОЛ 60, официальное сообщение о котором появилось в 1960 году. Параллельно закладывались концепции для разработки проблемно-ориентированных языков высокого уровня для решения, например, экономических задач и задач делопроизводства (COBOL), моделирования сложных систем (SOL, SIMULA) и т. п.

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

Как уже отмечалось, параллельно со средствами написания программ (языками) совершенствовались и системы программирования в целом. В настоящее время трансляторы позволяют получать "рабочие программы" (программы в числовых кодах) по качеству практически приближающиеся к оптимальным по объему требуемой для их решения памяти и производительности. Сервисные средства, в свою очередь, позволяют эффективно и удобно работать с текстами программ при их подготовке и модификации, находить и устранять допущенные ошибки, объединять и расчленять программы на отдельные модули, создавать библиотеки программ и, даже, компилировать программы просто объединяя по определенным правилам "картинки", которые соответствуют библиотечным модулям программам, программируя таким образом решение задачи в целом.

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

6. Формализованное определение понятия "язык"

Формально, хотя и недостаточно строго, язык определяется четверкой:

L= { V_T, V_H, P, S },

где :

V_T = {v_Ti}, i=(1,2,...,n) - множество терминальных символов или терминальный словарь языка, который также называют его алфавитом. Слово "алфавит" здесь почти полностью соответствует его неформальному определению в разговорных языках и отличается тем, что включает все символы, в то время как, например, точка, запятая, знак переноса, восклицательный знак и т.п. при неформальном определении разговорных языков в алфавит не включаются;