Алгоритмизация задач и проектирование программ

Введение
1 Классические языки логического управления
1.1 Булевы функции, таблицы истинности и таблицы решений
1.2 Булевы формулы и другие аналитические формы представления алгоритмов логического управления
1.3 Функциональные схемы.
1.4 Временные диаграммы и циклограммы.
1.5 Схемы алгоритмов
1.6 Логические схемы алгоритмов
2 Нетрадиционные языки логического управления.
2.1 Язык SDL.
2.2 Р-схемы
2.3 Сети Петри и графы операций.
2.4 Язык «Графсет»
2.5. Проблемно-ориентированные языки, близкие к естественным
3 Графы переходов как язык спецификаций
3.1 Стратегии синтеза алгоритмов логического управления
3.2 Факторы, ограничивающие широкое использование графов переходов в качестве языка алгоритмизации
3.3 Графы переходов
Заключение
Список литературы

Алгоритмизация задач и проектирование программ

Недостатки схем алгоритмов:
1) отсутствие требований к тому, что должна отражать схема
алгоритма: алгоритм управления; алгоритм реализации алгоритма управления; алгоритм, в котором учитываются свойства управляющих конструкций применяемого языка программирования; алгоритм выполнения программы;
2) отсутствие требований к организации схем алгоритмов (за исключением структурирования), которые обеспечивают простоту «чтения»;
3) необходимость в общем случае многократных преобразований схем алгоритмов для того, чтобы обеспечить возможность одновременного решения нескольких задач в одном управляющем вычислительном устройстве и учесть свойства управляющих конструкций языка программирования;
4) наличие промежуточных переменных, которые отсутствуют в «словесном алгоритме» логического управления. Они затрудняют чтение схем заказчиком.
5) применение большого числа битовых переменных. Каждую битовую переменную нужно устанавливать и сбрасывать. Битовые переменные относятся к отдельным состояниям автомата, а состояния автомата в целом обычно не определяются. Битовые переменные нецелесообразно использовать в алгоритмах с использованием языков программирования, поскольку языки программирования позволяют обрабатывать многозначные переменные.
6) существование флагов и умолчаний значений внутренних и выходных переменных, которые находятся в вершинах операторов. Они затрудняют чтение схем алгоритмов, потому что нужно помнить предысторию.
7) схемы алгоритмов являются громоздкими, потому что в условных вершинах значений проверяются только одиночные двоичные переменные.
8) трудность внесения изменений, вызванная тем, что операторные вершины связаны через условные вершины. Изменение условий перехода между вершинами операторов изменяет условия переходов в другие вершины операторов.
1.6 Логические схемы алгоритмов
Логические схемы алгоритмов (предложил Ляпунов А. А8) – это строчная форма записи линеаризованных схем алгоритмов. Они образованы буквами, которые соответствуют вершинам линеаризованных схем алгоритмов. В логических схемах алгоритмов присутствует нумерация стрелок, указывающих переходы, которые осуществляются тогда, когда не выполняются условия.
Достоинством логических схем алгоритмов является компактность описания а недостатком – плохая наглядность и трудность чтения.
2 Нетрадиционные языки логического управления.
2.1 Язык SDL.
SDL-диаграмма (Specification and Description Language) – графический язык спецификации и описания программ9. Он разработан международной комиссией по телефонии и телеграфии. SDL-диаграммы похожи на схемы алгоритмов, но отличаются от них тем, что в них вводятся состояния в явном виде. Недостатком SDL-диаграмм является громоздкость и то, что они соответствуют только автоматам Мили10.
2.2 Р-схемы
Р-схема (R-chart)– это нагруженный по дугам ориентированный граф, который изображается при помощи вертикальных и горизонтальных линий. Он состоит из структур, у каждой из которых только один вход и один выход. Р-схемы были предложены Вельбицким И. В11. Эта модель базируется на использовании автоматов Мили. В Р-схемах присутствуют два типа вершин и дуг и один тип соединительных линий. В этих схемах могут быть три типа соединений – последовательное, параллельное и вложенное.
Достоинством этого языка является компактное отражение структуры алгоритмов.
Недостатком Р-схем является то, что в них применяются нестандартные обозначения и только один тип автоматных моделей.
2.3 Сети Петри и графы операций.
Сеть Петри – это графовая модель, состоящая из двух типов вершин – позиций и переходов, которые связаны между собой дугами. В этой модели не может быть непосредственного соединения двух вершин одного типа. Эту графовую модель предложил Петри К.12 в 1962 г. для описания сложных и параллельных процессов.
Графы операций – это управляющие сети Петри. В них позиции помечены значениями выходных переменных, а переходы – значениями входных переменных. Графы операций предложил использовать Юдицкий С. А.13 для описания алгоритмов управления.
Достоинством графов операций является возможность описания в наглядной графической форме сложных алгоритмов управления, которые обладают параллелизмом.
Недостатки графов операций:
1) необходимость синхронизированности параллельных процессов;
2) использование только модели автомата Мура14 и невозможность применения других автоматных моделей;
3) использование только «единичных» кодов для кодирования позиций.
4) затруднение чтения алгоритма и анализа его функциональных возможностей из-за применения умолчаний, которые приводят к различию описаний алгоритма и его поведения.
2.4 Язык «Графсет»
Графический язык «Графсет» разработан в Центре космических исследований в Тулузе (Франция). Он применяется вместе с другими языками15 различными фирмами. Этот язык алгоритмизации является языком программирования, если существует транслятор с него.
Язык «Графсет» похож на язык графов операций. Он отличается от языка графов операций только формой изображения: для обозначения позиций вместо кружков применяются квадраты, а для записи значений выходных переменных используются прямоугольники, которые отсутствуют в графах операций. Так как язык «Графсет» и язык графов похожи, то у них есть общие достоинства и недостатки.
Достоинством диаграмм «Графсет» является стандартизация их изображений. Расположение диаграмм – сверху вниз. Но это является и недостатком, потому что такое расположение диаграмм не удобно для человека. Более целостно воспринимается плоскостное изображение, которое имеет место в графах переходов.
2.5. Проблемно-ориентированные языки, близкие к естественным
Проблемно-ориентированные языки называются также первичными16, так как они ориентированы на Заказчика и имеют развитые изобразительные средства и конструкции, которые употребляются при задании условий работы.
Недостатки проблемно-ориентированных языков:
1) необходимость изучения всем участникам процесса проектирования синтаксиса и семантики нового языка, который имеет ограниченное распространение;
2) построение на основе естественного языка, который не является математическим;
3) низкая наглядность «текстов», которые отображают структуру, взаимодействие и динамику процессов;
4) невозможность проверки полноты, непротиворечивости и отсутствия генерации и выполнения оптимизирующих преобразований;
5) необходимость использования различных типов языков (базовые, автоматные, машинные) в многоуровневой системе трансляции.
6) ориентированность на конкретный язык и конкретный тип автоматов;
7) отсутствие проверочных тестов и сложность верификации;
8) сложность внесения изменений;
9) если отсутствует транслятор для управляющего вычислительного устройства, то проблемно-ориентированные языки невозможно использовать.

3 Графы переходов как язык спецификаций
3.1 Стратегии синтеза алгоритмов логического управления
Существуют две стратегии синтеза алгоритмов логического управления.
При применении первой стратегии требуется синтезировать алгоритм логического управления, который обеспечивает заданное поведение объекта, по известному алгоритму функционирования объекта управления. Направление первой стратегии – от объекта управления к вычислителю.