Читать онлайн «Алгоритмы и машинное решение задач»

ЗГоп1|лярныс лекции ПО МАТЕМАТИКЕ Б. А. ТРАХТЕНБРОТ АЛГОРИТМЫ И МАШИННОЕ РЕШЕНИЕ ЗАДАЧ ГОГУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО ТЕХНИКО-ТЕОРЕТИЧЕСКОЙ ЛИТЕРАТуРЫ МОСКВА 195 7 ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ ВЫПУСК 26 Б. А. ТРАХТЕНБРОТ АЛГОРИТМЫ И МАШИННОЕ РЕШЕНИЕ ЗАДАЧ ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО ТЕХНИКО-ТЕОРЕТИЧЕСКОЙ ЛИТЕРАТУРЫ МОСКВА 1957 11-2-1 АННОТАЦИЯ Книга Б. А. Трахтенброта рассматривает в популярной форме основные вопросы тео- теории алгоритмов и связь этой теории с со- современной машинной математикой. Автор подробно рассказывает об истории разви- развития понятия алгоритм, о принципе работы со- современных быстродействующих вычисли- вычислительных машин, об основах программирова- программирования, о схеме машины Тьюринга, об алгорит- алгоритмически неразрешимых проблемах. Книга рассчитана на школьников стар- старших классов, преподавателей, инженерно- технических работников н всех лиц, инте- интересующихся перспективами применения но- новой вычислительной техники. СОДЕРЖАНИЕ Предисловие 4 Введение 5 § 1. Численные алгоритмы 7 § 2. Алгоритмы для решения логических задач 12 § 3. Проблема слов 23 § 4. Вычислительная машина с автоматическим управлением . 37 § 5. Программа (машинный алгоритм) 44 § 6. Необходимость уточнения понятия алгоритма 52 § 7. Машина Тьюринга 60 § 8. Реализация алгоритма в машине Тьюринга 67 § 9. Основная гипотеза теории алгоритмов 79 § 10. Универсальная машина Тьюринга 82 § 11. Алгоритмически неразрешимые проблемы 89 Заключительные замечания 94 1* ПРЕДИСЛОВИЕ Настоящая книга, являющаяся элементарным введением в теорию алгоритмов, посвящена разъяснению одного из са- самых основных понятий математики — понятия алгоритма; в ней рассматривается круг вопросов, лежащих на грани между математической логикой и теорией автоматических вычислительных машин. В основу книги легли популярные лекции и обзорные доклады, с которыми автор выступал в г. Пензе, начиная с 1951 года, перед разными аудиториями, а также одно- одноименная статья, написанная им для журнала «Математика в школе» (№№ 4—5, 1956 г. ). Тем, кто пожелает более основательно ознакомиться с этими вопросами, можно рекомендовать следующую лите- литературу: 1. А. А. Марков, Теория алгорифмов, Труды матем. ин-та им. Стеклова, т. XLII, Изд-во Академии наук СССР, Москва, 1954 г. 2. Р. Петер, Рекурсивные функции, Москва, 1954 г. 3. А. И. Китов, Электронные вычислительные машины, Изд-во Советское радио, Москва, 1956 г. 4. С. Клин и, Введение в метаматематику, ИЛ, Москва, 1956 г. ВВЕДЕНИЕ В послевоенные годы получили большое развитие авто- автоматические быстродействующие вычислительные машины, которые теперь применяются для решения самых разнообраз- разнообразных математических и логических задач. Характерная осо- особенность этих машин, отличающая их от прежних вычисли- вычислительных машин, заключается в том, что при выполнении своих функций, начиная с того момента, как в них введены начальные данные и программа, они работают без всякого вмешательства человека вплоть до выдачи окончательного результата.