Рефераты
 

Программирование

p align="left">· обеспечения независимости компонент системы;

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

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

6. Обеспечение точности перевода

Обеспечение точности перевода направлено на достижение однозначности интерпретации документов различными разработчиками, а также пользователями ПС. Это требует придерживаться при переводе определенной дисциплины. Майерс предлагает использовать общую дисциплину решения задач, рассматривая перевод как решение задачи [11]. Лучшим руководством по решению задач он считает книгу Пойа «Как решать задачу» [12]. В соответствии с этим весь процесс перевода можно разбить на следующие этапы:

· Поймите задачу;

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

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

· Проанализируйте полученное решение.

7. Преодоление барьера между пользователем и разработчиком

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

8. Контроль принимаемых решений

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

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

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

· сочетание как статических, так и динамических методов контроля.

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

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

ЛИТЕРАТУРА

Е.А. Жоголев. Введение в технологию программирования (конспект лекций). -- М.: «ДИАЛОГ-МГУ», 1994.

М. Зелковец, А. Шоу, Дж. Гэннон. Принципы разработки программного обеспечения. -- М.: Мир, 1982, с. 11.

К. Зиглер. Методы проектирования программных систем. -- М.: Мир, 1985, с. 15-23.

Дж. Фокс. Программное обеспечение и его разработка. -- М.: Мир, 1985, с. 53-67, 125-130.

Ian Sommerville. Software Engineering. -- Addison-Wesley Publishing Company, 1992.

Criteria for Evalution of Software. -- ISO TC97/SC7 #383.

Revised version of DP9126 -- Criteria for Evalution of Software Quality Characteristics. -- ISO TC97/SC7 #610. -- Part 6.

Б. Боэм, Дж. Браун, Х. Каспар и др. Характеристики качества программного обеспечения. -- М.: Мир, 1981.

В.В. Липаев. Качество программного обеспечения. -- М.: Финансы и статистика, 1983.

Б. Шнейдерман. Психология программирования. -- М.: Радио и связь, 1984. -- с. 99-103.

Г.Майерс. Надежность программного обеспечения. -- М.: Мир, 1980.

Д. Пойа. Как решать задачу. -- М.: Наука, 1961.

ЗАМОК ДРАКОНА

Не переходи мост, пока не дошел до него.

Народная пословица

Лекция 4.

ВНЕШНЕЕ ОПИСАНИЕ ПРОГРАММНОГО СРЕДСТВА

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

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

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

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

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

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

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

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

Внешнее описание ПС = спецификация качества ПС + функциональная спецификация ПС

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

2. Определение требований к программному средству

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

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

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

Известны три способа определения требований к ПС [2]:

· управляемый пользователем,

· контролируемый пользователем,

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

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

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

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

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

3. Спецификация качества программного средства

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. Функциональная спецификация программного средства

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

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

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

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

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

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

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

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

5. Методы контроля внешнего описания программного средства

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

· статический просмотр,

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

· пользовательский контроль,

· ручная имитация.

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

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

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

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

ЛИТЕРАТУРА

Ian Sommerville. Software Engineering. -- Addison-Wesley Publishing Company, 1992.

Г.Майерс. Надежность программного обеспечения. -- М.: Мир, 1980. с. 49-77.

Е.А. Жоголев. Введение в технологию программирования (конспект лекций). -- М.: «ДИАЛОГ-МГУ», 1994.

Criteria for Evalution of Software. -- ISO TC97/SC7 #383.

Revised version of DP9126 -- Criteria for Evalution of Software Quality Characteristics. -- ISO TC97/SC7 #610. -- Part 6.

Б. Боэм, Дж. Браун, Х. Каспар и др. Характеристики качества программного обеспечения. -- М.: Мир, 1981.

ЗАМОК ДРАКОНА

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

Л. Витгенштейн

Лекция 5.

МЕТОДЫ СПЕЦИФИКАЦИИ СЕМАНТИКИ ФУНКЦИЙ

Основные подходы к спецификации семантики функций. Табличный подход, метод таблиц решений. Алгебраический подход: операционная, денотационная и аксиоматическая семантика.

1. Основные подходы к спецификации семантики функций

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

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

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

L1 = R1,

(1) .………..

Ln = Rn.

 

где Li и Ri, i = 1, ..., n, некоторые выражения, содержащие предопределенные операции, константы, переменные, от которых зависят определяемые функции (формальные параметры этих функций), и вхождения самих этих функций. Семантика определяемых функций извлекается в результате интерпретации этой системы равенств. Эта интерпретация может производиться по-разному (базироваться на разных системах правил), что порождает разные семантики. В настоящее время активно исследуются операционная, денотационная и аксиоматическая семантики.

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

РАВНО(L1, R1),

(2) ……………….

РАВНО(Ln, Rn),

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

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

2. Метод таблиц решений

Метод таблиц решений базируется на использовании таблиц следующего вида (см. Табл. 1).

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

Табл. 1. Общая схема таблиц решений

Переменные / условия

Ситуации (комбинации значений)

x1

a1,1

a1,2

...

a1,m

*

x2

a2,1

a2,2

...

a2,m

*

.…..

.………………………………………….

xn

an,1

an,2

...

an,m

*

S1

u1,1

u1,2

...

u1,m

u1,m+1

S2

u2,1

u2,2

...

u2,m

u1,m+1

.…..

.…………………………………………

s1k

uk,1

uk,2

...

uk,m

uk,m+1

Действия

Комбинации выполняемых действий

Нижняя часть таблицы решений определяет действия, которые требуется выполнить в той или иной ситуации, определяемой в верхней части таблицы решений. Она также состоит из нескольких (k) строк, каждая из которых связана с каким-либо одним конкретным действием, указанным в первом поле (столбце) этой строки. В остальных полях (столбцах) этой строки (т.е., для ui j, i = 1, ..., m+1, j = 1, ..., k) указывается, следует ли (ui,j = '+') выполнять это действие в данной ситуации или не следует (ui,j = '-'). Таким образом, первый столбец нижней части этой таблицы представляет собой список обозначений действий, которые могут выполняться в той или иной ситуации, определяемой этой таблицей. В каждом следующем столбце этой части указывается комбинация действий, которые следует выполнить в ситуации, определяемой в том же столбце верхней части таблицы решений. Для ряда таблиц решений эти действия могут выполняться в произвольном порядке, но для некоторых таблиц решений этот порядок может быть предопределен, например, в порядке следования соответствующих строк в нижней части этой таблицы.

Табл. 2. Таблица решений «Светофор у пешеходной дорожки».

Условия

Ситуации

Состояние светофора

?

?

?

?

?

?

?

?

T = Tкр

Нет

Нет

Да

*

*

*

*

*

T = Tжёл

*

*

*

Нет

Да

*

*

*

T > Tзел

*

*

*

*

*

Нет

Да

Да

Появление привилегированной машины

Нет

Да

*

*

*

*

Нет

Да

Включить ?

-

-

-

-

-

-

+

-

Включить ?

-

+

+

-

-

-

-

-

Включить ?

-

-

-

-

+

-

-

-

T := 0

-

+

+

-

+

-

+

-

T := T+1

+

-

-

+

-

+

-

+

Освобождение пешеходной дорожки

-

-

-

+

-

-

-

-

Пропуск пешеходов

+

+

+

-

-

-

-

-

Пропуск машин

-

-

-

-

-

+

+

+

Действия

Комбинации выполняемых действий

Рассмотрим в качестве примера описание работы светофора у пешеходной дорожки. Переключение светофора в нормальных ситуациях должно производиться через фиксированное для каждого цвета число единиц времени (Tкр -- для красного цвета, Tжёл -- для жёлтого, Tзел -- для зелёного). У светофора имеется счетчик таких единиц. При переключении светофора в счетчике устанавливается 0. Работа светофора усложняется необходимостью пропускать привилегированные машины (об их появлении на светофор поступает специальный сигнал) с минимальной задержкой, но при обеспечении безопасности пешеходов. Приведенная на Табл. 2 таблица решений описывает работу такого светофора и порядок движения у него в каждую единицу времени. Звездочка (*) в этой таблице означает произвольное значение соответствующего условия.

Страницы: 1, 2, 3, 4, 5, 6


© 2010 BANKS OF РЕФЕРАТ