3. Объектно-ориентированное проектирование. Принципы проектирования. Схемы, диаграммы, инструменты.

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

Объектно-ориентированное проектирование (моделирование) основано на выделении классов, установлении свойств классов и методов их обработки, создании иерархии классов, наследовании свойств и методов их обработки.

Объект объединяет в себе данные и программу обработки этих данных.

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

Структурное проектирование основано на графической технике. Для описания различного рода моделей используются различные схемы и диаграммы.

Недостатки структурного проектирования:

- неадекватная спецификация требований,

- неспособность обнаружить ошибки в проектных решениях,

- затяжной цикл работы и неудовлетворительные результаты тестирования.

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

Объектно-ориентированное проектирование основано на построении 3-х видов моделей:

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

- динамическая: показывает поведение системы и последовательность взаимодействий в системе. Строится диаграмма состояний.

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

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

Билет 21

1. Детерминированные конечные автоматы. Эквивалентные состояния и автоматы.

Экивалентность состояний. Экивалентность автоматов.

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

Неформально два состояния эквивалентны, если они одинаково реагируют на все возможные продолжения входной цепочки. Это понятие применимо и к состояниям одного и того же автомата, и к состояниям разных автоматов. Применительно к конечным распознавателям, эквивалентность состояний можно определить так : состояние s конечного распознавателя М эквивалентно состоянию t конечного распознавателя N тогда и только тогда, когда автомат М, начав работу в состоянии s, будет допускать в точности те же цепочки, что и автомат N, начавший работу в состояний t.

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

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

автоматы M и N эквивалентны тогда и только тогда, когда эквивалентны их начальные состояния.

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