Geum.ru

Примерная программа наименование дисциплины «Дискретная математика» Рекомендуется для направлений подготовки

Вид материалаПримерная программа

Содержание


Место дисциплины в структуре ООП.
3. Требования к уровню освоения дисциплины.
4. Объём дисциплины и виды учебной работы
Аудиторные занятия
Другие виды аудиторных занятий (тактические занятия, учения, специальные игры, индивидуальные занятия)
Вид итогового контроля
5. Содержание дисциплины
6. Лабораторный практикум
8. Учебно-методическое обеспечение дисциплины
8.2. Средства обеспечения освоения дисциплины
10. Методические рекомендации по организации изучения дисциплины.
10.1. Рекомендуемый перечень тем практических занятий
10.2. Рекомендуемый перечень тем контрольных работ
Подобный материал:

Министерство образования и науки

Российской Федерации


Рекомендовано

Учебно-методическим

объединением

по образованию в области

информационной безопасности


ПРИМЕРНАЯ ПРОГРАММА

Наименование дисциплины

«Дискретная математика»


Рекомендуется для направлений подготовки


Специальность: 090106.65

«Информационная безопасность телекоммуникационных систем»


Москва 2009


  1. Цели и задачи дисциплины.



Дисциплина “Дискретная математика” является одной из основных дисциплин цикла “Математические и естественно - научные дисциплины”. Ее целью является ознакомление студентов с важнейшими разделами дискретной математики и ее применением для решения практических задач. Изучение дисциплины "Дискретная математика" должно воспитывать у слушателей творческое мышление, навыки самостоятельного решения задач научного содержания, трудолюбие и настойчивость в достижении результатов, строгость математического мышления.

К задачам дисциплины "Дискретная математика" относятся:
  • ознакомление слушателей с основами комбинаторики, математической логики, теории алгоритмов, теории автоматов, теории графов и их приложения к задачам математической кибернетики;

приобретение навыков свободного обращения с основными дискретными объектами.


  1. Место дисциплины в структуре ООП.


Цикл дисциплин “Математические и естественнонаучные дисциплины”. Дисциплина "Дискретная математика" строится на знаниях, полученных слушателями при изучении дисциплин «Ал­геб­ра и гео­мет­рия» и «Ма­те­ма­ти­че­ский ана­лиз».

Знания и навыки, полученные при изучении дисциплины «Дискретная математика», широко используются обучаемыми при изучении общепрофессиональных и специальных дисциплин, в частности, при изучении дисциплин: Теория информации и кодирования, Интеллектуальные информационные системы, Моделирование систем и сетей телекоммуникаций, Криптографические методы защиты информации, Теория радиотехнических сигналов, Электроника и схемотехника, Методы программирования.


3. Требования к уровню освоения дисциплины.



    Процесс изучения дисциплины направлен на формирование следующих компетенций:
  • способен к логическому мышлению, обобщению, анализу, критическому осмыслению, систематизации, прогнозированию, постановке исследовательских задач и выбору путей их достижения (ОК – 9);
  • способен самостоятельно применять методы и средства познания, обучения и самоконтроля для приобретения новых знаний и умений, в том числе в новых областях, непосредственно не связанных со сферой деятельности, развития социальных и профессиональных компетенций, изменения вида и характера своей профессиональной деятельности (ОК-10);
  • способен выявлять естественнонаучную сущность проблем, возникающих в ходе профессиональной деятельности, и применять соответствующий физико-математический аппарат для их формализации, анализа и выработки решения (ПК-1);
  • способен применять математический аппарат, в том числе с использованием вычислительной техники, для решения профессиональных задач (ПК-2);
  • способен применять методологии научно-исследовательской и практической деятельности (ПК-5).
  • спо­соб­ен применять основные методы, способы и средства получения, хранения, переработки и передачи информации, использовать компьютер как средство управления информацией (ПК-10);



В результате изучения дисциплины студент должен:


Знать

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


Уметь

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


Владеть:
  • на­вы­ка­ми по­строе­ния дис­крет­ных мо­де­лей при ре­ше­нии про­фес­сио­наль­ных за­дач;



4. Объём дисциплины и виды учебной работы:



Вид учебной работы
Всего часов
Семестры

3
4

Аудиторные занятия
120
60
60

Лекции
60
30
30

Семинары (С)









Практические занятия (ПЗ)
54
26
28

Лабораторные работы (ЛР)
–
–
–

Контрольные работы
6
4
2
Другие виды аудиторных занятий
(тактические занятия, учения, специальные игры, индивидуальные занятия)
-
-


-

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

Курсовая работа (проект)
–
–



Реферат
-
-



Домашняя работа (задание)
–
–



Самостоятельная проработка учебного материала
60
30
30

Другие виды самостоятельной работы
–
–
–

Вид итогового контроля
36
-
Экзамен

Общая трудоемкость дисциплины

часы
180+36
90
90+36

Кредитные единицы
5+1
2,5
2,5+1



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


5.1. разделы дисциплины и виды занятий



№ п/п
Разделы дисциплины
Лекции

ПЗ или С
ЛР

1
Введение
2
-



2
Основы комбинаторики
10
10



3
Логические функции и алгебра предикатов
12
12



4
Алгоритмы и их сложность
8
6



5
Конечные автоматы
8
6



6
Элементы теории графов
10
10



7
Линейные коды
10
10





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


Тема 1. ВВЕДЕНИЕ


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

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


Тема 2. Основы комбинаторики


2.1. Основные понятия теории множеств. Отношения эквивалентности. Принципы комбинаторики.

2.2. Метод включения - исключения.

2.3. Метод рекуррентных соотношений.

2.4. Перманенты и их применения. Методы вычисления перманентов.


Тема 3. Логические функции и алгебра предикатов .


3.1. Логика высказываний, логика предикатов. Логические исчисления, непротиворечивость и полнота.

3.2. Представление функций СДНФ и СКНФ. Полиномиальные представления. Весовые представления булевых функций.

3.3. Функциональная полнота, критерий полноты.

3.4. Представления булевых функций рядами Фурье.

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

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


Тема 4. Алгоритмы и их сложность.


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

4.2. Машины Тьюринга. Понятие об алгоритмической разрешимости и неразрешимости задач.

4.3. Функции сложности алгоритмов.

4.4. Методы построения эффективных алгоритмов. Метод разбиения и рекурсии. Сложность рекурсивных алгоритмов.


Тема 5. Конечные автоматы.


5.1. Основные понятия. Языки и грамматика.

5.2. Эквивалентность состояний. Алгоритм разбиения состояний.

5.3. Автоматы без потери информации.

5.4. Регулярные автоматы.

5.5. Линейные автоматы. Периодичность в линейных автоматах.


Тема 6. Элементы теории графов.


6.1. Графы, их вершины, ребра и дуги. Изображение графов.

6.2. Матрица инцидентности и список ребер. Матрица смежности. Степени вершин графов. Части, суграфы и подграфы. Операции с частями графа.

6.3. Маршруты, цепи и циклы. Связные компоненты граф. Пути и циклы в ориентированном графе.

6.4. Эйлеровы графы. Гамильтоновы графы.

6.5. Деревья, лес. Концевые вершины и ребра. Дерево с корнем, ветви. Типы вершин и центры деревьев.

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


Тема 7. Линейные коды.

7.1. Постановка задач теории кодирования. Общие границы параметров кодов.

7.2. Линейные коды. Порождающая и проверочная матрицы. Процесс кодирования и декодирования. Граница Варшамова-Гилберта.

7.3. Коды Хемминга. Циклические коды и их декодирование.

7.4. Распределение весов кода. Тождество Мак-Вильямс.

7.5. Оптимальные Коды Фано и Хаффмена.


6. Лабораторный практикум

Не предусмотрен.


7. Примерная тематика курсовых работ (проектов)

Курсовые работы не предусмотрены


8. Учебно-методическое обеспечение дисциплины


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


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

  1. В.А. Галкина. Дискретная математика: комбинаторные методы оптимизации. – М.: Гелиос АРВ, 2003. (учебное пособие УМО)
  2. М.О. Асанов, В.А. Баранский, В.В. Расин. Дискретная математика: графы, матроиды, алгоритмы. – М.: Ижевск: Изд-во РХД, 2001. (учебное пособие УМО университетов)
  3. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Из-во МАИ, 1992.
  4. А.И. Белоусов, С.Б. Ткачев Дискретная математика. – М.: МГТУ им. Н.Э. Баумана, 2004. - 742 с.- Математика в техническом университете
  5. С. В. Судоплатов, Е. В. Овчинникова. Элементы дискретной математики. Учебник. - М.: Инфра-М, Новосибирск: Изд. НГТУ. - 2002. -280 с.
  6. Гаврилов Г.П. Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. – М.: Физматлит, 2005.
  7. Maкоха А. Н., Сахнюк П. А., Червяков Н. И. Дискретная математика: Учеб. пособие. - М.: ФИЗМАТЛИТ, 2005. - 368 с.
  8. Глухов М.М. Алгебра и аналитическая геометрия: Учебное пособие. – М.: Гелиос АРВ, 2005. – 392с. (учебное пособие УМО)



Дополнительная литература:

  1. Яблонский С. В. Введение в дискретную математику: учебное пособие для вузов. – М.: Высшая школа, 2006.
  2. Аляев Ю.А. Тюрин С.Ф. Дискретная математика и математическая логика. — М.: Финансы и статистика, 2006. — 368 с.
  3. Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2000. - 304с
  4. Горбатов В. А. Фундаментальные основы дискретной математики. Информационная математика. — М.: Наука. Физматлит, 2000.—544с
  5. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М., 1988 г.
  6. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. – М.: Наука - Физматлит, 1997
  7. Сачков В. Н. Введение в комбинаторные методы дискретной математики. — М.: Изд-во МЦНМО, 2004. (учебное пособие Минобразования)



8.2. Средства обеспечения освоения дисциплины

Не предусмотрено.

  1. Материально-техническое обеспечение дисциплины


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


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

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

Примерным учебным планом на изучение дисциплины отводится два семестра. В каждом семестре целесообразно предусмотреть проведение контрольной работы. В конце второго семестра предлагается провести экзамен. На подготовку и сдачу экзамена в соответствии с госстандартом и примерным учебным планом выделяется дополнительно 36 часов.

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

1. Отношения эквивалентности.

2. Метод включения - исключения.

3. Метод рекуррентных соотношений.

4. Комбинаторные конфигурации.

5. Числа Стирлинга.

6. Перманенты и методы их вычислений.

7. Способы задания булевых функций.

8. Представление функций СДНФ и СКНФ.

9. Многочлен Жегалкина.

10. Функциональная полнота. Замкнутые классы.

11. Критерий Поста функциональной полноты.

12. Способы задания функций к-значной логики.

13. Основные классы функций к-значной логики.

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

15. Методы оценки сложности алгоритмов.

16. Способы и примеры построения эффективных алгоритмов.

17. Автоматы и операции с ними.

18. Эквивалентность состояний.

19. Регулярные автоматы.

20. Графы и способы их задания.

21. Деревья и остовы.

22. Эйлеровы графы.

23. Пути и циклы в графах.

24. Общие оценки параметров кодов.

25. Линейные коды. Декодирование с помощью синдромов.

26. Циклические коды. Нахождение параметров циклических кодов.

Декодирование циклических кодов.

27. Оптимальные коды.


10.2. Рекомендуемый перечень тем контрольных работ


1. Комбинаторика.

2. Булевы функции и способы их задания

3. Вычисление основных параметров графов.


Разработчики:


Институт криптографии, связи и информатики, доцент кафедры дискретной математики Подуфалова В.Д.


Институт криптографии, связи и информатики, доцент кафедры дискретной математики Зязин А.В.


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


Эксперты:


Программа одобрена на заседании ________________ совета __________


от _________________ года, протокол № ____.