Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Программа дисциплины «Инструментальные средства разработки информационных... 1 388.26kb.
Программа для вступительного испытания "Математика и информатика"... 1 69.09kb.
Рабочая программа производственной практики направление подготовки... 1 149.36kb.
Рабочая программа трудоемкость дисциплины 6 зачетных единиц направление... 1 318.95kb.
Кафедра информационных систем 4 583.96kb.
Методические указания к курсовой работе по дисциплине Базы данных... 10 522.88kb.
«проблемы автоматизации создания информационных систем и технологий» 1 394.65kb.
Параллельные вычисления 1 415.89kb.
Темы курсовых работ по дисциплине «Математическая логика и теория... 1 141.71kb.
Рабочая программа учебной дисциплины «Математика» Направление подготовки... 6 758.64kb.
Программа дисциплины «Администрирование операционных систем» 1 236.02kb.
№103 лоуренсий изобретатель циклотрона Э 1 14.45kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Томский государственный университет
УТВЕРЖДАЮ
Декан факультета информатики

Сущенко С.П.

" " декабря 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 г., протокол № ___.


izumzum.ru