Geum.ru

Рабочая программа по дисциплине Математическая логика и теория алгоритмов для специальности 220400 Программное обеспечение вычислительной техники и автоматизированных систем

Вид материалаРабочая программа

Содержание


1. Цели и задачи дисциплины, ее место в учебном процессе 1.1. Цель преподавания дисциплины
1.2. Задачи изучения дисциплины
1.3. Перечень дисциплин, усвоение которых студентами, необходимо для изучения данной дисциплины
2. Требования к знаниям и умениям студентов по дисциплине
3. Распределение трудоемкости дисциплины по темам и видам занятий
4. Содержание лекционного курса
5. Перечень тем практических занятий отсутствуют 6. Перечень лабораторных работ
7. Задания для самостоятельной работы студентов
8. Курсовой проект отсутствует 9. Курсовая работа отсутствует 10. Расчетно-графическая работа
13. Список основной и дополнительной литературы по дисциплине Основная
Подобный материал:
Саратовский Государственный технический университет

Кафедра «Техническая физика и информационные технологии»


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


по дисциплине

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

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


Курс 2

Семестр 3

Часов в неделю: лекции 1, лабораторные занятия 2

Курсовая работа –

Курсовой проект –

Расчетно-графическая работа –

Контрольная работа –

Экзамен 3 семестр

Зачет –


Энгельс, 2009.

1. Цели и задачи дисциплины, ее место в учебном процессе

1.1. Цель преподавания дисциплины


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

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


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

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


Для изучения дисциплины необходимо знание курсов «Математический анализ», «Алгебра», «Дискретная математика», «Информатика».

2. Требования к знаниям и умениям студентов по дисциплине


Студент должен знать:
  • формальные методы логического обоснования;
  • способы формального описания алгоритмов;
  • основные направления математической логики.

Студент должен уметь:
  • формализовать логические рассуждения;
  • строить формальные логические выводы;
  • составлять алгоритмы.



3. Распределение трудоемкости дисциплины по темам и видам занятий





№ модуля
№ недели
№ темы
Наименование темы
Часы

всего

лекции
лаб.зан
срс

I
1-3
1
Логика высказываний
18
4
8
6




4-6
2
Логика предикатов
18
4
8
6




7-9
3
Формальные системы
16
2
2
12

II
10-11
4
Алгоритмические системы
12
2
2
8




12-13
5
Вычислительные модели
16
2
8
6




14-15
6
Теория рекурсии
12
1
4
7




16-17
7
Алгоритмическая сложность и разрешимость
8
2
2
4

Итого
100
17
34
49


4. Содержание лекционного курса


№ темы
Всего часов
№ лекции
Тема лекции

1
2
1
1.1. Высказывания. 1.2. Закон исключенного третьего. 1.3. Синтаксис логики высказываний. 1.4. Тавтологии. 1.5. Законы логики высказываний. 1.6. Равносильность.

1
2
2
1.7. Логическое следствие.1.8. Правила вывода. 1.9. Дедуктивный метод. 1.10. Принцип резолюций.

2
2
3
2.1. Высказывания и предикаты. 2.2. Кванторы. 2.3. Связанные и свободные переменные. 2.4. Категорические высказывания.

2
2
4
2.5. Непосредственные заключения. 2.6. Опосредованные заключения. 2.7. Символизация языка. 2.8. Оценочная процедура. 2.9. Общезначимость. 2.10. Логическое следствие. 2.11. Принцип логического программирования.

3
2
5
3.1. Метатеория формальных систем. 3.2. Обзор неклассических логик. 3.3. Формальные грамматики.

4
2
6
4.1. Понятие алгоритма. 4.2. Основные свойства алгоритмов. 4.3. Эффективные алгоритмы. 4.4. Формальный вывод. 4.5. Канонические системы. 4.6. Нормальные системы. 4.7. Продукционная система Поста.

5
2
7
5.1. Машины Тьюринга. 5.2. Нормальные алгоритмы Маркова. 5.3. Машины Колмогорова. 5.4. Тезис Черча.

6-7
2
8
6.1. Рекурсивное определение. 6.2. Общерекурсивные функции. 6.3. Примитивно-рекурсивные функции. 6.4. Распространение принципов рекурсии на множества и предикаты. 6.5. Сводимость видов рекурсии. 7.1. Алгоритмически неразрешимые проблемы. 7.2. Меры сложности алгоритмов.

7
1
9
7.3. Классы задач P и NP. 7.4. NP-неполные задачи. 7.5. Понятие сложности вычислений.


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

отсутствуют


6. Перечень лабораторных работ


№ темы
Всего часов
№ занятия
Тема лабораторной работы

1
2
1
Логические функции и логические операции

1
2
2
Формализация естественного языка – логика высказываний

1
2
3
Доказательство тавтологий

1
2
4
Вывод логического следствия

2
2
5
Формализация естественного языка – логика предикатов

2
2
6
Категорические высказывания

2
2
7
Непосредственные и опосредованные заключения

2
2
8
Логический вывод в логике предикатов

3
2
9
Формальные системы - аксиоматика

4
2
10
Свойства алгоритмов

5
2
11
Алгоритмы для машины Тьюринга

5
2
12
Алгоритмы для машины Тьюринга

5
2
13
Нормальные алгоритмы Маркова

5
2
14
Нормальные алгоритмы Маркова

6
2
15
Рекурсивное описание

6
2
16
Примитивно-рекурсивные функции

7
2
17
Меры сложности алгоритмов



7. Задания для самостоятельной работы студентов


№ темы
Всего часов
Вопросы для самостоятельного изучения
Литература

1
3
Индуктивные рассуждения.
25 (с.5)

1
3
Рассуждения и их классификация.
25 (с. 31)

2
3
Логика предикатов с равенством.
12 (с. 86)

2
3
Принцип логического программирования.
20 (с. 34, с. 173)

3
2
Формальные языки. Классификация Н. Хомского.
8 (с. 62)

3
2
Первая проблема Гильберта.
9 (с. 137)

3
2
Описание синтаксиса и семантики языков программирования.
24 (с. 67)

3
2
Проблема полноты формальной системы. Теорема Геделя.
14 (с. 17)

3
2
Темпоральные логики высказываний линейного времени и вычислительных деревьев: их синтаксис и семантика.
15 (с. 203)

3
2
Пропозициональная динамическая логика: ее синтаксис и семантика.
15 (с. 45)

4
3
Алгоритмический подход к понятию количества информации.
23 (с. 224)

4
3
Вероятностные алгоритмы.
19 (с. 74)

4
2
Понятие относительного алгоритма.
21 (с. 217)

5
3
Машины Шёнхаге.
23 (с. 42)

5
3
Машины Поста.
6 (с. 318)

6
3
Обще-рекурсивные функции
21(с. 28)

6
4
Рекурсивные предикаты
10 (с. 53)

7
2
Сложность и энтропия конструктивных объектов.
14 (с. 179)

7
2
Верхние и нижние оценки сложности решения задач.
23 (с. 220)




8. Курсовой проект

отсутствует

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

отсутствует

10. Расчетно-графическая работа

отсутствует

11. Контрольная работа

отсутствует

12. Экзаменационные вопросы

  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. Классы задач P и NP.
  28. Влияние теории алгоритмов на практику программирования.


13. Список основной и дополнительной литературы по дисциплине

Основная:

  1. Верещагин. Лекции по математической логике и теории алгоритмов.
  2. Гетманова А.Д. Учебник по логике. – М.: ЧеРо, 1997.
  3. Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука, 1987.
  4. Ивлев Ю.В. Логика: учебник для вузов.- М.: Логос, 1997.
  5. Игошин В.И. Математическая и теория алгоритмов. – Саратов: изд. СГУ, 1991.
  6. Клини С. Математическая логика.– М.: Мир, 1973.
  7. Ковальский Р. Логика в решении проблем. – М.: Наука, 1990.
  8. Лавров С.С. Лекции по теории программирования. – СПб.: изд. НЕСТОР, 1999.
  9. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. – Москва: "Лань", 1999.
  10. Мальцев А.И. Алгоритмы и рекурсивные функции.
  11. Мендельсон Э. Введение в математическую логику. – М.: Наука, 1984.
  12. Непейвода Н.Н. Прикладная логика. – Новосибирск: изд НГУ, 2000.
  13. Новиков П.С. Элементы математической логики. – М.: Наука, 1973.



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

  1. Ершов Ю.Л. Определимость и вычислимость. – Новосибирск: Научная книга, 2000.
  2. Логический подход к искусственному интеллекту (от модальной логики к логике баз данных). – М.: Мир, 1998.
  3. Катленд Н. Вычислимость.
  4. Марков А.А., Нагорный Н.М. Теория алгорифмов. – М.: Наука, 1984.
  5. Клини С. Введение в метаматематику. – М.: ИЛ, 1957.
  6. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. – М.: Наука, 1983.
  7. Метакидес Г., Нероуд А. Принципы логики и логического программирования. – Москва: "Факториал", 1998.
  8. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость.
  9. Соар Р. Вычислимо перечислимые множества и степени.
  10. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и положения. – М.: Наука, 1987.
  11. Хигман Б. Сравнительное изучение языков программирования, М: Мир, 1974.
  12. Поспелов Д.А. Моделирование рассуждений. Опыт анализа мыслительных актов. – М.: Радио и связь, 1989.



14. Использование наглядных пособий, ТСО, вычислительной техники


При чтении курса лекций используется мультимедиа-проектор.

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


Рабочую программу составила доц. Шатурная О.С.