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

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

Теория алгоритмов: основные открытия и приложения — Успенский В. А., Семёнов А. Л.
Теория алгоритмов: основные открытия и приложения
Успенский В. А., Семёнов А. Л.
год издания — 1987, кол-во страниц — 288, тираж — 25000, язык — русский, тип обложки — мягк., масса книги — 220 гр., издательство — Физматлит
серия — Библиотечка программиста
цена: 500.00 рубПоложить эту книгу в корзину
Сохранность книги — хорошая

Р е ц е н з е н т:
член-корр. АН СССР Ю. Л. Ершов

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

Понятие алгоритма ивляется одним из наиболее фундаментальных понятий информатики и математики. Систематическое изучение алгоритмов привело к созданию особой дисциплины, пограничной между математикой и информатикой — теория алгоритмов.

В книге даётся обзор важнейших достижений теории алгоритмов за последние полвека, т.е. с момента зарождения этой теории. Излагаются в систематизированном виде основные открытия, связанные с понятием алгоритма, приложения теории алгоритмов к математической логике, теории вероятностей, теории информации и др. Рассматривается влияние теории алгоритмов на алгоритмическую практику.

Для специалистов по математике, информатике, кибернетике, а также для студентов вузов.

Библиогр. 465 назв.

ОГЛАВЛЕНИЕ

Предисловие6
Обозначения и терминология11
Введение13
 
Ч а с т ь  I.  Основные открытия общей теории алгоритмов15
 
§ 1.0. Предварительные понятия теории алгоритмов: конструктивные
объекты и их ансамбли, локальные свойства и локальные действия17
1.0.1. Первые примеры конструктивных объектов: слова и деревья
(18). 1.0.2. Конструктивные объекты: попытка общего описания
(19). 1.0.3. Локальные свойства и локальные действия:
неформальное изложение (21). 1.0.4. Колмогоровские комплексы
(22). 1.0.5. (Б, k)-комплексы (24). 1.0.6. Ансамбли (25). 1.0.7.
Локальные свойства и локальные действия: формальное определение
(27).
§ 1.1. Общее понятие алгоритма как самостоятельное (отдельное)
понятие29
1.1.1. X—Y-алгоритмы (34).
§ 1.2. Представительные вычислительные модели34
1.2.1. Машины Колмогорова (35). 1.2.2. Формальные задания (37).
1.2.3. Представительные модели (39). 1.2.4. Тезис Чёрча (41).
1.2.5. Языки программирования (41).
Добавление к § 1.2. Машины Шёнхаге42
§ 1.3. Общее понятие исчисления как самостоятельное (отдельное)
понятие44
1.3.1. Исчисления со входом (52).
Добавление к § 1.3. Алгебраические примеры53
§ 1.4. Представительные порождающие модели62
§ 1.5. Выяснение связей между алгоритмами и исчислениями63
§ 1.6. Время и ёмкость как сложности вычисления и порождения65
1.6.1. Машины Тьюринга (66). 1.6.2. Время (69). 1.6.3. Ёмкость
(71). 1.6.4. Норма (74). 1.6.Б. Примеры нормированных ансамблей
(75). 1.6.6. Ограниченно-искажающие отображения и изоморфизмы
(75). 1.6.7. Дополнительные требовании к нормам (75). 1.6.8.
Сложности порождения (76). 1.6.9. Эффективные алгоритмы (76).
Добавление к § 1.6. Моделирование в реальное время77
§ 1.7. Вычислимые функции и породимые множества; перечислимые
множества; разрешимые множества78
§ 1.8. Понятие μ-рекурсивной функции87
§ 1.9. Возможность арифметического и даже диофантова представления
любого перечислимого числового множества89
§ 1.10. Построение неразрешимого породимого множества91
§ 1.11. Проблема сводимости Поста93
§ 1.12. Понятие относительного алгоритма, или алгоритма с оракулом98
§ 1.13. Понятие вычислимой операции101
§ 1.14. Понятие программы: программы как объекты вычисления
и порождения106
1.14.1. Способы программирования (106). 1.14.2. Универсальные
алгоритмы и универсальные функции (110). 1.14.3. Главные, или
гёделевы, универсальны: функции (112). 1.14.4. Вычислительные
структуры (114). 1.14.5. Экономные по норме, или оптимальные
функции (117). 1.14.6. Программирование исчислений (119).
1.14.7. Преобразования программ (120).
§ 1.15. Понятие нумерации и теория нумераций122
1.15.1. Вычислимые нумерации (126). 1.15.2. Нумерованные
множества (132). 1.15.3. Операции над нумерованными
множествами (133).
§ 1.16. Начало создания инвариантной, или машинно-независимой,
теории сложности вычисления133
§ 1.17. Теория сложности и энтропии конструктивных объектов135
§ 1.18. Удобные вычислительные модели.141
 
Ч а с т ь  II.  Основные математические приложения теории
алгоритмов144
 
§ 2.1. Исследование массовых проблем146
2.1.0. Основные понятия (146). 2.1.1. Семь нерешимых проблем
(151). 2.1.2. Массовые проблемы в математике (154). 2.1.3.
Массовые проблемы в смысле Медведева (163). 2.1.4. О пользе
правильной терминологии (165).
§ 2.2. Приложения к основаниям математики: конструктивная семантика165
§ 2.3. Приложения к математической логике: анализ формализованных
языков логики н арифметики169
§ 2.4. Вычислимый анализ173
2.4.0. Ранняя история: Борель и Тьюринг (173). 2.4.1.
Конструктивный анализ (175). 2.4.2. Начальные понятия (176).
2.4.3. Главные результаты (178). 2.4.4. Эффективно метрические
пространства (179). 2.4.5. Эффективно топологические
пространства (180). 2.4.6. Отчасти вычислимый анализ (181).
2.4.7. Эффективно пренебрежимые множества (182).
§ 2.5. Нумерованные структуры184
2.5.1. Нумерации программного типа (185). 2.5.2. Квазистандартные
нумерации (186). 2.5.3. Конструктивизации (186). 2.5.4.
Расширения конструктивных структур (188). 2.5.5. Алгебраически
корректные массовые проблемы (189). 2.5.6. Алгоритмические
размеры (190). 2.5.7. Конструктивные и конструктивизируемые
модели (195). 2.5.8. Модели арифметики (197).
§ 2.6. Приложения к теории вероятностей! определения случайной
последовательности198
2.6.1. Частотный подход (200). 2.6.2. Каким должен быть класс
всех допустимых правил выбора? (206). 2.6.3. Сложностный подход
(208), 2.6.4. Количественный, или теоретико-мерный, подход (209).
2.6.5. Соотношения между различными определениями (210). 2.6.6.
Конечные последовательности о точки зрения случайности (212).
§ 2.7. Приложения к теории информации: алгоритмический подход
к понятию количества информации215
§ 2.8. Оценки сложности решения отдельных задач220
2.8.1. Верхние оценки (220). 2.8.2. Нижние оценки (223).
§ 2.9. Влияние теории алгоритмов на алгоритмическую практику224
2.9.1. Общее понятие алгоритма и возможность его формализации
(225). 2.9.2. Существование нерешимых алгоритмических проблем
в математике и нерешаемость многих естественно возникающих
проблем (225). 2.9.3. Появление различных понятий сложности
вычисления и порождения (225). 2.9.4. Неалгоритмическое описание
вычислимых функций (226). 2.9.5. Вычислительные и порождающие
модели (226). 2.9.6. Трактовка программ как объектов вычисления
(227). 2.9.7. Рассмотрение программ как объектов порождения
(227). 2.9.8. Смешанные вычисления (227). 2.9.9. Методы
программирования (229). 2.9.10. Программирование как вторая
грамотность (229). 2.9.11. Математическая логика и вычислительная
техника (230).
 
Д о п о л н е н и е.  О вероятностных алгоритмах (как использование
случайности позволяет укорачивать вычисления)231
 
§ Д.1. Предварительные замечания231
§ Д.2. Основные результаты235
§ Д.З. Формальные определения238
 
Список сокращений244
Список литературы245
Именной указатель272
Предметный указатель276

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

  1. Информатика, Луенбергер Д. Д., 2008
  2. Машины Тьюринга и рекурсивные функции, Эббинхауз Г. Д., Якобс К., Ман Ф. К., Хермес Г., 1972
  3. Арифметика. Алгоритмы. Сложность вычислений: Популярное введение в теорию чисел и арифметическую теорию сложности, Гашков С. Б., Чубариков В. Н., 1996
  4. Задачи по теории множеств, математической логике и теории алгоритмов, Лавров И. А., Максимова Л. Л., 1975
  5. Графы, сети и алгоритмы, Свами М., Тхуласираман К., 1984
  6. Анализ алгоритмов. Вводный курс, Макконнелл Д., 2002
  7. Теорема Гёделя о неполноте, Успенский В. А., 1982
  8. Алгебраическая алгоритмика (с упражнениями и решениями), Ноден П., Китте К., 1999
  9. История информатики в России: учёные и их школы, Захаров В. Н., Подловченко Р. И., Фет Я. И., сост., 2003
  10. Алгебра. Языки программирования. — 2-е изд., перераб., Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л., 1978
  11. Алгоритмы и вычислительные автоматы, Трахтенброт Б. А., 1974
  12. Алгоритмы + структуры данных = программы, Вирт Н., 1985
  13. Введение в теоретическое программирование (беседы о методе), Ершов А. П., 1977
  14. Идеалы, многообразия и алгоритмы. Введение в вычислительные аспекты алгебраической геометрии и коммутативной алгебры, Кокс Д., Литтл Д., О'Ши Д., 2000
  15. Библиотека алгоритмов 151б—200б: Справочное пособие. Вып. 4, Агеев М. И., Алик В. П., Марков Ю. И., сост., 1981
  16. Машины клеточных автоматов, Тоффоли Т., Марголус Н., 1991
  17. Математическая логика, Клини С. К., 1973
  18. Математическая логика в программировании: Сборник статей 1980—1988 гг., Захарьящев М. В., Янов Ю. И., ред., 1991
  19. Дискретная математика для программистов, Хаггарти Р., 2004
  20. Введение в дискретную математику, Яблонский С. В., 1979
  21. Основания теории множеств, Бар-Хиллел И., Френкель А. А., 1966
  22. Введение в теорию множеств и общую топологию, Александров П. С., 1977
  23. Теория множеств и метод форсинга, Йех Т., 1973
  24. Современная теория множеств: начала дескриптивной динамики, Кановей В. Г. , Любецкий В. А., 2007
  25. Теоретико-множественные модели языков, Маркус С., 1970
  26. Алгебра логики в задачах, Гиндикин С. Г., 1972
  27. Жемчужины теории формальных языков, Саломаа А., 1986
  28. Теория формальных грамматик, Гросс М., Лантен А., 1971
  29. Нечёткие множества в моделях управления и искусственного интеллекта, Аверкин А. Н., Батыршин И. 3., Блишун А. Ф., Силов В. Б., Тарасов В. Б., 1986

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