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



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

Содержание рабочей программы преподавания дисциплины



Выписка из государственного образовательного стандарта высшего профессио-нального образования требований к минимуму содержания и уровню подготовки инженера (специалиста) направления 090100 «Информационная безопасность» по специальности 090102 «Компьютерная безопасность».

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


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


  1. Цель дисциплины. Целью преподавания математической логики и теории алгоритмов является:

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

  • привитие навыков современных видов математического мышления в области математической логики и теории алгоритмов;

  • использование методов математической логики и теории алгоритмов в практической деятельности.

Задачи изучения курса математической логики и теории алгоритмов состоят в следующем:

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

  • ознакомить слушателей с основами математической логики и теории алгоритмов их приложениями к задачам математической кибернетики;

  • привить навыки свободного обращения с основными понятиями и символами математической логики и теории алгоритмов и их корректного употреблении для выражения количественных и качественных отношений реального мира;

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


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

Студент должен знать:

  1. Понятие множества. Подмножество. Примеры множеств. Пустое и универсальное множества.

  2. Операции над множествами. Дополнение, объединение, пересечение, разность и прямое произведение множеств.

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

  4. Определение отношений на множествах и способы их задания. Виды отношений.

  5. Бинарные отношения и их свойства.

  6. Отношения эквивалентности, порядка и толерантности.

  7. Мощность множества.

  8. Соответствия и их свойства.

  9. Понятие отображения.

  10. Определение алгебраической операции. Свойства и способы задания бинарных отношений.

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

  12. Понятие математической логики, ее сущность и особенность.

  13. Понятие высказывания. Простое и сложное высказывания. Структура сложного высказывания.

  14. Операции над высказываниями. Определения отрицания, конъюнкции, дизъюнкции, импликации и эквивалентности.

  15. Понятие формулы логики высказываний. Расширение понятия формулы за счет введения логических операций: штриха Шеффера, стрелки Пирса и кольцевой суммы.

  16. Равносильность формул. Основные равносильности.

  17. Тождественно-истинные, тождественно-ложные, выполнимые и опровержимые формулы.

  18. Абстрактное определение булевой алгебры. Примеры булевых алгебр.

  19. Булевы и переключательные функции. Задание булевых функций с помощью таблиц истинности. Число всех возможных булевых функций от n переменных.

  20. Логические функции одной и двух переменных. Задания булевых функций трех и более переменных.

  21. Разложение булевых функций. Дизъюнктивные (ДНФ) и конъюнктивные (КНФ) нормальные формы булевых функций.

  22. Совершенные ДНФ и КНФ. Первая и вторая теоремы Шеннона (без доказательства).

  23. Приведение произвольной булевой функции к ДНФ или КНФ.

  24. Приведение ДНФ к СДНФ.

  25. Приведение КНФ к СКНФ.

  26. Проблема минимизации булевых функций.

  27. Метод Квайна для минимизации булевых функций.

  28. Минимизация булевых функций с помощью карт Карно.

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

  30. Полином Жегалкина. Представление произвольной булевой функции в форме полинома Жегалкина.

  31. Операция замыкания подмножества булевых функций. Свойства замыкания. Определение и примеры функционально замкнутых классов булевых функций.

  32. Теорема Поста о функциональной полноте систем булевых функций (без доказательства). Классы Поста.

  33. Понятие предиката. Предметы, предметные переменные и поле предиката. Примеры предикатов.

  34. Операции квантирования. Кванторы существования и общности.

  35. Формулы логики предикатов. Понятия связанных и свободных переменных, а также определенных и неопределенных предикатов.

  36. Равносильность формул логики предикатов. Примеры. Тождественно-истинные предикаты.

  37. Определение формальной теории. Алфавит, формула, аксиома, правило вывода, язык и сигнатура формальной теории. Интерпретации формальных теорий.

  38. Исчисление высказываний. Алфавит, формулы, аксиомы и правило вывода в исчислении высказываний.

  39. Исчисление предикатов. Алфавит, формулы, аксиомы и правило вывода в исчислении предикатов. Чистое и прикладное исчисления предикатов. Формальные теории первого и второго порядков.

  40. Постановка задачи автоматического доказательства теорем. Понятия алгоритма автоматического доказательства теорем и метода резолюций.

  41. Сведение формул к предложениям при автоматическом доказательстве теорем.

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

  43. Правило резолюции для исчисления предикатов.

  44. Опровержение методом резолюций.

  45. Функции и формулы k – значной логики.

  46. Полнота и замкнутость систем функций k – значной логики.

  47. Особенности k – значной логики.

  48. Интуитивное понятие алгоритма и его характерные свойства.

  49. Проблема уточнения понятия алгоритма. Частичные и всюду определенные вычислимые функции.

  50. Простейшие (базисные), частично-, обще- и примитивно-рекурсивные функции.

  51. Формальное определение машин Тьюринга и их примеры

  52. Сложность алгоритмов. Основные понятия, классификация задач по степени сложности.


Студент должен уметь:

  1. Определить результаты теоретико-множественных операций на заданных множествах.

  2. Установить свойства конкретных бинарных отношений.

  3. Проверить аксиомы алгебраических систем.

  4. Записывать сложные высказывания посредством логических формул.

  5. Составлять таблицы истинности булевых выражений.

  6. Находить существенные переменные логических функций.

  7. Вычислять значения логических функций, заданных формулами.

  8. Представить произвольную формулу в форме СДНФ и СКНФ.

  9. Проверить эквивалентность булевых формул.

  10. Находить сокращенные, тупиковые и минимальные формы булевых функций.

  11. Строить полином Жегалкина.

  12. Определить классы Поста.

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

  14. Пользоваться картами Карно.




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

3.1. Разделы дисциплины и виды занятий (тематический план)



п/п

Разделы дисциплины

Лекции

(часы)

Прак.заня- тия (часы)


1.


2.
3

4.
.

Пятый семестр (36 ч)

Введение и краткие сведения о множествах, отношениях и алгебраических системах.

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

Булева алгебра.

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


Шестой семестр (17 ч)

Обобщения булевой алгебры.

Логика предикатов. Формальные системы (теории). Автоматическое доказательство теорем. k-значная логика.


Основы теории алгоритмов.

Основные положения теории алгоритмов и рекурсивных функций. Машина Тьюринга. Сложность алгоритмов.


8


10
8

9




8


10
-

-


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