РЕШАЕМ МАТЕМАТИКУ ВМЕСТЕ!
 
СТУДЕНТАМ:    Учебники     Решебники    Шпаргалки    Контрольные работы   Видео уроки

ШКОЛЬНИКАМ:  ГДЗ - 1 класс  2 класс  3 класс  4 класс  5 класс  6 класс  7 класс  8 класс  9 класс  10 класс  11 класс

Главная » Файлы » Учебные материалы » Математическая логика и теория алгоритмов
Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения.

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

СОДЕРЖАНИЕ
Предисловие
Обозначения и терминология

Введение
Часть I. Основные открытия общей теории алгоритмов
1.0. Предварительные понятия теории алгоритмов: конструктивные объекты и их ансамбли, локальные свойства и локальные действия
1.0.1. Первые примеры конструктивных объектов: слова и деревья (18).

1.0.2. Конструктивные объекты: попытка общего описания (19).

1.0.3. Локальные свойства и локальные действия: неформальное изложение (11).

1.0.4. Колмогоровские комплексе! (12).

1.0.5. (Б, k) -комплексы (14).

1.0.6. Ансамбли (25).

1.0.7. Локальные свойства я локальные действия: формальное определение (27).
§ 1.1. Общее понятие алгоритма как самостоятельное (отдельное) понятие
1.1.1. X — Y-алгоритмы (34).
§ 1.2. Представительные вычислительные модели 
1.2.1. Машины Колмогорова (35).

1.2.2. Формальные задания (37).

1.2.3. Представительные моделя (39).

1.2.4. Тезис Чёрча (41).

1.2.5. Языки программирования (41).
Добавление к § 1.2. Машины Шёнхаге
§ 1.3. Общее понятие исчисления как самостоятельное (отдельное) понятие
1.3.1. Исчясления со входом (52).
Добавление к § 1.3. Алгебраические примеры  
§ 1.4. Представительные порождающие модели
§ 1.5. Выяснение связей между алгоритмами и исчислениями
§ 1.6. Время и емкость как сложности вычисления и порождения
1.6.1. Машины Тьюрянга (66).

1.6.2. Время (69).

1.6.3. Емкость (71).

1.6.4. Норма (74).

1.6.5. Примеры нормированных ансамблей (75).

1.6.6. Ограниченно-искажающие отображения и изоморфизмы (75).

1.6.7. Дополнительные требовании к нормам (75).

1.6.8. Сложности порождения (76).

1.6.9. Эффективные алгоритмы (76)
Добавление к § 1.6. Моделирование в реальное время  
§ 1.7. Вычислимые функции и породимые множества; перечислимые множества; разрешимые   множества
§1.8. Понятие m-рекурсивной функции
§ 1.9. Возможность арифметического и даже диофантова представления любого перечислимого числового множества
§ 1.10. Построение неразрешимого породимого множества .
§ 1.11. Проблема сводимости Поста
§ 1.12. Понятие относительного алгоритма, или алгоритма с оракулом .
§1.13. Понятие вычислимой операции
§ 1.14. Понятие программы: программы как объекты вычисления и  порождения
1.14.1. Способы программирования (106).

1.14.2. Универсальные алгоритмы и универсальные функции (ПО).

1.14.3. Главные, или гёделевы, универсальны: функции (112).
1.14.4. Вычислительные структуры (114).

1.14.5. Экономные по норме, или оптимальные функции (117).

1.14.6. Программирование начислений (119)

1.14.7. Преобразования программ (120).
§ 1.15. Понятие нумерации и теория нумераций 
1.15.1. Вычислимые нумерации (126).

1.15.2. Нумерованные множества (132).

1.15.3. Операции над нумерованиями множествами (133).
§ 1.16. Начало создания инвариантной, или машино-независимой, теории сложности вычисления
§ 1.17. Теория сложности и энтропии конструктивных объектов
§ 1.18. Удобные вычислительные модели 
Ч а с т ь II. Основные математические приложения теории алгоритмов
§2.1. Исследование массовых проблем
2.1.0. Основные понятия (146)

2.1.1. Семь  нерешимых проблем (151).

2.1.2. Массовые проблемы в математике (154).

2.1.3. Массовые проблемы в смысле Медведева (163)
2.1.4. О пользе правильной терминологии (165)
§2.2. Приложения к основаниям математики: конструктивная семантика
§2.3. Приложения к математической логике: анализ формализованных языков логики и арифметики 
§2.4.  Вычислимый анализ
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. Нумерованные структуры
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. Приложения к теории вероятностей! определения случайной последовательности

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. Приложения к теории информации: алгоритмический подход к понятию количества информации
§2.8. Оценки сложности решения отдельных задач
2.8.1. Верхние оценки (220).

2.8.2. Нижние оценки (223).
§2.9. Влияние теории алгоритмов на алгоритмическую практику
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).
Дополнение. О вероятностных алгоритмах (как использование случайности позволяет укорачивать вычисления)
§ Д.1. Предварительные замечания
§ Д.2. Основные результаты
§ Д.З. Формальные определения
Список сокращений
Список литературы
Именной указатель
Предметный указатель







Размер файла: (3.61Mb)

Категория: Математическая логика и теория алгоритмов | Добавил: nikka
Просмотров: 2249 | Загрузок: 329 | Рейтинг: 5.0/1


Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]



ВЫБОР ПО КАТЕГОРИЯМ:

Аналитическая геометрия и алгебра [0]
Высшая алгебра [52]
История математики [55]
Математика для технарей [21]
Математика для экономистов, юристов и т.д.. [5]
Математическая логика и теория алгоритмов [40]
Теория вероятностей и мат. статистика [28]
Теория чисел [33]
Учебники по математике [46]



При полном или частичном использовании материалов
активная ссылка на портал VMATE.RU обязательна


Высшая математика онлайн - всё бесплатно, наш портал создан специально для студентов кому интересна высшая математика. У нас на портале возможно скачать бесплатно учебники по высшей математике, книги по математике или сделать заказ учебных пособий, скачать контрольные по высшей математике, заказать, задачники по высшей математики и решебники. Оставить запрос по предмету - аналитическая геометрия или задать вопрос - справочная по математике Заказать решение и т.д. Высшая математика онлайн - математический портал и здесь собраны шпаргалки по высшей математике и видео уроки. Добро пожаловать! Вход