Алгоритмы.

Под алгоритмом понимают эффективные процедуры, однозначно позволяющие получить результат решения задачи. Однако не следует думать, что эта фраза является точным определением алгоритма. Оказывается, что не для каждой задачи можно найти единый алгоритм её решения. Строгое изучение понятий алгоритмической теории, изучение алгоритмически неразрешимых проблем будет проводиться в шестом семестре при изучении третьей части курса спецглавы математики – «Математическая логика и теория алгоритмов». С современной точки зрения критерием алгоритмичности является возможность синтезировать устройство или написать программу по имеющемуся алгоритму. Схемы алгоритмов могут быть различными. Помимо уже изученных, могут быть использованы блок-схемы алгоритмов, логические схемы алгоритмов и т.д. Логические схемы алгоритмов наиболее компактны, но трудно читаемы. Блок-схема алгоритма (иногда её называют граф-схемой алгоритма) – это связный ориентированный граф. Поскольку алгоритм должен иметь начало и конец, то граф имеет одну начальную вершину, которая не имеет входов и содержит один выход, а также одну конечную вершину, которая не имеет выходов. Кроме этих вершин граф содержит операторные и условные вершины, число которых конечно.

Дополнительные требования к блок-схеме алгоритма:

- Выход может быть соединен только с одним входом;

- вход соединяется, по - крайней мере, с одним выходом;

- любая вершина лежит на одном или нескольких путях из начальной в конечную вершины;

-условная вершина имеет два выхода, помеченные символами 0 (условие не выполняется) и 1 (условие выполняется);

- выход условной вершины может соединяться с её входом;

- выход операторной вершины со своим входом соединяться не может.

Пример: Для ранее рассмотренного управляемого генератора периодической последовательности Т=11010 блок-схема алгоритма формирования периода будет выглядеть следующим образом:

Естественно, что от блок-схемы алгоритма можно перейти к другой форме, например, к таблице переходов-выходов. Для построения таблицы переходов-выходов автомата Мили входы вершин, следующих за операторными, помечают символами состояний конечного автомата . Символом начального состояния помечаются вход вершины, следующей за начальной и вход конечной вершины. Остальные вершины помечают различными символами, причем, если вход вершины помечается, то только одним символом. Затем, начиная с состояния , просматривают пути перехода от состояния в состояние и выписывают условия этого перехода и выполняемые операторы. В результате получают таблицу переходов-выходов:

		Условие перехода	Оператор

Можно переписать эту таблицу в привычном компактном виде:

	/	/	/	/	/
	/	/	/	/	/