Программа дисциплины о. 17 «теория алгоритмов и вычислительных процессов»



Pdf көрінісі
бет6/9
Дата23.01.2023
өлшемі487,97 Kb.
#62533
түріПрограмма
1   2   3   4   5   6   7   8   9
Байланысты:
B1.O.17 Teorija algoritmov i vychislitel\'nyh processov 2021

4.2 Образцы билетов 
 
Билет №1 
1. Причины введения рекурсивных функций. Определение базовых рекурсивных 
функций. Вычислимость этих функций по Тьюрингу. 
2. Функция Аккермана: определение и свойства. 
3. Пусть f(x) – некоторая всюду определенная вычислимая по Тьюрингу функция, 
g(x) – нигде неопределенная вычислимая по Тьюрингу функция. Как будет 
функционировать машина Тьюринга, вычисляющая функцию f(g(x))? 


Билет №2 
1. Тезисы Тьюринга и Черча. Статус этих тезисов и взаимосвязь между ними. 
2. Теорема Райса-Успенского: формулировка и смысл теоремы. 
3. Является ли разрешимой проблема остановки произвольной 
машины Тьюринга, если она стартует на ленте, на которой записано 
слово 1101001? 
4.3. Критерии оценивания к экзамену 
Оценка «отлично»: точные формулировки алгоритмов, теорем и правильные 
доказательства; точные определения математических объектов и ясные и 
правильные определения объектов, характеризующихся неформализованными 
понятиями. 
Оценка «хорошо»: при ответе на один вопрос даны точные 
формулировки алгоритмов, теорем и правильные доказательства; точные 
определения математических объектов и ясные 
и правильные определения 
объектов, 
характеризующихся неформализованными понятиями; при ответе на второй вопрос имеются неточности 
формулировки алгоритмов, теорем или пробелы в правильных
доказательствах; недостаточно точные определения математических 
объектов или неясные и не совсем правильные определения объектов, 
характеризующихся неформализованными понятиями. Оценка 
«удовлетворительно»: при ответе на оба вопроса имеются неточности 
формулировки алгоритмов, теорем или пробелы в правильных
доказательствах; недостаточно точные определения математических 
объектов или неясные и не совсем правильные определения объектов, 
характеризующихся неформализованными понятиями. Оценка 
«неудовлетворительно»: отсутствует ответ хотя бы на один из вопросов или 
имеются существенные неточности в формулировках алгоритмов, теорем, 
приведены неправильные 
доказательства; 
неверные определения 
математических 
объектов 
и неправильные 
определения
объектов, 
характеризующихся неформализованными 
понятиями. 


Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет