Введение
Понятие алгоритма является одним из основных понятий современной математики. Еще на самых ранних стадиях развития математики (Древний Египет, Вавилон, Греция ) в ней стали возникать различные вычислительные процессы чисто математического характера. С их помощью искомые величины ряда задач вычислялись последовательно из исходных величин по определенным правилам и инструкциям. Со временем все такие процессы в математике получили название алгоритмов.
Термин алгоритм происходит от имени средневекового узбекского математика Аль-Хорезми, который еще в 825г. сформулировал правила выполнения четырех арифметических действий в десятичной системе счисления.
Процесс выполнения арифметических действий был назван алгоризмом.
С 1777г. вместо слова алгоризм стали употреблять слово алгорисмус, смысл которого состоял в комбинировании четырех операций арифметического исчисления.
К 50-м годам ХХ-го века появился термин алгорифм. Смысл этого понятия чаще всего связывался с алгорифмами Евклида – процессами нахождения наибольшего общего делителя двух многочленов, наибольшего общего отрезка двух отрезков и т. п.
Вплоть до 30-х годов ХХ-го века понятие алгоритма имело скорее методическое, чем математическое значение. Под алгоритмом понимали конечную совокупность точно сформулированных правил, которые позволяют решать те или иные классы задач.
Такое определение алгоритма не является строго математическим, т.к. в нем не содержится точной характеристики того, что следует понимать под классом задач и под правилами их решения.
В течение длительного времени математики довольствовались этим определением, поскольку общей теории алгоритмов фактически не существовало. Однако, практически не было серьезных случаев, когда математики разошлись бы во мнении относительно того, является ли алгоритмом тот или иной конкретный процесс.
Положение существенно изменилось, когда на первый план выдвинулись такие алгоритмические проблемы, положительное решение которых было сомнительно. Действительно, одно дело доказать существование алгоритма, другое – доказать отсутствие алгоритма для решения поставленной задачи. Первое можно сделать путем фактического описания решения задачи. В этом случае достаточно и интуитивного понятия алгоритма, чтобы удостовериться в том, что описанный процесс и есть алгоритм. Доказать отсутствие существования алгоритма таким путем невозможно. Для этого надо точно знать, что такое алгоритм.
В 20-х годах ХХ го века именно задача такого определения понятия алгоритма стала одной из центральных математических проблем. Решение ее было получено в середине 30-х годов в работах известных математиков Гильберта, Геделя, Черча, Поста и Тьюринга в двух формах.
Первое решение было основано на понятии особого класса арифметических функций, получивших название рекурсивных, второе – на описании точно очерченного класса процессов. Впоследствии в работах Маркова, Калужнина появилось другое толкование теории алгоритмов, поставивших в основу определение алгоритма как особого соответствия между словами в том или ином абстрактном алфавите.
Первоначально теория алгоритмов возникла в связи с внутренними потребностями теоретической математики. Математическая логика, алгебра, геометрия, математический анализ и сегодня являются областями приложения теории алгоритмов.
Другая область её приложения возникла в 40-х годах в связи с созданием быстродействующих управляющих машин.
Появление ЭВМ также способствовало развитию теории алгоритмов, вызвало к жизни разделы этой теории, имеющие ярко выраженную прикладную направленность. Это, прежде всего, алгоритмические системы и алгоритмические языки, являющиеся основой современной теории программирования, способы точного описания отображений, реализуемых цифровыми автоматами. Наконец, теория алгоритмов оказалась тесно связанной с рядом областей лингвистики, экономики, физиологии мозга, психологии, философии, естествознания. Примером одной их задач этой области может служить точное описание алгоритмов, реализуемых человеком в процессе умственной деятельности.
Изучение теории алгоритмов является целью данного курса.
В процессе изучения курса будет дано понятие алгоритма, рассмотрены такие алгоритмические системы, как рекурсивные функции, нормальные алгоритмы Маркова и другие, исследована связь теории алгоритмов и теории автоматов, изучены теоретические основы построения и анализа алгоритмических языков, формальных преобразований и оценки алгоритмов.
Теоретические положения курса являются основой для успешного освоения серии специальных дисциплин, которые будут изучаться на последующих курсах.
0 коммент.:
Отправить комментарий