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

⇐ ПредыдущаяСтр 2 из 6Следующая ⇒

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

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], но мы рассмотрим лишь некоторые из них. К сожалению эти характеристики часто трудно формально определить, поэтому их вводят в форме " имеющая данное свойство программа должна быть такой-то".

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

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

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

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;

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

Участок₁

Пусто

Участок₂

Пусто

Участок₃

Замечание:

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

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

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

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

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

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

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

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

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

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

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

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

Работа

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

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

(программы)

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

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

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

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

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

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

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

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

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

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

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

Выводы:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Этапы разработки программы

Как осуществляется программирование, какие процессы происходят при этом?

Решение любой сложной задачи состоит из четырех этапов:

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

2) Разработка плана, в котором раскрывается стратегия решения (стратегия достижения цели);

3) Выполнение (реализация) плана. При этом любой сложный план преобразуется в определенную последовательность достаточно простых (по сравнению с исходной задачей) действий;

4) Проверка правильности решения;

5) Документирование;

6) Сдача решения потребителю.

Эти этапы применительно к программированию называют соответственно так:

1) определение требований к ПО и целей проектирования ПО (постановка задачи, ее формализация и разработка ТЗ);

2) проектирование ПО (разработка метода решения, структуры программы и алгоритмов);

3) кодирование (написанием собственно программы на выбранном языке программирования) и отладка программы;

4) тестирование программы, в том числе и на стороне Заказчика (по ПМИ);

5) выпуск документации (руководство программиста, руководство системного программиста и т.п.);

6) выпуск программного продукта для передачи потребителю (Заказчику).

По ГОСТ 19.102-77 «Стадии разработки» определены следующие этапы разработки ПО:

1) разработка ТЗ (ему соответствует названный выше этап «Постановка задачи и ее формализация»)

2) разработка ЭП (им соответствует названный выше этап «разработка метода решения,

3) разработка ТП структуры программы и алгоритмов»)

4) разработка РП (он включает названные выше этапы «Кодирование и отладка», «Тестирование» и «Документирование».

5) внедрение (ему соответствует названный выше этап «Выпуск программного продукта для передачи потребителю (Заказчику)»).

Более подробно о некоторых этапах (или подэтапах) разработки ПО.

Постановка задачи

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

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

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

- выбираются, согласовываются и фиксируются ограничения (на исходные данные и метод решения).

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

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

- теория графов;

- теория вероятностей;

- теория массового обслуживания;

- теория множеств

- и т.д.

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

Хорошая математическая постановка задачи часто позволяет сразу увидеть способ решения.

Поиск метода решения задачи (на этапе проектирования)

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

- те, которые уже ранее встречались, и решение их уже известно;

- те, для которых известна постановка, и решение их не представляет (для программиста) труда.

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

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

Замечание: Кроме названных двух подходов к разработке алгоритмов (программ) обычно выделяют следующие методологии (парадигмы) программирования:

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

- объектно-ориентированная (по сути тоже восходящий подход, но не процедурный);

- логическая (логико-ориентированная);

- функциональная.

Мы об этих парадигмах поговорим чуть позже.

Кодирование проходит обычно следующие шаги:

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

2).Подготовка программы для ПЭВМ, т.е. перенос рукописного текста программы с бумаги на машинный носитель информации. Для этого используется текстовый редактор.

3). Компиляция текста программы в машинный код с помощью программы, называемой компилятором.

Машинный код

(понятен ЭВМ)

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

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

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

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

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

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

Замечание: компилятор Турбо-Паскаля (и Free Pascal) производит компиляцию сразу в исполняемый код (отдельный этап линковки не требуется).

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

Отладка и Тестирование: После получения готового к выполнению кода программы начинается этап ее отладки и тестирования - поиск ошибок в программе (debugging), например, ошибок при работе с данными, логических ошибок и т.п.

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

Различают методы тестирования: а) белого ящика (структурное тестирование) и б) черного ящика (функциональное тестирование - может начинаться сразу после получения ТЗ).

Различают виды тестирования: а) альфа-тестирование (проводит сам программист) б) бета-тестирование (проводится у Заказчика или потенциального Потребителя).

По завершении (успешном) тестирования программа готова к передаче ее заказчику.

Замечание:

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

4. Средства записи и классификация алгоритмов.

⇐ Предыдущая 123 4 5 6 Следующая ⇒