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



Скачать 85.75 Kb.
Дата08.10.2012
Размер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 г., протокол № ___.

Похожие:

Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика iconРабочая программа для студентов очной формы обучения направление подготовки 230700. 62 «прикладная информатика»
Платонов м. Л. Алгебра и математическая логика. Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения...
Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика iconРабочая программа дисциплины Информатика Направление подготовки 230700 Прикладная информатика Квалификация выпускника
Целями освоения дисциплины «Информатика» развитие профессионального кругозора будущих специалистов, формирование профессионального...
Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика iconРабочая программа дисциплины математическая логика и теория алгоритмов
Для подготовки бакалавров по направлению 552800 – “Информатика и вычислительная техника” и дипломированных специалистов по направлению...
Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика iconРабочая программа дисциплины интеллектуальные системы направление подготовки 230700 Прикладная информатика
Цели освоения дисциплины – ознакомление студентов с основными математическими моделями представления знаний в системах искусственного...
Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика iconРабочая программа дисциплины Идентификация Направление подготовки 010400 Прикладная математика и информатика
Для изучения курса необходимы знания по предметам: математический анализ, линейная алгебра, теория вероятностей, математическая статистика,...
Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика iconУчебная программа Дисциплины р2 «Математическая логика и теория алгоритмов»
Фгос впо, содействует формированию мировоззрения и системного мышления. Целью преподавания дисциплины «Математическая логика и теория...
Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика iconРабочая программа дисциплины математическая логика и теория алгоритмов (наименование дисциплины)
«Информатика и вычислительная техника», а также задачами, стоящими перед Новосибирским государственным университетом по реализации...
Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика iconРабочая программа учебной дисциплины «теория систем и системный анализ» Направление 080800 Прикладная информатика
Рабочая программа предназначена для преподавания дисциплины блока ен студентам очной формы обучения специальности 080801 прикладная...
Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика iconРабочая программа дисциплины дискретная математика направление подготовки 230700 Прикладная информатика Квалификация выпускника
Целями освоения дисциплины «Дискретная математика» являются получение теоретических знаний по основам дискретной математики
Рабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика iconРабочая учебная программа по дисциплине «Математическая логика и теория алгоритмов» для направления 010400 Прикладная математика и информатика по циклу Б. 2 математический и естественнонаучный цикл вариативная часть
Тем самым развитие теории алгоритмов в 30-е годы XX столетия, явилось стимулом для появления в 40-х годах первых компьютеров
Разместите кнопку на своём сайте:
ru.convdocs.org


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