Алгоритмы вокруг нас Н.А.Криницкий Москва 1977 223стр Книга посвящена важнейшему разделу современной прикладной математики — теории алгоритмов. Рассматриваются ее наиболее важные приложения в области электронных вычислительных машин, программирования, автоматизации процессов управления. Актуальность темы, высокий научный уровень и вместе с тем популярная форма изложения делают книгу полезной как для специалистов, так и для широкого круга читателей, интересующихся последними достижениями современной науки и техники. ВВЕДЕНИЕ
Двадцатый век в области науки и техники принес человечеству много крупных достижений: радио, звуковое кино, телевидение, атомная энергия, космические полеты, электронные вычислительные машины — вот только главнейшие вехи, известные каждому. Наверное, не менее известны кибернетика, вирусология, генетика.
Но не всем известно, что крупнейшим достижением науки XX в. является теория алгоритмов — новая математическая дисциплина. Теория электронных вычислительных машин, теория и практика программирования не могут обойтись без нее. Математическая логика и кибернетика предъявляют на нее свои права. Однако она является самостоятельной наукой, которая готова служить всем наукам, и имеет свое лицо, свой предмет.
Само название — теория алгоритмов — говорит о том, что ее предмет — алгоритмы. Что это такое? Понятие алгоритма является и очень простым и очень сложным. Его простота — в многочисленности алгоритмов, с которыми мы имеем дело, в их обыденности. Но эти же обстоятельства делают его туманным, расплывчатым, трудно поддающимся строгому научному определению.
Слово «алгоритм» происходит от имени узбекского математика Хорезми (по-арабски ал-Хорезми), который в IX в. н. э. разработал правила четырех арифметических действий над числами в десятичной системе счисления. Совокупность этих правил в Европе стали называть «ал-горизм». Впоследствии это слово переродилось в «алгоритм» и сделалось собирательным названием отдельных правил определенного вида (и не только правил арифметических действий). В течение длительного времени его употребляли только математики, обозначая правила решения различных задач.
В начале XX в. понятие алгоритма стало объектом математического изучения (прежде им только пользовались), а с появлением электронных вычислительных машин получило широкую известность. Развитие электронной вычислительной техники и методов программирования способствовало уяснению того факта, что разработка алгоритмов является необходимым этапом автоматизации. То, что сегодня записано в виде алгоритма, завтра будет выполняться роботами. В настоящее время слово «алгоритм» вышло за пределы математики. Его стали применять в самых различных областях, понимая под ним точно сформулированное правило, назначение которого — быть руководством для достижения необходимого результата.
Формирование научного понятия алгоритма, ставшее важной проблемой, не закончено и в настоящее время. И хотя теория алгоритмов является математической дисциплиной, она еще не очень похожа на такие широко известные науки, как геометрия или теория чисел. Она еще только зарождается, причем тем исходным материалом, на основании которого должно быть построено широкое научное понятие алгоритма, является интуитивное понятие, тоже очень широкое, но недостаточно ясное.
Описывая зарождение теории алгоритмов, мы не пойдем путем, которым шла история этой науки (хотя о ней и расскажем), а сразу познакомим читателя с современным интуитивным понятием алгоритма. Затем это понятие уточним настолько, чтобы стали возможными изложение традиционных теорий алгоритмов, дальнейшее уточнение понятия алгоритма и, наконец, широкое формальное определение.
В реальной жизни выполнение всяких действий связано с расходом различных ресурсов: материалов, энергии и времени. Даже производя какие-либо записи, мы расходуем ресурсы (например, бумагу, чернила и время). Еще недавно некоторые задачи нельзя было решить из-за слишком большого числа необходимых для этого операций и слишком малой скорости их выполнения. Появление электронных вычислительных машин сделало такие задачи разрешимыми. Это значит, что «математизируя» понятие алгоритма, нужно абстрагироваться, отвлечься от ограниченности ресурсов, требуя только их конечности, иначе теория алгоритмов устареет как только развитие науки
И техники позволит переступить через существующие границы ресурсов.
Алгоритму в интуитивном смысле в книге противопоставляется алгоритм в математическом или формальном смысле. В последнем случае считается, что понятие определено методами, принятыми в математике, и основывается либо на других понятиях, имеющих математическое определение, либо на первоначальных, описанных настолько четко, что их свойства могут быть приняты за аксиомы новой теории.
Для понимания книги не нужна специальная подготовка, но порою требуется большая внимательность, например при чтении главы 4, в которой коротко изложены традиционные теории алгоритмов. Об электронных вычислительных машинах и программировании в этой книге сказано очень мало. Лишь столько, сколько нужно для того, чтобы стала ясной связь теории алгоритмов и этой области, которая не только нуждается в результатах теории алгоритмов, но и порождает многие идеи этой теории.
Теорию алгоритмов, которой посвящена эта книга, мы называем содержательной в том смысле, что именно алгоритмы как таковые во всем их разнообразии являются ее предметом. В этом отношении она является противоположностью традиционных теорий, которые изучали вопросы существования и несуществования алгоритмов путем сведения вопросов к исследованию какого-либо одного узкого класса алгоритмов и потому очень многие важнейшие проблемы оставляли вне своего поля зрения.
ОГЛАВЛЕНИЕ
Введение............. ?'
Глава 1. Алгоритмы в интуитивном смысле..... 6
§ 1. «Алгоритмические джунгли»...... 6
§ 2. Исходные данные и результаты.
Массовость алгоритма.......... Ю
§ 3. Потенциальная осуществимость алгоритма................... 14
§ 4. Понятность алгоритма.......... 16
§ 5. Рекурсивные определения........ 18
§ 6. Определенность алгоритма....... 19
§ 7. Выводы.................. 21
Глава 2. Создание алгоритмов.............. 23
§ 1. Роль алгоритмов в науке и технике . 23
§ 2. Как возникают алгоритмы ....... 24
§ 3. Алгоритмы в математике ....... 28
§ 4. Алгоритм Евклида............ 29
§ 5. Решето Эратосфена........... 31
§ 6. Алгоритм разложения на простые множители. Определение наименьшего кратного двух чисел......... 34
§ 7. Распознавание алгебраического тождества................... 37
§ 8. Задачи на построение алгоритмов ... 40
Глава 3. Кризис математики в начале XX в..... 43
§ 1. Арифметизация математики...... 43
§ 2. Теория множеств............ 45
§ 3. Кардинальные числа.......... 51
§ 4. Антиномии................ 53
§ 5. Выводы из антиномий.......... 57
Глава 4. Традиционные теории алгоритмов..... 61
§ 1. Рекурсивные функции......... 61
§ 2. Машины Тьюринга............ 69
§ 3. Нормальные алгорифмы Маркова . . 75
§ 4. Эквивалентность описанных теорий . 79
Глава 5. Алгоритмически неразрешимые проблемы 81
§ 1. Массовые проблемы. Неразрешимость
проблем................... 81
§ 2. Экстраалгоритм и три неразрешимые
проблемы................. 82
§ 3. Некоторые замечания.......... 86
Глава 6. Электронные вычислительные машины
и программирование .......... 89
§ 1. Устройство ЭВМ............. 89
§ 2. Процессоры ЭВМ. Рабочий цикл ... 92
§ 3. Что такое программа.......... 100
§ 4. Особенности современных ЭВМ .... 107
§ 5. Входные языки программирования . . 116
§ 6. Необходимость содержательной теории алгоритмов. Какой она должна
бьцть..........'............ 120
Глава 7. Формальные языки.............. 123
§ 1. Анализ естественного языка...... 123
§ 2. Искусственные языки. Формальные
языки................... 130
§ 3. Буквы, связи, оболочки, конструкции 133
§ 4. Формальные грамматики........ 1^0
§ 5. Нотация Бекуса. Тезаурусы...... 145
Глава 8. Расширение точного понятия алгоритма 151
§ 1. Что такое операция?.......... 151
§ 2. Натуральные операции......... 152
§ 3. Линеаризация и делинеаризация ... 158
§ 4. Первичные алгоритмы.......... 164
§ 5. Натуральные алгоритмы......... 167
§ 6. Ограничения на структуру исходных
данных сняты............... 171
§ 7. Алгоритмы в широком смысле. Еще
две степени свободы.......... 172
§ 8. Соотношение с алгоритмами в интуитивном смысле.............. 176
§ 9. Формальная семантика формального
языка.................. 177
Глава 9. Математическое обеспечение ЭВМ..... 181
§ 1. Анализ ЭВМ и программ........ 181
§ 2. Что такое математическое обеспечение
ЭВМ...................... 187
§ 3. Функциональная классификация программ математического обеспечения
ЭВМ................... 190
§ 4. Операционные системы.......... 191
Глава 10. Алгоритмы и автоматизация процессов 196
§ 1. Использование ЭВМ для управления 196
§ 2. Информационные системы...... 198
§ 3. Алгоритмизация процессов...... 204
§ 4. Язык алгоритмизации процессов . . . 207
§ 5. Наука и искусство алгоритмизации . . 213
Заключение ................ 217
| 1. Может ли машина мыслить? Может ли человек решить алгоритмически
неразрешимую проблему?........ 217
§ 2. Детерминированность машин. Самообучение.................. 218
§ 3. Последние замечания......... 220