2014-02-09
744
Второе направление связано с машинной математикой. Здесь сущность понятия алгоритма раскрывается путем рассмотрения процессов, осуществляемых в машине. Впервые это было сделано Тьюрингом, который предложил общую и вместе с тем самую простую концепцию вычислительной машины. Ее описание было дано Тьюрингом в 1937 г. А это направление в теории алгоритмов получило название - машина Тьюринга.
ТЕОРИЯ АЛГОРИТМОВ
Алгоритм – это точное, понятное предписание о том, какие действия и в каком порядке должны быть выполнены, чтобы решить любую задачу из класса однотипных задач.
Алгоритм обладает следующими характеристиками:
1. Дискретность. Алгоритм – это процесс последовательного построения величин таким образом, что в начальный момент задается исходная конечная система величин, а в каждый следующий момент система величин получается по определенному закону из системы, имевшихся в предыдущий момент времени.
2. Детерминированность. Система величин, получаемых в какой-то не начальный момент, однозначно определяется системой величин, полученных в предшествующие моменты времени.
|
|
|
3. Элементарность шагов алгоритмов. Закон получения последующей системы величин из предшествующих должен быть простым.
4. Массовость алгоритма. Начальная система величин может выбираться из некоторых потенциально бесконечного множества. Иначе говоря, алгоритм должен обеспечивать решение некоторому множеству (классу) задач с различными параметрами(коэффициентами).
5. Результативность алгоритма. Последовательный процесс построения величин должен быть конечным и давать результат, того есть решение задачи.
Основная задача теории алгоритмов – это решение проблемы алгоритмическойразрешимости, а не поиск правила (способа/метода) ее решения. Теория алгоритмов дает ответ на вопрос «Данная задача имеет решение?», и не отвечает на вопрос «Как решается данная задача?»
В рамках такого подхода к определению понятия алгоритма можно определить три основных направления:
1. Первое направление связано с уточнением понятия эффективно вычисляемой функции. В результате был выделен класс так называемых рекурсивных функций.
3. Третье направление связано с понятием нормальных алгоритмов, введенным и разработанным российским математиком А. А. Марковым. х Нормальные алгоритмы Маркова. Это направление получило название нормальные алгоритмы Маркова.
Основные понятия: элементарные функции, правила образования новых функций.
Простейшие функции:
1. Функция сохранения нуля (нуль-функция)
(4.1)
