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



Скачать 148.63 Kb.
Дата18.01.2013
Размер148.63 Kb.
ТипРабочая программа


Министерство образования Российской Федерации
Санкт-Петербургский государственный электротехнический

университет “ЛЭТИ”

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


дисциплины



МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ


Для подготовки бакалавров по направлению 552800 – “Информатика и вычислительная техника” и дипломированных специалистов по направлению 654600 – “Информатика и вычислительная техника”:

а) специальности 220100 – “Вычислительные машины, комплексы, системы и сети”,

б) специальности 220300 – “Системы автоматизированного проектирования”







Санкт-Петербург


2002

Санкт-Петербургский государственный электротехнический


университет “ЛЭТИ”

“УТВЕРЖДАЮ”



Проректор по учебной работе
проф. ___________ Ушаков В.Н.
“_____”_______________2002 г.

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


дисциплины



МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

Для подготовки бакалавров по направлению 552800 – “Информатика и вычислительная техника” и дипломированных специалистов по направлению 654600 – “Информатика и вычислительная техника”:

а) специальности 220100 – “Вычислительные машины, комплексы, системы и сети”,

б) специальности 220300 – “Системы автоматизированного проектирования”
Факультет компьютерных технологий и информатики

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



Курс – 2

Семестр – 3


Лекции

48 ч.




Экзамен

семестр













3

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

16 ч.




























Аудиторные занятия

64 ч.





Самостоятельные занятия

46 ч.




Всего часов

110 ч.






2002

Рабочая программа обсуждена на заседании кафедры вычислительной техники “____”_______________ 2002 г., протокол № ______.

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

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



Рабочая программа одобрена методической комиссией факультета компьютерных технологий и информатики “____”_____________2002 г.
Цели и задачи дисциплины:
Цель дисциплины – ознакомление с основными понятиями и методами математической логики и теории алгоритмов с ориентацией на их использование в практической информатике и вычислительной технике.

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



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

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

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

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



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



ВВЕДЕНИЕ
Предмет курса, его связь с другими дисциплинами учебного плана, значение в подготовке специалистов по направлению "Информатика и вычислительная техника" и инженеров-системотехников по специальности 220100 – “Вычислительные машины, комплексы, системы и сети”. Обзор литературы по курсу.

Раздел 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







1




1

3




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






















1

Основы логики высказываний

2




2

4

3

7

3

2

Вывод в логике высказываний

5




2

7

4

11

3




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






















3

Язык логики предикатов

4







4

6

10

3

4

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

6




8

14

6

20

3




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






















5

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

6




2

8

4

12

3

6

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

4







4

4

8

3




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



















3

7

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

6







6

6

12

3

8

Сложность алгоритмов

8




2

10

6

16




9

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

4







4

6

10







ЗАКЛЮЧЕНИЕ

2







2

1

3

3

ИТОГО:

48




16

64

46

110





ЛИТЕРАТУРА
Основная

Название, библиографическое описание

Л


Пз
К-во экз. в библ. (на каф.)
Гриф
1
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988
3
3
77(0)

2

Исследование вычислительной сложности алгоритмов логического вывода: Методические указания к курсовой работе по дисциплине "Математическая логика и теория алгоритмов"/ Сост.: M.Г. Пантелеев, А.С. Календарев; ГЭТУ. СПб., 1997.
3
3
20(60)

ч.з.-20

3
Логический вывод и сложность алгоритмов: Методические указания к практическим занятиям по дисциплине "Математическая логика и теория алгоритмов"/ Сост.: M.Г. Пантелеев, А.С. Календарев; ГЭТУ. СПб., 1998.
3
3
24(60)

ч.з.-20

4
Ковальски Р. Логика в решении проблем. – М.: Наука, 1990
3
3
26(0)

5
Тейз А. и др. Логический подход к искусственному интеллекту. - М.: Мир, 1990.3
3
3
23(0)



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



Название, библиографическое описание
К-во экз. в библ. (на каф.)
1

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979.

11(0)
2

Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. - М.: Мир, 1982.

15(0)
3

Мендельсон Э. Введение в математическую логику. - М.: Наука, 1971

97
4

Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. - М.: Наука, 1983.

0


Автор




к.т.н., доцент

Пантелеев М.Г.








Рецензент




к.т.н., доцент кафедры МО ЭВМ

Ивановский С.А.








Зав. кафедрой

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




д.т.н., профессор

Пузанков Д.В.








Декан факультета




компьютерных технологий

и информатики




д.т.н., профессор

Герасимов И.В.







Программа согласована:










Зав. кафедрой

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




д.т.н., профессор

Пузанков Д.В.








Зав. отделом учебной литературы

Киселева Т.В.







Председатель методической комиссии

факультета компьютерных технологий

и информатики




к.т.н., доцент

Чугунов Л.А.








Руководитель методического отдела




к.т.н., доцент

Марасина Л.А.



Похожие:

Рабочая программа дисциплины математическая логика и теория алгоритмов iconРабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика
Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются получение теоретических знаний по основам математическая...
Рабочая программа дисциплины математическая логика и теория алгоритмов iconУчебная программа Дисциплины р2 «Математическая логика и теория алгоритмов»
Фгос впо, содействует формированию мировоззрения и системного мышления. Целью преподавания дисциплины «Математическая логика и теория...
Рабочая программа дисциплины математическая логика и теория алгоритмов iconРабочая программа дисциплины Математическая логика и теория алгоритмов

Рабочая программа дисциплины математическая логика и теория алгоритмов iconРабочая программа дисциплины математическая логика и теория алгоритмов
Рабочая программа обсуждена на заседании кафедры вычислительной техники “ ” 2002 г., протокол №
Рабочая программа дисциплины математическая логика и теория алгоритмов iconРабочая программа по курсу «Математическая логика и теория алгоритмов» для специальности 090102 «Компьютерная безопасность»
«Математическая логика и теория алгоритмов», рекомендованной Министерством образования Российской Федерации в 2000 году для специальностей...
Рабочая программа дисциплины математическая логика и теория алгоритмов iconРабочая программа дисциплины математическая логика и теория алгоритмов (наименование дисциплины)
«Информатика и вычислительная техника», а также задачами, стоящими перед Новосибирским государственным университетом по реализации...
Рабочая программа дисциплины математическая логика и теория алгоритмов icon1. Организационно-методический раздел. 1 Название курса. Математическая логика и теория алгоритмов
Основной курс "Математическая логика и теория алгоритмов" предназначен для студентов первого курса отделения прикладной инфоматики...
Рабочая программа дисциплины математическая логика и теория алгоритмов iconРабочая программа дисциплина ен. Ф. 01. 04 Математическая логика и теория алгоритмов
Специальность 230102 – Автоматизированные системы обработки информации и управления
Рабочая программа дисциплины математическая логика и теория алгоритмов iconПрограмма дисциплины дпп. 04 Математическая логика и теория алгоритмов
Цель дисциплины: ознакомление студентов с основными приемами символической логики, используемыми при исследовании структуры математических...
Рабочая программа дисциплины математическая логика и теория алгоритмов iconУчебно-методический комплекс учебной дисциплины Математическая логика и теория алгоритмов Специальность 032200. 00 Физика
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org