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

 

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

 

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

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

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

Тема № 1

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

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

 

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

                  2. Позиционные системы счисления.

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

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

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

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

 

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

 

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

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

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

 

2. Позиционные системы счисления

 

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

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

777,77 = 7*10²  + 7*10¹   + 7*10 ⁰  + 7*10 ^-1   + 7*10^-2

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

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

25,75 = 1*2⁴  + 1*2³  +  0*2²  + 0*2¹  + 1*2⁰  + 1*2^-1   + 1*2^-2

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

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

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

(25,75)₁₀  = (11001,11) ₂

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

(654,2)₈  = 6*8²  + 5*8¹  + 4*8⁰  + 2*8^-1   = 6*64 + 40 + 4 + 0,25 = (428,25)₁₀

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

(5е1,4)₁₆ = 5*16² +14*16¹ +1*16⁰ +4*16^-1 = 5*256 +14*16 +1 +0,25 = (1505,25)₁₀

 

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

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

 

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

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

х = а_n*2ⁿ + а_n-1*2^n-1 + ... + а₁*2¹ + а₀*2⁰ + а_-1*2^-1 + а_-2*2^-2  + ...

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

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

(1011,01)₂ = 1*2³ + 0*2² + 1*2¹ + 1*2⁰ + 0*2^-1 + 1*2^-2 = 8 + 0 + 2 + 1 + 0 + 0,25 = (11,25)₁₀

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

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

 

25  2

  1   12   2

         0    6   2

               0     3   2

                      1    1    2

                            1    0

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

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

х = а_-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)₁₀= (1000  0011  0100,  0010  0101)_2-10

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

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

 

 

 

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

 

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

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

2^-14  | а | < 2⁹ .

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

а = А* Q^P,

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

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

3,14 = 3,14*10⁰  = 31,4*10^-1 = 0,0314*10²  = ...

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

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

1/ Q  | A | < 1,

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

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

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

 

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

 

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

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

 

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

 

                  X₁                                                                                            Y₁

 

                  X_i                                                                                             Y_j

 

                  X_n                                                                                             Y_m

 

 

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

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

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

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

Таблица 1

 

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

Таблица 2

 

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

Таблица 3

 

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

Таблица 4

 

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

Таблица 5

 

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

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

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

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

 

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тема № 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

                                                                                                                     Нет                    

 

 

 

 

                                                                                                                              

 

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

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). С его помощью можно связать события этих компонентов (нажатие на кнопку, выбор мышью элемента в списке и т.д.) с кодом его обработки – и простое приложение готово. При этом разработчик получает в свое распоряжение мощные средства отладки (вплоть до пошагового выполнения команд процессора), удобную контекстную справочную систему, средства коллективной работы над проектом и т.д., всего не перечислить.

Кобол (англ. Common Business Oriented Language - коммерческий язык) - язык, используемый, в первую очередь, для программирования экономических задач.

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

Паскаль (англ. Philips Automatic Sequence Calculator). Этот язык был разработан швейцарским ученым Никлаусом Виртом в 1969 году как учебный язык, но спустя некоторое время приобрел популярность как отличный инструмент для решения серьезных задач. Программирование на Паскале обеспечивает высокую надежность программ. Программы на Паскале понятны любому программисту и в то же время они легко транслируются в эффективные машинные коды. Паскаль, наряду с Бейсиком, считается также учебным языком; он принят во многих учебных заведениях как базовый язык для изучения программирования. Так, в США с 1983 года Паскаль введен в учебные курсы всех средних школ для учащихся, специализирующихся в области информатики. По мере своего развития язык Паскаль постоянно совершенствовался и приобретал новые свойства и сейчас более известен язык Турбо-Паскаль, разработанный фирмой Borland.

ПЛ/1 (англ. PL/I – Programming Language I). ПЛ/1 задумывался как универсальный язык высокого уровня для решения любых задач – от вычислительных до системных. Он объединил в себе лучшие черты своих предшественников – Алгола, Фортрана, Кобола и других, но привнес и множество новых, мощных и отчасти революционных решений. В своей основе ПЛ/1 является процедурно-ориентированным языком. Программа ПЛ/1 состоит из блоков. Начало, конец и вложенность блоков определяются явно. Поддерживается разграничение областей видимости переменных, включая перекрытие одинаковых имен. Имеются средства организации мультизадачности с управлением приоритетами и синхронизацией подзадач. Язык содержит мощные средства событийной обработки ошибок, причем их обработчики могут динамически включаться, отключаться и переназначаться, а также иметь индивидуальные области действия. Существуют переменные типа «метка» и их массивы, что позволяет строить сложные системы косвенных переходов, управляемых данными. В смысле переходов ПЛ/1 вообще очень гибок – допускаются межблочные переходы, вложенные и рекурсивные подпрограммы, а также дополнительные точки входа в них с собственными списками параметров. Даже в тело цикла можно войти, минуя его заголовок. ПЛ/1 имеет гибкие средства управления памятью, которая рассматривается как статическая, автоматическая и динамическая. Язык ПЛ/1 поддерживает файлы с прямым и последовательным доступом, а также индексно-последовательные файлы и файлы с доступом по ключу. В бывшем СССР язык ПЛ/1 стал широко известен с конца 60-х годов и использовался на машинах серии ЕС – клоне семейства IBM 360/370.

Пролог – язык, который наряду с языком Лисп (см. выше), применяется при разработке систем искусственного интеллекта. В основе этого языка лежит аппарат математической логики. Язык Пролог позволяет разрабатывать на основе ЭВМ экспертные системы, базы знаний и системы обработки естественного языка. Программа на Прологе содержит, во-первых, набор предикатов-утверждений, которые образуют проблемно-ориентированную базу данных. Другой тип выражений – это правила, имеющие вид условий «чтобы было Х, нужно Y» или «имеет место Х, если справедливо Y», где Х и Y – любые предикаты или переменные. Работа программы начинается с ввода предиката – утверждения или вопроса, который возбуждает перебор имеющихся в базе данных предикатов и правил, пока не будет достигнуто доказательство истинности или ложности исходного утверждения.

Си (англ. С) - язык, специально разработанный для написания системных программ и для переноса записи программного обеспечения с одной ЭВМ на другую. Этот язык был создан сотрудником фирмы Ball Labs Деннисом Ритчи в 1972 году и послужил главным инструментом для создания операционных систем UNIX и MS DOS. Как и все языки, язык С постепенно совершенствовался. Уже в начале 80-х годов Бьерн Страуструп в AT&T Bell Labs стал разрабатывать расширение языка С под условным названием «С с классами», дающий возможность определять и использовать новые типы данных. Первый коммерческий транслятор нового языка, получившего название С++, появился в 1983 году. Он представлял собой препроцессор, транслировавший программу в код на С. Однако фактически рождением языка можно считать выход в 1985 году книги Страуструпа «The C++ Programming Language». Именно с этого момента С++ начинает набирать всемирную популярность. Главным достоинством С++ является возможность создания и использования в программе своих собственных полноценных типов данных, «настроенных» на конкретную задачу. Например, работая в среде Turbo C++, программист может использовать такие концепции: окно редактора или отладчика; текст в текущем окне; меню команд; режим компиляции. Над ними могут выполняться, например, такие действия: открыть новое окно или закрыть ненужное; выбрать другое текущее окно; переместить окно или изменить его размер; выполнить вертикальный сдвиг текста в окне; упорядочить расположение окон на экране; выбрать нужную команду меню с помощью мыши; изменить режим компиляции; сохранить текущий режим компиляции.

Фортран (англ. Formula Translator - переводчик формул) был разработан в середине 50-х годов программистами фирмы IBM. В основном он используется для программ, выполняющих естественно - научные и математические расчеты.

Ява (англ. Java) – язык для программирования Internet, позволяющий создавать безопасные, переносимые, надежные, объектно-ориентированные интерактивные программы с параллельно выполняющимися подпроцессорами. Язык Ява жестко связан с Internet, потому, что первой серьезной программой, написанной на этом языке, был браузер Всемирной паутины.

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

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

назначение разрабатываемой программы – нужна ли она временно или будет использоваться постоянно, планируется ли передавать ее другим организациям, будут ли разрабатываться ее новые версии;

требуемая скорость работы программы, соотношение ее диалоговых и вычислительных компонентов;

ожидаемый размер программы – можно ли ее создавать как единое целое или придется разбивать на отдельные взаимодействующие модули, требуется ли минимизировать размер памяти, занимаемой программой во время работы;

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

предусматривается ли возможность переноса программы на другие типы ЭВМ;

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

необходимость в специальном программировании некоторых функций для работы с внешними устройствами;

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

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

 

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

 

1.      Что такое алгоритм?

2.      Приведите примеры алгоритмов.

3.      Что такое алгоритмический язык?

4.      Приведите пример записи алгоритма на алгоритмическом языке.

5.      Какие алгоритмы называются линейными?

6.      Нарисуйте разветвляющийся (циклический) алгоритм.

7.      Сформулируйте требования к алгоритмам.

8.      Что такое алгоритмизация?

9.      Какие этапы включает в себя процесс разработки алгоритма?

10. Какие символы используются при записи алгоритма?

11. Что такое программирование?

12. Что такое программа?

13. В чем состоит отличие компилятора от интерпретатора?

14. Что значит язык программирования низкого (высокого) уровня? В чем их отличие?

15. Какие языки низкого (высокого) уровня Вы знаете? Дайте им характеристику.

16. Какие критерии используются при выборе языка программирования?

Тема № 3

ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ

(по материалам лекций преподавателя МГУ Жоголева Е.А.)

 

Вопросы: 1. Программное средство: надежность, источники ошибок и общие

                      принципы разработок.

                  2. Внешнее описание программного средства.

                  3. Разработка структуры программы и модульное программирование.

                  4. Разработка программного модуля.

                  5. Тестирование и отладка программного средства.

 

1. Программное средство: надежность, источники ошибок

и общие принципы разработки

 

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

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

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

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

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

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

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

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

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

При разработке ПС мы не всегда можем уверенно знать обо всех связях между ее элементами из-за возможных ошибок. Поэтому полезно уметь оценивать сложность системы по числу ее элементов: числом потенциальных путей взаимодействия между ее элементами, т.е. n!, где n - число ее элементов. Систему называют малой, если n < 7 (6! = 720 < 1000), систему называют большой, если n > 7 . При n = 7 имеем промежуточный класс систем. Малая система всегда проста, а большая может быть как простой, так и сложной. Задача технологии программирования – научиться делать большие системы простыми.

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

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

Чтобы понять природу ошибок человека при переводе рассмотрим этапы его перевода:

1) получение информации;

2) запоминание полученной информации в своей памяти;

3) выбор из памяти преобразуемой информации и информации, описывающей процесс преобразования, перевод и посылка результата своему пишущему механизму;

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

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

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

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

Разработка ПС состоит из его внешнего описания, разработки текстов программ, процессов документирования и этапа аттестации ПС.

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

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

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

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

Надежность - это способность ПС безотказно выполнять определенные функции при заданных условиях в течение заданного периода времени

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

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

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

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

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

Рассмотрим общие принципы обеспечения надежности ПС. В технике известны четыре подхода обеспечению надежности:

1) предупреждение ошибок;

2) самообнаружение ошибок;

3) самоисправление ошибок;

4) обеспечение устойчивости к ошибкам.

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

а) борьбе со сложностью,

б) обеспечения точности перевода,

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

г) обеспечения контроля принимаемых решений.

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

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

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

1) обеспечения независимости компонент системы;

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

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

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

1) понять задачу;

2) составить план (включая цели и методы решения);

3) выполнить план (проверяя правильность каждого шага);

4) проанализировать полученное решение.

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

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

 

2. Внешнее описание программного средства

 

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

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

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

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

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

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

Функциональность: завершенность.

Надежность: завершенность, точность, автономность, устойчивость, защищенность.

Легкость применения: П-документированность, информативность (только применительно к документации по применению), коммуникативность, устойчивость, защищенность.

Эффективность: временная эффективность, эффективность по памяти, эффективность по устройствам.

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

Изучаемость: С-документированность, информативность, понятность, структурированность, удобочитаемость.

Модифицируемость: расширяемость, структурированность, модульность.

Мобильность: независимость от устройств, автономность, структурированность, модульность.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Функциональная спецификация состоит из трех частей:

1) описания внешней информационной среды, к которой должны применяться программы разрабатываемой ПС;

2) определение функций ПС, определенных на множестве состояний этой информационной среды (такие функции будем называть внешними функциями ПС);

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

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

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

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

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

 

3. Разработка структуры программы и модульное программирование

 

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

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

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

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

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

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

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

В модульных языках программирования как минимум имеются средства для задания функционально прочных модулей (например, модуль типа FUNCTION в языке ФОРТРАН). Средства же для задания информационно прочных модулей в ранних языках программирования отсутствовали - они появились только в более поздних языках. Так в языке программирования Ада средством задания информационно прочного модуля является пакет.

Сцепление модуля - это мера его зависимости по данным от других модулей. Характеризуется способом передачи данных. Чем слабее сцепление модуля с другими модулями, тем сильнее его независимость от других модулей. Для оценки степени сцепления используется упорядоченный набор из нескольких видов сцепления модулей. Худшим видом сцепления модулей является сцепление по содержимому. Таким является сцепление двух модулей, когда один из них имеет прямые ссылки на содержимое другого модуля (например, на константу, содержащуюся в другом модуле). Такое сцепление модулей недопустимо. Не рекомендуется использовать также сцепление по общей области - это такое сцепление модулей, когда несколько модулей используют одну и ту же область памяти. Такой вид сцепления модулей реализуется, например, при программировании на языке ФОРТРАН с использованием блоков COMMON. Единственным видом сцепления модулей, который рекомендуется для использования современной технологией программирования, является параметрическое сцепление (сцепление по данным) - это случай, когда данные передаются модулю либо при обращении к нему как значения его параметров, либо как результат его обращения к другому модулю для вычисления некоторой функции. Такой вид сцепления модулей реализуется на языках программирования при использовании обращений к процедурам (функциям), т.е. операторов процедур или указателей функций.

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

1) всегда следует использовать рутинный модуль, если это не приводит к плохим (не рекомендуемым) сцеплениям модулей;

2) зависящие от предыстории модули следует использовать только в случае, когда это необходимо для обеспечения параметрического сцепления;

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

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

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

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

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

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

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

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

1) статический контроль,

2) смежный контроль,

3) сквозной контроль.

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

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

Сквозной контроль - это мысленное прокручивание (проверка) структуры программы при выполнении заранее разработанных тестов.

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

 

4. Разработка программного модуля

 

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

1) изучение и проверка спецификации модуля, выбор языка программирования;

2) выбор алгоритма и структуры данных;

3) программирование модуля;

4) шлифовка текста модуля;

5) проверка модуля;

6) компиляция модуля.

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

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

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

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

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

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

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

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

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

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

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

б) раздел (совокупность) описаний на базовом языке, причем вместо описаний процедур и функций - только их внешнее оформление;

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

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

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

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

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

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

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

Ясность текста модуля:

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

2) используйте осмысленные (мнемонические) и устойчиво различимые имена (оптимальная длина имени - 4-12 литер, цифры - в конце), не используйте сходные имена и ключевые слова;

3) соблюдайте осторожность в использовании констант (уникальная константа должна иметь единственное вхождение в текст модуля: при ее объявлении или, в крайнем случае, при инициализации переменной в качестве константы);

4) не бойтесь использовать не обязательные скобки (скобки обходятся дешевле, чем ошибки);

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

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

Эффективность модуля:

1) сначала нужно разработать надежное ПС, а уж потом добиваться требуемой его эффективности в соответствии со спецификацией качества этого ПС;

2) для повышения эффективности ПС используйте, прежде всего, оптимизирующий компилятор - это может обеспечить требуемую эффективность;

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

4) не занимайтесь оптимизацией модуля, если этого не требуется для достижения требуемой эффективности ПС.

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

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

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

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

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

 

5. Тестирование и отладка программного средства

 

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

Отладка = Тестирование + Поиск ошибок + Редактирование

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

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

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

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

Ниже приводятся рекомендации по организации отладки:

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

2. Хорош тот тест, для которого высока вероятность обнаружить ошибку, а не тот, который демонстрирует правильную работу программы.

3. Готовьте тесты, как для правильных, так и для неправильных данных.

4. Избегайте невоспроизводимых тестов, документируйте их пропуск через ЭВМ; детально изучайте результаты каждого теста.

5. Каждый модуль подключайте к программе только один раз; никогда не изменяйте программу, чтобы облегчить ее тестирование.

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

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

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

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

Шаг 3. Убедитесь по тексту модуля, что для каждого цикла существует тест, для которого тело цикла не выполняется, тест, для которого тело цикла выполняется один раз, и тест, для которого тело цикла выполняется максимальное число раз. Добавьте недостающие тесты.

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

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

 

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

 

1.      Что называется программным средством?

2.      Что понимается под надежностью программного средства?

3.      Могут ли в надежном программнос редстве быть ошибки?

4.      Что понимается под технологией программирования?

5.      Что такое система? Какие бывают системы?

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

7.      Что входит в разработку программного средства?

8.      Что понимают под качеством программного средства?

9.      Перечислите критерии качества программного средства.

10. Что понимается под функциональностью (надежностью, легкостью, эффективностью, сопровождаемостью, мобильностью) программного средства?

11. Назовите общие принципы обеспечения надежности программного средства.

12. Какие действия предпринимают для предупреждения ошибок при разработке программных средств?

13. Какие методы используются для борьбы со сложностью программных средств?

14. Как обеспечивается точность перевода документов различными разработчиками программного средства?

15. Что нужно для преодоления барьера между пользователем и разработчиком?

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

17. Что такое примитив качества программного средства?

18. Перечислите примитивы качества программного средства. С какими критериями качества они связаны?

19. Дайте определния используемым примитивам качества программных средств.

20. Из чего сотоит функциональная спецификация?

21. Что таое модульное программирование (программный модуль)?

22. Какие критерии используются для оценки программного модуля?

23. Чем измеряется размер программного модуля?

24. Что такое прочность программного модуля? Приведите примеры различных по степени прочности модулей.

25. Что такое сцепление модуля?

26. Какой вид сцепления прораммных модулей рекомендуется современной технологией программирования?

27. Какой модуль называется рутинным (зависящим от предыстории)?

28. В чем состоит метод восходящей (нисходящей) разработки?

29. Какие методы используются для контроля структуры программы? В чем их суть?

30. Назовите порядок разработки программного модуля. Что делается на каждом шаге разработки?

31. Какое программирование называют структурным?

32. Для чего используется язык псевдокода?

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

34. Перечислите рекомендации по обеспечению ясности текста (эффективности) модуля.

35. Какие методы применяют для контроля программного модуля?

36. Что понимается под отладкой (тестированием) программного средства?

37. Какие виды отладки программных средств приняты в нашей стране?

38. Какие рекомендации по отладке программного средства Вы знаете?

39. Как осуществляется автономное тестирование (тестирование при комплексной отладке)?