Правительство Российской Федерации

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

Факультет прикладной математики и кибернетики

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

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

Автор программы:

, доцент, *****@***ru.

Одобрена на заседании кафедры прикладной математики «29» июня 2012 г.

Зав. кафедрой

Рекомендована секцией УМС [Введите название секции УМС] «___»____________ 20 г

Председатель [Введите ]

Утверждена УС факультета [Введите название факультета] «___»_____________20 г.

Ученый секретарь [Введите ] ________________________ [подпись]

Москва, 2012

2  Область применения и нормативные ссылки

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

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

Программа разработана в соответствии с:

·  ФГОС 090301 Компьютерная безопасность. 65 Математик.

·  Образовательной программой 090301.65 «Компьютерная безопасность».

·  Рабочим учебным планом университета по специальности 090301.65 «Компьютерная безопасность», специализации «Математические методы защиты информации», утвержденным в 2012 г.

НЕ нашли? Не то? Что вы ищете?

3  Цели освоения дисциплины

Дисциплина имеет своей целью: обеспечить выполнение требований, изложенных в федеральном государственном образовательном стандарте высшего профессионального образования по направлению подготовки 090301 Компьютерная безопасность. Изучение дисциплины направлено на формирование перечисленных ниже элементов общекультурных и профессиональных компетенций.

Также целями освоения дисциплины «Дискретная математика» являются ознакомление студентов с основными задачами и методами комбинаторики, теории графов и теории автоматов, алгоритмическими процедурами решения задач оптимизации на дискретных структурах.

4  Компетенции обучающегося, формируемые в результате освоения дисциплины

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

·  Знать основные понятия и методы

- комбинаторики,

- теории графов,

- теории автоматов;

·  Уметь

- исследовать комбинаторные свойства дискретных моделей;

- применять методы дискретной математики в различных приложениях математики и компьютерных наук.

Про­цесс изу­че­ния дис­ци­п­ли­ны на­прав­лен на фор­ми­ро­ва­ние сле­дую­щих ком­пе­тен­ций:

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

спо­соб­ность ло­ги­че­ски вер­но, ар­гу­мен­ти­ро­ва­но и яс­но стро­ить уст­ную и пись­мен­ную речь на рус­ском язы­ке, го­то­вить и ре­дак­ти­ро­вать тек­сты про­фес­сио­наль­но­го на­зна­че­ния, пуб­лич­но пред­став­лять соб­ст­вен­ные и из­вест­ные на­уч­ные ре­зуль­та­ты, вес­ти дис­кус­сии (ОК-7);

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

спо­соб­ность вы­яв­лять ес­те­ст­вен­но­на­уч­ную сущ­ность про­блем, воз­ни­каю­щих в хо­де про­фес­сио­наль­ной дея­тель­но­сти, и при­ме­нять со­от­вет­ст­вую­щий фи­зи­ко-ма­те­ма­ти­че­ский ап­па­рат для их фор­ма­ли­за­ции, ана­ли­за и вы­ра­бот­ки ре­ше­ния (ПК-1);

спо­соб­ность при­ме­нять ма­те­ма­ти­че­ский ап­па­рат, в том чис­ле с ис­поль­зо­ва­ни­ем вы­чис­ли­тель­ной тех­ни­ки, для ре­ше­ния про­фес­сио­наль­ных за­дач (ПК-2);

спо­соб­ность при­ме­нять ме­то­до­ло­гии на­уч­но-ис­сле­до­ва­тель­ской и прак­ти­че­ской дея­тель­но­сти (ПК-4);

спо­соб­ность к са­мо­стоя­тель­но­му по­строе­нию ал­го­рит­ма, про­ве­де­нию его ана­ли­за и реа­ли­за­ции в со­вре­мен­ных про­грамм­ных ком­плек­сах (ПК-12);

спо­соб­ность го­то­вить на­уч­но-тех­ни­че­ские от­че­ты, об­зо­ры, пуб­ли­ка­ции по ре­зуль­та­там вы­пол­нен­ных ра­бот (ПК-17).

5  Место дисциплины в структуре образовательной программы

Настоящая дисциплина относится к базовой части Математического и естественнонаучного цикла дисциплин, обеспечивающего подготовку специалиста.

Для специализации «Математические методы защиты информации», настоящая дисциплина является базовой.

Изучение данной дисциплины базируется на следующих дисциплинах:

· Алгебра.

· Математический анализ.

Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин:

· Крип­то­гра­фи­че­ские ме­то­ды за­щи­ты ин­фор­ма­ции;

·  Тео­рия ин­фор­ма­ции;

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

·  Тео­ре­ти­ко-чи­сло­вые ме­то­ды в крип­то­гра­фии;

·  Крип­то­гра­фи­че­ские про­то­ко­лы.

6  Тематический план учебной дисциплины

№

Название раздела

Всего часов

Аудиторные часы

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

Лекции

Семинары

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

1

Бинарные отношения

7

2

2

3

2

Общие понятия теории графов

14

4

4

6

3

Связность графов

7

2

2

3

4

Изоморфизм графов

7

2

2

3

5

Цикломатическое число графа

7

2

2

3

6

Планарность графов

18

5

5

8

7

Цикл Эйлера

6

2

2

2

8

Задача о поиске выхода из лабринта

7

2

2

3

9

Обобщенный метод волны

13

3

3

7

10

Двухполюсные транспортные сети

10

3

3

4

11

Задача оптимального назначения

10

3

3

4

12

Метод ветвей и границ

11

3

3

5

13

Алгоритм Литтла решения задачи

9

3

3

3

7  Формы контроля знаний студентов

Тип контроля

Форма контроля

1 год

Параметры **

 

2 семестр

Промежу­точный

Домашнее задание

5-я неделя семестра

Самостоятельная работа, с последующей защитой результатов

Домашнее задание

10 неделя семестра

Самостоятельная работа, с последующей защитой результатов

Контрольная работа

14 неделя семестра

Письменная работа на 60 минут

Итоговый

Зачет

В конце семестра

Устное собеседование

7.1  Критерии оценки знаний, навыков
Сдача студентом зачета оценивается по системе «зачет / незачет» в соответствии со знаниями и навыками, проявленными студентом на зачете, а также с учетом результатов контрольной работы и выполнения домашних заданий.

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

1. Бинарные отношения (БО).

Операции над БО. Различные способы представления БО на конечных множествах (список, бинарная матрица, граф, двудольный граф). Свойства бинарных отношений (рефлексивность, транзитивность, симметричность, антисимметричность, асимметричность, связность). Основные типы БО. Отношение толерантности, отношение эквивалентности, отношение квазиупорядоченности, отношение частичной упорядоченности, отношение линейной предупорядоченности, отношение линейного порядка и их свойства (примеры на конечных множествах). Классы эквивалентности и классы толерантности. Способы определения отношения эквивалентности. Соответствие свойств БО и операций над ними и свойств соответствующих матриц, списков, графов и др.

2. Общие понятия теории графов.

Ориентированный граф, неориентированный граф, мультиграф, псевдограф, гиперграф.

Абстрактный граф, нумерованный граф. Способы задания графа (матрица смежности, матрица инцидентности, список дуг графа). Операции над графами. Подграф, подграф порожденный, подграф остовный. Факторизация графа по заданному отношению эквивалентности..

Пути, цепи, контуры, циклы.

3. Связность графов.

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

4. Изоморфизм графов.

Гомоморфизм графов, изоморфизм графов, автоморфизмы графа, гомеоморфные графы. Алгоритм перебора перестановок применительно к решению задачи об изоморфности двух графов.

5. Цикломатическое число графа.

Свойства цикломатического числа. 1-цепи и 1-циклы. Алгоритм выделения цикла в графе с единичным цикломатическим числом. Алгоритм построения остовного дерева (леса) и базы независимых циклов. Алгоритм вычисления цикломатического числа.

6. Планарные графы.

Двумерные поверхности без края. Вычисление характеристики Эйлера двумерных поверхностей без края (тор, поверхность рода К, бутылка Клейна, проективная плоскость RP2).

Реализация на торе полных 5, 6 и 7 - графов Куратовского. Алгоритм построения плоской реализации графа. Алгоритм построения максимальной плоской части непланарного графа.

7. Цикл Эйлера.

Теорема существования цикла Эйлера. Алгоритм построения цикла Эйлера и вопросы программирования алгоритма.

8. Задача о поиске выхода из лабиринта.

Алгоритм последовательного двойного обхода ребер мультиграфа и вопросы его программирования.

9. Обобщенный метод волны.

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

10 Двухполюсные транспортные сети.

Транспортная сеть. Потоки в сетях. Алгоритм Форда-Фалкерсона построения потока максимальной величины и его обоснование. Многоитерационный обобщенный волновой алгоритм поиска потока максимальной величины в двухполюсной транспортной сети. алгоритмы оптимизации на графах.

11. Задача оптимального назначения.

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

12. Метод ветвей и границ.

Общие принципы метода ветвей и границ: разбиение (ветвление), вычисление нижней границы, выбор элемента разбиения для дальнейшего его разбиения на части. Стратегии применения метода с целью оптимизации количества элементов разбиения.

13. Алгоритм Литтла решения задачи.

Обсуждение вопросов программирования алгоритма Литтла.

9  Образовательные технологии

– чтение лекций

– проведение практических занятий

– проведение контрольной работы

– проведение зачета.

10  Оценочные средства для текущего контроля и аттестации студента

11  Учебно-методическое и информационное обеспечение дисциплины

11.1  Базовый учебник

, , Расин математика: графы,
матроиды, алгоритмы. – М., Ижевск: РХД, 2001..

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

Гаврилов и упражнения по курсу дискретной
математики. – М.: Физматлит, 2005.
Галкина математика: комбинаторные методы оптимизации. –
М.: Гелиос АРВ, 2003.
Сачков в комбинаторные методы дискретной математики. –
М.: МЦНМО, 2004.
Яблонский в дискретную математику: учебное пособие для вузов.
– М.: Высшая школа, 2006.

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

В. В Белов, , Методические указания к курсовым и лабораторным Ра ботам по дисциплине Алгоритмы дискретной математики", РИО МИЭМ, 1988.
А. Кристофидес, Теория графов (алгоритмический подход), М., Мир, 1978.
А. Кофман, Введение в прикладную комбинаторику, М., Наука, 1978.
В. Белов, Е. Воробьев, В. Шаталов, Теория графов М., Высшая школа, 1975.
В. Белов, С. Авдошин, Методические указания к проведению практических занятий по курсу "Алгоритмы дискретной математики". РИО МИЭМ, ч. I, 1980 г., ч. II, 1983.
Ф. Харари, Теория графов, М., Мир, 1973.
Р. Басакер, Т Саати, Конечные графы и сети, М., Наука, 1974.
, , Математический аппарат инженера Киев, Техника, 1977.
Т. Ху, Целочисленное программирование и потоки в сетях. М., Мир, 1974
Э. Рейнгольд, Ю. Нивергельт, И. Део, Комбинаторные алгоритмы. Теория и прак тика. М., Мир, 1980.
, Введение в комбинаторные методы дискретной математики. М., Наука, 1982.

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