Структурная схема алгоритмов. Операционная схема структурированной схемы алгоритмов.

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

Любую блок-схему с одним входом и одним выходом можно построить, используя только базисное множество базовых структур { следование, ветвление, цикл-пока }.

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

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

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

Правила записи блоков. Существует ГОСТ 19.701-90 (ИСО 5807-85) дата введения 01.01.92 «Единая система программной документации. СХЕМЫ АЛГОРИТМОВ, ПРОГРАММ ДАННЫХ И СИСТЕМ. Условные обозначения и правила выполнения» в котором все подробно представлено.

Опишем основные положения: 1) Любая программа\подпрограмма начинается и заканчивается данным блоком «терминатор». Для начального блока так и пишем "НАЧАЛО", а для завершающего "КОНЕЦ". В блок-схеме должно быть только одно начало, и только один конец; 2) Если какие-то данные поступают в программу извне, то отобразить это на блок-схеме, можно блоком «данные»; 3) Блок «процесс» позволяет работать с данными, введенными на предыдущем шаге. Стоит избегать "языковых" особенностей конкретного яз. прог; 4) Если в программе используются функц. и процедуры, то их вызов помещается в блок «предопределённый процесс». Вызываемая функция должна быть отображена на отдельной блок-схеме; 5) Участки кода, которые разветвляют работу программы, по определённому условию выполняются блоком «решение». При этом в блоке пишется само условие, а из блока выводят линии справа (для случая "условие не выполняется") и снизу (для случая "условие выполняется"). Линии, исходящие из блока, должны быть подписаны; 6) Блок «границы цикла» отображает цикличные (повторяемые действия). Первый блок показывает где начинается цикл, а второй - где заканчивается. Также циклы описываются блоками «подготовка» и «решение». 7) Блок «соединитель» используется для соединения схемы, если она не помещается в отведённое пр-во. Если схема заканчивается, данным блоком с цифрой 1, то она продолжается в другом месте точно таким же блоком.

Машина Тьюринга.

Машина Тьюринга (МТ) — математическая абстракция, представляющая вычислительную машину общего вида. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

Машина Тьюринга является расширением модели конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать (при наличии соответствующей программы) любую машину, действие которой заключается в переходе от одного дискретного состояния к другому.

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

Машина Тьюринга представляет собой: бесконечную в обе стороны ленту, разделённая на ячейки, и управляющее устройство (конечный автомат) с конечным числом состояний, и коретку.

Составляющие машины: 1) Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а₀) должна представлять собой пустой символ. 2) Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, q₁) должно быть начальным (запускающим программу). Еще одно из состояний (q₀) должно быть конечным (завершающим программу) – состояние останова. 3) Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.

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

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

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

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

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