Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Вычислительные алгоритмы

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

Пусть f – некоторая функция преобразования; Q – некоторое множество данных; I Î Q – подмножество данных, преобразуемых алгоритмом, т. е. если q Î I, то f(q) ¹ q; W Î Q – подмножество данных, не преобразуемых алгоритмом, т. е. если q Î W, то f(q) = q.

Каждый ввод значения x₀ Î I определяет последовательность значений x_k+1 = f(x_k), k = 0, 1, 2,.. Говорят, что эта последовательность заканчивается за N шагов, если N – наименьшее число, для которого x переходит из множества I в множество W, т. е. x_N Î W. Если N ® ¥, то такая последовательность вообще не заканчивается. Вычислительным считают алгоритм, который заканчивается за конечное число шагов для всех x Î I.

Вычислительные алгоритмы формируются с помощью алгоритмических выражений, которые записываются с помощью формального алгоритмического языка, в основе которого лежит алфавит – конечное непустое упорядоченное множество символов S Î {s₁, s₂, s₃,.. s_n}. Из символов алфавита формируются слова – конечные (возможно пустые) последовательности символов. Для слов определяется лексикографический порядок. Считается, что слово U = u₁ u₂... u_n предшествует слову V = v₁ v₂... v_n такой же длины, если существует такое 0 £ m £ n, что при всех 1 £ i < mu_i = v_i и u_m < v_m (например, для слов в алфавите {0, 1}1101 < 1110). Конечная последовательность слов составляет выражения. Выражения бывают арифметические или логические.

Арифметическое выражение <АВ> распознается по следующим признакам:

· любая числовая константа есть <АВ>;

· любая числовая переменная есть <АВ>;

· любая ссылка на арифметическую функцию есть <АВ>;

· если X – <АВ>, то (X) – также <АВ>;

· если X – <АВ>, Y – <АВ>, то (X+Y), (X–Y), (X*Y), (X/Y), (X^Y) – также <АВ>, приведенные в порядке возрастания приоритета операций;

· ни один объект не является <АВ>, если это не следует из конечного числа применений вышеперечисленных правил.

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

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

	Прямой порядок:	Top ® Left ® Right
Внутренний порядок:	Left ® Top ® Right
Обратный порядок:	Left ® Right ® Top

Понятие «прямая польская форма записи» и «обратная польская форма записи» введено польским математиком Лукасевичем.

Пример:

Порядки обхода:

Прямой: – ´ + A B C ¸ D – E F

Внутренний: A + B ´ C – D ¸ E – F

Обратный: A B + C ´ D E F – ¸

Логическое выражение < ЛВ > включает в себя:

· логические константы и переменные, принимающие значения из множества {FALSE, TRUE};

· логические функции, являющиеся некоторым отображением f:{FALSE, TRUE} ® {FALSE, TRUE};

· выражения отношения вида <АВ><отн><АВ>, где <отн> – одна из следующих операций: <, £, =, ¹, ³, >.

Логическое выражение <ЛВ> распознается по следующим признакам:

· любая логическая константа есть <ЛВ>;

· любая логическая переменная есть <ЛВ>;

· любая ссылка на логическую функцию есть <ЛВ>;

· если X – <ЛВ>, то (X) – также <ЛВ>;

· если X – <ЛВ>, Y – <ЛВ>, то (X or Y), (X and Y), not(X) – также <ЛВ>, приведенные в порядке возрастания приоритета операций;

· ни один объект не является <ЛВ>, если это не следует из конечного числа применений вышеперечисленных правил.

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