Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
«Особенности актуализации и качества реализации основных профессиональных образовательных программ в соответствии с ФГОС и профессиональными стандарта...полностью>>
'Документ'
Целью Стратегии развития инновационного территориального кластера «Донские молочные продукты» по производству и переработке молочной продукции в Росто...полностью>>
'Документ'
'Документ'
имеются подъезды и дороги с гравийным покрытием, возможность подключения к газу, разрабатывается проектная документация на электрификацию жилого масси...полностью>>

Главная > Программа дисциплины

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

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

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

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

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

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

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



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

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

Славнов С.А., доцент, sslavnov@.

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

Зав. кафедрой М.В. Карасев

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

Председатель [Введите И.О. Фамилия]

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

Ученый секретарь [Введите И.О. Фамилия] ________________________ [подпись]

Москва, 2013

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Уметь:

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

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

  • Владеть на­вы­ка­ми:

- при­ме­не­ния язы­ка и средств дис­крет­ной ма­те­ма­ти­ки;

- ре­ше­ния ком­би­на­тор­ных и тео­ре­ти­ко-гра­фо­вых за­дач.

    - по­строе­ния дис­крет­ных мо­де­лей при ре­ше­нии про­фес­сио­наль­ных за­дач.

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

Настоящая дисциплина относится к циклу «Общие математические и естественнонаучные дисциплины» и является Федеральным компонентом.

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

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

  • Алгебра.

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

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

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

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

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

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

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

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

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

Всего часов

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

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

Лекции

Семинары

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

1

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

7

2

2

3

2

Задача линейного программирования

7

2

2

3

3

Теория автоматов

7

2

2

3

4

Перечислительная комбинаторика

15

5

5

5

5

Композиции

7

2

2

3

6

Латинские квадраты и конфигурации

10

3

3

4

7

Прямые произведения матриц и проективные плоскости

9

3

3

3

8

Блок-схемы

7

2

2

3

9

Трансверсалии

7

2

2

3

10

Стохастические матрицы. Вероятностные преобразователи и цепи Маркова

7

2

2

3

11

Перманенты

8

3

2

3

12

Автоматы

18

6

6

6

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

Тип контроля

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

1 год

Параметры **

1

2

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

На 10-й неделе семестра

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

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

На 15-й неделе семестра

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

Итоговый

Экзамен

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

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

6.1Критерии оценки знаний, навыков
Сдача студентом экзамена оценивается по десятибальной системе в соответствии со знаниями и навыками, проявленными студентом на экзаменационном собеседовании и учетом результатов контрольных работ.

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

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

1. Задача оптимального квадратичного назначения.

Лемма Гилмора. Алгоритм решения задачи оптимального квадратичного назначения методом ветвей и границ.

2. Задача линейного программирования (ЗЛП).

Выпуклые множества. Симплекс метод решения ЗЛП.

3. Теория автоматов.

Конечные автоматы. Детерминированный конечный автомат. Эквивалентность автоматов. Алгоритм оптимизации памяти автомата. Тестирование автоматов. Декомпозиция автоматов

4. Перечислительная комбинаторика

Комбинаторные подсчеты. Числа сочетаний, размещений, размещений и сочетаний с повторениями. Принцип включения-исключения. Метод производящих функций. Рекуррентные соотношения. Экспоненциальные производящие функции.

5. Композиции

Лемма об инвариантности ортогональности относительно композиции с подстановками. Композиция латинских квадратов. Критерий ортогональности на основе композиции.

6. Латинские квадраты и конфигурации

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

7. Прямые произведения матриц и проективные плоскости

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

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

Построение множества попарно ортогональных латинских квадратов, по двум другим семействам ортогональных латинских квадратов. Теорема об эквивалентности существования проективной плоскости и семейства попарно ортогональных латинских квадратов максимальной мощности.

8. Блок-схемы

Блок-схемы. Применение блок схем. Алгебраическое исследование блок-схем с помощью единичной и полностью заполненной единицами матриц. Соотношения параметров блок-схемы. Тройки Штейнера. Генерация троек Штейнера с помощью композиции.

9. Трансверсалии.

Трансверсалии Теорема Холла о критерии существования трансверсали. Теорема существования латинского квадрата. Общие трансверсалии. Теорема существования общей трансверсали.

10. Стохастические матрицы. Вероятностные преобразователи и цепи Маркова

Декомпозиция неотрицательных матриц. Дважды стохастические матрицы. Теорема Биркгофа. Вероятностные автоматы. Декомпозиция вероятностных автоматов. Вероятностные преобразователи и цепи Маркова.

11. Перманенты

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

Метод включения - исключения, неравенство Бонферрони и оценка для перманентов.

12. Автоматы

Основные определения теории автоматов. Эквивалентность в автоматах. Функционирование автоматов. Эксперименты с автоматами. Вероятностные автоматы.

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

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

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

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

– проведение экзамена.

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

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

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

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

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

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

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

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

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

6



Похожие документы:

  1. Программа дисциплины "Дискретная математика" для направления 521600 Экономика

    Программа дисциплины
    Программа дисциплины "Дискретная математика" для направления 521600 - Экономика (вторая ... Михаил Николаевич. Требования к студентам: Учебная дисциплина «Дискретная математика» (5-й модуль учебного плана 1-го курса ...
  2. Программа дисциплины «Дискретная математика» (2)

    Программа дисциплины
    ... «Высшая школа экономики» Программа дисциплины «Дискретная математика» для специальности 090301 Компьютерная безопасность ... экономики" Факультет прикладной математики и кибернетики Программа дисциплины «Дискретная математика» для специальности 090301.65 ...
  3. Программа дисциплины «Дискретная математика» (3)

    Программа дисциплины
    ... университет «Высшая школа экономики» Программа дисциплины «Дискретная математика» для направления подготовки бакалавра 230400 ... школа экономики" Факультет прикладной математики и кибернетики МИЭМ Программа дисциплины «Введение в квантовую информатику» ...
  4. Программа дисциплины Дискретная математика для направления 010400. 68 «Прикладная математика и информатика» подготовки магистра Автор программы

    Программа дисциплины
    ... МАТЕМАТИКИ И ИНФОРМАТИКИ Программа дисциплины Дискретная математика для направления 010400.68 «Прикладная математика и информатика» подготовки магистра Автор программы ...
  5. Программа дисциплины Дискретная математика для социологов для направления 040200. 62 Социология подготовки бакалавра Автор: к ф. м н, преподаватель Андреева Т. В

    Программа дисциплины
    ... Высшая школа экономики» Факультет Менеджмента Программа дисциплины Дискретная математика для социологов для направления 040200 ... Пояснительная записка. Требования к студентам: Учебная дисциплинаДискретная математика для социологов” (4-й и 5-й модули ...

Другие похожие документы..