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



Скачать 250,02 Kb.
Дата22.05.2015
Размер250,02 Kb.
ТипРабочая программа

Министерство образования и науки Российской Федерации

Государственное образовательное учреждение

высшего профессионального образования

«Комсомольский-на-Амуре государственный технический университет»

Кафедра информационной безопасности автоматизированных систем

УТВЕРЖДАЮ

Первый проректор ГОУВПО «КнАГТУ»

______________________ А.Р. Куделько

"_____"___________________ 2010 года


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

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

основной образовательной программы подготовки дипломированных
специалистов по специальности 090105 «Комплексное обеспечение информационной безопасности автоматизированных систем»

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

Технология обучения традиционная

Объем дисциплины 100 часов, 3 зачетные единицы


Комсомольск-на-Амуре 2010

Рабочая программа обсуждена и одобрена на заседании кафедры "Информационная безопасность автоматизированных систем"
И.о. заведующего кафедрой _________________ И.А. Трещев

(подпись)


"_____" ______________ 2010 года

СОГЛАСОВАНО:

Начальник учебно-методического управления _______________ А.А. Скрипилев

(подпись)

"_____" ______________ 2010 года
Декан ФКТ _________________ В.П. Котляров

(подпись)

"_____" ______________ 2010 года
Рабочая программа рассмотрена, одобрена и рекомендована к использованию методической комиссией факультета компьютерных технологий.

Председатель методической комиссии _________________ В.П. Котляров

(подпись)

"_____" ______________ 2010 года

Автор рабочей программы

__________________ И.А. Трещев

(подпись)

"_____" ______________ 2010 года



СОДЕРЖАНИЕ
Введение 4

1. Пояснительная записка 4

1.1. Требования государственного образовательного стандарта высшего

профессионального образования к структуре и содержанию курса

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

1.2. Предмет, цели, задачи и принципы построения курса 5

1.3. Роль и место курса в структуре реализуемой образовательной программы 5

1.4. Объемы учебной работы и предусмотренные рабочими учебными планами

реализуемой образовательной программы формы аттестации ее результатов 5

2. Структура и содержание курса 6

3. Календарный график изучения курса 7

3.1. Лекции 7

3.2. Практические занятия (упражнения).............................///............................................8

3.3. Объем, структура и содержание самостоятельной работы студентов, график

ее выполнения 9

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

деятельности обучаемых 12

5. Ресурсное обеспечение курса 14

5.1. Список основной учебной и учебно-методической литературы 14

5.2. Список дополнительной учебной и учебно-методической литературы 14

5.3. Перечень программных продуктов, используемых при изучении курса 14


Введение

Дисциплина «Математическая логика и теория алгоритмов» изучается на третьем курсе (пятый семестр) в рамках цикла математических и общих естественно-научных дисциплин (федеральная компонента) учебного плана подготовки по специальности 090105 «Комплексное обеспечение информационной безопасности автоматизированных систем». Основная цель рабочей программы – отражение основной структуры и введение в общее содержание курса.

В рамках этой дисциплины студенты изучают различные исчисления математической логики и подходы к определению вычислимости. Помимо этого они усваивают теоретико-множественный подход в математике.

  1. Пояснительная записка

    1. Требования государственного образовательного стандарта высшего профессионального образования к структуре и содержанию курса


Рабочая программа разработана на основании требований государственного образовательного стандарта высшего профессионального образования специальности 090105 «Комплексное обеспечение информационной безопасности автоматизированных систем», утвержденного 05.04.2000 г., рег.№ 284 инф/сп. Данный стандарт содержит следующие требования по содержанию курса ЕН.Ф.01.04 «Математическая логика и теория алгоритмов»:


ЕН.Ф.01.04
Математическая логика и теория алгоритмов

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

100



    1. Предмет, цели, задачи и принципы построения курса


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

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

Специалист по защите информации по специальности 090105 «Комплексное обеспечение информационной безопасности автоматизированных систем»


  • должен знать

  • логику высказываний;

  • логику предикатов;

  • метод резолюций;

  • способы представления булевых функций формулами;

  • формализацию понятия алгоритма, псевдобулевые функции;

  • рекурсивные функции и машины Тьюринга;

  • основы модальной и нечеткой логики.

  • должен уметь

  • строить СДНФ, СКНФ, полиномы Жегалкина;

  • определять является ли система булевых функций полной;

  • строить простейшие вычислительные алгоритмы;

  • строить реляционные отношения;

  • должен владеть

  • методом карт Карно;

  • построением диаграмм Вейча;

  • методом резолюций;

Принципы построения курса

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

Второй принцип – доступность изучаемого материала. Изучение предмета начинается с темы «Булевы функции». Затем студенты переходят к выполнению более трудных заданий по логике предикатов, формальным теориям, псевдобулевым функциям.

Третий принцип – тесная взаимосвязь лекционных занятий и тем практических занятий и расчетно-графических заданий. Последовательность изучения и объем теоретического материала, излагаемый на лекциях, согласованы с темами практических занятий, РГЗ и графиком их выполнения.

    1. Роль и место курса в структуре реализуемой образовательной программы


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

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



    1. Объемы учебной работы и предусмотренные рабочими учебными планами реализуемой образовательной программы формы аттестации ее результатов


Характеристика трудоемкости курса представлена в таблице 1.
Таблица 1

Характеристика трудоемкости курса (дисциплины)





  1. Структура и содержание курса


Структуру курса можно представить в виде следующих модулей (табл. 2).
Таблица 2

Наименование

Описание раздела

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

Высказывания, пропозициональные формулы, интерпретация. Логическое следование и логическая эквивалентность. Подстановки. Функции к-значной логики.


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

Определение формальной теории. Выводимость. Интерпретация формальной теории. Общезначимость и непротиворечивость. Полнота, независимость и разрешимость.


Исчисление высказываний

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


Исчисление предикатов

Алфавит, формулы и аксиомы исчисления предикатов. Интерпретация. Непротиворечивость исчисления предикатов. Логическое следование и логическая эквивалентность. Формальная арифметика. Формальная теория множеств. Теория групп и другие теории первого порядка.


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

Понятие алгоритма. Примитивно рекурсивные функции. Оператор минимизации. Частично рекурсивные функции. Тезис Черча. Машина Тьюринга. Алгоритмическая неразрешимость проблемы остановки. Сложность алгоритмов. Вычислительные алгоритмы.

Реляционная алгебра и реляционное исчисление

Реляционные модели данных. Алгебра Кодда. Исчисление кортежей. Исчисление доменов. Замкнутость реляционной алгебры


  1. Календарный график изучения курса


3.1. Лекции

В таблице 3 представлена программа лекционного курса «Математическая логика и теория алгоритмов».



Таблица 3
Программа лекций



Номер темы

Наименование темы

Содержание темы

Объем в часах

1

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

Высказывания, пропозициональные формулы, интерпретация. Логическое следование и логическая эквивалентность. Подстановки.


1

2

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

Определение формальной теории. Выводимость. Интерпретация формальной теории. Общезначимость и непротиворечивость. Полнота, независимость и разрешимость.


1

3

Исчисление высказываний

Классическое и конструктивное определения исчисления высказываний. Унификатор и алгоритм унификации. Правила вывода. Теорема дедукции. Множество теорем и формальная непротиворечивость исчисления высказываний. Аксиоматизации Гильберта-Аккермана, Россера, Клини.


3

4

Исчисление предикатов

Алфавит, формулы и аксиомы исчисления предикатов. Интерпретация. Общезначимость. Полнота чистого исчисления предикатов. Логическое следование и логическая эквивалентность. Теория равенства. Формальная арифметика. Теория групп. Теоремы Геделя о неполноте.


4

5

Метод резолюции для автоматического доказаткльства теорем

Постановка задачи. Доказательство от противного. Сведение к предложениям. Правило резолюции для исчисления высказываний. Правило резолюции для исчисления предикатов. Опровержение методом резолюции. Алгоритм метода резолюций.


2

6

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

Понятие алгоритма. Нормальный алгоритм Маркова. Примитивно рекурсивные функции. Оператор минимизации. Частично рекурсивные функции. Тезис Черча. Алгоритмически неразрешимые проблемы.

2

7

Прикладные логические системы

Нечеткие множества и величины. Расплывчатые и неопределенные высказывания. Вывод с нечеткими посылками. Доказуемость и модальная логика. Темпоральная логика первого порядка.

2

8

Реляционная алгебра и реляционное исчисление

Реляционные модели данных. Алгебра Кодда. Исчисление кортежей. Исчисление доменов. Замкнутость реляционной алгебры.

2

Итого

17



3.2. Практические занятия (упражнения)
В таблице 4 представлена программа практических занятий по курсу «Математическая логика и теория алгоритмов».

Таблица 4


Программа практических занятий


Номер темы

Наименование темы

Содержание темы

Объем в часах

1

Алгебра высказываний

Формулы. Выполнимость. Тавтологии. Построение СНДФ. Стрелка Пирса и штрих Шеффера.

2

2

Исчисление высказываний

Выводы секвенций. Вывод формул в исчислении высказываний. Полином Жегалкина.

4

3

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

Термы и формулы. Модели.

4

4

Выполнимость формул логики предикатов

Выполнимость формул. Пренексная нормальная форма.

4

5

Рекурсивные функции

Примитивно рекурсивные функции. Часично рекурсивные функции.

4

6

Машины Тьюринга

Построение машин Тьюринга. Машины Тьюринга и рекурсивные функции.

4

7

Методы доказательства теорем

Унификация. Метод резолюции

4

8

Логические системы

Логические операции в нечеткой логике.

4

9

Реляционная алгебра

Алгебра Кодда, Алгебра А. Операция реляционного дополнения, объединения, разности, эквисоединения, коньюнкции, дизъюнкции.

4












Итого 34 часов.







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




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

Для самостоятельного изучения предлагаются следующие темы:





  1. Нечеткие множества и отношения.

  2. Нечеткая логика.

  3. Модальная логика. Семантика Крипке.

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

  5. Системы Гильберта.

  6. Темпоральная логика.

  7. Система Аксиом Цермело-Френкеля.



      1. Примерные требования к оформлению и сдаче отчетов по расчетно-графическим заданиям

По каждому РГЗ должен быть составлен отчет в виде документа MS Word или в письменном виде в тетради содержащий следующие разделы:



  • титульный лист;

  • задание;

  • теоретический материал, содержащий описание методики выполнения расчетно-графического задания;

  • решение задач;

  • список использованной литературы.



      1. Расчетно-графическое задание


Таблица 5



Тема

Объём само-

стоятельной

работы

1

Логические исчисления и вычислимость


18

Итого:

18


3.3.4. Примерная структура самостоятельной работы студентов
Примерная структура и график выполнения самостоятельной работы студентов представлены в таблице 6.

Таблица 6

График выполнения самостоятельной работы студентов

Виды самостоятельной работы

Число часов в неделю

Итого

по видам


работ

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17




Подготовка к лекциям

0,2

0,2

0,2

0,2

0,6

0,6

0,6

0,6

0,6

0,6

0,6

0,6

0,6

0,6

0,2

0,2

0,2

7,4

Подготовка к практическим занятиям (семинарам)

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

17

Изучение теоретических разделов курса

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,3

0,3

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

3,6

Подготовка к контрольным мероприятиям

























КР
1

1


1



















3

Выполнение и защита РГЗ

















РГЗ1

3

3

4

4

4





















18


Итого

1,4

1,4

1,4

1,4

1,8

4,8

4,8

5,9

6,9

6,8

2,8

1,8

1,8

1,8

1,4

1,4

1,4

49

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


Текущий контроль учебной деятельности студентов осуществляется на практических занятиях, при сдаче расчетно-графического задании, при проверке контрольной работы. Студент обязан в срок выполнить выданное ему расчетно-графическое задания (его тема приведены в таблице 5). Во время практических занятий студент выполняет одну контрольную работу (сроки см. в таблице 6). Пример билета на контрольную работу и билета на экзамен приводятся ниже.
Пример билета на контрольную работу
Решить следующие задачи по булевым функциям:
1. Для заданных булевых функций найти несущественные переменные и установить равны ли эти функции:

2. Построить таблицу истинности для булевой функции заданой с помощью формулы

3. Привести к совершенной дизъюнктивной нормальной форме заданную булеву функцию

4. С помощью карт Карно найти минимальную дизъюнктивную нормальную форму булевой функции заданной с помощью таблицы








00

01

11

10

00

1

1

0

0

01

0

0

0

1

11

0

0

0

1

10

1

1

0

0

Студент, не выполнивший к концу изучения дисциплины контрольную работу и расчетно-графическое задание, не допускается до экзамена. Экзамен проводится в письменной форме, время проведения экзамена – 2 академических часа. На экзамен каждому студенту предлагается три задания (1 билет). Пример экзаменационного билета приводится ниже.


Пример экзаменационного билета


  1. Частично упорядоченные множества.

  2. Равенство булевых функций.

  3. Построить машину Тьюринга для вычисления функции f(x)=x+2

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

A&B BA с помощью аксиом Клини?

1. A&B, A&B B, B, A (B A), BA

2. A&B, A&B A, A, A (B A), BA

3. A&B, A&B B, A, A (B A), BA

4. A&B, A&B A, A, A (B A), BA


2. Какой из выводов методом резолюций

AB, BC AC

верен?


  1. AB, BC, (AC), Res(AB, BC)= AC, Res((AC), AC)=0

  2. AB, BC, (AC), Res(AB, BC)= AC

  3. AB, BC, (AC), Res((AC), AB)=0

  4. AB, BC, (AC), Res(AB, BC)= AC, Res((AC), AB)=0

3.Задано множество операций F, состоящее из двух бинарных операций и . В какой последовательности выполняются следующие шаги для нахождения наибольшего общего унификатора термов ab) c и d(ab)?


1. (ab) c = d(ab) – в стек и потом – из стека

2. c = ab – в стек и потом – из стека

3. ab = d – из стека

4. = { c= ab , d= ab }

5. =

6. = {c= ab }



7. ab=d – в стек

4. Пусть P(x1, x2) – двухместный предикат на множестве A = {1,2,3}, определенные как P(x1, x2 ) = 1(истина) x1+x2 3. Какое из перечисленных ниже множеств состоит из элементов x2 , для которых предикат x1 P(x1, x2 ) принимает значения истина?

1. {1}

2. {2}


3. {1,2}

4. {2,3}
5. Пусть P(x1, x2) и Q(x1, x2 ) – двухместные предикаты на множестве A = {1,2,3}, определенные как

P(x1, x2 ) = 1(истина) x1+x2 4

Q(x1, x2) = 1(истина) x1< x2

Установить соответствие между полученными из них формулами и множествами пар, для которых эти формулы истинны
1. P(x1, x2) 1. {(1,2), (1,3),(2,2), (2,3), (3,1), (3,2), (3,3)}

2. Q(x1, x2 ) 2. {(1,3),(2,2),(2,3),(3,1), (3,2),(3,3)}

3. P(x1, x2) & Q(x1, x2 ) 3. {(1,3), (2,3)}

4. P(x1, x2) Q(x1, x2 ) 4. {(1,2),(1,3),(2,3)}


  1. Ресурсное обеспечение курса

    1. Список основной учебно-методической литературы





  1. Булос Дж., Джефри Р. Вычислимость и логика. – М.: Мир, 1994.

  2. Игошин В.И. Математическая логика и теория алгоритмов. – М.: Издательский центр «Академия», 2004.

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

  4. Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965.

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

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

  7. Хусаинов А.А., Михайлова Н.Н. Математическая логика и теория алгоритмов: Учеб. пособие. - Комсомольск-на-Амуре: ГОУВПО «КнАГТУ», 2005 - 95с.

  8. Шелупанов А.А., Зюзьков В.М. Математическая логика и теория алгоритмов. Учебное пособие. Гриф УМО.-Томск: STT, 2001.-176 с.


5.2. Список дополнительной учебно-методической литературы





  1. Прикладные нечеткие системы: под ред. Т. Тэрано, К. Асаи, М. Сугэно. – М.: Мир, 1993.

  2. Miller A. V. Introduction to mathematical logic. – Preprint 9601203,

1996

  1. Chomicki J., Toman D. Temporal Logic in Information Systems. –

BRICS Lecture Notes, LS-97-1, 1997.

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

дисциплины

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


  1. Операционная системы: Windows (XP/2000/2003).

  2. Текстовый редактор MS Word 2000.

Похожие:

Рабочая программа дисциплины «Математическая логика и теория алгоритмов» iconРабочая программа дисциплины «Математическая логика и теория алгоритмов»
...
Рабочая программа дисциплины «Математическая логика и теория алгоритмов» iconПрограмма-минимум кандидатского экзамена по специальности 01. 01. 06 «Математическая логика, алгебра и теория чисел» по физико-математическим наукам
В основу настоящей программы положены следующие дисциплины: математическая логика; алгебра; теория чисел
Рабочая программа дисциплины «Математическая логика и теория алгоритмов» iconРабочая программа для студентов очной формы обучения направление 010100. 62 «математика», профили подготовки: «Алгебра, теория чисел, математическая логика»
Математика, профили подготовки: «Алгебра, теория чисел, математическая логика»; «Вещественный, комплексный и функциональный анализ»;...
Рабочая программа дисциплины «Математическая логика и теория алгоритмов» iconМатематическая логика и теория алгоритмов
Большое внимание уделено практическим аспектам обсуждаемых понятий: автоматизации логического вывода, проверки корректности программ,...
Рабочая программа дисциплины «Математическая логика и теория алгоритмов» iconНазвание курса
Основной курс "Математическая логика и теория алгоритмов" предназначен для студентов первого курса отделения прикладной инфоматики...
Рабочая программа дисциплины «Математическая логика и теория алгоритмов» iconПрограмма-минимум вступительного экзамена в аспирантуру по специальности
В основу настоящей программы положены следующие дисциплины: математическая логика; алгебра; теория чисел
Рабочая программа дисциплины «Математическая логика и теория алгоритмов» iconПрограмма дисциплины теория вероятностей и математическая статистика Цикл ен. Ф. Специальность
Рабочая программа дисциплины "Теория вероятностей и математическая статистика" предназначена для студентов 1 курса
Рабочая программа дисциплины «Математическая логика и теория алгоритмов» iconПрограмма дисциплины теория вероятностей и математическая статистика Цикл ен. Ф
Рабочая программа дисциплины "Теория вероятностей и математическая статистика" предназначена для студентов 3 курса
Рабочая программа дисциплины «Математическая логика и теория алгоритмов» iconПрограмма вступительного экзамена направления подготовки аспирантов 01. 06. 01 Математика и механика
Вступительный экзамен проводится в устной форме, оценки выставляются по пятибальной шкале. В основу настоящей программы положены...
Рабочая программа дисциплины «Математическая логика и теория алгоритмов» iconРабочая программа дисциплины Математическая логика Направление подготовки 050100 Педагогическое образование
Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины 7
Разместите кнопку на своём сайте:
docs.likenul.com


База данных защищена авторским правом ©docs.likenul.com 2015
обратиться к администрации
docs.likenul.com