ВЯТСКИЙ

СОЦИАЛЬНО-ЭКОНОМИЧЕСКИЙ

ИНСТИТУТ

«Утверждаю»

Проректор по учебной работе

________________________

«___» ____________2010 г.

Кафедра информатики и вычислительной техники

УЧЕБНАЯ ПРОГРАММА

ПО ДИСЦИПЛИНЕ

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

и теория алгоритмов

Киров

2010

Рассмотрена на заседании Утверждена на заседании

кафедры информатики и учебно-методического совета

вычислительной техники

15 января 2010 г. 25 января 2010 г.

Протокол № 5 Протокол № 43

Зав. кафедрой ______________ Председатель УМС__________

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

является дисциплиной федерального компонента

цикла общих математических и естественнонаучных дисциплин.

Учебная программа составлена в соответствии с требованиями государственного образовательного стандарта и предназначена

для студентов, обучающихся по направлению

230100.62 Информатика и вычислительная техника

Составитель: Архангельский В.В., к.ф.-м.н., ВСЭИ

Рецензент: Князьков В.С., д.т.н., профессор ВятГУ

© Вятский социально-экономический

институт (ВСЭИ), 2010

1. Пояснительная записка

Цель курса: формирование знаний и представлений о понятиях и методах математической логики, ее месте и роли в науке, современной математике и в школьном курсе математики.

Задачи курса:

• заложить основы логики и исчисления высказываний и предикатов;

• дать представление о формальных математических теориях и вопросах обоснования математики;

• научить применению логики предикатов для записи математических предложений и их преобразования;

получить знания об основах логики высказываний, логики предикатов, нечеткой логики и теории алгоритмов;

- употреблять специальную математическую символику для  выражения количественных и качественных отношений между объектами;

• знать основные методы и алгоритмы математической логики, связанные с моделированием и оптимизацией систем различной природы.

В результате изучения курса студент должен:

знать:

• аппарат алгебры логики и теорию булевых функций;

• логику предикатов;

• теорию алгоритмов;

уметь:

• строить таблицы истинности для формул логики и упрощать формулы логики;

• выполнять операции над предикатами, записывать области истинности предикатов, формализовывать предложения с помощью логики предикатов;

• преобразовывать логические формулы;

• доказывать вычислимость функций.

При изучении курса необходимо знание студентами математики  в  объеме первого курса, а также дискретной математики.

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

2.1. Тематический план

по очной форме обучения

№ п/п	Наименование разделов и тем	Количество часов
		Всего	Лекции	Практ.	Самост. работа
1. Раздел: Логика высказываний
1.1	Логика высказываний	4	2	-	2
1.2	Исчисления	4	-	2	2
1.3	Непротиворечивость	2	1	-	1
1.4	Полнота	2	1	-	1
1.5	Логическое следование	2	1	-	1
1.6	Принцип дедукции	2	1	-	1
1.7	Метод резолюций	4	-	2	2
2. Раздел: Логика предикатов
2.1	Логика предикатов	4	2	-	2
2.2	Синтаксис и семантика языка логики предикатов	2	1	-	1
2.3	Клаузальная форма	4	-	2	2
2.4	Метод резолюций в логике предикатов	4	-	2	2
2.5	Логическое программирование	4	2	-	2
2.6	Темпоральные логики	4	2	-	2
2.7	Нечеткая и модальные логики	4	2	-	2
2.8	Нечеткая арифметика	2	1	-	1
2.9	Аксиоматическая логика Ч. Хоара	4	2	-	2
2.10	Аксиоматические системы	4	2	-	2
2.11	Формальный вывод	2	-	1	1
2.12	Метатеория формальных систем	2	1	-	1
3. Раздел: Теория алгоритмов
3.1	Понятие алгоритмической системы	4	2	-	2
3.2	Рекурсивные функции	4	-	2	2
3.3	Формализация понятия алгоритма	4	2	-	2
3.4	Машина Тьюринга	4	-	2	2
3.5	Тезис Черча	2	1	-	1
3.6	Алгоритмически неразрешимые проблемы	2	1	-	1
3.7	Меры сложности алгоритмов	2	1	-	1
3.8	Легко и трудноразрешимые задачи	2	-	1	1
3.9	Классы задач P и NP	4	2	-	2
3.10	NP-полные задачи	2	1	-	1
3.11	Понятие сложности вычислений	2	1	-	1
3.12	Эффективные алгоритмы	2	1	-	1
3.13	Основы нечеткой логики	4	-	2	2
3.14	Элементы алгоритмической логики	2	1	-	1
Итого:		100	34	16	50