Оценочные средства для текущего контроля успеваемости и промежуточной

представление в бинарном алфавите. 
11. Теорема о нормированной вычислимости произвольной вычислимой по Тьюрингу 
функции – формулировка и пояснение конструкции машины Тьюринга 
(декодировщика), формирующей по бинарной записи списка аргументов и 
результата счета представление в исходном конечном алфавите. 
12. Теорема о нормированной вычислимости произвольной вычислимой по Тьюрингу 
функции – формулировка и пояснение конструкции диаграммы машины Тьюринга, 
осуществляющей кодирование, моделирование в бинарном алфавите и 
декодирование в исходный алфавит результатов счета. 
13. Теорема о композиции вычислимых по Тьюрингу функций – формулировка и 
пояснение конструкции диаграммы результирующей машины Тьюринга. 
14. Тезисы Тьюринга и Черча. Статус этих тезисов и взаимосвязь между ними. 
15. Характеристическая функция для множества слов в заданном алфавите. 
Определение алгоритмически разрешимого множества (проблемы). 
16. Проблема самоприменимости – формулировка, статус проблемы, обоснование. 
17. Проблема остановки – формулировка, статус проблемы, обоснование. 
18. Метод сведение одной проблемы к другой. Пример его использования. 
19. Проблема остановки на пустой ленте – формулировка, статус проблемы, 
обоснование. 
20. Униформная проблема остановки и проблема бессмертия – формулировка и статус 
проблем. 
21. Проблем домино – формулировка, статус проблемы и обоснование. 
22. Проблема соответствия Поста - формулировка и статус проблемы. 
23. Универсальная машина Тьюринга U – общее описание U, зоны ленты U, их 
назначение. Представление таблицы команд произвольной машины Тьюринга – 
пример и пояснение использования. 
24. Универсальная машина Тьюринга U – пояснение диаграммы машины Тьюринга, 
отвечающей за обновление “текущего” состояния моделируемой машины Тьюринга. 
25. Универсальная машина Тьюринга U – пояснение диаграммы машины Тьюринга, 
описывающей весь алгоритм работы U. 
26. Проблема остановки универсальной машины Тьюринга – формулировка, статус 
проблемы, обоснование. 
27. Причины введения рекурсивных функций. Определение базовых рекурсивных 
функций. Вычислимость этих функций по Тьюрингу. 
28. Определение операторов суперпозиции и примитивной рекурсии. Примеры 
использования. Определение примитивно рекурсивной функции. Пример 
примитивно рекурсивной функции. 
29. Определение оператора минимизации. Пример использования. Определение 
частично рекурсивной функции и общерекурсивной функции. Пример частично 
рекурсивной и общерекурсивной функций. 
30. Теорема о суммировании и мультиплицировании примитивно рекурсивных 
функций. Пример использования. 
31. Теорема о мажорировании неявно заданной функции через примитивно рекурсивные 
функции. Пример использования. 
32. Канторовские нумерации числовых наборов: функции свертки набора в номер и 

функции проектирования – их основные свойства и статус вычислимости. Примеры 
использования на парах и тройках чисел. 
33. Геделевская нумерация числовых наборов. Ее отличие от канторовской и 
математическое обоснование. 
34. Геделевская нумерация числовых наборов. Функция Геделя, ее статус вычислимости 
и основное свойство функции Геделя. 
35. Определение рекурсивного и примитивно рекурсивного множества. Примеры 
рекурсивных и примитивно рекурсивных множеств. 
36. Свойства рекурсивных множеств – свойства замкнутости и свойство направленной 
функции. 
37. Понятие и определение рекурсивно перечислимого множества. Примеры рекурсивно 
перечислимых множеств. 
38. Свойства замкнутости рекурсивно перечислимых множеств. 
39. Теорема Поста о рекурсивной перечислимости множества и его дополнения. 
40. Характеристика рекурсивно перечислимого множества через область значений 
функции. 
41. Теорема о графике частично рекурсивной функции. 
42. Теорема об области определения частично рекурсивной функции. 
43. Теорема Клини о нормальной форме частично рекурсивной функции. 
44. Функция Аккермана: определение и свойства. 
45. Характеризация примитивно-рекурсивной функции посредством функции 
Аккермана. 
46. Теорема Райса-Успенского: формулировка и смысл теоремы. 
47. Определение вычислимости на конечно-порожденных алгебраических структурах и 
на множестве вещественных чисел. 
48. Содержательное определение сети Петри. Отличительные особенности и области 
применения сетей Петри. Примеры сетей Петри. 
49. Формальное определение сети Петри. Поведенческие свойства сетей Петри. 
Примеры сетей Петри с определенными свойствами. 
50. Дерево маркировок сети Петри. Пример дерева маркировок. Структурные свойства 
сетей Петри. Примеры сетей Петри с определенными свойствами. 

жүктеу/скачать 487,97 Kb.

Достарыңызбен бөлісу: