М., Наука, 1987г. -288 с.
Важнейшие достижения теории алгоритмов.
Приложения теории алгоритмов к математической логике, теории вероятностей, теории информации и др.
Влияние теории алгоритмов на алгоритмическую практику.
Содержание:
Основные математические приложения теории алгоритмов:
1. Исследование массовых проблем.
2. Приложения к основаниям математики.
3. Приложения к математической логике.
4. Вычислимый анализ. Нумерованные структуры.
5. Приложения к теории вероятностей.
6. Приложения к теории информации: алг. подход к понятию количества информации.
7. Оценки сложности решения отдельных задач.
8. Влияние теории алгоритмов на алгоритмическую практику.
Основные открытия общей теории алгоритмов:
1. Общее понятие алгоритма.
2. Представительные вычислительные модели.
3. Общее понятие исчисления.
4. Представительные порождающие модели.
5. Связи между алгоритмами и исчислениями.
6. Вычислимые функции и породимые множества.
7. Понятие м-рекурсивной функции.
8. Построение неразрешимого породимого множества.
9. Проблема сводимости Поста.
10. Понятие относительного алгоритма, или алгоритма о оракулом.
11. Понятие вычислимой операции.
12. Понятие программы: программы как объекты вычисления и порождения.
13. Понятие нумерации и теория нумераций.
14. Начало создания инвариантной, или машинно-независимой, теории сложности вычисления.
15. Теория сложности и энтропии конструктивных объектов.
16. Удобные вычислительные модели.
Книга предназначена для специалистов по математике, информатике, кибернетике, а также для студентов вузов.
Важнейшие достижения теории алгоритмов.
Приложения теории алгоритмов к математической логике, теории вероятностей, теории информации и др.
Влияние теории алгоритмов на алгоритмическую практику.
Содержание:
Основные математические приложения теории алгоритмов:
1. Исследование массовых проблем.
2. Приложения к основаниям математики.
3. Приложения к математической логике.
4. Вычислимый анализ. Нумерованные структуры.
5. Приложения к теории вероятностей.
6. Приложения к теории информации: алг. подход к понятию количества информации.
7. Оценки сложности решения отдельных задач.
8. Влияние теории алгоритмов на алгоритмическую практику.
Основные открытия общей теории алгоритмов:
1. Общее понятие алгоритма.
2. Представительные вычислительные модели.
3. Общее понятие исчисления.
4. Представительные порождающие модели.
5. Связи между алгоритмами и исчислениями.
6. Вычислимые функции и породимые множества.
7. Понятие м-рекурсивной функции.
8. Построение неразрешимого породимого множества.
9. Проблема сводимости Поста.
10. Понятие относительного алгоритма, или алгоритма о оракулом.
11. Понятие вычислимой операции.
12. Понятие программы: программы как объекты вычисления и порождения.
13. Понятие нумерации и теория нумераций.
14. Начало создания инвариантной, или машинно-независимой, теории сложности вычисления.
15. Теория сложности и энтропии конструктивных объектов.
16. Удобные вычислительные модели.
Книга предназначена для специалистов по математике, информатике, кибернетике, а также для студентов вузов.