Математическая логика и теория алгоритмов (стр. 1 )

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ

имени В. Г. БЕЛИНСКОГО

Принято на заседании Ученого совета физико-математического факультета Протокол заседания № 10 от « 18 » мая 2011 г. Декан факультета _________

УТВЕРЖДАЮ Проректор по учебной работе __________________ «_____» ___________________ 2011 г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

Математическая логика и теория алгоритмов

Направление подготовки 050100 Педагогическое образование

Профиль подготовки ФИЗИКА

Квалификация (степень) выпускника – Бакалавр

Форма обучения очная

Пенза – 2011

1. Цели освоения дисциплины «Математическая логика и теория алгоритмов»

Целью освоения дисциплины «Математическая логика и теория алгоритмов» является формирование и развитие у студентов общекультурных и специальных компетенций, формирование систематизированных знаний, умений и навыков в области математической логики и теории алгоритмов, позволяющих подготовить конкурентноспособного выпускника для сферы образования, готового к инновационной творческой реализации в образовательных учреждениях различного уровня и профиля.

Задачи изучаемой дисциплины:

Исходя из общих целей подготовки бакалавра педагогического образования по профилю «Информатика»:

содействовать средствами дисциплины «Математическая логика и теория алгоритмов» развитию у студентов мотивации к педагогической деятельности, профессионального мышления, коммуникативной готовности, общей культуры; научить студентов ясно, точно, грамотно излагать свои мысли в устной и письменной речи.

Исходя из конкретного содержания дисциплины:

формировать систематизированные знания в области математической логики, представлений о проблемах оснований математики и роли математической логики в их решении; развивать логическое мышление, логическую культуру, разъяснять понятие алгоритма, его основных свойств, изложить основы теории рекурсивных функций, теории машин Тьюринга и нормальных алгоритмов Маркова.

2. Место дисциплины «Математическая логика и теория алгоритмов» в структуре ООП бакалавриата

Дисциплина «Математическая логика и теория алгоритмов» относится к вариативной части профессионального цикла.

Для освоения дисциплины обучающиеся используют знания, умения, сформированные в ходе изучения дисциплин вариативной части профессионального цикла: «Линейная алгебра», «Дискретная математика», «Элементы абстрактной и компьютерной алгебры».

3. Компетенции обучающегося, формируемые в результате освоения

дисциплины «Математическая логика и теория алгоритмов»

Процесс изучения дисциплины направлен на формирование элементов следующих компетенций в соответствии с ФГОС ВПО по данному направлению:

Коды компетенции	Наименование компетенции	Структурные элементы компетенции (в результате освоения дисциплины обучающийся должен знать, уметь, владеть)
1	2	3
ОК-1	владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей её достижения	Знать: основные методы доказательного построения умозаключений.
Уметь: применять эти методы при анализе задач, поиске путей их решения.
Владеть: методами анализа, обобщения информации.
ОК-4	способен использовать знания о современной естественнонаучной картине мира в образовательной и профессиональной деятельности, применять методы математической обработки информации, теоретического и экспериментального исследования	Знать: методы формализации для исследования условия поставленной задачи.
Уметь: использовать логические методы исследования для построения и реализации плана решения задачи.
Владеть: навыками применения методов логической обработки информации при формализации условия.
ОК-6	способен логически верно строить устную и письменную речь	Знать: законы логической равносильности, законы логического следования.
Уметь: использовать законы логики.
Владеть: навыками логического вывода, построения доказательства.
СК-1	готов применять знания теоретической информатики, фундаментальной и прикладной математики для анализа и синтеза информационных систем и процессов	Знать: законы логической равносильности; компоненты (аксиомы и правила вывода) и характеристики (свойства) исчислений высказываний и важнейших теорий первого порядка; результаты о непротиворечивости и независимости в арифметике и теории множеств; методы математической логики для изучения математических доказательств и теорий. Основные черты алгоритмов.
Уметь: распознавать тождественно истинные формулы языка логики высказываний (предикатов); применять средства языка логики предикатов для записи и анализа математических предложений; строить простейшие выводы (в виде дерева) в исчислениях высказываний и использовать эти модели для объяснения сути и строения математических доказательств.
Владеть: техникой равносильных преобразований логических формул; методами распознавания тождественно истинных формул и равносильных формул; дедуктивным аппаратом изучаемых логических исчислений.
СК-3	владеет современными формализованными математическими, информационно-логическими и логико-семантическими моделями и методами представления, сбора и обработки информации	Знать: принципы аксиоматического построения формализованного исчисления высказываний, понятие вывода, свойства выводимости из гипотез, теорему о дедукции, её применение, производные правила вывода, свойства формализованного исчисления высказываний.
Уметь: использовать основные положения математической логики при решении задач.
Владеть: основными методами математической логики и теории алгоритмов.

4. Структура и содержание дисциплины «Математическая логика и теория алгоритмов»

4.1. Структура дисциплины «Математическая логика и теория алгоритмов»

Общая трудоемкость дисциплины составляет 6 зачетных единиц, 216 часов.

№ п/п	Наименование разделов и тем дисциплины (модуля)	Семестр	Недели семестра	Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)											Формы текущего контроля успеваемости (по неделям семестра)
Аудиторная работа	Самостоятельная работа
Всего	Лекция	Практические занятия	Лабораторные занятия	Всего	Подготовка к аудиторным занятиям	Подготовка к собеседованию	Подготовка к коллоквиуму	Подготовка к тесту	Подготовка к контрольной работе	Подготовка к экзамену	собеседование	коллоквиум	тест	контрольная работа
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
1.	Раздел 1. Алгебра высказываний	4	1-8	16	8	8		14	8	2		4
1.1	Высказывания. Формулы алгебры высказываний.	4	1-2	4	2	2		2	2
1.2	Логическая равносильность формул. Нормальные формы.	4	3-4	4	2	2		4	2			2
1.3	Логическое следование формул. Приложение алгебры высказываний.	4	5-6	4	2	2		4	2			2					6
1.4	Применение алгебры высказываний к описанию релейно-контактных схем.	4	7-8	4	2	2		4	2	2
2.	Раздел 2. Исчисление высказываний	4	9-18	20	10	10		22	10	2	4		6
2.1	Построение исчисления высказываний.	4	9-10	4	2	2		4	2	2					10
2.2	Теорема дедукции и ее применение.	4	11-14	8	4	4		8	4		4					12
2.3	Свойства исчисления высказываний.	4	15-18	8	4	4		10	4				6					17
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
3.	Раздел 3. Алгебра предикатов и исчисление предикатов	5	1-6	18	12	6		18	12	6
3.1	Логические и кванторные операции над предикатами.	5	1	4	2	2		4	4
3.2	Формулы логики предикатов.	5	2	2	2
3.3	Приведенная форма и предваренная нормальная форма.	5	3	4	2	2		6	4	2					3
3.4	Проблема разрешения формул логики предикатов.	5	4	2	2
3.5	Применение логики предикатов.	5	5	4	2	2		6	4	2
3.6	Исчисление предикатов и его свойства.	5	6	2	2			2		2					6
4.	Раздел 4. Теория алгоритмов	5	7-18	36	24	12		36	24		6		6
4.1	Необходимость уточнения понятия алгоритма. Понятие вычислимой функции.	5	7-8	6	4	2		4	4
4.2	Частично рекурсивные функции.	5	9-10	6	4	2		6	4		2
4.3	Рекурсивность нумерующих функций	5	11-12	6	4	2		8	4		4					12
4.4	Кусочное задание функции.	5	13-14	6	4	2		4	4
4.5	Машины Тьюринга.	5	15-16	6	4	2		6	4				2
4.6	Нормальные алгоритмы Маркова.	5	17-18	6	4	2		8	4				4					17
	Общая трудоемкость, в часах			90	54	36		90	54	10	10	4	12	36	Промежуточная аттестация
Форма	Семестр
Зачет	4
Экзамен	5

4.2. Содержание дисциплины «Математическая логика и теория алгоритмов»