1. Понятие алгоритма и программы. Свойства алгоритма.

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

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

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

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

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

1. Детерминированность (формальность): предписание должно однозначно (не путать со словом понятно) описывать порядок действий, сами действия и объекты действий. Инструкции (команды) не должны оставлять места для произвола (произвольного толкования) исполнителя.

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

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

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

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

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

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

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

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

Свойство массовости означает возможность применения предписания ко всем объектам из области применимости (ее еще надо суметь определить).

Пример :

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

= x*x*x*...*x= - эта формула (в цикле вычисляется) верна лишь, когда n>0

- эта формула верна лишь, когда a>0 и x>0.

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

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

1 шаг 2 шаг n-й шаг

. . .

время выполнения предписания

Объясняется дискретность следующими моментами:

а) последовательным характером работы исполнителя;

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

Пример:

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

S₁=x₁

S₂=S₁+x₂

S₃=S₂+x₃ порядок выполнения

S₄=S₃+x₄

...............

S_n=S_n-1+x_n

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

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

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

2. Критерии оценки качества программ (программных проодуктов)

Программа в настоящее время рассматривается как некоторый продукт деятельности по её разработке. Появился даже термин «программный продукт». Решение одной и той же инженерной задачи может обеспечиваться выполнением различных программ (для решения одной задачи может существовать несколько методов, а каждый метод может быть реализован несколькими алгоритмами). При этом возникает проблема выбора одной программы (лучшей) из нескольких. Эту проблему решают на основе оценки качества программ. Существует довольно большое число таких критериев [Бутаков Е.А. Методы создания качественного ПО ЭВМ. М.: Энергоиздат. – 1984, с. 6-45], но мы рассмотрим лишь некоторые из них. К сожалению эти характеристики часто трудно формально определить, поэтому их вводят в форме "имеющая данное свойство программа должна быть такой-то".

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

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

на Паскале на Си

S := 0; for (s=0, i=1;i<=10;s+=a[i++]);

for i := 1 to 10 do

begin

{

s := s + a[i];

}

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

- программа (и подпрограммы) должна занимать не более 1 листа;

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

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

• использование осмысленного набора имен а) имена должны соответствовать решаемой задаче (надо избегать конструкций типа z := x*(1-0.13)-y, где неизвестно, что такое z, x, y. В то же время формула зарплата=начислено*(1-0.13) – аванс понятна всем или почти всем); б)надо использовать длинные имена;

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

• использование стиля программирования:

- использование отступов для отображения подчиненности (иерархии) элементов программы (при этом элементы одного и того же уровня иерархии должны иметь один и тот же размер отступа);

- запись операторных скобок на отдельных строках программы

for i:=1 to 10 do

begin

…….

end;

- использование пробелов (отступов) для лучшего (более наглядного) отделения элементов операторов друг от друга

Var

a : char ;

begin

c := a + b;

end;

• использование пустых строк для отделения (выделения) участков программы друг от друга

Участок1

Пусто

Участок2

Пусто

Участок3

Замечание:

Часто понятность программы достигается за счет снижения ее эффективности (на языке Си программы менее понятны, но более эффективны, чем на Паскале).

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

• требуемое машинное время (чистое время процесса и время оператора ЭВМ)

• требуемая оперативная память;

• требуемая память на магнитных дисках;

• количество типов и единиц используемых программой внешних устройств (внешние по отношению к системному блоку);

• интенсивность использования устройств и т.п.

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

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

3. Надежность : обычно считается, что надежная программа - это та, которая работает без ошибок.

Существует две стороны надежности:

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

Работа

Состояния сбой из-за ошибок

системы отказ

(программы)

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

Отказ – устойчивая длительная потеря программой работоспособности.

б) Надежность как качество (см. Лебланк «Защищенный код», 2004 и 2008 г.г.): когда мы говорим о надежности ПО, то подразумеваем отсутствие ошибок в программе. Однако поскольку ошибки неизбежны, то надежная программа д.б. организованна так, чтобы возможные ошибки не вели к фатальным последствиям (отказам) и могли быть быстро исправлены (программистом или пользователем – если ошибки в данных). То есть надежной программой считается та, которая даже при наличие ошибок не завершается аварийно. Для этого в программе должна быть предусмотрена обработка ошибок (исключительных ситуаций). Ошибки в общем случае делятся на :

1. ошибки внешние по отношению к программе:

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

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

2. ошибки в самой программе, точнее в голове ее разработчика (внутренние) :

• ошибки в постановке,

• ошибки в проектировании

• ошибки в кодировании

• ошибки в записи на внешний носитель.

Выводы:

1. внутренние ошибки (в голове) желательно не делать.

2. при их (внутренних ошибках) обнаружении (при тестировании) правильное выполнение программы возможно лишь после их полного исправления.

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

4.Удобство сопровождения -

Этапы жизненного цикла ПО после завершения его разработки :

эксплуатация оператор (пользователь)

разработка сопровождение программист

испытания заказчик

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

- исправление найденных при эксплуатации ошибок;

- адаптация ПО к новым условиям (новая ОС, новое оборудование и т.п.);

- повышение скорости работы ПО (если замечено, что оно работает слишком медленно).

Удобнее всего сопровождать ту программу, которая:

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

б) понятна программисту.

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