Реферат: Логические основы ЭВМ вопросы: Представление команд в ЭВМ

ОСНОВЫ ПРОГРАММИРОВАНИЯ

Изучаемые темы:


1. Представление команд и чисел в ЭВМ. Логические основы ЭВМ.

2. Алгоритмы и алгоритмизация. Языки программирования.

3. Технология программирования.

Тема № 1

ПРЕДСТАВЛЕНИЕ КОМАНД И ЧИСЕЛ В ЭВМ.

ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ


Вопросы: 1. Представление команд в ЭВМ.

2. Позиционные системы счисления. Арифметические операции в

позиционных системах счисления.

3. Перевод чисел из одной системы счисления в другую.

Смешанные системы счисления.

4. Представление чисел в ЭВМ.

5. Логические основы ЭВМ.


1. Представление команд в ЭВМ


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

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

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


^ 2. Позиционные системы счисления. Арифметические операции в позиционных системах счисления


Под системой счисления понимают совокупность приемов записи и наименования чисел.

Примером системы счисления является хорошо известная десятичная система счисления. Любое число в ней представлено с помощью набора из десяти цифр от 0 до 9. При этом значение каждой цифры в записи числа зависит от места (позиции), на котором она стоит в этой записи. Так, например, в записи 777,77 цифра 7 встречается пять раз, но в каждой позиции она имеет разный смысл: крайняя левая цифра 7 означает количество сотен, следующая цифра 7 означает количество десятков, цифра 7, стоящая перед запятой, означает количество единиц, цифра 7 после запятой - количество десятых долей единицы, и, наконец, последняя цифра 7 - количество сотых долей единицы. Все это можно выразить следующим образом:

777,77 = 7*102 + 7*101 + 7*10 0 + 7*10 -1 + 7*10-2

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

Итак, представление чисел в десятичной системе счисления основано на том, что любое число можно разложить по степеням числа 10, где каждый из коэффициентов - одно из базисных чисел этой системы. Последовательность этих коэффициентов и есть запись числа в десятичной системе счисления. Но ведь можно разлагать числа не только по степеням числа 10, а по степеням любого другого целого числа. Разложим, например, число 25,75 по степеням числа 2:

25,75 = 1*24 + 1*23 + 0*22 + 0*21 + 1*20 + 1*2-1 + 1*2-2

Коэффициенты в разложении здесь представлены одной из двух возможных цифр - 0 или 1. И точно также как и в десятичной системе, можно записать число, собрав все коэффициенты при степенях числа 2: 11001,11.

Получившаяся запись есть числа в двоичной системе счисления: основание системы счисления - число 2, а базисные числа есть 0 и 1.

Чтобы отличать числа, записанные в разных системах счисления, их обычно заключают в скобки и внизу пишут основание системы счисления:

(25,75)10 = (11001,11) 2

Кроме двоичной системы счисления существует еще и восьмеричная система счисления. Здесь основанием системы счисления является 8, а базисными числами 0, 1, 2, 3, 4, 5, 6, 7. Например:

(654,2)8 = 6*82 + 5*81 + 4*80 + 2*8-1 = 6*64 + 40 + 4 + 0,25 = (428,25)10

Полезно познакомиться и с шестнадцатеричной системой счисления. Базисные числа здесь от 0 до 15 включительно, т.е. любое число разлагается по степеням числа 16 с коэффициентами из указанного набора базисных чисел. Здесь, однако, возникает проблема обозначения базисных чисел - арабских цифр уже не хватает. Поэтому для обозначения базисных чисел от 0 до 9 используют обычные арабские цифры от 0 до 9, а для последующих чисел - от 10 до 15 используют буквы a, b, c, d, e, f. Так, запись (5е1,4)16 означает:

(5е1,4)16 = 5*162 +14*161 +1*160 +4*16-1 = 5*256 +14*16 +1 +0,25 = (1505,25)10

Арифметические операции во всех позиционных системах счисления выполняются по одним и тем же правилам. Рассмотрим эти правила на примере двоичной системы счисления.

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

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 10

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

Сложение многоразрядных двоичных чисел происходит в соответствии с вышеприведенной таблицей сложения с учетом возможности переносов из младших разрядов в старшие. В качестве примера сложим два двоичных числа 1102 и 112:

1102

+

112

-------

10012

В основе вычитания двоичных чисел лежит таблица вычитания одноразрядных двоичных чисел:

0 - 0 = _0

0 - 1 = 11

1 - 0 = 1

1 - 1 = 0

Следует заметить, что при вычитании из меньшего числа (0) большего (1) производится заем из старшего разряда. Такой заем обозначается 1 с чертой.

Вычитание многоразрядных двоичных чисел происходит в соответствии с вышеприведенной таблицей вычитания с учетом возможности заемов из старших разрядов. В качестве примера произведем вычитание двоичных чисел 1102 и 112:

1102

-

112

-------

112

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

0 ∙ 0 = 0

0 ∙ 1 = 0

1 ∙ 0 = 0

1 ∙ 1 = 1

Умножение многоразрядных двоичных чисел происходит в соответствии с вышеприведенной таблицей умножения по обычной схеме, применяемой в десятичной системе счисления с последовательным умножением множимого на цифры множителя. В качестве примера произведем умножение двоичных чисел 1102 и 112:

1102

×

112

-------

110

110

-------

100102

Операция деления выполняется по алгоритму, подобному алгоритму операции деления в десятичной системе счисления. В качестве примера произведем деление двоичного числа 1102 на 112:

_ 1102 112

11 102

----------

0

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

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


3. Перевод чисел из одной системы счисления в другую.
^ Смешанные системы счисления

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

Рассмотрим перевод чисел из двоичной системы счисления в десятичную. Известно, что запись любого числа в двоичной системе счисления представляет набор коэффициентов в разложении этого числа по степеням числа 2:

х = аn*2n + аn-1*2n-1 + ... + а1*21 + а0*20 + а-1*2-1 + а-2*2-2 + ...

Здесь каждое из аi равно либо 0, либо 1.

Для получения десятичного изображения этого выражения достаточно перемножить эти коэффициенты с соответствующими степенями числа 2 и сложить результаты. Например:

(1011,01)2 = 1*23 + 0*22 + 1*21 + 1*20 + 0*2-1 + 1*2-2 = 8 + 0 + 2 + 1 + 0 + 0,25 = (11,25)10

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

Например, алгоритм перевода числа 25 из десятичной системы счисления в двоичную записывается в следующем виде:


25 2

1 12 2

0 6 2

0 3 2

1 1 2

1 0

Собирая остатки от деления, получим (25)10 = (11001)2 (стрелка показывает порядок записи коэффициентов результата).

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

х = а-1*2-1 + а-2*2-2 + а-3*2-3 + ...

Здесь аi(i = 1, 2, ...) - коэффициенты, принимающие значения либо 0, либо 1.

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

В качестве примера рассмотрим перевод числа х = 0,125 в двоичную систему счисления. Алгоритм перевода записывается в следующем виде:




0 125

0 25

0 5

1 0


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

Переведем теперь число х = 0,3:


0 3

0 6

1 2

0 4

0 8

1 6


Легко видеть, что процесс здесь периодический и никогда не оборвется. До каких пор продолжать вычисления? Если считать, что исходная величина задана точно, то чем больше результатов будет получено, тем лучше. Если это число нужно будет ввести в машину, то достаточно того количества цифр в результате, которое можно записать в ячейку памяти машины. Наконец, если исходное число задано с известной погрешностью, то примерно с той же погрешностью можно брать и переведенное число.

Схема Горнера применима и для перевода чисел в четверичную, восьмеричную, шестнадцатеричную и т.д. системы счисления. В этом случае необходимо только делить и умножать соответственно на 4, 8, 16 и т.д.

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

Например, десятичное число 834,25 в двоично-десятичной системе запишется так:

(834,25)10= (1000 0011 0100, 0010 0101)2-10

Каждая четверка цифр здесь соответствует одной десятичной цифре:

(8)10 = (1000)2-10, (3)10 = (0011)2-10, (4)10 = (0100)2-10, (2)10 = (0010)2-10, (5)10 = (0101)2-10.


^ 4. Представление чисел в ЭВМ


В различных ЭВМ может быть различная длина ячейки памяти и различные формы представления чисел. Пусть, например, ячейка памяти машины имеет 24 двоичных разряда. В ячейку можно поместить любое машинное слово, т.е. произвольный набор из нулей и единиц. Если слово - число, то его представление может быть таким: крайний слева разряд - знаковый, затем следующие 9 разрядов отводятся под целую часть, затем следует разряд под запятую и, наконец, оставшиеся 14 разрядов отводятся под дробную часть числа.

Диапазон чисел, которые можно записать в ячейку памяти машины, здесь таков:

2-14 | а | < 29 .

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

а = А* QP,

где А называют мантиссой числа, а Р - порядком.

Очевидно, что такое представление не однозначно. Так, например, число 3,14 можно записать в виде:

3,14 = 3,14*100 = 31,4*10-1 = 0,0314*102 = ...

Порядок числа определяет положение запятой в записи мантиссы. При корректировке порядка соответствующим образом меняется и положение запятой - запятая как бы “плавает”. Отсюда и название метода представления чисел.

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

1/ Q | A | < 1,

где Q - основание системы счисления, а А - мантисса.

Так, для двоичной системы счисления 0,5 | A | <1.

При представлении чисел с плавающей запятой в ячейке памяти ЭВМ нулевой разряд отводят под знак числа, первый - под знак порядка, в следующих семи разрядах, т.е. со 2-го по 8-й - порядок, и, наконец, с 9-го по 23-й разряды отводятся под мантиссу числа. Причем знак “+” обозначается нулем, а знак “-” обозначается единицей, как для знака числа, так и для знака порядка.


^ 5. Логические основы ЭВМ


Теоретической основой построения ЭВМ являются специальные математические дисциплины. Одной из них является алгебра логики или булева алгебра (Дж. Буль (1815-1864) – английский математик, основоположник этой дисциплины). Ее аппарат широко используется для описания схем ЭВМ, их оптимизации и проектирования.

Как уже отмечалось, вся информация в ЭВМ представляется в двоичной системе счисления. Поставим в соответствие входным сигналам отдельных устройств ЭВМ соответствующие значения xi (i =1,n), а выходным сигналам – значения функций yj (j =1,m):

Структурная
схема

ЭВМ

X1 Y1


Xi Yj


Xn Ym


В этом случае зависимостями yj = f(x1, x2, … ,xn), где xi – i-й вход, n – число входов, yj – j-й выход, m – число выходов в устройстве, можно описывать алгоритм работы любого устройства ЭВМ. Каждая такая зависимость yj является булевой функцией, у которой число возможных состояний и каждой ее независимой переменной равно двум, т.е. функцией алгебры логики, а ее аргументы определены на множестве {0,1}. Символы «0» и «1» в алгебре логики характеризуют состояния переменных или состояния их функций, в связи с чем их нельзя рассматривать как арифметические числа. Алгебра логики является алгеброй состояния, а не алгеброй чисел, и для нее характерны основные действия, отличные от принятых в обычной алгебре действий над числами. Алгебра логики исследует высказывания, а также связи между ними.

Различают простое и сложное высказывание. Под высказыванием понимается всякое предложение, принимающее два значения – «истинно» или «ложно». Значение истинности обозначают цифрой 1, значение ложности – цифрой 0. Исходные высказывания называют простыми, а образованные из них другие высказывания – сложными. Например, высказывание «Школа – учебное заведение» является истинным, а высказывание «Драйвер – устройство для подключения приборов» – ложным.

Будем обозначать высказывания переменными X, Y, Z, … .Из простых высказываний можно образовывать сложные высказывания, соединяя их связками «И», «ИЛИ», «НЕ» и др.

Объединение двух (или нескольких) высказываний в одно с помощью союза «И» называется операцией логического умножения, или конъюнкцией. Эту операцию принято обозначать знаком «Λ» или знаком умножения «•». Сложное высказывание X Λ Y истинно только в том случае, когда истинны оба входящих в него высказывания. Истинность такого высказывания задается следующей таблицей (таблица 1)

Таблица 1

X

Y

X  Y

0

0

0

0

1

0

1

0

0

1

1

1


Объединение двух (или нескольких) высказываний с помощью союза «ИЛИ» называется операцией логического сложения, или дизъюнкцией. Эту операцию обозначают знаком «V» или знаком сложения «+». Сложное высказывание X V Y истинно, если истинно хотя бы одно из входящих в него высказываний. Таблица истинности для логической суммы имеет вид (таблица 2):

Таблица 2

X

Y

X + Y

0

0

0

0

1

1

1

0

1

1

1

1


Присоединение частицы «НЕ» к данному высказыванию называется операцией отрицания. Она обозначается X и читается «НЕ X». Если высказывание X истинно, то X ложно, и наоборот. Таблица истинности в этом случае имеет вид (таблица 3):

Таблица 3




X


X

0

1

1

1


Помимо операций «И», «ИЛИ», «НЕ» в алгебре логики существует много других операций. Например, операция эквивалентности (X ~ Y), которая имеет следующую таблицу истинности (таблица 4):

Таблица 4

X

Y

X ~ Y

0

0

1

0

1

0

1

0

0

1

1

1


Другим примером может служить логическая операция импликации (X→Y), объединяющая высказывание «Если…то» и имеющая следующую таблицу истинности (таблица 5):

Таблица 5

X

Y

X→Y

0

0

1

0

1

1

1

0

0

1

1

1


Исходя из определений дизъюнкции, конъюнкции и отрицания, устанавливаются свойства этих операций и взаимные распределительные свойства. Приведем некоторые из этих свойств:

X+1 = 1; X+X = 1; X•0 = 0; X+0 = X; X+X = X; X•1 = X; X•X =0;
X•X = X; X+X+ … +X = X; X•X• … •X = X
В алгебре логики установлен целый ряд законов:

Переместительный закон (закон коммутативности) для логического сложения и умножения:
^ X+Y = Y+X X•Y = Y•X
Сочетательный закон (закон ассоциативности) для логического сложения и умножения:

(X+Y)+Z = X+(Y+Z) (X•Y)•Z = X•(Y•X)

Распределительный закон (закон дистрибутивности логического умножения по отношению к сложению):

X•(Y+Z) = X•Y + X•Z X + Y•Z = (X+Y)•(X+Z)

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

1) X•Y + X•Y = X

2) X + X•Y = X

3) X•(X+Y) = X

4) X•(X+Y) = X•Y

5) (X+Y)•(X+Z) = X + Y•Z

В справедливости тождеств 1 и 2 нетрудно убедиться, вынося за скобку в левой части переменную X. Тождество 3 доказывается с помощью распределительного закона X•(X+Y) = X•X + Y•Y = X + X•Y = X. Аналогично доказывается и тождество 4. Для доказательства тождества 5 раскроем скобки в левой части:

(X+Y)•(X+Z) = X + X•Z + X•Y + Y•Z = X + X•Y + Y•Z = X + Y•Z

К основным законам алгебры логики относятся законы инверсии для логического сложения и умножения (теоремы де Моргана):
^ X+ Y+Z = X•Y•Z X•Y•Z = X+Y+Z
Убедиться в тождественности приведенных зависимостей можно путем построения таблицы истинности для логических функций, находящихся в левой и правой частях.

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

Контрольные вопросы



Как осуществляется выполнение машинной операции в ЭВМ?

Как представлены команды в ЭВМ?

Что такое система счисления?

Что значит позиционная система счисления?

Что является основанием двоичной (восьмеричной, десятичной, шестнадцатеричной) системы счисления?

Какое число является базисным в двоичной (восьмеричной, шестнадцатеричной) системе счисления?

Запишите таблицу сложения (вычитания, деления) одноразрядных двоичных чисел.

Проведите сложение, вычитание, умножение и деление двоичных чисел 10101 и 110.

Проведите сложение и вычитание восьмеричных чисел 31 и 17.

Проведите сложение и вычитание шестнадцатеричных чисел 42 и 18.

Как осуществляется перевод целых (дробных) чисел из десятичной системы счисления в двоичную (четверичную, восьмеричную, шестнадцатеричную) систему счисления по схеме Горнера?

Переведите в десятичную форму записи двоичное число 11110.

Переведите в двоичную форму записи десятичное число 64.

Переведите в двоичную форму записи восьмеричное число 67.

Переведите в двоичную форму записи шестнадцатеричное числоА3.

Как представлены числа в смешанной двоично-десятичной системе счисления?

Как представлены числа в ЭВМ, ячейка памяти которых имеет 24 двоичных разряда?

Как представлены числа в форме записи с плавающей запятой?

Что понимается под высказыванием? Приведите примеры истинного и ложного высказываний.

Что понимается под конъюнкцией? Запишите таблицу истинности логического умножения двух переменных.

Что понимается под дизъюнкцией? Запишите таблицу истинности логического сложения двух переменных.

Что является операцией отрицания (эквивалентности, импликации)? Приведите примеры таблиц истинности этих операций.

Приведите примеры свойств операций дизъюнкции, конъюнкции и отрицания.

Запишите выражения для переместительного (сочетательного, распределительного) закона.

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

Тема № 2

^ АЛГОРИТМЫ И АЛГОРИТМИЗАЦИЯ. ЯЗЫКИ ПРОГРАММИРОВАНИЯ


Вопросы: 1. Понятия алгоритма и алгоритмизации.

2. Языки программирования.


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


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

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

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

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

1. В определении алгоритма говорится, что алгоритм - это точное предписание, которое задает некоторый процесс. Действительно, в данном случае есть точное предписание насчет того, что, сколько и как варить для того чтобы получился борщ.

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

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

Другим примером алгоритма является инструкцию по пользованию телефоном-автоматом, которую можно представить следующим образом:

начало

снимите трубку

если слышан непрерывный гудок

то вставьте карточку и наберите номер

если абонент ответил

то говорите с абонентом

иначе выньте карточку и повесьте трубку

конец

Приведенный алгоритм записан с использованием элементов алгоритмического языка (языка для записи алгоритмов), позволяющего читать алгоритмы и пользоваться ими для решения задач.

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

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

алг имя алгоритма

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

надо цель выполнения алгоритма

нач начало алгоритма

| тело алгоритма (последовательность команд)

кон конец алгоритма

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

В качестве примера вычислительного алгоритма рассмотрим алгоритм Евклида (алгоритм нахождения наибольшего общего делителя для двух натуральных чисел X и Y). Этот алгоритм состоит из отдельных пунктов-указаний, предписывающих исполнителю выполнять некоторые действия. Каждое такое указание называется командой. Команды алгоритма выполняются одна за другой. На каждом шаге исполнения алгоритма исполнителю точно известно, какая команда должна выполняться следующей. Поочередное выполнение команд алгоритма за конечное число шагов приводит к решению задачи, в данном случае нахождению наибольшего общего делителя двух чисел:

1. Присвоить значения двум числам X и Y.

2. Если X > Y, перейти к шагу 5.

3. Если X < Y, перейти к шагу 6.

4. Если X = Y, то X- результат. Конец работы алгоритма.

5. Заменить пару (X,Y) парой (X - Y, Y) и перейти к шагу 2.

6. Заменить пару (X,Y), парой (X,Y - X) и перейти к шагу 2.

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

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

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

ветвление цикл



Условие

Условие


Да Нет Да




Команда 1

Команда 2

Команда 1
Нет








Команда 2

При разработке алгоритмов необходимо соблюдать определенные требования:

1. Конечность. Работа алгоритма должна заканчиваться за конечное число шагов.

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

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

4. Вывод. Алгоритм должен давать результат.

5. Эффективность. Общее время работы алгоритма должно быть в разумных пределах.

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

Процесс разработки алгоритма включает в себя следующие этапы:

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

2. Построение математической модели исходной задачи (описание исходной задачи с использованием математических формул).

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

На рис. 1 показаны символы, используемые при построении алгоритма решения задачи, а на рис. 2 алгоритм Евклида, построенный с использованием этих символов.

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


^ 2. Языки программирования


Программирование появилось задолго до появления компьютеров. Первым программистом считается дочь известного поэта лорда Байрона Ада Лавлейс – ученица английского математика Чарльза Бэббиджа, разработавшего в XIX веке проект вычислительной машины. В честь Ады Лавлейс один из языков программирования был назван ее именем, впоследствии широко применяемый в Министерстве Обороны Соединенных Штатов Америки.

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

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

^ Язык программирования низкого уровня - это язык программирования, структура команд которого определяется форматом команд и данных машинного языка, а также архитектурой ЭВМ.

Ярким представителем языка программирования низкого уровня является язык Ассемблер (Assembler), который был разработан в 50-е годы прошлого века и позволяет писать программы с использованием специальных обозначений машинных кодов - мнемоники. Ассемблер широко применяется в программах, где необходимо высокое быстродействие.

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

^ Язык программирования высокого уровня - это язык программирования, средства которого допускают описание задачи в наглядном, легко воспринимаемом виде.

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

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

Каждый язык программирования высокого уровня имеет свой стиль, свои правила и свою область применения. К основным языкам программирования высокого уровня относятся (в алфавитном порядке):

Ада (англ. Ada) – назван в честь Августы Ады Байрон, графини Лавлейс, дочери лорда Байрона, которая была сотрудницей Чарльза Бэббиджа, изобретателя аналитической машины, и написала для нее практически законченную программу вычисления коэффициентов Бернулли. Кроме того, она ввела многие понятия (цикл, условный оператор), которые теперь составляют базу программирования. Сам язык Ада является универсальным языком программирования, поддерживающим методологии разработки снизу вверх и сверху вниз, раздельную компиляцию, настраиваемые пакеты, абстрактные типы данных, параллельное программирование и работу реальном времени, средства для низкоуровнего программирования, контролируемую точность вычислений, возможность гибкой настройки на конкретную платформу и многое другое. В настоящее время Ада является основным языком программирования Министерства обороны США.

Алгол (англ. Algoritmithmic Language - алгоритмический язык) - универсальный язык для программирования вычислительных задач. Ему свойственна близость к математической символике.

Бейсик (Beginer All-Purpose Symbolic Code - универсальный символический код для начинающих) - язык для создания программ и их решения ЭВМ в режиме диалога. Он был разработан в середине 60-х годов профессорами Дармутского колледжа Джоном Кемени и Томасом Курцом. Бейсик является одним из самых простых и распространенных в мире языков программирования. В середине 80-х годов фирмой Microsoft был реализован язык QuickBasic (последняя версия 4.5). Это полностью компилируемый язык, с нормальными структурными конструкциями, пользовательскими типами данных, причем еще и совместимый со старыми версиями. C появлением Windows и моды на визуальные средства разработки изменился и Basic. Его новая версия, названная Visual Basic, была отлично приспособлена для написания несложных программ с развитым пользовательским интерфейсом. Visual Basic, наравне с Visual С является весьма популярным средством разработки под Windows.

Делфи (англ. Delphi) оказался одним из первых продуктов, который сделал процесс программирования простым и понятным даже начинающим разработчикам. Это было связано с появлением в начале 90-х операционных систем со встроенным графическим интерфейсом. Действительно, процесс разработки программы в Delphi предельно упрощен. В первую очередь это относится к созданию интерфейса, на который уходит 80% времени разработки программы. Вы просто помещаете нужные компоненты на поверхность Windows-окна (в Delphi оно называется формой) и настраиваете их свойства с помощью специального инструмента (Object Inspector). С его помощью можно связать события этих компонентов (нажатие на кнопку, выбор мышью элемента в списке и т.д.) с кодом его обработки – и простое приложение готово. При этом разработчик получает в свое распоряжение мощные средства отладки (вплоть до пошагового выполнения команд процес