Примеры численных алгоритмов. Основные черты алгоритмов. Необходимость уточнения понятия алгоритмов

Понятие алгоритма принадлежит к числу основных понятий математики. Первые примеры алгоритмов встречаются в средней школе. Примерами таких алгоритмов являются:

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

б) алгоритм вычитания;

в) алгоритм умножения двух натуральных чисел;

г) алгоритм Евклида;

д) алгоритм разложения натурального числа на простые множители;

е) алгоритм извлечения квадратного корня из натурального числа и т.д.

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

Характерные черты алгоритмов:

1. Дискретность;

2. Детерминированность;

3. Элементарность шагов;

4. Направленность;

5. Массовость.

На практике интуитивного представления об алгоритме бывает достаточно, чтобы установить, является ли данное предписание алгоритмом или нет.

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

Возможные уточнения понятия алгоритм: теория частично-рекурсивных функций, машина Тьюринга, нормальные алгоритмы Маркова.

Числовые функции и алгоритмы их вычисления. Понятие вычислимой функции

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

Примеры числовых функций и алгоритмов их вычисления.

1. . В качестве алгоритма используется решение Эратосфена.

2. f(x,y)={ наибольший общий делитель чисел x и y}. Алгоритмом, вычисляющим эту функцию служит алгоритм Евклида.

3. f(x,y)={натуральное число ≤9, чья цифровая запись является x-м десятичным знаком в десятичном разложении числа π}. В качестве алгоритма можно взять квадратуру круга, радиуса 1 по правилу Симпсона.

4. f(x,y)={сумма x и y}. Алгоритмом служит известное правило сложения натуральных чисел, записанных в десятичной системе счисления.

5. f(x,y)={произведение x и y}. Алгоритм умножения, изучают в школьном курсе математики.