Электронная библиотека
Программисту веб-дизайнеру
Другие материалы
Бесплатная электронная библиотека. Скачать книги DJVU, PDF бесплатно
Б.А. Трахтенброт, Алгоритмы и машинное решение задач
• Бесплатно скачать книгу, объем 560 Кб, формат .djvu
§ 1. Численные алгоритмы
§ 2. Алгоритмы для решения логических задач
§ 3. Проблема слов
§ 4. Вычислительная машина с автоматическим управлением
§ 5. Программа (машинный алгоритм)
§ 6. Необходимость уточнения понятия алгоритма
§ 7. Машина Тьюринга
§ 8. Реализация алгоритма в машине Тьюринга
§ 9. Основная гипотеза теории алгоритмов
§ 10. Универсальная машина Тьюринга
§ 11. Алгоритмически неразрешимые проблемы
Краткая аннотация книги
Книга Б.А. Трахтенброта рассматривает в популярной форме основные вопросы теории алгоритмов и связь этой теории с современной машинной математикой. Автор подробно рассказывает об истории развития понятия алгоритм, о принципе работы современных быстродействующих вычислительных машин, об основах программирования, о схеме машины Тьюринга, об алгоритмически неразрешимых проблемах. Книга рассчитана на школьников старших классов, преподавателей, инженерно-технических работников н всех лиц, интересующихся перспективами применения новой вычислительной техники.
Настоящая книга, являющаяся элементарным введением в теорию алгоритмов, посвящена разъяснению одного из самых основных понятий математики - понятия алгоритма; в ней рассматривается круг вопросов, лежащих на грани между математической логикой и теорией автоматических вычислительных машин. В основу книги легли популярные лекции и обзорные доклады, с которыми автор выступал в г. Пензе, начиная с 1951 года, перед разными аудиториями, а также одноименная статья, написанная им для журнала "Математика в школе" (NN 4-5, 1956 г.).
В послевоенные годы получили большое развитие автоматические быстродействующие вычислительные машины, которые теперь применяются для решения самых разнообразных математических и логических задач. Характерная особенность этих машин, отличающая их от прежних вычислительных машин, заключается в том, что при выполнении своих функций, начиная с того момента, как в них введены начальные данные и программа, они работают без всякого вмешательства человека вплоть до выдачи окончательного результата. Производительность современных электронных автоматических машин огромна. Область применения автоматических машин продолжает расти: машины решают сложные системы уравнений, переводят с одного языка на другой, играют в шахматы и т. д. Очень велики перспективы применения на производстве автоматических машин, осуществляющих управление всем технологическим процессом в масштабе крупного завода. Кроме того, возможность быстрой и надежной математической обработки, а также анализа экспериментальных данных создает предпосылки для появления новых, ранее недоступных методов исследования во многих областях науки.
Теперь уже все признают, что автоматические вычислительные машины представляют собою мощные орудия умственного труда, способные не только облегчить умственный труд человека, но и полностью освободить человека от некоторых видов большой и напряженной умственной работы.
Вместе с тем достигнутые успехи могут породить и действительно порождают много неоправданных иллюзий и чисто фантастических прогнозов по поводу всемогущества машин. Особо следует указать на рекламную шумиху, поднятую в части зарубежной печати о "гигантском электронном мозге", об автоматах, способных решать любые задачи и заменить творческий труд ученого.
В связи с указанными обстоятельствами приобретает большую актуальность и остроту вопрос о том, какие виды умственной работы могут выполнять автоматические вычислительные машины. Этот вопрос с определенной точки зрения рассматривается и решается в современной теории алгоритмов, являющейся важной ветвью математической логики. Для математической логики характерно исследование сущности таких понятий, как "вычислительный процесс", "математическое доказательство", "алгоритм" и т. д. Еще за несколько лет до создания современных электронных автоматических вычислительных машин в математической логике были выработаны точные понятия "алгоритм" и общая схема автоматической вычислительной машины (машина Тьюринга), а также выяснена тесная связь между алгоритмами и машинами. Это позволило установить ряд важных теорем, раскрывающих сущность процессов, реализуемых в автоматических машинах; в частности, было строго доказано существование таких проблем, для которых невозможно машинное решение. Рассмотрению связи между алгоритмами и машинами и посвящена предлагаемая книга.
В §§ 1-3 на ряде примеров разъясняется, что такое алгоритм, и строятся алгоритмы для решения некоторых классов математических и логических задач.
В §§ 4-5 изложены принципы устройства электронных вычислительных машин и составления программ, т. е. алгоритмов, приспособленных для реализации их в машинах.
Параграфы 6-11 посвящены ряду важных фактов теории алгоритмов, причем в качестве основного понятия теории взято понятие машины Тьюринга.
Чисто техническая громоздкость многих доказательств не позволяет в такой небольшой книжке давать их полное изложение. Поэтому имеются некоторые отступления от строгости и полноты изложения, которые, однако, как нам кажется, не мешают, а, наоборот, благоприятствуют лучшему уяснению существа дела. Для общности картины кое-что дано в обзорном порядке (§ 6).
Примечание. Сохраняйте книги на мобильный телефон и скачивайте их с Вашего телефона на компьютер. Удобное скачивание книг через мобильный телефон (в память телефона) и на Ваш компьютер через мобильный интерфейс. Быстрый Интернет без излишних тэгов. Материал носит неофициальный характер и приведен для ознакомления. Прямые ссылки на файлы книг запрещены.