Тема 13. Постановка задачи и спецификация программы
Одним из наиболее важных шагов программирования является постановка задачи. Она выполняет функции контракта между пользователем и программистом (программистами). Как и юридически плохо составленный контракт, плохая постановка задачи бесполезна.
При хорошей постановке задачи как пользователь, так и программист ясно и недвусмысленно представляют задачу, которую необходимо выполнить, т.е. в этом случае учитываются интересы как пользователя, так и программиста. Пользователь может планировать использование еще несозданного программного обеспечения, опираясь на знание того, что оно может. Хорошая постановка задачи служит основой для формирования ее решения.
Постановка задачи (спецификация программы); по существу, означает точное, полное и понятное описание того, что происходит при выполнении конкретной программы. Пользователь обычно смотрит на компьютер, как на черный ящик: для него неважно, как работает компьютер, а важно, что может компьютер из того, что интересует пользователя. При этом основное внимание фокусируется на взаимодействии человека с машиной.
Первый СОЛЬНЫЙ полёт в США!
Характеристики Хорошей Постановки Задачи:
Точность, т.е. исключение любой неоднозначности. Не должно возникать вопросов относительно того, каким будет вывод программы при каждом конкретном вводе.
Полнота, т.е. рассмотрение всех вариантов для заданного ввода, включая ошибочный или непредусмотренный ввод, и определение соответствующего вывода.
Ясность, т.е. она должна быть понятной и пользователю и системному аналитику, поскольку постановка задачи – это единственный контракт между ними.
Часто требование точности, полноты и ясности находятся в противоречии. Так, многие юридические документы трудно понять, потому что они написаны на формальном языке, который позволяет предельно точно сформулировать те или иные положения, исключая любые самые незначительные разночтения. Например, некоторые вопросы в экзаменационных билетах иногда сформулированы настолько точно, что студент тратит больше времени на то, чтобы понять вопрос, чем на то чтобы на него ответить. Более того, студент вообще может не уловить основной смысл вопроса из-за большого количества деталей. Наилучшая постановка задачи та, при которой достигается баланс всех трех требований.
Стандартная форма постановки задачи.
Рассмотрим следующую постановку задачи: «Ввести три числа и вывести числа в порядке».
Такая постановка не удовлетворяет приведенным выше требованиям: она не является ни точной, ни полной, ни понятной. Действительно, должны ли числа вводиться по одному на строке или все числа на одной строке? Означает ли выражение «в порядке» упорядочение от большего к меньшему, от меньшего к большему или тот же порядок, в каком они были введены.
Очевидно, что подобная постановка не отвечает на множество вопросов. Если же учесть ответы на все вопросы, то постановка задачи станет многословной и трудной для восприятия. Поэтому Д. Райли предлагает для постановки задачи пользоваться стандартной формой, которая обеспечивает максимальную точность, полноту, ясность и включает:
Квесты в Zunal
наименование задачи (схематическое определение);
общее описание (краткое изложение задачи);
ак уже отмечалось выше, в качестве модульной структуры программы принято использовать древовидную структуру, включая деревья со сросшимися ветвями. В узлах такого дерева размещаются программные модули, а направленные дуги (стрелки) показывают статическую подчиненность модулей, т.е. каждая дуга показывает, что в тексте модуля, из которого она исходит, имеется ссылка на модуль, в который она входит.
Другими словами, каждый модуль может обращаться к подчиненным ему модулям, т.е. выражается через эти модули. При этом модульная структура программы, в конечном счете, должна включать и совокупность спецификаций модулей, образующих эту программу. Спецификация программного модуля содержит, во-первых, синтаксическую спецификацию его входов, позволяющую построить на используемом языке программирования синтаксически правильное обращение к нему (к любому его входу), и, во-вторых, функциональную спецификацию модуля (описание семантики функций, выполняемых этим модулем по каждому из его входов). Функциональная спецификация модуля строится так же, как и функциональная спецификация ПС.
В процессе разработки программы её модульная структура может по-разному формироваться и использоваться для определения порядка программирования и отладки модулей, указанных в этой структуре. Поэтому можно говорить о разных методах разработки структуры программы. Обычно в литературе обсуждаются два метода : метод восходящей разработки и метод нисходящей разработки.
Метод восходящей разработки заключается в следующем. Сначала строится модульная структура программы в виде дерева.
Затем поочередно программируются модули программы, начиная с модулей самого нижнего уровня (листья дерева модульной структуры программы), в таком порядке, чтобы для каждого программируемого модуля были уже запрограммированы все модули, к которым он может обращаться. После того, как все модули программы запрограммированы, производится их поочередное тестирование и отладка в принципе в таком же (восходящем) порядке, в каком велось их программирование.
На первый взгляд такой порядок разработки программы кажется вполне естественным: каждый модуль при программировании выражается через уже запрограммированные непосредственно подчиненные модули, а при тестировании использует уже отлаженные модули. Однако, современная технология не рекомендует такой порядок разработки программы.
Во-первых, для программирования какого-либо модуля совсем не требуется текстов используемых им модулей — для этого достаточно, чтобы каждый используемый модуль был лишь специфицирован (в объёме, позволяющем построить правильное обращение к нему), а для тестирования его возможно (и даже, как мы покажем ниже, полезно) используемые модули заменять их имитаторами (заглушками). Во-вторых, каждая программа в какой-то степени подчиняется некоторым внутренним для нее, но глобальным для ее модулей соображениям (принципам реализации, предположениям, структурам данных и т.п.), что определяет её концептуальную целостность и формируется в процессе ее разработки. При восходящей разработке эта глобальная информация для модулей нижних уровней ещё не ясна в полном объеме, поэтому очень часто приходится их перепрограммировать, когда при программировании других модулей производится существенное уточнение этой глобальной информации (например, изменяется глобальная структура данных). В-третьих, при восходящем тестировании для каждого модуля (кроме головного) приходится создавать ведущую программу (модуль), которая должна подготовить для тестируемого модуля необходимое состояние информационной среды и произвести требуемое обращение к нему. Это приводит к большому объему «отладочного» программирования и в то же время не дает никакой гарантии, что тестирование модулей производилось именно в тех условиях, в которых они будут выполняться в рабочей программе.
Метод нисходящей разработки заключается в следующем. Как и в предыдущем методе сначала строится модульная структура программы в виде дерева.
Затем поочередно программируются модули программы, начиная с модуля самого верхнего уровня (головного), переходя к программированию какого-либо другого модуля только в том случае, если уже запрограммирован модуль, который к нему обращается. После того, как все модули программы запрограммированы, производится их поочередное тестирование и отладка в таком же (нисходящем) порядке.
При таком порядке разработки программы вся необходимая глобальная информация формируется своевременно, т.е. ликвидируется весьма неприятный источник просчетов при программировании модулей. Существенно облегчается и тестирование модулей, производимое при нисходящем тестировании программы.
Первым тестируется головной модуль программы, который представляет всю тестируемую программу и поэтому тестируется при «естественном» состоянии информационной среды, при котором начинает выполняться эта программа. При этом все модули, к которым может обращаться головной модуль, заменяются их имитаторами (так называемые заглушки [5]).
Каждый имитатор модуля представляется весьма простым программным фрагментом, сигнализирующим, в основном, о самом факте обращения к имитируемому модулю с необходимой для правильной работы программы обработкой значений его входных параметров (иногда с их распечаткой) и с выдачей, если это необходимо, заранее запасенного подходящего результата. После завершения тестирования и отладки головного и любого последующего модуля производится переход к тестированию одного из модулей, которые в данный момент представлены имитаторами, если таковые имеются.
Для этого имитатор выбранного для тестирования модуля заменяется на сам этот модуль и добавляются имитаторы тех модулей, к которым может обращаться выбранный для тестирования модуль. При этом каждый такой модуль будет тестироваться при «естественных» состояниях информационной среды, возникающих к моменту обращения к этому модулю при выполнении тестируемой программы. Таким образом, большой объем «отладочного» программирования заменяется программированием достаточно простых имитаторов используемых в программе модулей. Кроме того, имитаторы удобно использовать для подыгрывания процессу подбора тестов путем задания нужных результатов, выдаваемых имитаторами.
Лекция 8
Источник: studopedia.ru
Урок 35
Доказательство правильности программ
(§37. Доказательство правильности программ)
Для доказательства правильности программы необходимо иметь спецификацию — точное описание того, что должно быть сделано в результате работы программы.
Спецификация — точная и полная формулировка задачи, содержащая информацию, необходимую для построения алгоритма её решения.
На практике спецификации программ обычно формулируют на естественном языке, в котором слова могут иметь несколько разных значений. Для строгого доказательства желательно, чтобы спецификация была задана в формальном виде, с помощью формул или соотношений между величинами.
По предложению английского ученого Ч. Хоара, спецификация записывается в форме S, где Q — начальное условие, S — программа и R — утверждения, описывающие конечный результат. Запись S означает следующее: «Если выполнение программы S началось в состоянии, удовлетворяющем Q, то гарантируется, что оно завершится через конечное время в состоянии, удовлетворяющем R».
Корректная программа — это программа, соответствующая спецификации.
Если для исходных данных не удовлетворяется условие Q, программа должна сообщать об этом пользователю и закончить работу. Это говорит о надёжности программы.
Например, для алгоритма Евклида условия Q и R могут выглядеть так:
Q:m ≥ n > 0, R: а = НОД(m,n),
а для программы суммирования элементов массива А[1:n] — так:
Спецификации могут (и должны) быть составлены не только для программы в целом, но и для её отдельных блоков (процедур, функций, циклов и т. д.). Полезно вносить утверждения Q и R прямо в текст программы. Построенная таким образом аннотированная программа — это ещё один шаг к доказательному программированию.
Ч. Хоар разработал специальный аппарат, позволяющий доказывать правильность программы на основе спецификаций отдельных блоков. Приведём простейшие правила преобразования:
• если S и Р => R (из истинности Р следует истинность R), то S;
• если S и R => Q, то S;
• если программа S — это последовательное выполнение блоков S1 и S2, для которых выполняются спецификации S1 и S2, то выполняется спецификация S.
Доказательство правильности программ используют в двух ситуациях:
• доказывают правильность готовых программ (верификация программ);
• строят программы одновременно с доказательством их правильности (синтез программ).
Как правило, верификация — это очень трудоёмкий и сложный процесс, и оказывается значительно проще использовать доказательства правильности во время разработки программы. При этом программы получаются проще, эффективнее и значительно надёжнее.
Следующая страница Вопросы и задания
Cкачать материалы урока
Источник: xn—-7sbbfb7a7aej.xn--p1ai
Исследование и формализация задачи. Информационно-математическая модель задачи.
Информатика – это научная и прикладная область знаний, изучающая информационные процессы.
Информационным процессом называется процесс получения, хранения, обработки и передачи информации с помощью компьютерных и других технических средств.
Термин «информатика» (франц. informatique) происходит от французских слов information (информация) и automatique (автоматика) и дословно означает «информационная автоматика»
Широко распространён также англоязычный вариант этого термина — «Сomputer science», что означает буквально «компьютерная наука».
Информатику обычно представляют состоящей из двух частей:
− технические средства;
− программные средства.
Технические средства, то есть аппаратура компьютеров, в английском языке обозначаются словом hardware, которое буквально переводится как «твёрдые изделия».
Для программных средств создано слово software (буквально — «мягкие изделия»), которое подчёркивает равнозначность программного обеспечения и самой машины и вместе с тем подчёркивает способность программного обеспечения модифицироваться, приспосабливаться и развиваться.
Информация— сведения об объектах и явлениях окружающей среды, их параметрах, свойствах и состоянии, которые воспринимают информационные системы (живые организмы, управляющие машины и др.) в процессе жизнедеятельности.
Информация – мера уменьшения неопределённости знаний. Термин «информация» происходит от латинского слова «informatio», что означает сведения, разъяснения, изложение.
Информация передаётся в виде сообщений от некоторого источника информации к её приёмнику (потребителю) посредством канала связи между ними.
Информация есть характеристика не сообщения, а соотношения между сообщением и его потребителем. Без наличия потребителя, хотя бы потенциального, говорить об информации бессмысленно.
Информацию любой природы, зафиксированную тем или иным способом, принято называть данными.
Основные понятия информатики: алгоритм, исполнитель алгоритма, программа, жизненный цикл программы.
Алгоритм – это точное описание последовательности действий над входными данными, выполнение которых исполнителем приводит к получению выходных данных.
Исполнитель алгоритма— это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.
В информатике универсальным исполнителем алгоритмов является компьютер
Запись алгоритма в форме понятной компьютеру называется компьютерной программой.
Жизненный цикл программы – временной промежуток от момента создания программы до момента полного отказа от её эксплуатации.
Постановка задачи. Внешняя спецификация программы.
Создание программы начинается с конкретизации требований пользователя, т.е. с постановки задачи. Как результат формируется внешняя спецификация программы
Внешняя спецификация — это точное описание того, что должно быть совершено в результате выполнения программы.
Внешняя спецификация содержит:
1. Конечные цели решения задачи.
2. Условие задачи с описанием данных.
3. Формы получения исходных данных и выдачи результатов.
Постановка задачи включает в себя:
1. Сбор информации о задаче.
2. Формулировка условия задачи
3. Определение конечных целей решения задачи.
4.Определение формы выдачи результатов
5. Описание данных(типов,величин,структуры)
Исследование и формализация задачи. Информационно-математическая модель задачи.
Сформулировав на этапе постановки задачи, что должна делать программа, на этапе формализации уже определяется, как должна решаться поставленная задача
На текущем этапе выделяются наиболее важные характеристики предметной области и способы решения задачи
Как результат создается информационно-математическая модель предметной области
Информационная модель — набор величин, содержащий всю необходимую информацию для решения рассматриваемой задачи
Математическая модель — это система математических соотношений — формул, уравнений, неравенств и т.д., отражающих существенные свойства объекта или явления
Критерии качества информационно-математической модели: полнота
Информационно-математическая модель позволяет получить все результаты, заявленные во внешней спецификации, при любых допустимых наборах входных данных
Источник: poisk-ru.ru
Большая Энциклопедия Нефти и Газа
Спецификация программы ( модуля) [ Program ( Module) Specification ] — точная и полная формулировка задачи, содержащая информацию, необходимая для построения алгоритма ( программы) решения этой задачи. [1]
Спецификация программы , программная спецификация [ program specification ] — точная и полная формулировка определенной задачи или гуппы задач, содержащая сведения, необходимые для построения алгоритма их решения. Содержит описание результата, который должен быть достигнут с помощью конкретной программы, а также действий, выполняемых программой для достижения конечного результата без упоминания того, как указанный результат достигается. [2]
Спецификации программ разработаны не только для пояснения концепций и методов, представленных в книге, но также для передачи некоторого опыта создания достаточно сложных программ машинной графики. Хорошо выполненные, они могут составить инструментарий полезных графических программ. [3]
Спецификация программы , программная спецификация [ program specification ] — точная и полная формулировка определенной задачи или гуппы задач, содержащая сведения, необходимые для построения алгоритма их решения. Содержит описание результата, который должен быть достигнут с помощью конкретной программы, а также действий, выполняемых программой для достижения конечного результата без упоминания того, как указанный результат достигается. [4]
Спецификации программ , разработанных на фазе их проектирования, должны точно описывать характер исходных данных и то, что должно быть получено в результате выполнения программы. Отдельные части спецификации могут отражать время выполнения, сложность вычисления, размер массивов, возможные инварианты, контролирующие ход вычислительного процесса. Один из способов спецификации заключается в описании на естественном языке того, что должно быть получено по заданным исходным данным. Однако в этом случае трудно избежать двусмысленностей при разборе их разными специалистами. Естественно, что многие ученые предлагают различные методы формальных спецификаций. [5]
Спецификации программ разработаны не только для иллюстрации концепций и технологий, представленных в книге, но также чтобы передать некоторый опыт создания достаточно сложных программ машинной графики. Хорошо реализованные, они могут составить инструментарий полезных графических программ. Результатом законченных программных проектов являются полезные программы общего назначения. [6]
Спецификацией программы является любое множество определений ( не обязательно записанных в логических терминах), которое точно задает содержимое каждого из отношений, встречающихся в программе. [7]
Здесь приведена спецификация программы генерации и манипуляции с кривыми. [8]
Здесь приведена спецификация программы генерации и манипуляции для поверхности. Она очень похожа на программу генерации и преобразований для кривой из гл. В этом случае генерация и манипуляция поверхностью является просто дополнительной функцией. [9]
Операторы блока спецификации программы PSB представляют собой набор макрокоманд языка ассемблера. [10]
При создании операционных маршрутов роль спецификации программ выполняет процедура с программным ответственным исполнителем, в которой в общей форме и описывается функционирование будущей программы, причем в совокупности с деятельностью оператора. [11]
По параметрам оператора ВЫПОЛНИТЬ Управляющий модуль определяет название блока спецификации программы и извлекает его из библиотеки спецификаций PSBLIB. Обрабатывая данные блока спецификации, система определяет названия баз данных, с которыми должна работать прикладная программа, извлекает из библиотеки описаний баз DBDLIB соответствующие описания и открывает связанные с ними файлы. [13]
В дальнейшем пусть А обозначает множество дизъюнктов, представляющее спецификацию программы . [14]
Выявляются неясные и двусмысленные места, после чего составляется окончательно зафиксированная спецификация программы . Эта спецификация не должна изменяться ( хотя на практике, к сожалению, она обычно не рассматривается как инвариантная) до тех пор, пока не будет представлена полностью оттестированная программа, если только пользователь не захочет покрыть расходы по разработке до внесения изменений и заплатить за начало работ над новой системой. [15]
Источник: www.ngpedia.ru
Понятие «спецификация программы»
Средства спецификации — это любые средства получения и построения таких описаний. Язык спецификаций — это рационально организованный и синтаксически оформленный набор таких средств.
- 3. [163] Спецификация программы — это точная и полная формулировка задачи, содержащая информацию, необходимую для построения алгоритма (программы) решения этой задачи.
- 4. Команда-комментарий — это спецификация программы, выраженная с помощью помещённого в программу утверждения (или приказа) на псевдокоде.
Мы часто вынуждены обращаться к формальным спецификациям, так как естественный язык (используемый в псевдокоде) обладает таким свойством, как полисемия.
Определение [141].
Полисемия — это наличие различных (но в какой-то мере связанных) смыслов и(или) значений у одного и того же слова (словосочетания, фразы), различных интерпретаций у одного и того же знака или знакосочетания.
Пусть PL — некоторый язык программирования (в частности, им может являться один из модельных языков Н, D, М), АР1— его алфавит, G — алфавит языка первого порядка.
Определение (синтаксическое).
1. Формальной спецификацией программы S будем называть слово
в алфавите G и АР1 и [1] , где Q, и R — формулы языка первого порядка, S — программа на языке PL.
Предусловием программы S называется формула Q.
Пустым предусловием программы S называется предусловие Q= S H
Постусловием программы S называется формула R.
2. Языком спецификаций назовём язык для записи предусловий и постусловий.
1. [88, с. 107] Для задачи о суммировании элементов массива В [0: п -1] и помещении результата в переменную S предусловие и постусловие имеют следующий вид:
2. Для вычисления целой части квадратного корня из натурального числа п и помещения результата в целочисленную переменную S предусловие и постусловие имеют следующий вид:
3. Для задачи сортировки массива В [0: п — 1] предусловие и постусловие имеют следующий вид:
Определение (no [88, c. 106]) (семантическое).
Интерпретация формальной спецификации S такова: если выполнение программы S началось в состоянии, удовлетворяющем Q, то имеется гарантия, что оно завершится через конечное время в состоянии, удовлетворяющем R.
- 1. Утверждением будем называть содержательную или формальную спецификацию, включённую в текст программы.
- 2. Аннотированной программой будем называть программу, содержащую утверждения между каждой парой соседних команд.
Итак, аннотированная программа является «формулой» в языке вида:
Язык программирования + Язык спецификаций.
Использование аннотированных программ открывает широкие возможности для формальных преобразований программ и формальных доказательств их свойств, что является основой для верификации и оптимизации программ.
Источник: studme.org