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




Скачать 85.75 Kb.
НазваниеРабочая программа дисциплины Математическая логика и теория алгоритмов Направление
Дата07.02.2013
Размер85.75 Kb.
ТипРабочая программа
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ


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


УТВЕРЖДАЮ


Декан факультета информатики

Сущенко С.П.

" " декабря 2010 г.


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


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


Направление подготовки


230700 Прикладная информатика


Квалификация выпускника


Бакалавр


Форма обучения


Очная


Томск

2010


1. Цели освоения дисциплины


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


2. Место дисциплины в структуре ООП бакалавриата


Раздел образовательной программы: Б.3. Профессиональный цикл. Базовая часть.

Для изучения курса необходимо знание следующих дисциплин:

- дискретная математика.

Для того чтобы приступить к изучению курса «Математическая логика и теория алгоритмов», студент должен обладать следующими знаниями и умениями:

- знать теорию множеств, теорию отношений, теорию булевых функций.

Знания и умения, полученные в ходе освоения данной дисциплины, понадобятся при изучении таких последующих дисциплин ООП, как:

- теория графов;

- алгоритмы и анализ сложности;

- основы программирования;

- базы данных;

- методы оптимизации и исследование операций;

- интеллектуальные системы;

- теория автоматов и формальных языков;

- теория систем и системный анализ.


3. Компетенции обучающегося, формируемые в результате освоения дисциплины «Математическая логика и теория алгоритмов»


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


- знание основных понятий и методов математической логики;

- знание основных понятий теории алгоритмов;

- умение применять на практике методы математической логики;


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


4. Структура и содержание дисциплины «Математическая логика и теория алгоритмов»


Общая трудоемкость дисциплины составляет 3 зачетных единиц, 108 часов.






п/п



Раздел

Дисциплины

Семестр

Неделя семестра

Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)

Формы текущего контроля успеваемости (по неделям семестра)

Форма промежуточной аттестации (по семестрам)













всего

лекции

сем

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




1

Логика высказываний

2

1-2

12

4




8




2

Методы анализа выполнимости и общезначимости формул

2

3-4

12

4




8




3

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

2

5-6

18

4

4

10

Тест

4

Логика предикатов

2

7-8

14

4




10




5

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

2

9-10

18

4

4

10

Тест


6

Формальные системы

2

11-12

12

4




8

Тест

7

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

2

13-14

11

4




7




8

Теория алгоритмов

2

15-16

11

4




7

Тест

ИТОГО










108

32

8

68

Экзамен



Лекционный курс

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


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

Тема 2. Методы анализа выполнимости и общезначимости формул.


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

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


Понятие логического следования Методы логического вывода. Метод резолюций в логике высказываний, стратегии вычеркивания.

Тема 4. Логика предикатов.


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

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


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

Тема 6. Формальные системы.


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

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


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

Тема 8. Теория алгоритмов.


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


Семинары.


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

  2. Вывод в логике предикатов.



5. Образовательные технологии.


В ходе преподавания дисциплины используются следующие образовательные технологии:


- лекционный курс;

- семинарские занятия с решением задач по конкретным темам.


6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.


Самостоятельная работа студентов по дисциплине организуется в следующих формах:

- самостоятельное изучение основного теоретического материала, ознакомление с дополнительной литературой, Интернет-ресурсами;

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

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


7. Учебно-методическое и информационное обеспечение дисциплины «Математическая логика и теория алгоритмов»

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


  1. Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2000.


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


б) дополнительная литература:


  1. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М., Наука, 1984.


2. Ковальски Р. Логика в решении проблем. – М.: Наука, 1990.

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

4. Непейвода Н.Н. Прикладная логика. Учебное пособие. – Ижевск, изд-во Удм. ун-та, 1997.


    8. Материально-техническое обеспечение дисциплины



Требуется обеспечение литературой, которую в достаточном объеме может предложить книжный фонд Научной библиотеки Томского госуниверситета и факультета информатики.


Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ООП ВПО по направлению подготовки 230700 Прикладная информатика.


Автор: ст. преподаватель В.В. Матушевский

Рецензент: д.физ-мат.н., профессор О. А. Змеев.


Программа одобрена на заседании Ученого Совета Факультета информатики
от «___»_________2010 г., протокол № ___.

Похожие:

Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление iconПрограмма дисциплины математическая логика и теория алгоритмов
Рабочая программа дисциплины "Математическая логика и теория алгоритмов" предназначена для студентов 3 курса
Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление iconРабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов
Математическая логика и теория алгоритмов в соответствии требованиями фгос впо, утвержденного приказом Министра образования и науки...
Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление icon«Математическая логика и теория алгоритмов»
Математическая логика и теория алгоритмов" является фундаментальное образование в области принципов построения эффективных и надежных...
Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление iconУльянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов
Ульянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов. – М.: Мгапи, 2003. – 80 с
Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление iconРабочая программа учебной дисциплины
Учебная дисциплина «Математическая логика и теория алгоритмов» знакомит с основными понятиями и положениями современной «компьютерной...
Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление iconМатематическая логика и теория алгоритмов

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

Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление iconПрограмма дисциплины по кафедре Прикладная математика и информатика математическая логика и теория алгоритмов
Утверждена научно-методическим советом университета для направлений подготовки (специальностей) в области информатики и вычислительной...
Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление iconРабочая программа по дисциплине “Математическая логика и теория алгоритмов” для специальности 230105 (220400) “Программное обеспечение вычислительной техники и автоматизированных систем”
Томский государственный университет систем управления и радиоэлектроники (тусур )
Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление iconМинистерство образования и науки российской федерации государственное образовательное учреждение высшего профессионального образования
Цель дисциплины «Математическая логика и теория алгоритмов» – формирование систематизированных знаний в области математической логики...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница