Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 214

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 208 209 210 211 212 213 < 214 > 215 216 217 218 219 220 .. 316 >> Следующая

b) теоретическое (математическое) представление, которое предназначено для анализа свойств системы и ее преобразований; его можно рассматривать как формализацию задачи;
c) алгоримическое предс авление, связываее визуальное и теоретическое представление с программой и являееся спецификацией программы;
d) программное представление, которое наконец-то предназначено для исполнения некоторого прибли ения к данной системе на реальном вычислителе.
Рассмотрим требования к различным формам представления.
• к визуальным представлениям: понятность для человека, в том числе,
елательно, и для неспециалиста;
• к математическим представлениям: понятность для специалиста и наличие моной системы преобразований;8
• обее требование к первм двум пунктам: статическая проверяемость свойств;
8 Таким образом, в принципе математическое представление избыточно, если у нас нет возможности эффективно использовать его для преобразования алгоритма. Но оно зачастую играет еще и другие роли, одна из которых отмечена в следующем пункте, а вторая — защита принятых решений от неквалифицированной критики и убеждение заказчика и/или начальника и оппонентов в их обоснованности.
610
ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ
• к алгоритмическим представлениям: ясность для программиста;
• к программным представлениям: осуществимость эффективной обработки;
• обее требование к паре соседних представлений: достаточно простое (в идеале однозначное) соответствие меду ними, позволяее легко переходить меду уровнями и поддеривать согласованность и адекватность всей системы описаний.
Теперь перейдем к более систематическому рассмотрени тех структур, которе леат в основе программирования от состояний. заметили, что общее визуальное представление алгоритмической спецификации, которая затем перерабатывается в программу, написанну в стиле от состояний — граф состояний и переходов.
Определение 10.4.1. Граф состояний и переходов, называемый также диаграммой переходов — нагруженный ориентированный граф G. Каждой вершине графа G сопоставлено наименование состояния, а каждой дуге — условие.
Конец определения 10.4.1.
ример таких диаграмм мо но посмотреть в преддуем параграфе. сло-вие AB, сопоставленное дуге, ведущей из a в b, содержательно интерпретируется следующим образом. При выполнении AB в состоянии a управление передается состоянию b (или же в другом смысле осуществляется переход по данной дуге).
Когда граф состояний и переходов используется для документирования программы, наименования состояний, как правило, совпадают с именами процедур, выполняихся в данном состоянии.
Прежде всего, рассмотрим подробнее вопрос, по какой причине в программистских работах диаграммы переодов и конечные автоматы употре-бля тся почти как синонимы. ычисления, соответствуие диаграммам переходов, могут бть представлены циклом, телом которого является последовательность трех действий:
Исполнение процедуры, сопоставленной состоянию; Проверка условий, сопоставленных выходящим дугам,
выбор дуги, соответствующей истинному условию; ереход к состояни , в которое ведет вбранная дуга;
10.4. ДИАГРАММЫ СОСТОЯНИЙ И ПЕРЕХОДОВ. ИХ СВЯЗЬ С МАТЕМАТИЧЕСКИМИ МОДЕЛЯМИ611
Если отвлечься от конкретных действий, выполняемх в состояниях (природа которых может быть очень сложной), и перейти к схеме программ, то мы получаем схему Янова (см. § A.3), и, более того, схему Янова частного вида. Если далее упростить условия на дугах, то мы можем закодировать их символами алфавита, моность которого не болье моности мно ества состояний на диаграмме. При этом коды всех дуг, выходящих из данного состояния, будут различаться. Далее мы можем построить конечный автомат, моделирующий поведение схемы Янова в следующем смысле:
1. Состояния автомата обозначаются натуральными числами i и взаимнооднозначно соответствуют функциональным блокам (действиям) схемы Янова, и, соответственно, состояниям диаграммы переходов;
2. Символы входного алфавита обозначаются теми же натуральными ча-слами;
3. В программной матрице автомата элемент Aj = k тогда и только тогда, когда в диаграмме переходов дуга, начинающаяся в состоянии, код которого i, и закодированная буквой j, ведет в состояние, закодированное числом k.
ля кадого исполнения схемы нова, соответствуей наей диаграмме переходов, суествует входная лента построенного нами автомата, поро да-ая ту е последовательность состояний.
Таким образом, математический переход от диаграмм состояний к конечным автоматам весьма прям и весьма груб. Это типичное приближение первого порядка9. Приближения первого порядка являются легче всего исследу-емми математическими моделями систем. деланне при их построении огрубления часто приводят к тому, что, базируясь на таком прибли ении, приходят к ло ным вводам о поведении системы. апример, прибли ени-ем первого порядка функции sin в точке 0 является прямая y = x. Поведение этой прямой и поведение синуса на достаточно больших отрезках не имеют ничего обего да е с качественной точки зрения. Такой эффект огрубления
9 Понятие приближения первого порядка, приближения второго порядка и т. д. появились при применении разложений функций в ряд Тейлора для получения приближенных решений систем. В общем случае системного анализа эти понятия служат полезным маяком и порождают аналогичную, но, конечно, не формализованную и неформализуемую, систему оценок для нечисленных математических моделей.
Предыдущая << 1 .. 208 209 210 211 212 213 < 214 > 215 216 217 218 219 220 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100