Функциональных блоков, Каждый из которых соответствует выполнению одного или нескольких действий.

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

Название символа	Обозначение и пример заполнения	Пояснение
Процесс		Вычислительное действие или последовательность действий
Условие		Проверка условий
Модификация		Начало цикла
Предопределенный процесс		Вычисления по подпрограмме, стандартной подпрограмме
Ввод-вывод		Ввод-вывод в общем виде
Пуск-останов		Начало, конец алгоритма, вход и выход в подпрограмму
Документ		Вывод результатов на печать

 

Любой алгоритм может быть записан совокупностью 3-х базовых структур.

 

· Следование;

· Ветвление;

· Повторение.

 

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

 

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

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

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

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

 

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

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

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

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

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

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

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

 

Машина Тьюринга – абстрактная вычислительная машина.

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

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

М

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

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

Результат:

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

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

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

Команда имеет вид: aq₁bq₂ 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. Граф. Строится из точек и дуг направления: Точки – Состояние машины Тьюринга, Дуги – Переходы машины из одного состояния в другое, причем все дуги являются помеченными.

 

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

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

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

входные данные.

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

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

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

результата.

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

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

 

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

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

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

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

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

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

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

i – Символ который стоит в строке,

p₁ – Начальное состояние,

S – движение остаться на месте.

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

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

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

i – Символ который соответствует строке, где записана команда,

q₁ – Начальное состояние, S – движение остаться на месте.

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

 

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

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

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

Аналогично, заключительными формулами подстановки называются слова вида , где L и D — два произвольных слова в алфавите алгорифма.

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

 

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