Теория алгоритмов: основные открытия и приложения

Description

Предисловие.обозначения и терминология.введение.предварительные понятия теории алгоритмов: конструктивные объекты и их ансамбли, локальные свойства и локальные действия.Общее понятие алгоритма как самостоятельное (отдельное) понятие.Представительные вычислительные модели.Общее понятие исчисления как самостоятельное.(отдельное) понятие.Представительные порождающие модели.Выяснение связей между алгоритмами и исчислениями.Время и емкость как сложности вычисления и порождения.Вычислимые функции и породимые множества; перечислимые множества; разрешимые множества.Понятие рекурсивной функции.Возможность арифметического и даже диофантова представления любого перечислимого числового множества.Построение неразрешимого породимого множества.Проблема сводимости Поста.Понятие относительного алгоритма, или алгоритма с оракулом.Понятие вычислимой операции.Понятие программы: программы как объекты вычисления и порождения.Понятие нумерации и теория нумераций.Начало создания инвариантной, или машинно-независимой, теории сложности вычисления.Теория сложности и энтропии конструктивных объектов.Удобные вычислительные модели.Именной указатель.предметный указатель.