Готовые шпоры по Дисциплине Теория алгоритмов скачать: список вопросов: 1Неформальное понятие алгоритма. Основные свойства алгоритмов. 2 Исходные функции. Оператор постановки (примеры). 3 Оператор примитивной рекурсии (примеры). 4 Оператор минимизации ( примеры). 5 Примитивно рекурсивные функции (определение, примеры). 6 Частично-рекурсивные и общерекурсивные функции 7 Тезис Черча 8 Машина Тьюринга. Определение, примеры 9 Функции вычислимые с помощью машины Тьюринга (примеры ). 10 Строки (цепочки ). Простые и заключительные правила Маркова. Алгорифмы Маркова. 11Основные понятия, связанные с алгорифмами Маркова. Применимость алгорифмов Маркова к цепочке. Функции, вычислимые с помощью алгорифмов Маркова. Принцип нормализации (тезис) Маркова. 12 Машины с неограниченными регистрами (МНР) Функции вычислимые на машине с неограниченным числом регистров 13 Реализация подстановки с помощью МНР 14 (Реализация примитивной рекурсии с помощью МНР) 15 (Реализация минимизации на МНР) 16 (Вычислимость с помощью МНР примитивно рекурсивных функций) 17 (Вычислимость с помощью МНР частично рекурсивных и общерекурсивных функций) 18 (Биективные нумерации пар, троек и произвольных цепочек натуральных чисел.) 20 (Универсальные функции для класса функций. Универсальные функции для классов общерекурсивных и частично-рекурсивных функций.) 21 (Разрешимые множества. Характеристические и представляющие функции. Теоремы о разрешимых множествах) 22 (Рекурсивные и Рекурсивно перечислимые множества.) 24 (Массовые алгоритмические проблемы) 25 (Проблема самоприменимости) 26 (Проблемы останова. Неразрешимость класса общерекурсивных функций)
|