Плиско В.Е. Теория алгоритмов. Курс лекций ОНЛАЙН

Из других алгоритмов можно указать алгоритм разложения натурального числа на простые множители, извлечения квадратного корня из натурального числа, решения системы линейных уравнений методом Гаусса и т. д. Каждый из этих алгоритмов представляет собой некоторую вычислительную процедуру, выполнение которой не требует изобретательности или сообразительности, а состоит лишь в строгом следовании инструкциям.
Содержание
1. Основные понятия теории алгоритмов
2. Машина Тьюринга
3. Частично-рекурсивные функции
4. Машина с неограниченными регистрами
5. МНР-вычислимость частично-рекурсивных функций
6. Нумерация вычислимых функций
7. Теорема о параметризации
8. Универсальная вычислимая функция
9. Разрешимые и перечислимые множества
10. Теоремы о разрешимых и перечислимых множествах
11. Нумерация перечислимых множеств
12. Неразрешимые алгоритмические проблемы
13. Теорема Раиса
14. Десятая проблема Гильберта
15. Индексы разрешимых и конечных множеств
16. Рекурсивно неотделимые перечислимые множества
17. Теорема Раиса – Шапиро
18. Многозначная сводимость
19. Продуктивные множества
20. Креативные множества
21. Простые множества
22. m-полные перечислимые множества
23. Язык формальной арифметики
24. Арифметические множества и функции
25. Гёделева нумерация арифметических формул
26. Теорема Тарского
27. Первая теорема Гёделя о неполноте
28. Меры сложности вычислений
29. Теорема о неподвижной точке
З0. Теорема об ускорении



Читать онлайн
скачать бесплатно


Теги:
теория алгоритмов, Плиско курс лекций

Коментарі до Плиско В.Е. Теория алгоритмов. Курс лекций ОНЛАЙН