Запись алгоритмов с помощью псевдокода. Понятие языка программирования.

Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов.

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

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

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

1. Любой алгоритм должен иметь свое собственное имя.

2. Ключевые слова при записи подчеркиваются.

3. Любой алгоритм всегда имеет начало и конец.

4. Если какое то из действий имеет сложную структуру, то тогда эта структура обозначается началом и концом.

5. Алгоритм всегда записывается со сдвигом.

Языки программирования – формальный язык для записи алгоритмов с помощью ЭВМ. (Pascal, Delphi, C++, Visual Basic, Java). Алгоритм написанный на языке программирования, называется программным.

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

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

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

М

Машина обладает внутренней памятью, она может иметь К-состояний. Состояние внутреннее памяти = состоянию машины Тьюринга.

Машина имеет собственную программу для функционирования (набор команд = программа). Какой символ прочитан с ленты? В каком состоянии находится машина?

Результат: - Символ, который записывается в ячейку;

- Возможное изменение состояний машины;

- Возможное перемещение читающей головки.

Команда имеет вид: a q₁ b q₂ D

a – Символ который читается с ленты, q₁ – начальное состояние, b – символ, который записывается, q₂ – новое состояние, D – возможное перемещение читающей головки. D={L, R, S} L – переместится на одну ячейку в лево, R – вправо, S – остаться на месте.

Символы, это символы из некоторого алфавита, которые остаются вместе с программой. A={a₁, … , a_n, e}, где e – пустое значение. Q={q₁, …, q_k}, k возможных состояний.

Для того что бы определить машину Тьюринга, нужно определить: Алфавит; Состояние; Программу.

Способы записи машины Тьюринга:

1. Двумерная таблица. По строкам таблицы записываются все символы алфавита, по столбцам – состояние машины. Внутри это результат работы, если не входе определен символ и определено состояние.

	q1	…	qk
a1	bq2D
…
an

2. Граф. Строиться из точек и дуг направления: Точки – Состояние машины Тьюринга, Дуги – Переход машины из одного состояния в другое, причем все дуги являются помеченными.

Обозначение: - Начальный символ

- Конечный символ

- Направления перемещения читающей головки.

a:bD

q₁ q₂

Дополнительные условия машины Тьюринга:

1. Для некорректных исходных данных программы для машины Тьюринга должны зациклиться.

· Данные считаются корректными, если в начальный момент времени читающая головка находиться на единице, входные данные.

· Исходные данные должны состоять только из алфавита машины

· Входные данные должны отвечать дополнительным условиям задачи.

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

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

Композиции машин Тьюринга.

По другому их можно назвать операции над машиной Тьюринга.

ü ИТЕРАЦИЯ, последовательное соединение.

Имеются две машины Тьюринга, Т1 и Т2, задается некоторое начальное состояние Т1 и некоторая комбинация на ленте. Эта программа выполняется и в один этап, мы получаем результат. Результат исходные данные для Т2 и после этого выполниться машина Т2.

Алгоритм работы последовательного соединения.

1. Механически объединить в одну таблицу две программы.

2. Заменить конечное состояние Т1 на начальное состояние Т2.

3. Нужно заменить клетки Т1, которые означают завершение первой программы, команды следующего вида. i p₁ S

i – Символ который стоит в строке, p₁ – Начальное состояние, S – движение остаться на месте.

ü ПОВТОРЕНИЕ машины Тьюринга.

1. В тех машинах где встречается конечное состояние, нужно указать начальное состояние этой же машины.

2. В пустых клетках указать i q₁ S

i – Символ который соответствует строке, где записана команда, q₁ – Начальное состояние, S – движение остаться на месте.

Алгорифмы Маркова.

Нормальные алгорифмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах. Определение всякого нормального алгорифма состоит из двух частей: определения алфавита алгорифма (к словам в котором алгорифм будет применяться) и определения его схемы. Схемой нормального алгорифма называется конечный упорядоченный набор т. н. формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида , где L и D — два произвольных слова в алфавите алгорифма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида , где L и D — два произвольных слова в алфавите алгорифма. При этом предполагается, что вспомогательные буквы и не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).

Примером схемы нормального алгорифма в пятибуквенном алфавите | * abc может служить схема

15. Композиция Маркова

Композиции алг Маркова

Правила объединения: 1) сегм.кот выполняет операции М2 должен идти первым в записи объединеного алг. 2) строка должна защищена от обработки М2 пока не кончит М1 3) в М1 надо заменить кажд.правило вида α→.β на α→a’β а последним правилом добавить λ→a’. 4) в М2 надо заменить все λ на с’ все строки вида S₁,S₂.. на с’S₁,с’S₂.. α→β меняем на α→D’β а последним правилом добавить с’→D’