38. Автомат Мура. Структурная схема и способы задания.
Для автомата Мура функции переходов и выходов выглядят следующим образом:
Функция выходов для автомата Мура определяется внутренним состоянием автомата.
39. Преобразование автомата Мили в автомат Мура и наоборот.
40. Машина Тьюринга.
Машина Тьюринга (МТ)— абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингомв1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
В состав машины Тьюринга входит бесконечная в обе стороны лента(возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.
Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk(если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <qi, aj> имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.
41. Алгоритм. Свойства и способы представления.
Алгоритм— это упорядоченный законченный набор четко определенных правил для решения задач за конечное количество шагов.
Любой алгоритм должен иметь такие основные свойства:
Определенность. Алгоритм не должен содержать указаний, содержание которых может быть воспринято неоднозначно. Кроме того, после выполнения очередного указания алгоритма не должны возникать никаких разногласий относительного того, какое указание будет выполняться следующим. Иначе говоря, при выполнении алгоритма никогда не должна появляться потребность в принятии любых решений, которые непредусмотрены составителем алгоритма.
Массовость. Алгоритм составляется не для решения одной конкретной задачи, а для целого класса задач одного типа. В простом случае эта вариативность алгоритма обеспечивает возможность использования разных допустимых исходных данных.
Дискретность. Процесс, который описывается алгоритмом, должен быть разделен на последовательность отдельных действий. Описания, которые при этом возникают, представляют собой последовательность четко разделенных друг от друга указаний, которые образовывают дискретную структуру алгоритмического процесса - лишь выполнив требования одного указания, можно перейти к следующему.
Результативность – обязательное свойство алгоритмов. Её суть состоит в том, что при точном выполнении всех указаний алгоритма процесс принятия решения (получение результата) должен закончиться через конечное количество шагов и при этом должен быть получен ответ на поставленные в задачи вопросы.
Существует несколько способов представления алгоритмов: словесный, символический, графический.
Словесный способ заключается в описи алгоритма в терминах какого либо языка. Данный способ применяется редко, поскольку запись при этом довольно громоздкая и могут возникнуть противоречивые толкования алгоритма.
Символический способ заключается в записи алгоритма с помощью условных символов. Данный способ представления алгоритма делает запись алгоритма очень кратким, и не наглядным.
Графический способ – изображение алгоритма в виде структурной схемы, которая состоит из отдельных блоков. Этот способ представления алгоритма есть наиболее удобным и наглядным.
При представлении задачи графическим способом применяют такие основные виды блоков:
Блок в виде прямоугольника символизирует выполнение определенных указаний задачи. Стрелками обозначается направление хода выполнения условий задачи.
Блок в виде ромба символизирует проверку выполнения определенного утверждения с целью принятия решения о направлении хода дальнейшего выполнения условия задачи. Внутри блока описывается условие, которое требуется проверить. Возможные операции указываются на выходах - линиях, которые выходят из блока.
Начало и конец алгоритма изображаются в виде овальных блоков.
Если существует потребность свести несколько линий в одну, то используют соединительный круг.
При составлении структурной схемы алгоритма составитель должен придерживаться следующих правил, так называемых правил для составления структурной схемы алгоритма:
Любой алгоритм должен иметь начало и конец
Все блоки, кроме проверки условия, имеют только один выход.
Все блоки алгоритма имеют не больше одного входа.
Линии алгоритма не могут разветвляться.
Типы алгоритмов и их структурные схемы