94. Блок-схемы алгоритмов

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

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

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

95.Машины Тьюринга. Основные определения.Машина

Тьюринга (МТ) — математическая абстракция, представляющая вычислительную машину общего вида. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга представляет собой автомат, имеющий бесконечную в обе стороны ленту, счи- тывающую головку и управляющее устройство. Управляющее устройство может находиться в одном из состояний, образую- щих конечное множество Q = {q0, q1, ..., qn}. Множество Q называют внутренним алфавитом машины Тьюринга.

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

невозможна ее физическая реализация. Лента разделена на ячейки, в каждой из которых может быть записан один из символов конечного алфавита A = {a0, a1, . . . , am}, который

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

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

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

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