Рабочая программа по курсу «Математическая логика и теория алгоритмов» для специальности 090102 «Компьютерная безопасность»



Скачать 274.6 Kb.
страница3/4
Дата19.01.2013
Размер274.6 Kb.
ТипРабочая программа
1   2   3   4




    1. Содержание разделов дисциплины


V семестр (34 ч)
Раздел 1. Введение и краткие сведения о множествах, отношениях и

алгебраических системах (8 ч)
Лекция 1. Введение.

Предмет дисциплины. Принципы построения и изучения дисциплины. Краткое содержание. Роль и место курса в формировании специалистов. Рекомендации по изучению курса, самостоятельной работе и литературе. О формах контроля и отчетности при изучении курса.

Лекция 2. Элементы теории множеств.

Множества, операции над множествами. Диаграммы Венна.

Лекция 3 Отношения на множествах.

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

Лекция 4 Общие сведения об алгебраических системах.

Соответствия и их свойства. Понятие отображения. Алгебраические операции. Понятие алгебраической системы. Морфизмы алгебраических систем.
Самостоятельное изучение Реляционная алгебра и реляционное исчисление. Алгебра отношений и ее использование для создания реляционных баз данных. Операции объединения, пересечения, разности и декартова произведения отношений. Понятия домена и идентификатора отношения. Специальные операции над отношениями: выбор, проекция и соединение. (2 ч).

Раздел 2. Булева алгебра (10 ч)


Лекция 5. Основы математической логики.

Сущность математической логики. Особенности математической логики. Алгебра логики (законы логики). Операции над высказыванием: конъюнкция, дизъюнкция, отрицание, импликация, эквивалентность. Логическая структура сложного высказывания. Общие понятия формул логики высказываний: алфавит, слово и формула. Равносильность формул. Тождественно-истинные формулы.

Лекция 6. Функции алгебры логики.

Абстрактное определение булевой алгебры. Модели булевых алгебр: двоичная, исчисления высказываний и теоретико-множественная. Определения булевой, двоичной и переключательной функций. Способы задания булевых функций. Унарные и бинарные логические операции. Понятие фиктивной (несущественной) логической переменной. Эквивалентность или равносильность формул, представляющих одну и ту же булеву функцию.

Лекция 7. Нормальные формы булевых функций.

Разложение булевых функций. Понятия литеры, конъюнкта, дизъюнкта, а также дизъюнктивной (ДНФ) и конъюнктивной (КНФ) нормальных форм. Алгоритм приведения формулы к ДНФ и КНФ. Совершенные ДНФ и КНФ. Понятия конституент единицы и нуля. Первое и второе разложения Шеннона.

Лекция 8. Минимизация булевых функций.

Проблема минимизации булевых функций.
Понятие импликанты булевой функции. Сокращенная, кратчайшая, тупиковая и минимальная ДНФ. Метод Квайна для нахождения сокращенной ДНФ. Минимизация с помощью карт Карно.

Лекция 9. Полнота и замкнутость булевых функций.

Определение (функционально) полной системы булевых функций. Теорема о полноте систем функций. Примеры функционально полных систем. Полиномы Жегалкина. Определение замыкания множества булевых функций и классы функционально замкнутых функций. Функционально замкнутые классы Поста булевых функций: сохраняющих нуль и единицу, самодвойственных, монотонных и линейных. Теорема Поста о полноте произвольной системы булевых функций. Базис системы булевых функций.
VII семестр (17 ч)

Раздел 3. Обобщения булевой алгебры (8 ч)
Лекция 10. Логика предикатов.

Понятие предиката. Предметы, предметные переменные и поле предиката. Операции над предикатами. Операции квантирования. Формулы логики предикатов. Связанные и свободные предметные переменные сложного предиката. Определенные и переменные предикаты. Равносильность формул логики предикатов. Тождественно-истинные формулы.

Лекция 11. Формальные системы (теории).

Определение формальной теории. Алфавит, формула, аксиома и правило вывода. Язык и сигнатура. Схемы аксиом. Посылки и заключения. Вывод формул. Гипотезы и теоремы. Интерпретация и модели теории. Тавтологии и противоречия. Аксиоматизируемые, независимые и разрешимые теории. Исчисление высказываний и предикатов. Категории и функторы. Терм и атом предиката. Чистое и прикладное исчисления предикатов. Формальные теории первого и второго порядков.

Лекция 12. Автоматическое доказательство теорем.

Понятие алгоритма автоматического доказательства теорем. Частичный алгоритм. Основы метода резолюций. Сведение формул к предложениям. Элиминация импликации. Протаскивание отрицаний. Разделение связанных переменных. Приведение к предваренной форме. Элиминация кванторов существования и всеобщности. Приведение к КНФ. Элиминация конъюнкции. Правило резолюции для исчисления высказываний. Резольвента и резольвируемые предложения. Правило резолюции для исчисления предикатов. Понятие унификатора. Наиболее общий унификатор. Опровержение методом резолюции.

Лекция 13. .k-значная логика.

Функции и формулы k-значной логики. Элементарные функции k-значной логики. Представление функций в виде аналога СДНФ. Полнота и замкнутость систем функций k-значной логики. Теорема Кузнецова и критерий Слупецкого о полноте системы функций. Особенности k-значной логики.
Раздел 3. Основы теории алгоритмов (9 ч)

Лекция 14. Основные положения теории алгоритмов и рекурсивных функций.

Интуитивное понятие алгоритма и его уточнение. Преобразование функций. Примитивно-рекурсивные, частично-рекурсивные и общерекурсивные функции.

Лекция 15. Машина Тьюринга.

Элементы машины и ее работа. Примеры машин Тьюринга. Композиция машин Тьюринга. Понятие итерации машин Тьюринга. Теорема Тьюринга.

Лекция 16 Сложность алгоритмов.

Основные понятия. Классификация задач по степени сложности.

Лекция 17 Недетерминированные алгоритмы. NP-трудные и NP-сложные задачи.
4. Лабораторный практикум (не предусмотрен)
5. Учебно-методическое обеспечение дисциплины

5.1. Рекомендуемая литература

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

  1. Глухов М.М. Математическая логика. - М., 1982

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

  1. Шелупанов А.А., Зюльков В.М. Математическая логика и теория алгоритмов. – Томск: STT, 2001. – 176 с.

  2. Судоплатов С.В., Овчинникова Е.В. Дискретная математика: Учебник. - М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002. – 280 с.

  3. Яблонский С.В. Введение в дискретную математику: Учеб. пособие для вузов / Под ред. В.А. Садовничего. – 3-е изд. стер. – М.: Высш. шк., 2002. – 384 с.

  4. Игошин В.И. Математическая логика и теория алгоритмов. – Саратов: Изд. Саратовск. ун-та, 1991. – 256с.

  5. Гаврилов В.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики: Учеб. пособие для вузов – 2-е изд., перераб. и доп. – М: Наука. Гл. ред. физ.-мат. лит., 1992. – 408с.

  1. Носов В.А. Основы теории алгоритмов и анализа их сложности. – М., 1992.

  2. Гиндикин С.Г. Алгебра логики в задачах. – М: Наука. Гл. ред. физ.-мат. лит., 1972. - 288с.

  3. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – 2-е изд.– М: Наука. Гл. ред. физ.-мат. лит., 1984. - 224с.

  4. Глухов М.М., Шапошников В.А. Задачи и упражнения по математической логике. М: 1984.

  5. Мальцев А.И. Алгоритмы и рекурсивные функции. – М: Наука. Гл. ред. физ.-мат. лит., 1965. - 392с.

  6. Колмогоров А.Н., Драгалин А.Г. Введение в математическую логику. – М: Изд. МГУ, 1982. – 120с.

  7. Клини С.К. Математическая логика. – М: Мир, 1978. – 480с.


в) методическая литература:

1. Собенина О.В. Методические указания к практическим занятиям по дисциплине «Математическая логика и теория алгоритмов», ВГТУ, 2002.

7. Методические рекомендации по организации изучения математической логики и теории алгоритмов

Четкая организация изучения дисциплины «Математическая логика и теория алгоритмов», основанная на правильном сочетании аудиторных учебных занятий, продуктивной самостоятельной работе студентов и систематическом контроле, играет основополагающую роль в глубоком математическом образовании современного студента. Исходя из этих принципов, рекомендуются следующие контрольные мероприятия, обеспечивающие систематическую работу студентов и ее контроль в течение всего срока обучения и, в совокупности, охватывающие весь материал этой дисциплины:

V семестр

  1. Контрольная работа «Элементы теории множеств и отношений» (6-ая неделя).

  2. Прием коллоквиума «Основные теоретические положения булевой алгебры» (10-ая неделя).

  1. Прием расчетно-графической работы «Расчет логических задач» (16-ая неделя).


VI семестр


  1. Контрольная работа «Логика предикатов» (2-ая неделя).

  2. Коллоквиум «Обобщения булевой алгебры» (10-ая неделя).

  3. Прием курсвой работы «Функциональные преобразователи» (16-ая неделя).

  4. Прием отчета по самостоятельной работе (17-ая неделя).


8. Рекомендуемый перечень тем практических занятий
VI семестр


2.

Операции над множествами и свойства бинарных отношений.

4.

Отображения и алгебраические системы

6.

Контрольная работа «Элементы теории множеств и отношений»

8.

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

10.

Основные теоретические положения булевой алгебры. Прием коллоквиума.

12.

Дизъюнктивные и конъюнктивные нормальные формы и их минимизация.

14.

Классы Поста.

16.

Прием типового расчета.




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




  1. Варианты типового расчета в приложении к учебнику Судоплатова С.В. и Овчинниковой Е.В. Элементы дискретной математики. М.: 2002.


Приложение 1. Календарный план чтения лекций
VI семестр


Номер лекции

Тема

1

2

Лекция 1.

Введение.

Предмет дисциплины. Принципы построения и изучения дисциплины. Краткое содержание. Роль и место курса в формировании специалистов. Рекомендации по изучению курса, самостоятельной работе и литературе. О формах контроля и отчетности при изучении курса.

Лекция 2.

Элементы теории множеств.

Множества, операции над множествами. Диаграммы Венна.

Лекция 3.

Отношения на множествах.

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

Лекция 4.

Общие сведения об алгебраических системах.

Соответствия и их свойства. Понятие отображения. Алгебраические операции. Понятие алгебраической системы. Морфизмы алгебраических систем.

Лекция 5.

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

Сущность математической логики. Особенности математической логики. Алгебра логики (законы логики). Операции над высказыванием: конъюнкция, дизъюнкция, отрицание, импликация, эквивалентность. Логическая структура сложного высказывания. Общие понятия формул логики высказываний: алфавит, слово и формула. Равносильность формул. Тождественно-истинные формулы.

Лекция 6.

Функции алгебры логики.

Абстрактное определение булевой алгебры. Модели булевых алгебр: двоичная, исчисления высказываний и теоретико-множественная. Определения булевой, двоичной и переключательной функций. Способы задания булевых функций. Унарные и бинарные логические операции. Понятие фиктивной (несущественной) логической переменной. Эквивалентность или равносильность формул, представляющих одну и ту же булеву функцию.

Лекция 7.

Нормальные формы булевых функций.

Разложение булевых функций. Понятия литеры, конъюнкта, дизъюнкта, а также дизъюнктивной (ДНФ) и конъюнктивной (КНФ) нормальных форм. Алгоритм приведения формулы к ДНФ и КНФ. Совершенные ДНФ и КНФ. Понятия конституент единицы и нуля. Первое и второе разложения Шеннона.

Лекция 8.

Минимизация булевых функций.

Проблема минимизации булевых функций. Понятие импликанты булевой функции. Сокращенная, кратчайшая, тупиковая и минимальная ДНФ. Метод Квайна для нахождения сокращенной ДНФ. Минимизация с помощью карт Карно.

Лекция 9.

Полнота и замкнутость булевых функций.

Определение (функционально) полной системы булевых функций. Теорема о полноте систем функций. Примеры функционально полных систем. Полиномы Жегалкина. Определение замыкания множества булевых функций и классы функционально замкнутых функций. Функционально замкнутые классы Поста булевых функций: сохраняющих нуль и единицу, самодвойственных, монотонных и линейных. Теорема Поста о полноте произвольной системы булевых функций. Базис системы булевых функций.
1   2   3   4

Похожие:

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

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


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