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

МГАПИ

Кафедра “Управление и моделирование систем”

УТВЕРЖДАЮ

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

_______________/ Соколов В.В./

«_____»____________2002г

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

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

ЕН.Ф.01.04

(1604)

Рекомендуется для направления подготовки

дипломированного специалиста

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

специальность - 22.04.00 –

Программное обеспечение вычислительной техники и автоматизированных систем

Москва 2004

1. Цели и задачи дисциплины

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

Задача дисциплины – получение базовых знаний в области математической логики, теории формальных систем и прикладной теории алгоритмов.

2. Требования к уровню освоения содержания дисциплины

Знания, приобретенные в результате освоения содержания дисциплины:

• Основные логические функции одной и двух переменных.

• Законы булевой алгебры.

• Основные модели алгоритмов.

• Меры сложности алгоритмов. Классы задач P и NP.

Умения и навыки, приобретенные в результате освоения дисциплины:

• по разделу «Математической логики»:

 Умение использовать функции алгебры логики в инженерной практике.

 Умение использовать предикаты и кванторы.

 Умение использовать принцип дедукции.

• по разделу « Теория алгоритмов»:

 Умение использовать рекурсивные функции.

 Знать меры сложности алгоритмов.

 Уметь различать классы задач P, NP и NP полные задачи.

1. Объем дисциплины и виды учебной нагрузки

Виды учебной нагрузки	Всего часов	Семестры
		3	4
Общая трудоемкость дисциплины	100		100
Аудиторные занятия	60		60
Лекции	34		34
Практические занятия (ПЗ)	8		8
Семинары (С)
Лабораторные занятия (ЛР)	4		4
и (или) другие виды аудиторных занятий
Самостоятельная работа	40		40
Курсовой проект (работа)
Расчетно-графические работы
Реферат
и (или) другие виды самостоятельных занятий	А,Д		А,Д
Дополнительные занятия	14		14
Вид итогового контроля	Экзамен		Экзамен

4. Содержание дисциплины

В дисциплину должны входить следующие темы:

Логика высказываний; логика предикатов; исчисления; непротиворечивость; полнота; синтаксис и семантика языка логики предикатов. Клазуальная форма. Метод резолюций в логике предикатов. Принцип логического программирования. Темпоральные логики; нечеткая и модальные логики; нечеткая арифметика Ч. Хоара. Логика высказываний. Логическое следование, принцип дедукции. Метод резолюций. Аксиоматические системы, формальный вывод. Метатеория формальных систем. Понятие алгоритмической системы. Рекурсивные функции. Формализация понятия алгоритма; Машина Тьюринга. Тезис Черча; Алгоритмически неразрешимые проблемы. Меры сложности алгоритмов. Легко и трудноразрешимые задачи. Классы задач P и NP. NP- полные задачи. Понятие сложности вычислений; эффективные алгоритмы. Основы нечеткой логики. Элементы алгоритмической логики.

4.1. Разделы дисциплин и виды занятий (тематический план)

№ п/п	Раздел дисциплины	Лекции	ПЗ (или С)	ЛР
1	Введение в математическую логику.	2
2	Функции алгебры логики. Основные понятия и определения	2
3	Основные логические функции одной и двух переменных.	2	2	2
4	Основные законы булевой алгебры	2	2	2
5	Классификация логических функций	2	2
6	Полнота и замкнутость логических функций.	2	2
7	Аксиоматические системы, формальный вывод.	2
8	Исчисление высказываний	2
9	Синтаксис и семантика языка логики предикатов.	2
10	Метод резолюций в логике предикатов	2
11	Нечеткая и модальные логики	2
12	Понятие алгоритмической системы.	2
13	Формализация понятия алгоритма. Модели алгоритмов.	2
14	Рекурсивные функции.	2
15	Понятие о машине Тьюринга. Тезис Черча.	2
16	Меры сложности алгоритмов. Классы задач P и NP.	2
17	Понятие сложности вычислений

1. 1. Содержание разделов дисциплины.

№ лекции	№ раздела	Содержание	Объем в часах	Семестр
1	1	Введение в математическую логику.	2	4
2	1	Логика высказываний. Основные понятия и определения.	2	4
3	1	Логические функции одной и двух переменных.	2	4
4	1	Основные законы булевой алгебры.	2	4
5	1	Классификация логических функций.	2	4
6	1	Полнота и замкнутость логических функций.	2	4
7	1	Введение в формальные системы.	2	4
8	1	Исчисление высказываний.	2	4
9	1	Синтаксис и семантика языка логики предикатов.	2	4
10	1	Метод резолюций в логике предикатов.	2	4
11	1	Неклассические логики.	2	4
12	2	Понятие алгоритмической системы.	2	4
13	2	Формализация понятия алгоритма. Модели алгоритмов.	2	4
14	2	Рекурсивные функции.	2	4
15	2	Понятие о машине Тьюринга. Тезис Черча.	2	4
16	2	Меры сложности алгоритмов. Классы задач P и NP.	2	4
17	2	Понятие сложности вычислений	2	4

4.2.2 Содержание практических занятий

№ практич. занятия	№ раздела	Содержание	Объем в часах	Семестр
1	3	Основные логические функции одной и двух переменных	2	4
2	4	Основные законы булевой алгебры	2	4
3	5	Классификация логических функций	2	4
4	6	Полнота и замкнутость логических функций	2	4

4.2.3. Курсовая работа

Курсовая работа не предусмотрена.