[ ЧАСТНОЕ УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ
«МИНСКИЙ ИНСТИТУТ УПРАВЛЕНИЯ »
УТВЕРЖДАЮ
Ректор
Минского института управления
Н.В.Суша
«» 2009 г.
Регистрационный № УД-/р.
ДИСКРЕТНАЯ МАТЕМАТИКА И МАТЕМАТИЧЕСКАЯ ЛОГИКА
Учебная программа для специальности 1–31 03 04 «Информатика»Факультет учетно-финансовый Кафедра информационных технологий и высшей математики Курсы 3(4) Семестры 5(6,7) Лекции Экзамен 18 Практические Зачет (семинарские) занятия Лабораторные Курсовой проект занятия (работа) 4 нет Всего аудиторных часов по дисциплине Всего часов Форма получения по дисциплине высшего образования заочное Составил: А.Н. Лаврёнов, кандидат физ.-мат.наук, доцент 2009 г.
Учебная программа составлена на основе типовой учебной программа по дисциплине «Дискретная математика и математическая логика» для высших учебных заведений по специальностям: 1-31 03 03 Прикладная математика (по направлениям); 1-31 03 04 Информатика; 1-31 03 05 Актуарная математика; 1- 03 06-01 Экономическая кибернетика (математические методы в экономике); 1- 01 01-01 Компьютерная безопасность (математические методы и программные системы), утвержденной 24.09.2008 г., регистрационный № ТД-G.153/тип.
Рассмотрена и рекомендована к утверждению в качестве рабочего варианта на заседании кафедры информационных технологий и высшей математики «»_20 года, протокол № _ Заведующий кафедрой _ В.В. Гедранович Одобрена и рекомендована к утверждению Научно-методическим советом Минского института управления «»_20 года, протокол № _ Председатель _ С.Н. Спирков
I. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
.Основной спецификой дискретной математики и математической логики (ДМ и МЛ) является алгоритмическая основа и демонстрация использования дискретности в современной науке. ДМ и МЛ включает ряд разделов, которые наиболее интенсивно стали развиваться в середине прошлого столетия в связи с появлением ЭВМ. Этот курс является не только фундаментом математической кибернетики, но и важным звеном математического образования для специалистов в области прикладной математики и информатики.
Учебная программа по дисциплине «Дискретная математика и математическая логика» разработана для студентов специальности 1-31 Информатика.
Программа предусматривает требования к содержанию лекционного материала, перечню тем практических и лабораторных занятий по данной дисциплине.
Дисциплина «Дискретная математика и математическая логика» является одной из дисциплин подготовки специалистов с высшим образованием студентов в области информационных технологий и является базовой для соответствующих дисциплин, изучаемых студентами на последующих курсах.
Целью изучения дисциплины является подготовка специалиста, владеющего теоретическими и алгоритмическими основами базовых разделов современной дискретной математики, навыками описания дискретных объектов в прикладных задачах.
Задачами изучаемой дисциплины являются:
• приобретение студентами теоретических знаний по теории множеств, комбинаторике, алгебре логики, теории графов, теории кодирования и • овладение студентами практическими навыками решения прикладных задач по теории множеств, комбинаторике, алгебре логики, теории графов, теории кодирования и криптографии.
В результате изучения дисциплины обучаемый должен:
o теоретико-множественные концепции современной математики;
o логические исчисления и операции;
o основные методы теории множеств и комбинаторики;
o булевы функции и функции k-значной логики;
o основные понятия и базовые результаты теории графов;
o элементы теории формальных грамматик и языков;
o основы теории алгоритмов, понятие о классах сложности P и o элементы теории кодирования и криптографии;
формализации и решения прикладных задач;
o выполнять логические операции;
o строить графовые модели и определять их свойства;
o переводить предложения на формальный язык логики o решать базовые комбинаторные задачи;
o исследовать на полноту системы булевых функций;
o анализировать и строить конкретные грамматики;
o исследовать на изоморфизм простейшие графы, определять связность, двудольность и планарность графов;
o программировать на языке машин Тьюринга;
o определять принадлежность функций классам: примитивнорекурсивных, частично-рекурсивных, общерекурсивных;
o определять разделимость кода, строить оптимальный код.
• -иметь представление:
o о высказываниях и предикатах (основные операции над ними и o об элементах теории кодирования и криптографической защите В ходе освоения обучающимися содержания учебного курса рекомендуется использовать активные формы и методы обучения: проблемную лекцию, лекциювизуализацию, метод анализа конкретных ситуаций, методы коллективного обсуждения проблем, метод проектов и др. В качестве информационнометодической поддержки может (как правило, должен) выступать учебнометодический комплекс по дисциплине, включающий электронные презентации лекционных занятий, задания для лабораторных работ, примеры выполнения типовых заданий, материалы для контролируемой самостоятельной работы, тестовые задания.
Программа дисциплины рассчитана на объем 196 учебных часа, из них – аудиторных. Распределение аудиторных часов по видам занятий: лекций – часов, практических занятий – 6 часов, лабораторных работ – 4 часа.
Распределение аудиторных часов по семестрам: 5-ый семестр – всего часов, из них лекций – 6 часов, практических занятий – 2 часа; 6-ий семестр – часов, из них лекций – 6 часов, практических занятий – 2 часа, лабораторных работ – 2 часа.
II. СОДЕРЖАНИЕ УЧЕБНОГО МАТЕРИАЛА
Раздел 1. Комбинаторный анализ Множества, задание множеств. Подмножества и их свойства. Операции над множествами и основные равенства. Покрытия и разбиения множеств. Правило суммы. Принцип Дирихле. Декартово произведение множеств. Правило произведения. Бинарные отношения и их свойства. Отношение эквивалентности.Размещения с повторениями и без повторений. Сочетания без повторений и сочетания с повторениями. Бином Ньютона. Полиномиальная теорема.
Рекуррентные соотношения и методы их решения. Формула включений и исключений. Производящие функции.
Раздел 2. Высказывания и предикаты Высказывания, операции над высказываниями и их основные союзы.
Высказывательные формулы, тавтологии. Логическое следствие. Предикаты, операции над предикатами и их свойства. Предикатные формулы, их интерпретации и модели. Понятия об исчислении высказываний и об аксиоматическом описании общезначимых формул.
Раздел 3. Графы и сети Графы. Изоморфизм графов. Способы задания графов. Понятие о верхних и нижних оценках. Верхняя оценка числа неизоморфных графов без изолированных вершин. Двудольные графы. Критерий двудольности. Деревья. Код Прюфера дерева. Плоские и планарные графы. Формула Эйлера. Гомеоморфные графы.
Критерий планарности Понтрягина–Куратовского. Эйлеровы и гамильтоновы графы. Критерий эйлеровости. Раскраска графов, хроматическое число графа, проблема четырех красок. Корневые деревья. Верхняя оценка числа неизоморфных корневых деревьев. Сети, -сети.
Раздел 4. Булевы функции Понятие булевой функции. Элементарные функции. Формулы, основные равносильности. Описание работы сумматора. Принцип двойственности. СДНФ и СКНФ, ДНФ и КНФ. Полные системы булевых функций. Полином Жегалкина.
Методы построения полинома Жегалкина. Замкнутые классы. Критерий функциональной полноты. Теорема о минимальном базисе. Понятие о результатах Поста. Проблема минимизации ДНФ. Алгоритм построения всех тупиковых ДНФ.
Геометрическая интерпретация проблемы минимизации ДНФ. Понятие о функциях k-значной логики, их особенности.
Раздел 5. Формальные грамматики Основные понятия. Некоторые свойства грамматик. Иерархия языков.
Леммы о разрастании для КС- и А-языков. Грамматический разбор. КСграмматики и синтез языков программирования.
Раздел 6. Алгоритмические модели Интуитивное понятие алгоритма и необходимость его уточнения. Машины Тьюринга (одноленточные детерминированные), функции ими вычислимые.
Тезис Тьюринга. Проблема самоприменимости. Понятие о сложности алгоритма и о сложностях вычислений. к-ДМТ и к-HМТ. Проблема P = ?NP. Полиномиальная сводимость. NP-полные проблемы. Проблемы выполнимости и 3-выполнимости.
Простейшие арифметические функции. Операции суперпозиции, примитивной рекурсии, минимизации. Классы рекурсивных функций; соотношения между ними и классом функций, вычислимых по Тьюрингу.
Раздел 7. Элементы теории кодирования Схема передачи информации. Двоичное кодирование. Примеры кодовых систем. Критерий разделимости кода. Оптимальные коды, метод Хаффмена. Код Шеннона–Фано. Сжатие информации. Самокорректирующиеся коды (код Хэмминга) с исправлением одного замещения.
III. УЧЕБНО-МЕТОДИЧЕСКАЯ КАРТА
Номер раздела, темы, Дискретная математика и математическая логика (28ч.) Ньютона. Полиномиальная теорема.Рекуррентные соотношения и методы их исключений. Производящие функции.
Высказывания и предикаты (3 ч.) Высказывательные формулы, тавтологии.
Логическое следствие. Предикаты, операции над предикатами и их свойства.
Предикатные формулы, их интерпретации и модели. Понятия об исчислении высказываний и об аксиоматическом описании общезначимых формул.
верхних и нижних оценках. Верхняя оценка изолированных вершин. Двудольные графы. Критерий двудольности. Деревья.
Код Прюфера дерева. Плоские и планарные графы. Формула Эйлера. Гомеоморфные графы. Критерий планарности Понтрягина– Куратовского. Эйлеровы и гамильтоновы графы. Критерий эйлеровости. Раскраска графов, хроматическое число графа, проблема четырех красок. Корневые неизоморфных корневых деревьев. Сети, сети.
сумматора. Принцип двойственности.
СДНФ и СКНФ, ДНФ и КНФ. Полные системы булевых функций. Полином Жегалкина. Методы построения полинома Жегалкина. Замкнутые классы. Критерий функциональной полноты. Теорема о результатах Поста. Проблема минимизации интерпретация проблемы минимизации ДНФ. Понятие о функциях k-значной логики, их особенности Формальные грамматики (3 ч.) разрастании для КС- и А-языков.
Грамматический разбор. КС-грамматики и синтез языков программирования Алгоритмические модели (4ч.) вычислимые. Тезис Тьюринга. Проблема самоприменимости. Понятие о сложности алгоритма и о сложностях вычислений. кДМТ и к-HМТ. Проблема P = ?NP.
Полиномиальная сводимость. NP-полные проблемы. Проблемы выполнимости и 3выполнимости. Простейшие арифметические функции. Операции суперпозиции, примитивной рекурсии, функций; соотношения между ними и Элементы теории кодирования (3 ч.) Критерий разделимости кода. Оптимальные коды, метод Хаффмена. Код Шеннона– замещения.
Примечание: символ (*) указывает на выполнение работы за счет часов, отводимых на УСРС
IV. ИНФОРМАЦИОННО-МЕТОДИЧЕСКАЯ ЧАСТЬ
ЛИТЕРАТУРА
Основная 1. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: ФИЗМАТЛИТ, 2005. 416 с.2. Мощенский А.В., Мощенский В.А. Курс математической логики. – Мн.: БГУ, 1999. – 129 с.
3. Мощенский А.В., Мощенский В.А. Математические основы информатики. – Мн.: БГУ, 2002. – 149 с.
4. Нефедов В.Н., Осипова В.А. Курс дискретной математики. М.: Изд-во МАИ, 1992. – 264 с.
5. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. – М.:Наука, 1980. – 402 с.
Дополнительная 6. Андерсон Дж.А. Дискретная математика и комбинаторика. М.: Издательский дом “Вильямс”, 2004. – 960 с.
7. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990. – 384 с.
8. Журавлев Ю.И., Флеров Ю.А., Федько О.С. Дадашев Т.М. Сборник задач по дискретному анализу. Комбинаторика. Элементы алгебры логики. Теория графов. – М.: МФТИ, 2004. – 100 с.
9. Йордан Денев и др. Дискретная математика. – София: Наука, 1985. 312 с.
10. Марченков С.С. Булевы функции. – М.: ФИЗМАТЛИТ, 2002. – 72 с.
11. Романовский И.В. Дискретный анализ. – С.-Петербург, 1999. –158 с.
12. Харари Ф. Теория графов. – М.: Мир, 1973. – 300 с.
13. Холл М. Комбинаторика. – М.: Мир, 1970. – 424 с.
14. Хопкорфт Дж. и др. Введение в теорию автоматов, языков и вычислений. – М.:
Издательский дом “Вильямс”, 2002. – 528 с.
15. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1979. – ПЕРЕЧЕНЬ ТЕМ ЛАБОРАТОРНЫХ
ЗАНЯТИЙ
Лабораторное занятие №3. Алгоритмические модели Лабораторное занятие №4. Элементы теории кодирования
ПЕРЕЧЕНЬ КОМПЬЮТЕРНЫХ ПРОГРАММ
1. Операционная система (например, Windows).2. Среда Web-программирования, MS Internet Explorer, Opera, Netscape Navigator, Mozilla, Macromedia Dreamweaver.
«