Тема № 3 Алгоритмические основы вычислительных процессов. Элементы теории алгоритмов и формальных языков.

3.3. Сведение произвольных алгоритмов к числовым функциям. Понятие вычислимой функции. Алгоритмическая полнота эвм.

Сведение произвольных алгоритмов к числовым функциям

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

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

Включим все условия задачи, доступные для переработки данным алгоритмом А, в занумерованную неотрицательными целыми числами последовательность

А₀, А₁, А₂, … , А_n, …

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

B₀, B₁, B₂, … , B_n, …

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

m=φ(n),

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

Понятие вычислимой функции

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

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

Пусть имеется класс функций типа y(x₁, x₂, ..., x_n), особенностями которых является то, что все аргументы функции x₁,..., x_n целочисленны, и значение функции y также выражается целым числом. Другими словами, рассматриваются функции, аргументы и значения которых дискретны.

Функция y(x₁, x₂, ..., x_n) называется эффективно вычислимой, если существует алгоритм, позволяющий вычислить ее значение по известным значениям аргументов.

Алгоритмическая полнота ЭВМ

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

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

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

Алгоритмическая полнота обеспечила ЭВМ выход за пределы научных и инженерных вычислений – к проблемам экономики и управления.