Отправить другу/подруге по почте ссылку на эту страницуВариант этой страницы для печатиНапишите нам!Карта сайта!Помощь. Как совершить покупку…
московское время05.10.24 00:44:08
На обложку
Афроамериканцы США. XX век: этноисторический очеркавторы — Нитобург Э. Л.
Финтех: Путеводитель по новейшим финансовым технологиямавторы — Чишти С., Барберис Я., ред.
История евангельских христиан-баптистов в СССРИстория евангельских христиан-баптистов в СССР
б у к и н и с т и ч е с к и й   с а й т
Новинки«Лучшие»Доставка и ОплатаМой КнигоПроводО сайте
Книжная Труба   поиск по словам из названия
В ВЕСЕННЕ-ЛЕТНЕ-ОСЕННЕЕ ВРЕМЯ ВОЗМОЖНЫ И НЕМИНУЕМЫ ЗАДЕРЖКИ ПРИ ОБРАБОТКЕ ЗАКАЗОВ
Авторский каталог
Каталог издательств
Каталог серий
Моя Корзина
Только цены
Рыбалка
Наука и Техника
Математика
Физика
Радиоэлектроника. Электротехника
Инженерное дело
Химия
Геология
Экология
Биология
Зоология
Ботаника
Медицина
Промышленность
Металлургия
Горное дело
Сельское хозяйство
Транспорт
Архитектура. Строительство
Военная мысль
История
Персоны
Археология
Археография
Восток
Политика
Геополитика
Экономика
Реклама. Маркетинг
Философия
Религия
Социология
Психология. Педагогика
Законодательство. Право
Филология. Словари
Этнология
ИТ-книги
O'REILLY
Дизайнеру
Дом, семья, быт
Детям!
Здоровье
Искусство. Культурология
Синематограф
Альбомы
Литературоведение
Театр
Музыка
КнигоВедение
Литературные памятники
Современные тексты
Худ. литература
NoN Fiction
Природа
Путешествия
Эзотерика
Пурга
Спорт

/Наука и Техника/Математика

Алгоритмы и вычислительные автоматы — Трахтенброт Б. А.
Алгоритмы и вычислительные автоматы
Трахтенброт Б. А.
год издания — 1974, кол-во страниц — 200, тираж — 27500, язык — русский, тип обложки — мягк., масса книги — 160 гр., издательство — Советское радио
цена: 399.00 рубПоложить эту книгу в корзину
Сохранность книги — хорошая

Формат 84x108 1/32. Бумага типографская №2
ключевые слова — алгоритм, логик, кибернет, тьюринг, распознаван, выводимост, программирующ, вычислим, полулент, неразрешим, черч, самоприменимост, переводимост, сложн, автоматов, нейман, кодирован

Книга является общедоступным введением в теорию алгоритмов и рассматривает круг вопросов, лежащих на грани между математической логикой и теорией автомагических вычислительных машин. Рассчитана на широкий круг читателей, интересующихся кибернетикой, вычислительной математикой и техникой.


Эта книга, являющаяся введением в теорию алгоритмов, посвящена разъяснению одного из самых основных понятий математики — понятия алгоритма; в ней рассматривается круг вопросов, лежащих на грани между математической логикой и теорией автоматических вычислительных машин.

Книга состоит из трёх почти равных по объёму частей. Первая часть, «Алгоритмы» (§ 1—6), ещё не относится к теории алгоритмов, хотя в ней сплошь и рядом идёт речь об алгоритмах. Дело в том, что здесь слово «алгоритм» понимается в интуитивном смысле; теория же начинается лишь там, где термин обозначает уже точно определяемое математическое понятие. Тем не менее материал этой части, носящий подготовительный характер, весьма важен и полезен для понимания содержательных стимулов в пользу теории.

Вторая часть, «Машины Тьюринга» (§ 7—13), вводит уже непосредственно в круг основных понятий теории алгоритмов.

Третья часть, «Алгоритмические проблемы» (§ 14—23), является кульминационной. В ней излагается ряд фундаментальных результатов теории, которые, к счастью, поддаются популяризации. Более подробная характеристика содержания книги дана во введении.

Несколько слов нужно сказать о происхождении книги.

Начальным стимулом к популяризации теории алгоритмов в печати явились для автора трудности и огорчения, которые он испытывал при первых попытках устной её популяризации. Это случилось более 20 лет назад, когда автор выступил на эту тему перед своими коллегами — математиками Пензенского педагогического института. Такие идеи и результаты теории алгоритмов, как формализация вычислительного процесса, существование неразрешимых алгоритмических проблем выглядели тогда не только непривычными, но и отпугивающими.

Написание популярной статьи или небольшой книги, в которой читатель кратчайшим путём мог бы дойти до теорем об алгоритмической неразрешимости, представлялось тогда автору неотложным делом.

В результате этого появилась статья «Алгоритмы и машинное решение задач» («Математика в школе», 1956, № 4— 5); её расширенные варианты были изданы дважды (Гостехиздат, 1957 г.; Физматгиз, 1960 г.) в виде одноимённой книги, переведённой и на ряд иностранных языков.

Параграфы 1—9 и 13—16 настоящей книги целиком включают содержание упомянутых выше публикаций, которые подверглись тщательному просмотру и переработке.

Кроме того, книга содержит довольно обширный новый материал, а именно § 10—12 и § 17—24, в основу которых легли лекции, прочитанные автором студентам отделения математической лингвистики и слушателям факультета повышения квалификации Новосибирского университета. Этот материал представляет, как нам кажется, большой интерес для понимания таких разделов теории алгоритмов, которые уже не связаны непосредственно с явлением алгоритмической неразрешимости. Здесь имеются в виду главным образом следующие три проблемы: программирование (§ 10—12), качество алгоритмов (§ 17—20) и автоматы параллельного действия (§ 21—23). Впрочем, часть этого материала невозможно было включить в предыдущие издания потому, что он касается новых результатов, появившихся сравнительно недавно…

ПРЕДИСЛОВИЕ
Б. Трахтенброт
Новосибирск, Академгородок, ноябрь, 1973 г.

ОГЛАВЛЕНИЕ

Предисловие3
Введение5
 
ЧАСТЬ I. Алгоритмы11
 
§ 1. Численные алгоритмы11
1.1. Арифметические действия; алгоритм Евклида11
1.2. Численные алгоритмы13
1.3. Диофантовы уравнения14
§ 2. Алгоритмы игр15
2.1. Одиннадцать предметов16
2.2. Побеждает чёт17
2.3. Дерево игры17
2.4. Существование выигрышной стратегии20
§ 3. Алгоритмы поиска пути в лабиринте25
3.1. Лабиринты25
3.2. Алгоритм поиска26
3.3. Обоснование алгоритма поиска29
§ 4. Проблема слов33
4.1. Ассоциативные исчисления33
4.2. Проблема эквивалентности слов34
4.3. Проблема слов и лабиринты36
4.4. Построение алгоритмов37
4.5. Самосовмещения квадрата42
4.6. Уравнения в словах46
§ 5. Вычислительная машина с автоматическим управлением46
5.1. Человек-вычислитель46
5.2. Вычислительные машины48
5.3. Машинные команды50
§ 6. Программа (машинный алгоритм)52
6.1. Программа для линейных уравнений53
6.2. Повторение54
6.3. Программирование алгоритма Евклида57
6.4. Функционирование вычислительной машины58
6.5. Другие применения вычислительных машин59
 
ЧАСТЬ II. Машины Тьюринга60
 
§ 7. Необходимость уточнения понятия алгоритма60
7.1. Существование алгоритмов60
7.2. Распознавание выводимости63
7.3. Формулировка определения «алгоритма»65
§ 8. Машина Тьюринга68
8.1. Определение машины Тьюринга68
8.2. Функционирование машины Тьюринга73
§ 9. Реализация алгоритма в машине Тьюринга (тьюрингово вычисление)76
9.1. Переход от n к n + 1 в десятичной системе счисления76
9.2. Перевод унарной записи в десятичную79
9.3. Сложение81
9.4. Повторное суммирование и умножение82
9.5. Нахождение общего наибольшего делителя84
§ 10. Программирующие алгоритмы88
10.1. Стандартные программы и формальные операции над программами88
10.2. Последовательная композиция91
10.3. Параллельная композиция93
10.4. Разветвление алгоритмов94
10.5. Повторное применение алгоритма96
10.6. Языки программирования98
§ 11. Рекурсивные функции и функции, вычислимые по Тьюрингу99
11.1. Вычисление функций и алгоритмические проблемы99
11.2. Простейшие операторы102
11.3. Примитивная рекурсия103
11.4. μ-оператор107
11.5. Рекурсивные описания и их тьюрингово программирование108
11.6. Рекурсивное программирование функций, вычислимых по
    Тьюрингу112
§ 12. Варианты внешней памяти115
12.1. Полуленты и параллельная композиция116
12.2. Доказательство теоремы о полуленте117
12.3. Многоэтажные и многомерные ленты119
§ 13. Основная гипотеза теории алгоритмов120
13.1. Гипотеза и её значение120
13.2. Обоснование гипотезы123
 
ЧACTb III. Алгоритмические проблемы125
 
§ 14. Универсальная машина Тьюринга125
14.1. Алгоритм подражания125
14.2. Универсальная машина127
§ 15. Алгоритмически неразрешимые проблемы131
15.1. Теорема Черча131
15.2. Распознавание самоприменимости и переводимости132
15.3. Краткий исторический обзор134
§ 16. Невозможность алгоритма для проблемы эквивалентности слов138
16.1. Невозможность алгоритма распознавания переводимости слов138
16.2. Неразрешимость проблемы эквивалентности143
§ 17. Качество алгоритмов и вычислений144
17.1. Сигнализирующие функции144
17.2. Оценки для примеров § 9145
17.3. Поиск лучшего алгоритма146
17.4. Распознавание симметрии148
§ 18. Следы тьюринговых вычислений150
18.1. Следы150
18.2. Эксперимент с разрезанной лентой152
18.3. Замещения152
§ 19. Нижние оценки сложности153
19.1. Сложность распознавания симметрии153
19.2. Сложность перевода в десятичную запись155
§ 20. Существование сколь угодно сложных проблем156
20.1. Уточнение постановки вопроса157
20.2. Распознавание f-самоприменимости158
§ 21. Автоматы Неймана161
21.1. Системы тьюринговых машин161
21.5. Автоматы Неймана163
21.3. Пример: неймановы часы166
21.4. Нейманово моделирование машин Тьюринга167
§ 22. Задача о стрелках172
22.1. Стрелки172
22.2. Стрелки и автоматы173
22.3. Решение задачи176
§ 23. Сравнение неймановых и тьюринговых вычислений179
23.1. Кодирование179
23.2. Вычислимость по Нейману и по Тьюрингу182
23.3. Распознавание симметрии на автомате Неймана185
23.4. Тьюрингово моделирование автомата Неймана188
§ 24 заключительный190
 
Указатель195
Содержание198

Книги на ту же тему

  1. Ориентированные графы и конечные автоматы, Мелихов А. Н., 1971
  2. Основы кибернетики, Джордж Ф., 1984
  3. Машины Тьюринга и рекурсивные функции, Эббинхауз Г. Д., Якобс К., Ман Ф. К., Хермес Г., 1972
  4. Булева алгебра и конечные автоматы, Кунцман Ж., Наслен П., ред., 1969
  5. Теория алгоритмов: основные открытия и приложения, Успенский В. А., Семёнов А. Л., 1987
  6. Машины клеточных автоматов, Тоффоли Т., Марголус Н., 1991
  7. Компьютер и задачи выбора, Журавлёв Ю. И., сост., 1989
  8. Арифметика. Алгоритмы. Сложность вычислений: Популярное введение в теорию чисел и арифметическую теорию сложности, Гашков С. Б., Чубариков В. Н., 1996
  9. Задачи по теории множеств, математической логике и теории алгоритмов, Лавров И. А., Максимова Л. Л., 1975
  10. Анализ алгоритмов. Вводный курс, Макконнелл Д., 2002
  11. Введение в дискретную математику, Яблонский С. В., 1979
  12. Эволюционная кибернетика, Редько В. Г., 2001
  13. Бионика, Жерарден Л., 1971
  14. Адаптация и обучение в автоматических системах, Цыпкин Я. З., 1968
  15. Нечёткие множества в моделях управления и искусственного интеллекта, Аверкин А. Н., Батыршин И. 3., Блишун А. Ф., Силов В. Б., Тарасов В. Б., 1986
  16. Кибернетика, или управление и связь в животном и машине, Винер Н., 1958

Напишите нам!© 1913—2013
КнигоПровод.Ru
Рейтинг@Mail.ru работаем на движке KINETIX :)
elapsed time 0.020 secработаем на движке KINETIX :)