Рабочая программа по дисциплине «Математическая логика и теория алгоритмов» для специальности 230102 «Автоматизированные системы обработки информации и управления» Факультет: Систем управления

Вид материала

Рабочая программа

Содержание Цели и задачи дисциплины, ее место в учебном процессе Содержание дисциплины 2. Логические рассуждения – 6 часов. 3. Логика предикатов – 4 часа. 4. Неклассические логики и формальная арифметика – 4 часа. 5.Основы теории алгоритмов – 4 часа. Индивидуальные задания Тестовые опросы на лекциях – 20 баллов.

Подобный материал:

• Учебно-методический комплекс дисциплины «Математическая логика и теория алгоритмов», 376.44kb.
• Рабочая программа дисциплина ен. Ф. 01. 04 Математическая логика и теория алгоритмов, 415.85kb.
• Рабочая программа по дисциплине: Теория принятия решений Для специальности: 230102, 84.08kb.
• Рабочая программа по дисциплине "Организация ЭВМ и систем" Для специальности: 230102, 148.01kb.
• Рабочая программа по курсу "Моделирование систем" для специальности 230102 "Автоматизированные, 99.53kb.
• Рабочая программа по дисциплине " Метрология, стандартизация и сертификация " для специальности, 284.04kb.
• Рабочая программа по дисциплине «Основы разработки Internet-приложений» для специальности, 51.53kb.
• Рабочая программа по дисциплине: Методы и средства защиты компьютерной информации Для, 75.18kb.
• Рабочая программа по дисциплине: Теория информации Для специальности: 230102 Автоматизированные, 90.58kb.
• Рабочая программа по дисциплине Системное программное обеспечение Для специальности, 113.75kb.

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ


Томский государственный университет систем управления и радиоэлектроники

(ТУСУР)


УТВЕРЖДАЮ

Проректор по УР ТУСУР

_______________М.Т. Решетников

________________2007 г.


РАБОЧАЯ ПРОГРАММА

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

для специальности 230102 – «Автоматизированные системы

обработки информации и управления»


Факультет: Систем управления

Профилирующая кафедра: АОИ


Курс: I

Семестр: 2


Учебный план набора 2004 г. и последующих лет


Распределение учебного времени:

Лекции 26 часов

Практические занятия 16 часов

Самостоятельная работа 50 часов

Общая трудоемкость 92 часа


Зачет 2 семестр


2007


Рабочая программа составлена на основании государственного образовательного стандарта профессионального образования для направления 230102 - Автоматизированные системы обработки информации и управления. Рабочая программа обсуждена и утверждена на заседании кафедры АОИ, протокол № 218 от 15 января 2007 г.


Разработчик программы:

ст. преп. каф. АОИ, к.т.н. Т.О. Перемитина


Зав. кафедрой АОИ,

д.т.н., профессор Ю.П. Ехлаков


Рабочая программа согласована с факультетом


Декан ФСУ,

д.т.н., профессор Н.В. Замятин

1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ, ЕЕ МЕСТО В УЧЕБНОМ ПРОЦЕССЕ
   

1.1. Цель изучения дисциплины

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

1.2. Задачи изучения дисциплины

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

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

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

2. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
   
   0. Лекции – 26 часов.
      

1. Логика высказываний - 8 часов.

Введение. Математическая логика и ее применение. Понятие высказывания. Логические операции. Формулы логики выска­зываний. Таблицы истинности. Приоритет логических операций. Тавтология, противоречие, выполнимая формула. Проблема разрешимости. Список переменных формулы. Равносильные формулы. Критерий равносильности. Основные равносильности логики высказываний. Исчисление высказываний. Функции алгебры логики. Разложение булевых функций по переменным. Нормальные формы формул. Понятие элементарной дизъюнкции, элементарной конъ­юнкции. Дизъюнктивная и конъюнктивная нормальные формы. Теоремы о приведении фор­мулы ЛВ к ДНФ, к КНФ. Теорема о существовании КНФ (ДНФ) особого вида для тавтологии (противоречия). Понятие полной ЭК (ЭД) относительно данного списка переменных. Понятие совершенной ДНФ (КНФ).


2. Логические рассуждения – 6 часов.

Теоремы о существовании СДНФ и СКНФ. Единственность представления в СКНФ (СДНФ). Критерий равносильности. Закон двойственности. Понятие логического следования, критерий логического следования. Принцип дедукции. Схема рассуждения, правильность логического рассуждения. Способы проверки пра­вильности схем. Способы косвенного доказательства теорем. Понятие формальной теории, требования к аксиомам формальной теории. Принцип дедукции. Метод резолюций.


3. Логика предикатов – 4 часа.

Синтаксис и семантика языка логики предикатов. Формулы логики предикатов. Интерпретация формул. Клазуальная форма. Метод резолюций в логике предикатов. Равносильность, общезначимость, проблема разрешимости. Доказательство равносильностей логики предикатов. Приведение формул к предваренной нормальной форме. Ме­тод резолюций в логике предикатов, принцип логического программирования.


4. Неклассические логики и формальная арифметика – 4 часа.

Темпоральные логики. Нечеткая и модальные логики. Нечеткая арифметика. Алгоритмическая логика Ч. Хоара. Эгалитарные теории. Язык и правила вывода формальной арифметики. Непротиворечивость формальной арифметики. Теорема Генцена. Теорема Гёделя о неполноте. Автоматический вывод теорем. Логическое программирование. Логическая программа.


5.Основы теории алгоритмов – 4 часа.

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

0. Практические занятия – 16 часов.
   

1. Алгебра высказываний – 2 часа.
   
2. Нормальные формы формул – 2 часа.
   
3. Логические рассуждения – 2 часа.
   
4. Логика предикатов – 2 часа.
   
5. Алгебра Жегалкина – 2 часа.
   
6. Замкнутые классы булевых функций – 2 часа.
   
7. Рекурсивность функций – 2 часа.
   
8. Построение программ для машин Тьюринга – 2 часа.
   

0. Самостоятельная работа
   

1. Проработка лекционного материала. Форма контроля: тестовый опрос – 30 часов.
   
2. Подготовка к практическим занятиям. Форма контроля: самостоятельные или контрольные работы – 20 часов.
   

0. Темы контрольных работ
   

В курсе предусмотрено проведение 3 контрольных работ по следующим темам:

1. Логические операции и их приоритеты алгебры высказываний.
   
2. Предваренная нормальная форма. Общезначимость и выполнимость формул логики предикатов.
   
3. Неразрешимые алгоритмические проблемы.
   

0. Применение рейтинговой системы
   

Максимальный рейтинг дисциплины в семестре – 120 баллов.

Для получения зачета необходимо набрать 60 баллов.

Набор баллов:

Контрольные работы – 30 баллов:

1. Законы равносильностей алгебры высказываний – 10 баллов.
   
2. Кванторные операции и формулы логики предикатов – 10 баллов.
   
3. Основные направления уточнения понятия алгоритма – 10 баллов.
   

Если студент по уважительной причине не посетил занятие, на котором проводилась контрольная работа, то он может написать контрольную работу в резервный день.

Индивидуальные задания – 40 баллов:

№	Вид контроля	Баллы
1.	Высказывания и формулы алгебры высказываний	5
2.	Равносильные формулы алгебры высказываний	5
3.	Нормальные формы формул алгебры высказываний	5
4.	Логические рассуждения	5
5.	Формулы логики предикатов и предваренная нормальная форма формул логики предикатов	5
6.	Алгебра Жегалкина и замкнутые классы булевых функций	5
7.	Рекурсивность функций	5
8.	Построение программ для машин Тьюринга	5
Всего		40

При сдаче индивидуального задания позже установленного срока студент теряет от 50 до 100 % баллов, которые возможно получить за задание.


Тестовые опросы на лекциях – 20 баллов.


Коллоквиумы – 20 баллов.

1. Нормальные формы формул алгебры высказываний и логики предикатов – 10 баллов;
   
2. Класс рекурсивных функций и машинная арифметика.
   

Индивидуальное задание – 10 баллов.

Индивидуальное задание выполняют студенты желающие повысить свой рейтинг (не является обязательным).


Основная литература:

1. Смыслова З.А. Спецглавы математики. Часть 2: Учебное пособие. – Томск: Томский межвузовский центр дистанционного образования, 2001.
   
2. Шелупанов А.А., Зюзьков В.М. Математическая логика и теория алгоритмов. Учебное пособие.- Томск: STT, 2001.
   

Дополнительная литература:

1. Карпов Ю.Г. Теория автоматов. – СПб.: Питер, 2002.