Студопедия  
Главная страница | Контакты | Случайная страница

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

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

Читайте также:
  1. Автоматизированные информационно-вычислительные системы.
  2. Алгоритмы
  3. Алгоритмы и их свойства
  4. Алгоритмы компьютерного моделирования
  5. Алгоритмы на циклы с условием.
  6. Алгоритмы оперативного контроля процедуры анализа
  7. Все справочно-поисковые системы имеют собственные алгоритмы поиска.
  8. Вычислительные сети: понятие, классификация, основы построения.
  9. Решение задач с Разветляющим алгоритмы

 

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

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

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

Вычислительные алгоритмы формируются с помощью алгоритмических выражений, которые записываются с помощью формального алгоритмического языка, в основе которого лежит алфавит – конечное непустое упорядоченное множество символов S Î {s1, s2, s3,.. sn}. Из символов алфавита формируются слова – конечные (возможно пустые) последовательности символов. Для слов определяется лексикографический порядок. Считается, что слово U = u1 u2... un предшествует слову V = v1 v2... vn такой же длины, если существует такое 0 £ m £ n, что при всех 1 £ i < mui = vi и um < vm (например, для слов в алфавите {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
Внутренний Инфиксная A ´ B
Обратный Постфиксная (обратная польская) A B ´

 

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

 

Пример:

 

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

Прямой: ´ + 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) – также <ЛВ>, приведенные в порядке возрастания приоритета операций;

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

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




Дата добавления: 2015-04-11; просмотров: 29 | Поможем написать вашу работу | Нарушение авторских прав

1 | 2 | <== 3 ==> |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав