Дискретная математика и математическая логика

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Брянский государственный технический университет


Кафедра «ВЫСШАЯ МАТЕМАТИКА»



«УТВЕРЖДАЮ»
Первый проректор по учебной работе В. И. Попков
« » 2005 г.








ДИСКРЕТНАЯ МАТЕМАТИКА

Рабочая программа ОПД №
дисциплины ОПД.04 для студентов, обучающихся по программе подготовки
специалистов со средним профессиональным образованием по специальности 2203 «Программное обеспечение вычислительной техники и
автоматизированных систем»



Вид учебной нагрузки
Объём в часах
Семестр

Всего
108
1

Аудиторная
85


Лекции
51


Практические занятия
34


Самостоятельная работа
23


Экзамен
+





Брянск 2005







Рабочая программа составлена на основании государственного образовательного стандарта среднего профессионального образования и учебного плана подготовки специалистов по специальности 2203 «Программное обеспечение вычислительной техники и автоматизированных систем», утверждённого учёным советом БГТУ в 2003 году.









Программу разработали ст. преподаватель Кобзев В. М.,
ассистент. Вискина Г. Г










Рабочая программа обсуждена на заседании кафедры
«Высшая математика» 21.10.05 (протокол № 3)





Зав. кафедрой А. П. Мысютин

Декан ФЭИ К. В. Дергачёв
ВВЕДЕНИЕ
Развитие экономики любого процветающего государства основано на применении новейших технологий, обязательным компонентом которых являются компьютерно-информационные средства. Эти средства позволяют осваивать недра Земли и просторы Космоса, управлять производством материальных благ и осуществлять оптимальное управление страной, используя при этом ситуационные центры стратегического моделирования, и т. п. Разработка указанных средств требует прежде всего «мудрого» абстрактного мышления, формированием которого и занимается дискретная математика.
В настоящее время интерес к дискретной математике неуклонно растёт. Всё больше в обязательную программу учебных заведений включаются курсы теории множеств, математической логики, комбинаторики, теории графов и их фрагменты. Специалисты в области современных компьютерных технологий уже осознали, что эти разделы математики являются фундаментом для построения настоятельно необходимой сейчас хорошей теории математического обеспечения информационных технических систем. Многие специалисты, казалось бы, далёкие от математики, также начинают сознательно знакомиться с их содержанием.

ЦЕЛИ ИЗУЧЕНИЯ ДИСЦИПЛИНЫ
Познакомить студентов с кругом понятий дискретной математики; сформировать терминологический запас, необходимый для самостоятельного изучения специальной математической и теоретико-программистской литературы.
Сообщить студентам необходимые конкретные сведения из дискретной математики, предусматриваемые образовательными стандартами среднего профессионального образования и учебного плана подготовки специалистов по специальности 2203 «Программное обеспечение вычислительной техники и автоматизированных систем»; помочь студентам овладеть методами дискретной математики, наиболее употребительными при решении практических задач.

ТРЕБОВАНИЯ К УРОВНЮ УСВОЕНИЯ
В результате изучения данной дисциплины студент должен
знать:
основные понятия дискретной математики;
основные методы решения задач по соответствующим разделам дискретной математики;
уметь:
формулировать математические модели задач, решаемых методами дискретной математики;
решать задачи по соответствующим разделам дискретной математики;
применять технические средства для решения этих задач;
иметь представление:
о роли и месте дискретной математики в программировании.
ТРЕБОВАНИЯ ГОСУДАРСТВЕННОГО ОБРАЗОВАТЕЛЬНОГО СТАНДАРТА
Логические операции, формулы логики, законы алгебры логики; понятие функции алгебры логики, представление функций в совершенных нормальных формах, многочлен Жегалкина; основные классы функций, полнота множества функций, теорема Поста; основные понятия теории множеств, теоретико-множественные операции и их связь с логическими операциями; логика предикатов, бинарные отношения и их виды; элементы теории отображений и алгебры подстановок; основы алгебры вычетов и их приложение к простейшим криптографическим шифрам; метод математической индукции; алгоритмическое перечисление основных комбинаторных объектов; основные понятия теории графов, характеристики графов, эйлеровы и гамильтоновы графы, плоские графы, деревья, ориентированные графы, бинарные деревья; элементы теории автоматов.

СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

Содержание лекционного курса
Объём в часах
Темы практических занятий

1
Введение.
1


2
Основные понятия теории множеств, операции над мно
·жествами, диаграммы Эйлера-Венна, доказательство тождеств методом включений; элементы теории отображений; алгебра подстановок; алгоритмическое перечисление основных комбинаторных объектов; мощность множества; бинарные отношения и их виды свойства отношений (рефлексивность, симметричность, транзитивность, антирефлексивность, антисимметричность, асимметричность), отношения строгого и нестрогого порядка, отношение эквивалентности, вполне упорядоченные, частично упорядоченные множества), цепь.
8
ПЗ №1. Множества и отображения.


ПЗ № 2. Мощность множества.


ПЗ № 3. Отношения на множестве.

3
Основные понятия теории графов; характеристики графов (связный граф, компонента связности, мультиграф, взвешенный, (нагруженный) граф), задачи о нахождении пути в графе); эйлеровы и гамильтоновы графы (эйлерова цепь, эйлеров цикл задача Эйлера, гамильтоновы графы); плоские графы (плоские, планарные графы, формула Эйлера, непланарные графы № 1 и № 2, типа № 1 и типа № 2, матрица смежности, код Харари) деревья (дерево, ордерево, бинарное ордерево, уровень вершины ордерева, глубина ордерева, висячая вершина ордерева и дерева, код Прюфера); ориентированные графы (матрица инциндентности,); бинарные деревья (префиксный код бинарного дерева, способы обхода бинарного ордерева, дерево поиска, атом, список);
14
ПЗ № 4. Основные понятия теории графов. Поиск путей в графе.


ПЗ № 5. Задача Эйлера. Формула Эйлера.

ПЗ № 6. Неплоские графы. Представление графов матрицами.


ПЗ № 7. Представление графов кодами. Деревья. Деревья и списки.


ПЗ № 8. Контрольная работа № 1


4
Логические операции, формулы логики, законы алгебры логики; понятие функции алгебры логики, представление функций в совершенных нормальных формах, многочлен Жегалкина; основные классы функций, полнота множества функций, теорема Поста, связь с логическими операциями теоретико-множественных операций, логика предикатов
16
ПЗ № 9. Высказывания и математические операции. Булевы функции.

ПЗ № 10. Нормальные формы БФ. Двойственность БФ.

ПЗ № 11. Арифметический подход к БФ. Монотонные БФ. Функционально замкнутые классы.

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


ПЗ № 13. Контрольная работа № 2

ПЗ № 14. Исчисление предикатов

5
Метод математической индукции
2
ПЗ № 15. Метод математической индукции.

6
Основы алгебры вычетов и их приложение к простейшим криптографическим шифрам;
4
ПЗ № 16. Приложения алгебры вычетов к простейшим криптографическим шифрам.

7
Элементы теории автоматов.
4
ПЗ № 17. Элементы теории автоматов.

8
Обзорная лекция
2



САМОСТОЯТЕЛЬНАЯ РАБОТА

Вид работы
Объём
Трудоёмкость

1
Самостоятельное выполнение задач и упражнений
3-5 задач по каждому практическому занятию
17 часов

2
Выполнение РГР
5 задач
6 часов

итого


23 часа


СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

Основная литература
Кузнецов, О.П. Дискретная математика для инженера./ О. П. Кузнецов. - Изд. 3-е, перераб. и доп. - СПб. Лань, 2004. - 394 с.
Спирина, М.С. Дискретная математика: учебник./ М. С. Спирина, П. А. Спирин. - М.: ACADEMIA, 2004. - 367 с.
Пугач, Л.И. Высшая математика. Задачи по дискретной математике, математической логике и теории алгоритмов : метод. указания к практическим занятиям для студентов 1 курса спецальностей 220400 "Программное обеспечение", "22300 " Системы автоматизированного проектирования" и 075300 "Организация и технология защиты информации"./ Л. И. Пугач ; БГТУ. - Брянск: Изд-во БГТУ, 2005. - 16 с.
Асеев, Г.Г. Дискретная математика : учеб. пособие./ Г. Г. Асеев, О. М. Абрамов, Д. Э. Ситников. - Ростов н/Д; Харьков: Феникс: Торсинг, 2003. - 141 с.

Дополнительная литература
Яблонский, С.В. Введение в дискретную математику: Учеб. пособие для вузов./ С. В. Яблонский. - 3-е изд., стер. - М.: Высш. шк., 2001. - 384с.
Белоусов, А.И. Дискретная математика: Учеб. Вып. 19./ А. И. Белоусов, С. Б. Ткачев; под ред. В. С. Зарубина, А. П. Крищенко. - М.: МГТУ им Н. Э. Баумана, 2001. - 743с.
Горбатов, В.А. Основы дискретной математики: Учеб. пособие для вузов./ В. А. Горбатов. - М.: Высш. шк., 1986. - 310 с. - (Учебное пособие для вузов).
Горбатов, В.А Дискретная математика: Учебник для студентов втузов./ В. А. Горбатов, А. В. Горбатов, М. В. Горбатова - М.: ООО «Издательство АСТ», ООО «Издательство Астрель», 2003. - 447 с.
Фалевич, Б.Я. Теория алгоритмов: учеб. пособие./ Б. Я. Фалевич. - М.: Машиностроение, 2004. - 160 с.
Введение в криптографию: Новые мат. дисциплины./ В. В. Ященко [и др.]; Под ред. В. В. Ященко. - СПб. и др.: МЦНМО: Питер, 2001. - 287с.
13PAGE 15





13 PAGE 14615



13 EMBED Word.Picture.8 1415



Root Entry

Приложенные файлы

  • doc 8882080
    Размер файла: 95 kB Загрузок: 0

Добавить комментарий