3. ТЕОРИЯ АЛГОРИТМОВ

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

Теория алгоритмов — раздел математики, изучающий общие свойства алгоритмов. Эта теория тесно связана с математической логикой, поскольку на понятие алгоритма опирается одно из центральных понятий математической логики — понятие исчисления. По существу вся математика связана с теми или иными алгоритмами. Одним из наиболее замечательных достижений математической логики и теории алгоритмов явилась разработка понятия рекурсивной функции и формулировка тезиса Чёрча, утверждающего, что понятие рекурсивной функции является уточнением интуитивного понятия алгоритма.

Само понятие «алгоритм» сформировалось лишь в первой половине XX века. Началом систематической разработки теории алгоритмов можно считать 1936 году, когда А. Чёрч опубликовал первое уточнение понятия вычислимой функции и привёл первый пример функции, не являющейся вычислимой. Приблизительно в это же время появились первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин). В дальнейшем теория алгоритмов получила развитие в трудах многих математиков (А. М. Тьюринг, Э. Л. Пост, С. К. Клини, А. А. Марков, А. Н. Колмогоров и др.).

Алгоритмом называется общий единообразный, точно определенный способ решения любой задачи из данной массовой проблемы.

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

63