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