Развитие теории алгоритмов

РЕФЕРАТ

по учебной дисциплине «Математический анализ»

на тему: «Развитие теории алгоритмов»

СОДЕРЖАНИЕ

Введение

1. Алгоритмы в математике древних цивилизаций
2. Возникновение современной теории алгоритмов
3. Основные результаты теории алгоритмов

1.  Нормальный алгоритм Маркова
2. Универсальная машина Тьюринга
3.  Основная гипотеза теории алгоритмов (тезис Чёрча)

Заключение

Список использованных источников и литературы

Введение

Понятие «алгоритм» уже давно вошло в математическую практику, образовав теоретический фундамент вычислительных наук, и свободно используется в других областях деятельности. Применение теории алгоритмов осуществляется как в использовании самих результатов (особенно это касается использования разработанных алгоритмов), так и в обнаружении новых понятий и уточнении старых. С ее помощью проясняются такие понятия как доказуемость, эффективность, разрешимость и другие.

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

Но знаем ли мы, когда понятие «алгоритм» вошло в столь широкое употребление? Откуда произошло само слово «алгоритм»?

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

1. Алгоритмы в математике древних цивилизаций

История понятия «алгоритм» уходит корнями в древние цивилизации, как сама математика. Из древних цивилизаций нам известно о математике  древнего Египта и древнего Вавилона.  

О математике древних египтян известно из папируса Райнда, который был найден и расшифрован в 19 веке. В папирусе были перечислены задачи на подсчёт единиц и измерение площадей полей. В нём также излагались инструкции жрецов для писцов. Быть писцом в древнем Египте было очень почётно, так как писец заведовал административно-хозяйственной частью, подсчитывал и указывал, сколько человек нужно направить и на какие работы. В папирусе Райнда содержались инструкции о том, как подсчитывать. Они документально подтверждают существования алгоритма ещё в древнем Египте. Но такой алгоритм ещё не рассматривался самой математикой, к тому же сама математика ещё не была осознана как отдельная область деятельности. Основным объектом математики древнего Египта были числа и элементарные операции над ними. По папирусу Райнда можно заметить, что основным алгоритмом при вычислении операций деления натуральных чисел и сложения дробей был перебор. На бумагу последовательно выписывались числа и элементарные операции с этими числами, а затем перебором подбирались правильные ответы, которые сходились в проверке.

Из материалов, что дошли до нас о древнем Египте, нельзя твердо сказать, что тогда существовало отдельное понятие «алгоритм», хотя в математику уже тогда закладывались основные алгоритмические истины.

О математике древнего Вавилона мы знаем из клинописных глиняных табличек. С помощью них нам известно, что тогда решались математические задачи, которые не имели отношения к практической деятельности: вместо привычных нам переменных тогда использовались слова «длина» (x), «ширина» (y), «глубина» (z), «площадь» (xy), «объём» (xyz). Тогда же зародилась алгебра - решение систем линейных и квадратичных уравнений.