Учебное пособие по информатике 2014. Основы информатики
 Скачать 4.61 Mb.
|
|
2.5 Нормальный алгоритм Маркова По аналогии с интуитивным определением алгоритма определим понятие «алгоритм в алфавите А»: I. Алгоритмом в алфавите А называется всякое общепонятное точное предписание, определяющее потенциально осуществимый процесс над словами из А, допускающий любое слово в качестве исходного и последовательно определяющий новые слова в этом алфавите. Алгоритм применим к некоторому слову Р, если, отправляясь от этого слова и действуя согласно предписаний, мы получим в конце концов новое слово Q, на котором процесс оборвется. Будем тогда говорить, что алгоритм перерабатывает Р в Q. Например, следующее предписание удовлетворяет нашему определению. Перепиши заданное слово, начиная с конца. Полученное слово есть результат. Остановка. Этот алгоритм представляет собой совершенно точное предписание, применимое к любому слову. Однако определение I. слишком широко: уточнение понятия «алгоритм в алфавите А» связано с использованием аппарата подстановок, т.е. с построением ассоциативного исчисления. II. Будем считать, что алгоритм в алфавите А задается в виде некоторой системы допустимых подстановок, дополненной общепонятным, точным предписанием о том, в каком порядке и как нужно применять допустимые подстановки, и когда наступает остановка. Так как алфавит и система допустимых подстановок задают ассоциативное исчисление, которому, как мы знаем, можно поставить в соответствие бесконечный лабиринт, то во вторую составную часть этого определения алгоритма (т.е. общепонятное и точное предписание о том, как пользоваться подстановками) можно понимать как точное предписание о способе движения в бесконечном лабиринте. Приведем пример алгоритма в алфавите А в смысле II. 40 Пусть алфавит А содержит три буквы: А = {а, b, с}, а алгоритм определен с помощью системы подстановок bca ab ad cca cc cd и следующего указания о способе применения этих подстановок: исходя из произвольного слова Р, следует просмотреть схему подстановок в том порядке, в каком они выписаны, разыскивая первую формулу, левая часть которой входит в Р. Если же такой формулы не найдется, то процесс обрывается сразу же. В противном случае берется первая из найденных формул и делается подстановка ее правой части вместо первого вхождения ее левой части в слово Р, что дает новое слово Р 1 , в алфавите А. Затем слово Р 1 играет роль Р, т.е. вновь берется в качестве исходного, и процесс повторяется. Остановка наступает в том случае, если на n-м шаге получено слово P n , в которое не входит ни одна из левых частей формул схемы подстановок. Итак, схема подстановок вместе с указанием, как ими пользоваться, определяет алгоритм в алфавите А. Этот алгоритм перерабатывает слово babaac в слово bbcaac (применена 3-я формула), слово cbacacb - последовательно в слова ccacacd, ccacacc, abcacc и, наконец, в bcacacc, на котором процесс обрывается; слово bсасаbс порождает бесконечно повторяющуюся последовательность слов bcacabc: bcacbcac, bcaccac, bcacabc и т.д., т.е. остановка нe наступит, и, следовательно, к слову bcacabc наш алгоритм неприменим. Наш алгоритм несколько напоминает такой способ задания движения в бесконечном лабиринте: выйдя на какую-либо площадку, иди в первый коридор направо и т.д. Остановка наступит, когда придешь в тупик. Ясно, что здесь также может быть три случая: отходя от данной площадки, мы можем либо попасть в тупик (сравним слово сbасасb), либо бесконечно кружиться по циклу (сравним слово bcacabc), либо двигаться бесконечно долго, не попадая в циклы. С первого взгляда можно решить, что определение алгоритма в смысле II уже, чем определение в смысле I. Однако оказывается, что на деле такого сужения нет, ибо для любого известного алгоритма в смысле I может быть построен эквивалентный ему алгоритм в смысле II. Это, конечно, не доказательство того, что определения I и II равносильны: такого доказательства не может существовать вообще в силу неточности и расплывчатости обоих определений (везде фигурируют слова «общепонятное, точное предписание»). Во всяком случае, очевидно, что определение II - шаг вперед по пути уточнения понятия «алгоритм». Определим теперь понятие эквивалентности алгоритмов: два алгоритма А 1 и А 2 в некотором алфавите называются эквивалентными, если 41 области их применимости совпадают, и результаты переработки ими любого слова из общей области применимости также совпадают. Иначе говоря, если алгоритм А 1 применим к некоторому слову Р, то и А 2 должен быть применим к этому слову, и наоборот; Оба алгоритма должны перерабатывать слово Р в некоторое слово Q. Если же один из алгоритмов неприменим к некоторому слову B, то и другой алгоритм должен быть неприменим к нему. Для того, чтобы дать точное математическое определение алгоритма, потребовалось сделать еще один шаг по пути дальнейшего уточнения. Этот шаг был сделан А. A. Марковым. Построенный им нормальный алгоритм, так же, как и алгоритм в смысле определения II, выражен в терминах системы подстановок; однако вместо расплывчатого «общепонятного указания» о том, как пользоваться подстановками, Марков дал стандартные, раз и навсегда определенные точные указания о порядке использования подстановок. Определение нормального алгоритма Маркова таково: Задается алфавит А и фиксируется схема подстановок. Алгоритм предписывает, исходя из произвольного слова P в алфавите А, просмотреть формулы подстановок в том порядке, в каком они заданы в схеме, разыскивая формулу с левой частью, входящей в Р. Если такой формулы не найдется, то процесс обрывается. В противном случае берется первая из таких формул и делается подстановка ее правой части вместо первого вхождения ее левой части в Р, что дает новое слово Р 1 , в алфавите А. После только что выполненного первого шага процесса приступают ко второму его шагу, отличающемуся от первого только тем. что роль Р играет Р 1 . Далее делают аналогичный третий шаг и т.д. до тех пор, пока не придется оборвать процесс. Оборваться же он может лишь двумя способами: во-первых, когда мы получим такое слово Р n , что ни одна из левых частей формул схемы подстановок не будет в него входить; во-вторых, когда при получении слова Р n нам придется применить последнюю формулу. В обоих этих случаях мы считаем, что наш алгоритм перерабатывает слово Р в слово Р n Как мы видим, приведенный в определении II пример является примером «почти нормального» алгоритма. Вся разница состоит в том, что там остановка наступает лишь в одном случае, когда ни одна из подстановок неприменима, а здесь остановка может наступать в двух случаях. Различные нормальные алгоритмы отличаются друг от друга лишь алфавитами и системами допустимых подстановок. Чтобы задать какой-либо нормальный алгоритм достаточно задать алфавит и систему подстановок. Понятие алгоритма в некотором алфавите было уточнено Марковым следующим образом: всякий алгоритм в алфавите А эквивалентен некоторому нормальному алгоритму в этом же алфавите. Это утверждение является гипотезой; оно не может быть строго доказано, так как с одной стороны фигурирует расплывчатое понятие «всякий алгоритм», а с другой стороны - точное понятие «нормальный алгоритм». На это утверждение можно смотреть как на закон, который не доказан, но который проверен и подтвержден всем нашим опытом. 42 В пользу высказанной гипотезы говорит и тот факт, что никому еще не удалось сформулировать пример такого алгоритма в алфавите А, для которого нельзя было бы построить эквивалентный ему нормальный алгоритм. Возвращаясь к содержанию последних абзацев предыдущего параграфа, естественно рассматривать алгоритм Маркова как удобную «стандартную форму» для задания любого алгоритма, т. е. предположить, что вообще любой алгоритм может быть задан в форме нормального алгоритма Маркова. Разумеется, это не более чем гипотеза, и притом значительно менее ясная, чем гипотеза Маркова, о которой шла речь выше, так как она не может даже быть высказана в точных терминах, но интуитивный смысл ее очевиден. Как только мы примем эту гипотезу, сразу становится ясным один из путей, каким можно строго проводить доказательство алгоритмической неразрешимости того или иного круга проблем. Например, чтобы доказать алгоритмическую неразрешимость проблемы слов, т.е. доказать, что не существует алгоритма, позволяющего для любого ассоциативного исчисления и для произвольных заданных слов P и Q, ответить на вопрос: эквивалентны ли эти два слова, достаточно было построить пример ассоциативного исчисления и доказать, что для этого исчисления не существует нормального алгоритма, распознающего эквивалентность слов. Впервые такие примеры были построены А.А. Марковым в 1946 г. и Э. Постом в 1947 г. После этого стало ясно, что не существует алгоритма для распознавания эквивалентности слов в любом ассоциативном исчислении. Примеры ассоциативных исчислений, приведенные Марковым и Постом, были весьма громоздкими, насчитывали сотни допустимых подстановок. Позже ленинградский математик Г.С. Цейтин привел пример ассоциативного исчисления, насчитывающего всего лишь семь допустимых подстановок, в котором проблема эквивалентности слов также алгоритмически неразрешима. В качестве иллюстрации приведем одну схему доказательства алгоритмической неразрешимости. Пусть в некотором алфавите А={а 1 , а 2 , … а n } задан с помощью системы подстановок нормальный алгоритм U. В записи этого алгоритма, кроме букв алфавита А, содержатся символы и , . Приписав этим символам новые буквы а n+1 и а n+2 мы получим возможность изображать алгоритм U словом в расширенном алфавите А={а 1 , а 2 , … а n+2 } . Применим теперь алгоритм U к слову, которое его изображает. Если алгоритм U перерабатывает это слово в некоторое иное слово, после чего наступает остановка, то это означает, что алгоритм U применим к собственной записи. Такой алгоритм назовем самоприменимым. В противном случае алгоритм будем называть несамоприменимым. Естественно, возникает задача распознавания самоприменимости: по записи данного алгоритма определить, самоприменим этот алгоритм или нет. 43 Решение этой задачи мыслится в виде построения некоторого нормального алгоритма V. который, будучи применен ко всякой записи самоприменимого алгоритма U, перерабатывает эту запись в некоторое слово М, а примененный ко всякой записи несамоприменимого алгоритма U, перерабатывает эту запись в некоторое иное слово L. В этом случае по результату применения распознающего алгоритма V мы могли бы узнать, является ли данный алгоритм U самоприменимым или нет. Доказано, что такого нормального алгоритма V не существует: тем самым доказано, что проблема распознавания самоприменимости алгоритмически неразрешима. Доказательство проводится от противного. Допустим, что нормальный алгоритм V распознавания построен и перерабатывает всякую запись самоприменимого алгоритма в слово М, а всякую запись несамоприменимого алгоритма в слово L. Тогда, путем некоторого изменения системы подстановок алгоритма V можно построить иной алгоритм Ũ, который всякую записи несамоприменимого алгоритма по-прежнему перерабатывает в слово L, а ко всякой записи самоприменимого алгоритма неприменим (остановка никогда не наступает). Итак, Ũ применим ко всякой записи несамоприменимого алгоритма (перерабатывая ее в слово L) и неприменим к записи самоприменимых алгоритмов (остановка не наступает). Однако это приводит к противоречию. Действительно: 1. Пусть Ũ самоприменим, т.е. он применим к собственной записи в виде слова (остановка наступает). Но это свидетельствует как раз о том, что Ũ несамоприменим. 2. Пусть Ũ несамоприменим, тогда он применим к своей записи (так как он применим к любой записи несамоприменимого алгоритма): но это означает как раз, что Ũ самоприменим. Полученное противоречие доказывает алгоритмическую неразрешимость проблемы распознавания самоприменимости. Итак, решая какую-либо задачу, приходится считаться с тем, что алгоритм для ее решения может существовать, а может и не существовать. Поэтому одновременно с поиском нужного алгоритма приходится направлять усилия и на доказательство его несуществования. Отметим еще, что несуществование алгоритма для решения того или иного класса задач не означает неразрешимости вообще; это означает лишь, что рассматриваемый класс задач настолько широк, что единого эффективного метода для решения всех задач не существует. Так, хотя в ассоциативном исчислении Г.С. Цейтина общая проблема распознавания эквивалентности слов алгоритмически неразрешима, тем не менее для конкретных пар слов мы обычно тем или иным способом можем сделать вывод об их эквивалентности или неэквивалентности. До уточнения понятия «алгоритм» в математике было две точки зрения: 1) Все проблемы, для решения которых, пока не удалось найти алгоритм, алгоритмически разрешимы, но искомый алгоритм еще не найден, 44 потому что не хватает средств в современной математике для его построения. Иначе говоря, в наше время ситуация в ряде проблем похожа на ситуацию, когда пытались найти площадь круга с помощью циркуля и линейки или решить уравнение n-ой степени в радикалах. Естественно, что решения найдено не было, так как для этого использовались недостаточные средства. Может быть и нам для решения проблем, которые мы называем алгоритмически неразрешимыми, просто не хватает средств современной математики, и построение искомых алгоритмов дело завтрашнего дня? 2) Существуют классы задач, для решения которых не существует алгоритма вообще. Иначе говоря, есть такие проблемы, которые нельзя решать механически с помощью формальных рассуждений и вычислений и которые требуют творческого мышления. Утверждение это тем более сильно, что оно имеет характер прогноза на все будущие времена, применительно ко всем будущим средствам. Не тратьте сил зря на поиски несуществующих алгоритмов! Но как могли бы сторонники второго взгляда доказать несуществование какого-либо алгоритма? До тех пор, пока в определении алгоритма так или иначе фигурируют слова «общепонятное точное предписание», о таком доказательстве нельзя и думать, так как невозможно вести доказательство путем перебора всех «общепонятных точных предписаний» и показа того, что ни одно из них не годится. Поэтому само существование второй точки зрения возможно только благодаря наличию смелых гипотез с существовании «стандартных форм» для любого алгоритма, например, нормального алгоритма Маркова, т.е. гипотез, делающих возможным сформулировать снятия «алгоритм» и «алгоритмически неразрешимая проблема» в точных терминах. 2.6 Языки программирования Компьютер не может работать без программного обеспечения - то есть, программ, которые управляют различными аппаратными компонентами компьютера в последовательности, определенной пользователем. Простой заменой программы компьютер может быть настроен так, чтобы работать различными способами. Другими словами, программное обеспечение обеспечивает компьютер универсальной вычислительной способностью. Рассмотрим простую вычислительную задачу: прибавить число X, хранящееся в памяти по адресу 8, к числу Y в памяти с адресом 10 и затем сохранить результат в памяти с адресом 5. Это задание может быть записано как следующая программа, состоящая только из трех команд, хотя программа в общем случае может состоять из любого числа команд: ЗАГРУЗИТЬ 8 ДОБАВИТЬ 10 ХРАНИТЬ 5 Первая команда, ЗАГРУЗИТЬ 8, считывает число X из памяти по адресу 8, и помещает его в арифметико-логическое устройство (АЛУ), удаляя 45 любое число, ранее помещенное там. Вторая команда добавляет число Y, хранящееся в памяти по адресу 10, к X в АЛУ. Третья команда сохраняет сумму, содержащуюся в АЛУ, в памяти с адресом 5. Числа X и Y не должны быть упомянуты явно в этой программе, потому что принято, что они были сохранены в соответствующих ячейках памяти предыдущими командами, которые здесь не показываются. Первая часть каждой команды, типа ЗАГРУЗИТЬ, называется кодом операции, а вторая часть, типа 8, называется операндом. Некоторые вычислительные среды имеют команды, в каждой из которых содержатся два или три операнда. Например - ДОБАВИТЬ 8 10 означает сложение чисел, хранящихся в памяти по адресам 8 и 10. Команды в программе называются кодом. Каждая программа составляется по определенным правилам, которые называются языком программирования, которых существует огромное количество. Компьютер может непосредственно понимать только машинный язык, который является уникальным для каждого отдельного компьютера (т.е. архитектуры). Таким образом, команда ЗАГРУЗИТЬ 8, в предыдущем примере, могла бы быть записана, как 010100001000 в машинном коде, где 0101 в начале означает операцию ЗАГРУЗИТЬ и где последующие символы 00001000 означают десятичное число 8. Хотя компьютеры легко работают с машинным языком, такой код затруднителен для записи и чтения людьми. Поэтому программисты используют языки, которые являются удобочитаемыми для них. Например, мнемонический код операции ЗАГРУЗИТЬ на человеческом языке - гораздо проще для понимания, чем 0101 на машинном языке. Такой читаемый человеком язык должен транслироваться на машинный язык программами специального назначения, называемыми языковыми процессорами. Языки программирования могут быть классифицированы с точки зрения удобочитаемости. Языки, удобочитаемость которых является близкой к таковой для машинных языков, называют языками низкого уровня, например, ассемблеры. Те языки, чья удобочитаемость является близкой к человеческим языкам, называются языками высокого уровня. Бейсик и Паскаль - примеры языков высокого уровня. Программы, написанные на языках низкого уровня, обычно могут быть выполнены быстрее и требовать меньшего пространства памяти в компьютере, чем написанные на языках высокого уровня. КОБОЛ, язык высокого уровня, который широко использовался для деловых прикладных приложений, имеет структуру, подобную структуре английского языка и его словарю. Рассмотрим следующий пример программы на COBOL: IF ITEM -- COUNT = 0 THEN NEXT SENTENCE ELSE 46 COMPUTE AVERAGE--PRICE = AVERAGE -- PRICE / ITEM -- COUNT. MOVE AVERAGE -- PRICE TO PRINT--AVERAGE--PRICE PERFORM 300 – PRINT – DETAIL -- LINE. Слово COMPUTE, например, легко будет понято пользователями, знакомым с английским языком, без проблем, поэтому, например, COMPUTE, может быть сокращено до СОМР или даже до еще более короткого слова, требующего меньшее количество памяти. Языки программирования классифицируются с различных точек зрения, таких, как основные области их приложений или способы решения проблем. Фортран и Алгол классифицированы как языки программирования для научных или проектных приложений, в то время как Кобол и Лисп подходят для деловых проблем. Некоторые языки, типа PL/1, Бейсик, С и Паскаль, являются универсальными языками. Например, и научные, и проектные программы, и языковые процессоры, и деловые программы, как правило, написаны на различных диалектах языка C (например, C++, C# и т.д.). Команды, как описано ранее, являются шагами программ, написанных в трансляторах или машинных языках. Каждый шаг языка высокого уровня называется инструкцией. Каждая команда определяет операцию АЛУ, памяти или других аппаратных средств. Каждая инструкция, однако, определяет вычислительную задачу, которая не может быть непосредственно связана с аппаратными действиями и которая в общем случае соответствует многим командам, когда транслируется в ассемблер или машинный язык. |