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

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

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

Содержание Рабочая программа дисциплины Составитель рабочей программы Кафедра ПМ и ВТ Дискретная математика Требования к уровню освоения дисциплины Содержание рабочей программы Тема 2. Вывод в логике высказываний Тема 4. Логический вывод в логике предикатов Раздел 3. ФОРМАЛЬНЫЕ (АКСИОМАТИЧЕСКИЕ) СИСТЕМЫ Тема 6. Метатеория формальных систем Раздел 4. ТЕОРИЯ АЛГОРИТМОВ Тема 8. Сложность алгоритмов Тема 9. Алгоритмическая логика Перечень практических занятий Распределение учебных часов по темам и видам занятий

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

• Рабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов шифр, 316.78kb.
• Рабочей программы учебной дисциплины дв2 Математическая логика и теория алгоритмов, 50.1kb.
• Рабочая учебная программа по дисциплине «Математическая логика и теория алгоритмов», 69.99kb.
• Рабочая учебная программа по дисциплине математическая логика, 72.41kb.
• Рабочая программа дисциплины «Математическая логика и теория алгоритмов» Направление, 175.54kb.
• Рабочая программа дисциплина ен. Ф. 01. 04 Математическая логика и теория алгоритмов, 415.85kb.
• Рабочая программа учебной дисциплины ен. Ф. 01. 04 Математическая логика и теория алгоритмов, 259.76kb.
• Рабочая программа по дисциплине Математическая логика и теория алгоритмов для специальности, 135.74kb.
• В. Б. Гисин Дисциплина по выбору «Математическая логика и теория алгоритмов» Настоящий, 5.87kb.
• Программа дисциплины по кафедре Прикладная математика и информатика математическая, 224kb.

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

Государственное образовательное учреждение

высшего профессионального образования

«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО-СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ»

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

	УТВЕРЖДАЮ
	Проректор по учебной работе
	________________
	«____»_______________ 2009 г.

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

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


Индекс дисциплины по учебному плану ЕН.Ф.01.3


Направление 230200 Информационные системы


Специальность 230201 Информационные системы и технологии


Самара

2009


Составитель рабочей программы к. ф.-м. н., доцент А.Ю. Трусова


Рецензент к. ф.-м. н., доцент Л.К. Ширяева


Рабочая программа утверждена на заседании кафедры ПМ и ВТ

(протокол № от «____» _________ 2009 г.)


Заведующий кафедрой

____ _____________ 2009 г. _______________ С.А. Пиявский


СОГЛАСОВАНО


Декан

факультета

____ _____________ 2009 г. _________________ С.А. Пиявский


Начальник

методического отдела

____ _____________ 2009 г. _______________ С.А. Пиявский

ОДОБРЕНО

Председатель

методической


комиссии факультета


____ _____________ 2009 г. ________________ С.А. Пиявский


Факультет информационных систем и технологий

Кафедра ПМ и ВТ

Курс – 2

Семестр – 4

Лекции		32ч.		Экзамен		семестр
						4
Практические занятия		32ч.
	Аудиторные занятия	64ч.
	Самостоятельные занятия	45 ч.
	Всего часов	109ч.

Рабочая программа согласована с рабочими программами изученных ранее дисциплин:

1. Дискретная математика
   

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


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

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

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

1. Знать основные понятия и методы математической логики и теории алгоритмов, используемые в информатике и вычислительной технике.
   
2. Уметь использовать их для построения несложных логических моделей предметных областей, реализации логического вывода и оценки вычислительной сложности алгоритмов
   
3. Иметь представление о направлениях развития данной дисциплины и перспективах ее использования в информатике и вычислительной технике.
   

Содержание рабочей программы

Раздел 1. ЛОГИКА ВЫСКАЗЫВАНИЙ

Тема 1. Основы логики высказываний

Язык логики высказываний. Синтаксис языка: алфавит и правила построения формул. Семантика языка, интерпретация формул. Свойства формул: общезначимость, выполнимость, противоречивость.

Методы анализа выполнимости и общезначимости формул: семантическое дерево, тривиальный алгоритм, алгоритм Квайна, алгоритм редукции, алгебраический подход. Алгоритм преобразования формул в КНФ. Базовый алгоритм проверки общезначимости КНФ, модификация Девиса-Патнема.

Тема 2. Вывод в логике высказываний

Понятие логического следования, проблема дедукции. Принцип дедукции. Правило резолюций, метод резолюций. Стратегии метода резолюций.


Раздел 2. ЛОГИКА ПРЕДИКАТОВ

Тема 3. Язык логики предикатов

Синтаксис языка логики предикатов: алфавит, термы, атомы, правила построения формул. Свободные и связанные вхождения переменных, замкнутые формулы. Семантика языка логики предикатов, интерпретация формул.

Тема 4. Логический вывод в логике предикатов

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


Раздел 3. ФОРМАЛЬНЫЕ (АКСИОМАТИЧЕСКИЕ) СИСТЕМЫ

Тема 5. Основы теории формальных систем

Понятия формальной системы и формального вывода. Исчисление высказываний как формальная система, множественность аксиоматизаций. Теорема дедукции. Связь выводимости и истинности формул в логике высказываний. Исчисление предикатов как формальная система. Примеры формального вывода.

Тема 6. Метатеория формальных систем

Основные свойства формальных систем: непротиворечивость, полнота, разрешимость. Теоремы о неполноте формальных систем, смысл и значение теорем Геделя для практической информатики.


Раздел 4. ТЕОРИЯ АЛГОРИТМОВ

Тема 7. Алгоритмические системы. Алгоритмически разрешимые и неразрешимые задачи

Понятие алгоритмической системы. Частично-рекурсивные функции, тезис Черча.

Машины Тьюринга, тезис Тьюринга. Рекурсивные и рекурсивно-перечислимые множества и языки. Алгоритмически разрешимые и неразрешимые задачи. Проблема остановки, проблема пустой ленты, метод сведения.

Тема 8. Сложность алгоритмов

Меры сложности алгоритмов: временная и емкостная сложность. Асимптотическая сложность, порядок сложности. Сложность в среднем и в худшем случае.

Языки и задачи. Легко- и трудноразрешимые задачи, классы задач P и NP. NP-полные задачи. Недетерминированная машина Тьюринга (НМТ). Сложность моделирования НМТ с помощью ДМТ. Примеры NP-полных задач. Полиномиальная сводимость и полиномиальная трансформируемость. Теорема Кука. Примеры практически значимых NP-полных задач. Задача 3-выполнимости, доказательство NP-полноты методом сведения.

Тема 9. Алгоритмическая логика

Алгоритмическая логика Хоара. Предусловие и постусловие алгоритма. Тройки Хоара. Формальная постановка задачи верификации. Понятие слабейшего предусловия и его основные свойства. Верификация операторов присваивания и их последовательностей.

ЗАКЛЮЧЕНИЕ

Перспективы развития методов математической логики для решения задач спецификации и верификации программно-аппаратных средств, создания систем искусственного интеллекта и Семантического Web.

Перечень практических занятий

№	Наименование темы занятия	Номер темы программы
1	Язык логики высказываний, анализ свойств логических формул. Преобразование формул в КНФ.	1
2	Метод резолюций в логике высказываний. Сравнение эффективности различных стратегий.	2
3	Язык логики предикатов. Преобразование формул в предваренную форму.	4
4	Преобразование формул логики предикатов в сколемовскую и клаузальную формы.	4
5	Метод резолюций в логике предикатов. Унификация атомов, построение наиболее общего унификатора.	4
6	Примеры логического программирования, реализация логического вывода на хорновских дизъюнктах.	4
7	Примеры формального вывода в логических исчислениях	5
8	Оценка сложности алгоритмов	8

Распределение учебных часов по темам и видам занятий

№ темы	Название разделов и тем
		Лекции (кол-во часов)	Практ. Занятия (кол-во часов)	Аудит. Занятия (кол-во часов)	№ уч. недели
	Раздел 1. ЛОГИКА ВЫСКАЗЫВАНИЙ				12
1	Основы логики высказываний	2	2	4
2	Вывод в логике высказываний	2	2	4
	Раздел 2. ЛОГИКА ПРЕДИКАТОВ				13
3	Язык логики предикатов	4	2	6
4	Логический вывод в логике предикатов	4	2	6
	Раздел 3. ФОРМАЛЬНЫЕ (АКСИОМАТИЧЕСКИЕ) СИСТЕМЫ				14
5	Основы теории формальных систем	4	2	6
6	Метатеория формальных систем	4	2	4
	Раздел 4. ТЕОРИЯ АЛГОРИТМОВ				15,16
7	Алгоритмические системы. Алгоритмически разрешимые и неразрешимые задачи.	4	2	6
8	Сложность алгоритмов	4	2	6
9	Алгоритмическая логика	2	2	2	17
	ЗАКЛЮЧЕНИЕ	1		1
ИТОГО:		32	16	48

Литература


Основная

1. Шапорев С.Д.Математическая логика. Курс лекций и практических занятий. – СПб.:БХВ-Петербург, 2005. – 416 с.
   
2. Капитонова Ю.В. и др. Лекции по дискретной математике. – СПб.: БХВ-Петербург, 2004. – 624 с.
   
3. Гаврилов Г. П., Сапоженко А. А. "Задачи и Упражнения по Курсу Дискретной Математики". Москва, ФИЗМАТЛИТ, 2004ю – 416 с.
   
4. Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2001. – 304 с.
   
5. Асеев Г.Г., Абрамов О.М., Ситников Д.Э. Дискретная математика: Учебное пособие.- Ростов н/Д: «Феникс», Харьков: «Торсинг», 2003.- 144 с. (Серия «Учебники»).
   
6. Непейвода Н.Н. Прикладная логика. Учебное пособие. Ижевск, Изд-во Удмурского университета, 1997, 385 с.
   

Дополнительная

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979.
   
2. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. - М.: Мир, 1982.
   

Приложение. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ (МАТЕРИАЛЫ) ДЛЯ ПРЕПОДАВАТЕЛЯ.

Курс математической логики требует от студентов умения абстрагироваться и грамотно оперировать математическими категориями. С этой целью рекомендуется использовать лекции- дискуссии. На семинарских занятиях можно использовать, так называемые деловые игры. Студенты могут быть разделены на группы, каждая из которых самостоятельно придумывает задачи. Уровень сложности задач, скорость решения, грамотное объяснение также предлагается оценивать группам-соперникам. Деловые игры рекомендуется использовать при изучении логики высказываний, логики предикатов, алгебры логики, теории алгоритмов.

Приложение. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ СТУДЕНТОВ.

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

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

Инновационные методы в высшем профессиональном образовании:

• электронные учебники и учебные пособия;
  
• мультимедийные учебники и пособия;
  
• компьютерные диалоговые учебники;
  
• электронные ресурсы библиотеки;
  
• лекционные презентации;
  
• видеолекции и материалы на СD;
  
• аудиолекции и материалы на CD;
  
• электронные практикумы;
  
• компьютерные обучающие и расчетные программы;
  
• использование ресурсов Internet;
  

Материалы, устанавливающие содержание и порядок проведения промежуточных и итоговых аттестаций:

2. выполнение домашних работ;
   
3. выполнение аудиторных контрольных работ;
   
4. контроль остаточных знаний;
   
5. экзамен.
   

Контроль остаточных знаний. Список вопросов.

1. Высказывания (суждения) математической логики.
   
2. Основные логические операции. Таблица истинности. Приоритет выполнения логических операций
   
3. Законы и следствия алгебры логики.
   
4. Логические функции и переменные. Определение значений логических функций
   
5. Формализация сложных высказываний
   
6. Тождественность логических формул
   
7. ДНФ и КНФ. Приведение логических функций и СДНФ и СКНФ.
   

8. Методы анализа выполнимости и общей значимости формул: семантическое дерево, тривиальный алгоритм, алгоритм Квайна, алгоритм редукции, алгебраический подход.

9. Принцип дедукции. Правило резолюций, метод резолюций. Стратегии метода резолюций.

10. Синтаксис языка логики предикатов: алфавит, термы, атомы, правила построения формул.

11. Свободные и связанные вхождения переменных, замкнутые формулы. 12. Семантика языка логики предикатов, интерпретация формул.

13.Метод резолюций в логике предикатов.

14. Основные свойства формальных систем: непротиворечивость, полнота, разрешимость.

15. Понятие алгоритмической системы. Частично-рекурсивные функции, тезис Черча.

16. Машины Тьюринга, тезис Тьюринга.

17. Рекурсивные и рекурсивно-перечислимые множества и языки.

18. Меры сложности алгоритмов: временная и емкостная сложность.

19. Асимптотическая сложность, порядок сложности.

20. Сложность в среднем и в худшем случае.

Вопросы к экзамену:

1. Язык логики высказываний. Синтаксис языка: алфавит и правила построения формул.
   
2. Семантика языка, интерпретация формул.
   
3. Свойства формул: общезначимость, выполнимость, противоречивость.
   
4. Методы анализа выполнимости и общезначимости формул: семантическое дерево, тривиальный алгоритм, алгоритм Квайна, алгоритм редукции, алгебраический подход.
   
5. Алгоритм преобразования формул в КНФ.
   
6. Базовый алгоритм проверки общезначимости КНФ, модификация Девиса-Патнема.
   
7. Понятие логического следования, проблема дедукции.
   
8. Принцип дедукции.
   
9. Правило резолюций, метод резолюций.
   
10. Стратегии метода резолюций.
    
11. Синтаксис языка логики предикатов: алфавит, термы, атомы, правила построения формул.
    
12. Свободные и связанные вхождения переменных, замкнутые формулы. Семантика языка логики предикатов, интерпретация формул.
    
13. Предваренная, сколемовская и клаузальная формы.
    
14. Алгоритм получения клаузальной формы.
    
15. Метод резолюций в логике предикатов.
    
16. Подстановка, композиция подстановок, унификатор.
    
17. Алгоритм построения наиболее общего унификатора.
    
18. Хорновские дизъюнкты и метод резолюций на хорновских дизъюнктах.
    
19. Принцип логического программирования.
    
20. Понятия формальной системы и формального вывода.
    
21. Исчисление высказываний как формальная система, множественность аксиоматизаций.
    
22. Теорема дедукции. Связь выводимости и истинности формул в логике высказываний.
    
23. Исчисление предикатов как формальная система. Примеры формального вывода.
    
24. Основные свойства формальных систем: непротиворечивость, полнота, разрешимость.
    
25. Теоремы о неполноте формальных систем, смысл и значение теорем Геделя для практической информатики.
    
26. Понятие алгоритмической системы. Частично-рекурсивные функции, тезис Черча.
    
27. Машины Тьюринга, тезис Тьюринга.
    
28. Рекурсивные и рекурсивно-перечислимые множества и языки.
    
29. Алгоритмически разрешимые и неразрешимые задачи.
    
30. Проблема остановки, проблема пустой ленты, метод сведения.
    
31. Меры сложности алгоритмов: временная и емкостная сложность.
    
32. Асимптотическая сложность, порядок сложности.
    
33. Сложность в среднем и в худшем случае.
    
34. Языки и задачи. Легко- и трудноразрешимые задачи, классы задач P и NP.
    
35. NP-полные задачи. Недетерминированная машина Тьюринга (НМТ).
    
36. Сложность моделирования НМТ с помощью ДМТ.
    
37. Примеры NP-полных задач.
    
38. Полиномиальная сводимость и полиномиальная трансформируемость.
    
39. Теорема Кука. Примеры практически значимых NP-полных задач.
    
40. Задача 3-выполнимости, доказательство NP-полноты методом сведения.
    
41. Алгоритмическая логика Хоара. Предусловие и постусловие алгоритма.
    
42. Тройки Хоара. Формальная постановка задачи верификации.
    
43. Понятие слабейшего предисловия и его основные свойства.
    
44. Верификация операторов присваивания и их последовательностей.