Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Делай, как делается (правила для решения задач/. Глава 5. ТЕОРИЯ АЛГОРИТМОВ Теория алгоритмов является одной из ветвей (разделов) математической логики. Первоначально теория алгоритмов возникла в связи с внутренними потребностями теоретической математики. Основания математики, алгебра, геометрия и анализ остаются и сегодня одной из основных областей приложения теории алгоритмов. Другая область ее приложения возникла в 40-х годах XX века в связи с созданием быстродействующих вычислительных машин. Наконец, теория алгоритмов оказалась тесно связанной и с рядом областей лингвистики, экономики и философии. §1. Неформальное понятие алгоритма Понятие алгоритма принадлежит к числу основных понятий математики. Под алгоритмом понимают точное предписание о выполнении в определенном порядке системы операций для решения всех задач некоторого данного типа. Простейшими алгоритмами являются правила, по которым выполняется та или другая из четырех арифметических операций в десятичной системе счисления. Само слово алгоритм (алгорифм) происходит от имени узбекского математика Аль-Хорезми, который в IX веке систематизировал правила арифметических операций. Полное имя Аль-Хорезми: Аль-Хорезми Абу Абдалла Мухаммед бен Муса аль-Маджуси. Рассмотрим правила сложения целых чисел в десятичной системе счисления. Этот алгоритм перерабатывает выражение, записанное с использованием цифр 0,1,...,9. Результатом является выражение, записанное с помощью цифр 0,1,...,9. Таким образом, имеем процедуру преобразования некоторых символьных входов (цифр, означающих слагаемые) в определенные символьные выходы (цифры, означающие сумму). В общем случае понятно, что алгоритм есть преобразование каких-то входов, записанных с помощью некоторых символов, в выходы, записанные тоже с помощью символов. Грубо говоря, алгоритм - это детерминированная процедура, которую можно применять к любому элементу некоторого класса символьных входов и которая ^ ^рекомендация по методу (правилу, алгоритму) решения задач в древнеегипетском папирусе Ринда (2000 г. до н.э.) 146