7. Структура и содержание самостоятельной работы студентов

1. План-график самостоятельной работы

№	Темы самостоятельной работы	Вопросы для самостоятельной работы	Контроль усвоения
1	Интуитивное понятие алго­ритма	Приметы алгоритмов в ма­тематике, некор­ректность интуитив­ного понятия.	К/р №1
2	Свойства алгоритмов	Определение алго­ритма через его ос­новные свой­ства, не­зависимость свойств при различных под­ходах.	К/р №1
3	Различные подходы к уточнению понятия алгоритма	Краткое перечисле­ние раз­личных под­ходок к уточ­нению понятия алгорит­мов, взаимосвязь	К/р №1
4	Основные функции и операции	Нуль функция, функ­ция выбора аргу­мента, функ­ция сле­дования. Операция рекурсии, минимиза­ции, суперпозиции.	К/р №2
5	Рекурсивность различных функций	Доказательство ре­курсив­ности основ­ных функций ариф­метики. Иные функ­ции, их рекурсив­ность	К/р №2
6	Тезис Черча.	Связь интуитивного поня­тия вычислимой функции и рекурсив­ной функции.	К/р №2
7	Машины Тьюринга и опе­ра­ции над ма­ши­на­ми Тью­рин­га.	Устройство машины Тью­ринга. Примеры построе­ния и реше­ния задач на их со­ставление.	К/р №3
8	Фун­кция, вы­чис­ли­мая по Тью­рин­гу. До­ка­за­те­ль­ст­во су­ще­ст­во­ва­ния фун­кций, не­вы­чис­ли­мых по Тью­рин­гу. При­мер не­вы­чис­ли­мой по Тью­рин­гу фун­кции.	Примеры функций, вычис­лимых по Тью­рингу и со­ответст­вующие программы этих машин. Беско­нечно и конечные машины Тью­ринга. Невычислимые по Тьюрингу функции.	К/р №3
9	При­ме­ры ал­го­рит­ми­че­с­ки не­раз­ре­ши­мых про­блем (про­бле­ма рас­по­зна­ва­ния са­мопри­ме­ни­мо­сти, про­бле­ма при­ме­ни­мо­сти).	Проблема останова. Проблема самопри­мени­мости.	Коллоквиум №1

2. Структура и трудоемкость самостоятельной работы студентов

№ раздела дисциплины	Наименование раздела дисциплины	Формы самостоятельной работы (ак. час. / зач. ед.)						Общая трудоемкость (ак. час. / зач. ед.)
		Конспектирование в рабочей тетради	Написание реферата	Работа с монографией	Выполнение контольных домашних работ		Составление аналитических таблиц
1.	Алгебра высказываний	2	2	2	4	1		11
2.	Исчисление высказываний	2	2	1	3		2	10
3	Логика предикатов	2	2	1	3		2	10
4	Исчисление предикатов	2	2	1	3		2	10
5	Рекурсивные функции	3	2	2	2		3	12
6	Машины Тьюринга	3	3	2	3		3	14
7	Дополнительные вопросы	3	3	2	4		3	15
	Итого:	17	16	11	22		16	82