Методичка. Учебное пособие В. М. Лопатин издание второе, стереотипное 1 17
 Скачать 4.33 Mb.
|
|
Системы и технологии программирования История развития технологий программирования В истории развития языков программирования выделяется несколько этапов [12]. Этап 1 (от появления первых ЭВМ до середины 1960-х) характеризуется пол- ным отсутствием правил программирования. Первые программы имели простую структуру и были написаны на машинном языке (в двоичном коде). Перед програм- мистом возникали большие сложности по формированию двоичных кодов и отсле- живанию порядка выполняемых операций. Дополнительная трудность была свя- зана с определением местонахождения данных. Для упрощения процесса програм- мирования отдельные группы кода были заменены на символические имена, так появился первый язык программирования, который назвали Ассемблер (от англ. assembler– сборщик). Ассемблер относится к машинно-ориентированным языкам низкого уровня и отличается привязкой к системе команд конкретного процессора. Дальнейшее снижение трудоемкости процесса программирования произошло после появления языков высокого уровня, первыми из которых были языки Fortran и Algol. Языки высокого уровня были построены на основе алгоритмиче- ских конструкций, которые удобны для записи, более универсальны и не связаны с системой команд конкретного процессора. Все это снизило уровень детализа- ции и повысило сложность разрабатываемых программ. В языках высокого уровня появилось средство, которое позволяло опериро- вать подпрограммами. Подпрограммы можно было сохранять и использовать при создании других программ. Для поддержки этой технологии были созданы биб- лиотеки расчетных и служебных подпрограмм. Типичная программа того времени состояла из основной программы с набором глобальных данных и ряда подклю- ченных к ней библиотечных подпрограмм. Первоначально все глобальные данные собирались в основной программе, но со временем стало ясно, что более удачным решением будет введение локальных данных для каждой подпрограммы. При использовании подпрограмм разработка велась по принципу «снизу – вверх», т. е. сначала проектировали подпрограммы, а потом их использовали для создания сложной программы. Недостатки этого подхода проявлялись в сложно- сти стыковки созданных подпрограмм и в значительном затягивании работ по реализации больших проектов. Этап 2 (1960–1970-е гг.) связан с появлением структурного подхода к программированию. В основе структурного подхода лежит разбиение сложных программ на части (декомпозиция) и реализация отдельных частей в виде под- программ. При этом процесс проектирования строился под общей идеей и фор- мировался по принципу «сверху – вниз». Структурный подход позволял предста- вить решаемую задачу в виде иерархии подчиненных задач. Одновременно с этим вводились формальные модели алгоритмов, правила описания алгоритмов, а также метод пошаговой детализации алгоритмов. Принципы структурного программирования были реализованы при создании процедурных языков программирования, например языка Pascal. В таких языках 11 / 17 80 появились операторы, которые обеспечивали перемещение по структуре, в част- ности, оператор передачи управления. В результате развития структурного программирования появилась техноло- гия модульного программирования. Архитектура модульного программиро- вания предполагает создание в составе программы модулей, состоящих из групп подпрограмм, использующих одни и те же глобальные данные. Этот подход поз- волил упростить процесс программирования, поскольку позволял каждому из программистов разрабатывать свои модули независимо от других. Сочетание структурного подхода с модульным программированием позволило получать до- статочно сложные и надежные программы. Но при значительном увеличении числа проектируемых модулей появлялись ошибки, связанные с функциониро- ванием межмодульного интерфейса. Для разработки программного обеспечения с большим числом модулей потребовалось сделать переход к третьему этапу раз- вития программного обеспечения. Этап 3 (середина 1980-х – конец 1990-х) характеризуется появлением объ- ектно-ориентированного программирования. Технология объектно-ори- ентированного программирования основана на представлении программы в виде совокупности объектов, каждый из которых является экземпляром определен- ного класса, а классы в свою очередь образуют иерархическую структуру с воз- можностью наследования свойств объектов. При этом взаимодействие между объектами основано на передаче сообщений. Выбранный подход обеспечил более полную декомпозицию программного обеспечения и существенно упростил работу, поскольку позволил практически независимо вести разработку отдельных подпрограмм. Дополнительное упроще- ние было достигнуто путем введения новых способов организации программ, ос- нованных на механизмах наследования, полиморфизма, композиции и наполнения, которые позволили конструировать сложные объекты из сравнительно простых. В рамках этого подхода был разработан графический интерфейс используемых средств, с помощью которого была реализована технология визуального програм- мирования, в частности, в системах Delphi, Visual C++. Привлечение визуальных средств позволило по упрощенной схеме создавать заготовку будущей программы, что привело к дополнительному уменьшению трудоемкости проектирования. Основные недостатки объектного подхода связаны со сложностью компиля- ции (перевод в двоичные коды) созданных объектов и последующей компоновки компилированных блоков-модулей в единое целое. Проблема компоновки в свою очередь связана с недостаточно отработанным механизмом обмена дан- ными между модулями. Этап 4 (с середины 1990-х до нашего времени) связан с переходом на ком- понентный подход и возникновением CASE-технологий. Основу компо- нентного подхода составляет построение программного обеспечения из от- дельно существующих частей, взаимодействие между которыми организовано на основе двоичных интерфейсов стандартного типа. Понятие объектов при этом трансформируется в объект-компоненты, которые сохраняются в двоичном коде и могут использоваться в языках программирования, которые поддержи- 12 / 17 81 вают эту технологию. Сформированный подход позволяет собирать библиотеки разработанных компонентов и использовать наработанные результаты при раз- работке новых продуктов. На сегодняшний день местом сбора компонентов яв- ляются серверы сети Интернет. Компонентный подход лежит в основе двух типов технологий, первая из ко- торых разработана на базе компонентной модели объекта COM (Component Ob- ject Model), а вторая связана с созданием распределенных приложений CORBA (Common Object Request Broker Architeture – общая архитектура с посредником обработки запросов объектов). В этих технологиях используются общие прин- ципы компонентного подхода и различаются некоторые детали реализации. Современный этап развития программирования характеризуется активным привлечением средств автоматизации разработки, без которых трудно со- здавать сложное программное обеспечение. Комплекс автоматизированных тех- нологий, которые обеспечивают разработку и сопровождение программного обеспечения, называют CASE-технологиями (Computer-Aided Software/Sys- tem Engineering – разработка программного обеспечения программных систем с использованием компьютерной поддержки). Областью применения CASE- технологий в первую очередь являются программы высокой сложности, при раз- работке которых программисты не могут фиксировать все особенности создава- емого продукта и вынуждены использовать средства автоматизации. Этапы решения задач на программной основе Решение сложной задачи с использованием компьютерных программ предпо- лагает выполнение определенного круга действий. Эти действия можно разло- жить на этапы. Этап 1.Определение цели и постановка задачи. На первом этапе определяется основная цель предстоящей работы и переченьзадач, которые необходимо решить для достижения поставленной цели. Здесь же формируются известные исходные данные, а также определяется формат и способ представления конечныхданных. Если работа укладывается в рамки технического проекта, то постановка за- дачи формулируется в специальном документе, который называется техниче- ским заданием. Правильная постановка задачи позволяет последовательно выполнить все по- следующие этапы. Напротив, допущенные ошибки могут привести к тяжелым последствиям с повторным выполнением всей работы. Этап 2.Моделирование. Этап выполняется при условии, когда прямое реше- ние задачи невозможно из-за отсутствия реального объекта или по причине эко- номической нецелесообразности известных подходов. В этом случае реальный объект заменяется формальным описанием или моделью, которая сохраняет лишь некоторые свойства реального объекта. Например, для сбора данных о со- стоянии здоровья населения целесообразно от изучения каждого человека пе- рейти к обработке медицинских карт. Этап завершается описанием выбранной модели и перечнем свойств модели, которые необходимо учитывать в процессе решения задачи. 13 / 17 82 Этап 3. Построение алгоритма. На этом этапе выстраивается логическая по- следовательность действий, направленных на решение конкретных задач. После- довательность действий выстраивается в форме алгоритма, который задает неко- торый набор предписаний и правил, определяющих процесс преобразования ис- ходных данных в результат решения задачи. Сложные алгоритмы строят на основе модельных представлений, заложен- ных на предыдущем этапе. Этап 4. Разработка программы. Полученный алгоритм используется для разра- ботки программы, которая позволяет передать дальнейшее решение задачи от чело- века к машине. Запись программы производится на языке программирования. Этап завершается созданием текста программы, которая передается на этап трансляции. Этап 5. Трансляция программы. Текст созданной программы подвергается автоматическому преобразованию использованных в программе переменных и операций в машинные команды. Перевод программы на машинный язык осу- ществляется с помощью транслятора, который привязан к конкретному языку программирования. При трансляции программы исходными данными является текст программы, а результатом – запись программы на машинном языке. Для каждого языка программирования существуют свои программы-трансляторы. Этап 6. Отладка программы. Цель отладки заключается в выявлении и устранении ошибок, допущенных на предыдущих этапах. Суть отладки сводится к тестированию, которое включает стадии альфа-тестирования (с использова- нием тестов разработчика) и бета-тестирования (в реальных условиях эксплу- атации). При возникновении сложностей отладка по длительности процесса мо- жет значительно превышать этап разработки программы. Этап 7. Эксплуатация программы. Этап включает доработку программы по предложениям заказчика, установку программы на аппаратную базу заказчика, обучение пользователей программы, разработку эксплуатационной документа- ции. Для отдельных программ, требующих постоянного контроля и обновления, этап эксплуатации по длительности приближается к продолжительности жизнен- ного цикла созданной программы. Моделирование как процесс упрощения задачи Моделирование относится к одному из начальных этапов работы по созданию компьютерной программы. Моделирование – это процесс построения модели в целях упрощения за- дачи и последующего изучения оригинала на основе построенной модели. Модель – материальный или мысленно представляемый объект (процесс, яв- ление), который в процессе исследования замещает оригинал и сохраняет при этом важные свойства оригинала. Классическим примером модели является географиче- ский глобус, который замещает оригинал, планету Земля, сохраняя ее форму. Замена оригинала моделью может быть вызвана разными причинами, в частности: − из-за отсутствия или недоступности оригинала; − в связи с возможным разрушением оригинала в процессе исследования; − по причине высокой стоимости процесса исследования. 14 / 17 83 Модель отличается от оригинала, поэтому содержит не все, а только суще- ственные сведения об объекте.Эти сведения выбираются с учетом цели, для до- стижения которой модель создана. Модель всегда связана с определенным набо- ром упрощений. Если модель при наличии всех упрощений дает удовлетвори- тельные результаты, то говорят, что модель адекватна рассматриваемому объ- екту (процессу или явлению). Для создания моделей используют следующие методы. 1. Предметное моделированиезаключается в созданииматериальной мо- дели, имеющей некоторые свойства оригинала (модели самолетов, кораблей, ав- томобилей). 2. Физическое моделирование выражается в экспериментальном исследо- вании модели, имеющей общие свойства с оригиналом (изучение молнии как электрического разряда между проводниками). 3. Аналоговое моделирование основано на аналогии (изоморфизме) различ- ных явлений, для которых можно использовать одинаковое описание (форма са- молета и летящей птицы). 4. Знаковое моделированиеиспользует для построения модели в форме схемы, графика, чертежа или других знаковых систем (периодическая таблица Д. И. Менделеева). 5. Мысленное моделирование – разновидность знакового моделирования, при котором реальное построение заменяется мысленным представлением зна- ков или операций над ними (игра в шахматы вслепую). Большое разнообразие моделей позволяет проводить их классификацию по раз- ным признакам. В частности, в классификации по форме представления выделяют: − материальные (предметные) – модели, которые воспроизводятся в форме реального объекта и используются в экспериментальных методиках познания окружающей среды; к ним относятся игрушки для детей, учебные пособия, экс- периментальные исследовательские установки; − информационные (теоретические) – модели, которые заменяют реальные данные об объекте формальным описанием, например компьютерной программой. Информационная модель– совокупность формальных данных, которая характеризует существенные свойства объекта и характер его взаимосвязей с внешней средой (электронная карта местности характеризует только состояние земной поверхности). Множество существующих информационных моделей может быть классифи- цировано по видам моделей: − вербальные – модели, выраженные с помощью естественных языков в ре- чевой или текстовой форме, например текст компьютерной программы; − абстрактные, или мысленные, – модели, которые используют не суще- ствующие в жизни понятия, такие как абсолютно черное тело или идеальный газ; − знаковые – модели, которые основаны на записи специальных символов, связанных с системой представления данных в изучаемой области знаний, например запись музыкального произведения с помощью нот на нотном стане; 15 / 17 84 − графические – модели, основанные на представлении объекта в виде схемы, графика, диаграммы, карты, чертежа, таблицы, диаграммы и т. п. По способу организации данных выделяются информационные модели: − табличные – модели, в которых данные оформляются в виде пересекаю- щихся строк и столбцов (электронные таблицы); − иерархические – модели с распределением объектов по разным уровням, сгруппированным в форме дерева (файловая структура); − сетевые – модели, в которых объекты взаимодействуют между собой че- рез множество связей (локальная компьютерная сеть); сетевые модели можно представлять в форме графа – математического объекта, состоящего из конеч- ного множества вершин или узлов, связанных между собой ребрами или дугами. Моделирование может выступать в качестве отдельного этапа работы в про- цессе создания компьютерной программы или служить средством для получения основного результата. Во втором случае в качестве основной цели выбирается разработка компьютерной модели и проведение на базе созданной модели иссле- довательской работы, которую невозможно провести с реальным объектом. Раз- работка и исследование такой модели выполняется на компьютере, а сама модель в этом случае называется имитационной моделью. Имитационное моделирование – это процесс создания модели реальной системы и постановки компьютерного эксперимента на этой модели для изуче- ния и прогнозирования ее поведения в целях улучшения характеристик рассмат- риваемой системы [13]. Имитационное моделирование применяется к исследованию сложных моде- лей, которые невозможно построить другими способами. При этом создание мо- дели в виде компьютерной системы и проведение исследований на компьютере является обязательным условием. Необходимость в проведении имитационного моделирования возникает в случаях, когда известные подходы не позволяют решить поставленную задачу: − не существуют аналитические методы решения созданных математиче- ских моделей или эти методы связаны с высокой трудоемкостью; − реальные условия, в которых находится объект исследования, трудно или невозможно обеспечить; − нет физической возможности для отслеживания параметров процесса, например, в случае быстропротекающих или опасных процессов. Имитационное моделирование целесообразно применять при решении чис- ленных задач в области математики и естественных наук или при решении задач организационного управления в разных сферах деятельности, например при про- ектировании производственных систем. Возможной областью применения ими- тационного моделирования является сфера образования, науки и профессио- нальной подготовки. Замена реального эксперимента на исследование модели за- частую дает более глубокие и порой неожиданные результаты. Сфера применения имитационных моделей ограничена существующими не- достатками: 16 / 17 85 − на решение задачи требуется много времени, необходимо также привлече- ние высококвалифицированных специалистов; − полученные результаты выражаются только в численном виде; − возникают трудности с получением исходных данных, необходимых для формирования модели. Алгоритм и его основные свойства Построение алгоритма относится к этапу работ, предшествующему разра- ботке программы. Понятие «алгоритм» связано, как правило, с решением сложных задач, требу- ющих привлечения вычислительной техники. Вместе с тем это понятие можно ис- пользовать и при описании простых операций и решений. Примеры простых ре- шений, в которых используются алгоритмические подходы: рецепты кулинарной книги, порядок автоматической стирки белья, кипячение воды в чайнике. Простые подходы связаны с произвольным толкованием последовательности и содержания действий, в вычислительной технике последовательность дей- ствий тесно привязана к исполнителю алгоритма и перечню операций, которые может выполнять исполнитель. Алгоритм – определенная последовательность действий, которая описывает порядок перехода объекта из начального состояния в конечный результат с ис- пользованием понятной исполнителю системы команд. Из определения следует, что алгоритм можно представить как некоторую со- вокупность предписаний, которая выбирается из набора правил и инструкций конкретного исполнителя и позволяет решать задачу из некоторого класса одно- типных задач. Различают процессы создания и реализации алгоритмов. Создание алгоритма – творческий процесс, выполняемый специалистом в области разработки алгоритмов. Реализация– процесс выполнения предписанных команд формальным ис- полнителем, к которым в первую очередь относятся различные автоматические устройства, в том числе вычислительная техника. Формальный исполнитель не вникает в смысл того, что он делает, но получает при этом необходимый результат. Строгое выполнение последовательности опера- ций с отвлечением исполнителя от содержания поставленной задачи выражается в особенности, которая называется формальностью алгоритма. Наряду с фор- мальностью алгоритм характеризуется и другими определенными свойствами. 1. Дискретность. Одно из свойств алгоритма, которое выражается в разбие- нии описываемого процесса на последовательность отдельных шагов или команд. Совокупность отдельных шагов образует дискретную структуру алгоритма. 2. Понятность. Для создания алгоритма могут быть использованы только те команды, которые исполнитель понимает и может выполнить. Другими словами, алгоритм должен состоять из команд, которые имеются в системе команд испол- нителя. 17 / 17 86 3. Определенность,или детерминированность. При разработке алго- ритма не могут быть использованы команды, смысл которых воспринимается ис- полнителем неоднозначно. Иначе говоря, алгоритм не должен оставлять места для произвола исполнителя. 4. Результативность. Процесс, описываемый алгоритмом, должен прекра- титься за конечное число шагов с получением определенного результата. 5. Массовость. Чаще всего алгоритмы обеспечивают решение не одной кон- кретной задачи, а некоторого класса задач данного типа. Это свойство позволяет выделять область применимости алгоритма. Каждый алгоритм формируется из некоторого определенного набора типо- вых действий. Набор этих действий получается довольно наглядным в случае графического описания алгоритма, которое основано на представлении каждого действия в виде геометрической фигуры (блока). Графическое описание позво- ляет представлять алгоритм как систему связанных между собой функциональ- ных блоков.Примеры графического изображения блоков, из которых складыва- ется описание алгоритма, представлены в табл. 28. Таблица 28 Графическая запись алгоритмических действий Наименование действия Обозначение Функция Пуск – останов начало или конец дей- ствия Ввод – вывод ввод или вывод данных Процесс (действие) вычислительное дей- ствие Условие (ветвление) проверка условия и вы- бор направления Предопределенный про- цесс расчет по подпрограмме Модификация начало цикла Документ вывод на печать Графическое представление алгоритма называют блок-схемой алгоритма. 1 / 15 87 Блок-схема состоит из связанных между собой блоков, которые располага- ются сверху вниз и соединяются между собой стрелками перехода. Взаимное расположение блоков показывает очередность выполнения процесса, а стрелки – направление вычислительного процесса. Внутри каждого блока вводится надпись, которая уточняет функцию блока или описывает математическое дей- ствие. Алгоритмы в зависимости от цели, начальных условий, путей решения за- дачи, последовательности действий исполнителя подразделяются на разные типы. К основным наиболее часто используемым типам относятся линейные и циклические алгоритмы. Блок-схемы основных типов алгоритмов представлены в табл. 29. Кроме этого выделяют и другие типы, механические или жесткие ал- горитмы, которые описывают работу механизмов, например двигателя внутрен- него сгорания. Таблица 29 Разновидности алгоритмов Тип алгоритма Блок-схема Линейныеалгоритмы состоят из набора команд, которые выполняют последовательно друг за другом Циклическиеалгоритмы связаны с многократным заранее определенным количеством повторяемых действий и обновлением расчетных данных на каждом действии Циклические с предусловиемалго- ритмы содержат предварительную проверку возможности выполнения цикла 2 / 15 88 Продолжение табл. 29 Тип алгоритма Блок-схема Циклические с постусловиемалго- ритмы основаны на проверке резуль- татов циклических вычислений и остановке цикла после выполнения постусловия Приведенные в табл. 29 блок-схемы могут использоваться для построения различных алгоритмических конструкций. На рис. 25 в качестве примера пока- зана схема алгоритма для расчета значения функции f(n) = 3 n при n = 5. Рис. 25. Циклический алгоритм с предусловием Наряду с графическим представлением существуют и другие формы записи алгоритмов. Для сравнения разных подходов рассмотрим пример составления алгоритма в разных формах записи. Пример. Составим алгоритм начисления заработной платы, используя следу- ющие правила: − если стаж работы менее 1 года, то заработная плата равна А; − при стаже от 1 до 3 лет – заработная плата возрастает в два раза; − более 3 лет – каждый год идет повышение на величину В. Введем обозначения: заработная плата – ZP, стаж работы – ST; запишем ма- тематическую формулировку задачи: 3 / 15 89 = 2 ∙ 2 ∙ + ( − 3) ∙ < 1 1 ≤ ≤ 3 > 3 1. Словесно-формульное описаниеосновано на представлении алго- ритма в форме последовательности слов, предложений и формул с использова- нием естественного языка. Решение задачи с использованием этого описания складывается следующим образом. 1) Ввести ST, перейти к п. 2. 2) Если ST<1, то ZP=А, перейти к п. 4, иначе перейти к п. 3. 3) Если ST<=3, то ZP=2*А, иначе ZP=2*А+(ST-3)*В, перейти к п. 4. 4) Вывести (на печать) значение ZP. 5) Вычисления прекратить. Распространение словесно-формульного описания на практике ограничива- ется отсутствием строгой формализации, наличием многословности, а также неоднозначностью толкования отдельных действий алгоритма. 2. Графическое представлениеэтого же алгоритмана основе структурной блок-схемы показано на рис. 26. Графический подход отличается простотой и наглядностью, дает хорошие ре- зультаты при решении относительно небольших задач, но занимает значительно больше места. Объемная задача раздвигает границы блок-схемы до такой сте- пени, что ее визуальное восприятие становится трудным или невозможным. По этой причине использование графического подхода при всех его преимуществах ограничено относительно небольшими программами. 3. Описаниенаосновепсевдокодоввыражается в полуформализованном представлении алгоритмов на условном алгоритмическом языке, который содержит элементы языка программирования, фразы естественного языка, общепринятые ма- тематические обозначения. Сочетание естественного языка с математической запи- сью и общепринятыми служебными словами выводит псевдокодна промежуточное место между естественным и формальным языками. Запись алгоритма для начисле- ния заработной платы на псевдокоде производится следующим образом: алг Зарплата (цел ST, вещ ZP) арг ST, рез ZP нач если ST<1 то ZP = А иначе если ST<=3 то ZP=2*А иначе ZP= 2*А+(ST-3)*В все все кон. 4 / 15 |