Программа дисциплины «Дискретная математика» - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Программа дисциплины «Дискретная математика и теория алгоритмов» 1 174.94kb.
Программа дисциплины Дискретная математика для направления 080500. 1 334.03kb.
Программа дисциплины Дискретная математика для направления 010400. 1 145.02kb.
Программа дисциплины «Дискретная математика» 1 185.8kb.
Программа дисциплины «Дискретная математика» 1 108.45kb.
Программа дисциплины «Дискретная математика» 1 124.98kb.
Вопросы к экзамену по курсу "Дискретная математика" 8 467.03kb.
Учебно-методическое пособие по предмету «Математика» 1 143.54kb.
Программа дисциплины «Дискретная математика» 1 125.36kb.
Рабочая программа дисциплины математика направление подготовки: 270800. 5 584.17kb.
Программа дисциплины Спецкурс «Гомологическая алгебра» для направления... 1 101.74kb.
Краткие рекомендации 1 22.72kb.
Направления изучения представлений о справедливости 1 202.17kb.

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




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





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


Национальный исследовательский университет
"Высшая школа экономики"

Факультет Бизнес информатики

Программа дисциплины

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



для направления 080500.62 «Бизнес-информатика»


подготовки бакалавра

Автор программы: Лебедев Анатолий Николаевич, к.ф.-м.н.,с.н.с., alebedev@hse.ru, lan@lancrypto.com

Одобрена на заседании кафедры высшей математики на факультете экономики г.

Зав. кафедрой Алескеров Ф.Т.

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

Председатель

Утверждена Ученым Советом факультета экономики «___»_____________20 г.

Ученый секретарь

Москва, 2012
Настоящая программа не может быть использована другими подразделениями
университета и другими вузами без разрешения кафедры-разработчика программы.

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


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

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

Программа разработана в соответствии с требованиями следующих документов:


  • Образовательным стандартом государственного образовательного бюджетного учреждения высшего профессионального образования «Государственный университет – Высшая школа экономики», в отношении которого установлена категория «Национальный исследовательский университет»;

  • Рабочим учебным планом университета подготовки магистра по направлению 080500.62 «Бизнес-информатика» подготовки бакалавра, утвержденным в 2011 г.

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


Целями освоения дисциплины «Дискретная математика» являются

  • ознакомление студентов с основами современной дискретной математики;

  • формирование навыков работы с абстрактными понятиями математики;

  • знакомство с прикладными задачами дисциплины.

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


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

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

  • Уметь применять идеи и методы современной дискретной математики для решения задач, возникающих в дисциплинах, их использующих;

  • Владеть навыками применения современного инструментария дискретной математики.

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



Компетенция

Код по ФГОС / НИУ

Дескрипторы – основные признаки освоения (показатели достижения результата)

Формы и методы обучения, способствующие формированию и развитию компетенции

Общенаучная

ОНК-1

Способность к анализу и синтезу на основе системного подхода

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-2

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

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-3

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

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-4

Готовность использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы дискретной математики и моделирования, теоретического и экспериментального исследования при работе в какой-либо предметной области

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-5

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

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-6

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

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-7

Способность порождать новые идеи (креативность)

Стандартные (лекционно-семинарские)

Инструментальные

ИК-2

Умение работать на компьютере, навыки использования основных классов прикладного программного обеспечения, работы в компьютерных сетях, составления баз данных

Стандартные (лекционно-семинарские)

Профессиональные

ПК-1

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

Стандартные (лекционно-семинарские)

Профессиональные

ПК-2

Способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат

Стандартные (лекционно-семинарские)

Профессиональные

ПК-4

Способность критически оценивать собственную квалификацию и её востребованность, переосмысливать накопленный практический опыт, изменять при необходимости вид и характер своей профессиональной деятельности

Стандартные (лекционно-семинарские)

Профессиональные

ПК-8

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

Стандартные (лекционно-семинарские)



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


Настоящая дисциплина относится к циклу дисциплин ОПД.00 «Общие профессиональные дисциплины направления» и блоку дисциплин СД.00 «Специальные дисциплины» и является базовой.

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



  • Начала математического анализа;

  • Геометрия;

  • Алгебра;

  • Начала информатики.

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

  • Знаниями основных определений и теорем перечисленных выше дисциплин;

  • Навыками решения типовых задач этих дисциплин.

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

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

  • Линейная алгебра и аналитическая геометрия;

  • Теория вероятностей и математическая статистика;

  • Дискретные модели;

  • Теория игр;

  • Методы оптимизации.

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




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

Всего часов

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

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

Лекции

Семинары

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



Элементы теории чисел:

- Теория делимости;

- Алгоритм Евклида, вычисление в кольце вычетов ℤn;

- Квадратичные вычеты.



22

8

8




6



Алгебра:

- Группы, группы подстановок n;

- Кольца и поля;

- Конечные кольца и поля.



16

4

6




6



Теория сложности:

- Сложные вычислительные задачи;

- Асимптотические оценки сложности: О(n), o(n), Ω(n), (n);

- Классы P и NP.



6

2

2




2



Математические алгоритмы современной криптографии:

- Протокол Диффи-Хеллмана;

- Система открытого шифрования и электронной подписи RSA;

- Современные стандарты шифрования данных: DES, AES, ГОСТ Р 28147-89;

- Алгоритмы хэширования данных: SHA-1, SHA-2, SHA-3, ГОСТ Р 34.11-94, ГОСТ Р 34.11-2012 («Стрибог»);

- Современные стандарты электронной подписи на основе вычислений в группе точек эллиптической кривой: ECDSA, ГОСТ Р 34.10-2001, ГОСТ Р 34.10-2012.



4

4












Алгоритмы генерации больших простых чисел и псевдопростых чисел.

Открытые проблемы современной дискретной математики.

Зачет


2

2

2



2

2





2






Итого

54

22

16

2

14



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


Тип контроля

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

1 модуль

Параметры **

1







Текущий

(неделя)



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

1







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













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

8







Исполнение в течение недели

Итоговый

Зачетная работа

1







Письменный зачет по всем разделам курса.

6.1Критерии оценки знаний, навыков


Для прохождения контроля студент должен, как минимум, продемонстрировать знания основных определений и формулировок теорем; умение решать типовые задачи, разобранные на семинарских занятиях. При этом для получения зачета необходимо предоставить, как минимум, 80 % решенных в домашних заданиях задач.

Оценки по всем формам текущего контроля выставляются по 10-ти балльной шкале.


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


Тема I. Элементы теории чисел

Понятие натурального и целого числа. Делимость целых чисел. Наибольший общий делитель и наименьшее общее кратное целых чисел. Простые числа, решето Эратосфена. Разложение целого числа на простые множители. Единственность разложения на простые множители.

Деление целых чисел с остатком. Алгоритм Евклида, расширенный алгоритм Евклида.

Вычисления по модулю целого числа n, свойства арифметики кольца ℤn. Китайская теорема об остатках. Квадратичные вычеты, закон взаимности Гаусса.



Литература: основная: [1], с. .
Тема II. Алгебра

Алгебраические системы. Группоиды, полугруппы, моноиды, группы. Примеры: полугруппа (ℕ, +), моноид (ℕ, *), группы (ℤ, +), (ℚ, +), (ℚ\0, *), (ℝ, +), (ℝ\0, *), (ℂ, +), (ℂ\0, *), (n, ℝ).

Конечные группы, абелевы группы, циклические группы. Задание групповой операции таблицей Кэли.

Подгруппы. Смежные классы группы по подгруппе. Теорема Лагранжа. Нормальные делители группы, фактор группы, гомоморфизмы групп. Теоремы о гомоморфизмах. Примеры для ℤn.

Подстановки. Группы подстановок n, цикловая запись подстановки, порядок подстановки, представление конечной группы группой подстановок.

Кольца и поля. Арифметика конечных колец и полей. Группа обратимых элементов кольца и поля. Кольцо многочленов над полем, неприводимые и примитивные многочлены. Обратные элементы в фактор кольце кольца многочленов над конечным полем. Поля Галуа, группы Галуа.



Литература: основная: [2], с. .
Тема III. Теория сложности

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

Асимптотические оценки сложности, классы O(n), o(n), Ω(n), (n).

Классы P и NP, NP-сложные задачи, NP-полные задачи и попытки их использования для построения стойких криптографических алгоритмов.



Литература: основная: [3], с. .
Тема IV. Математические алгоритмы современной криптографии

- Криптография с открытым ключом, протокол Диффи-Хеллмана;

- Система открытого шифрования и электронной подписи RSA;

- Современные стандарты шифрования данных: DES, AES, ГОСТ Р 28147-89;

- Алгоритмы хэширования данных: национальные стандарты США SHA-1, SHA-2, SHA-3, государственные стандарты России ГОСТ Р 34.11-94, ГОСТ Р 34.11-2012 («Стрибог»);

- Современные стандарты электронной подписи на основе вычислений в группе точек эллиптической кривой: ECDSA, ГОСТ Р 34.10-2001, ГОСТ Р 34.10-2012



Литература: основная: [4], с. .
Тема V. Генерация больших простых чисел. Открытые проблемы современной дискретной математики.

Датчики случайных чисел, программные генераторы псевдослучайных чисел.

Генераторы больших простых и псевдо простых чисел.

Оценка сложности вычислительных задач: разложения на множители целого числа (FACT), задачи дискретного логарифмирования в конечной циклической группе (DLOG), задача декодирования общего линейного кода (DECODE), решение системы полиномиальных уравнений от нескольких переменных (POLYSYS), задача об укладке ранца (KNAPSACK).



Литература: основная: [5], с.; дополнительная: [], с. .

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

8.1Тематика заданий текущего контроля


Примерные вопросы/ задания для домашнего задания:

  1. Вопросы:


Тематика [Укажите название текущего контроля - курсовые, эссе или другое] :



  1. Тема



Тема [Укажите название текущего контроля - эссе, рефераты или другое] для каждого студента утверждается преподавателем в индивидуальном порядке.

8.2Вопросы для оценки качества освоения дисциплины


Примерный перечень вопросов к зачету (экзамену) по всему курсу или к каждому промежуточному и итоговому контролю для самопроверки студентов.

8.3Примеры заданий промежуточного /итогового контроля


По желанию автора программы, приводятся примеры билетов с вопросами и задачами, заданий для зачета или экзамена, тренировочные тесты по дисциплине.

9Порядок формирования оценок по дисциплине


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

Оценки за самостоятельную работу студента преподаватель выставляет в рабочую ведомость. Накопленная оценка по 10-ти балльной шкале за самостоятельную работу определяется перед промежуточным или итоговым контролем – Осам. работа.


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

Отекущий = 0,6·Оаудиторная + 0,4·Осам. работа .

Способ округления накопленной оценки текущего контроля производится по правилам арифметики округления.


Результирующая оценка за промежуточный контроль в форме зачета выставляется по следующей формуле, где Озачет – оценка за работу непосредственно на зачете:

Опромежуточный = 0,6·Озачет + 0,3·Одз + 0.1·Отекущий .

Способ округления накопленной оценки промежуточного контроля производится по правилам арифметики округления.

Результирующая оценка за итоговый контроль в форме экзамена выставляется по следующей формуле, где Оэкзамен – оценка за работу непосредственно на экзамене:

Оитоговый = 0,5·Оэкзамен + 0,2·Окр1 + 0,2·Окр2 + 0,1· Отекущий.

Способ округления накопленной оценки итогового контроля производится по правилам арифметики округления.

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

В диплом выставляется результирующая оценка по учебной дисциплине, которая формируется по следующей формуле:



Одисциплина = 0,3·Опромежуточный + 0,7·Оитоговый .

Способ округления результирующей оценки по учебной дисциплине производится по правилам арифметики округления.


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

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


[1] Виноградов И.М., Основы теории чисел. – М.: Наука, 1990.

[2] Кострикин А.И., Введение в алгебру. Часть I. Основы алгебры: Учебн. для вузов. – 2-е изд., исправл. - М.: ФИЗМАТЛИТ, 2004.


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


[3] Глухов М.М., Круглов И.А., Пичкур А.Б., Черемушкин А.В., Введение в теоретико-числовые методы криптографии: Учебное пособие. – СПб.: Издательство «Лань», 2011.

[4] Абрамов С.А., Лекции о сложности алгоритмов. – М.: МЦНМО, 2009.

[5] Schneier, Bruce, Applied Cryptography Second Edition: protocols, algorithms, and source code in C/ John Wiley&Sons, Inc., 1996.

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


[6] Дэвенпорт Г., Высшая арифметика. Введение в теорию чисел / Г. Дэвенпорт; Пер. с англ. – М.: Наука, 1965.

[7] Крупский В.Н., Введение в сложность вычислений / В.Н. Крупский; – М.: Факториал Пресс, 2006.



[8] Афафнасьев А.А., Веденьев Л.Т., Воронцов А.А., Газизова Э.РюЮ Додохов А.Л., Крячков А.В., Полянская О.Ю., Сабанов А.Г., Скида М.А., Халяпин С.Н., Шелупанов А.А., Аутентификация ысшая арифметика. Введение в теорию чисел / Г. Дэвенпорт; Пер. с англ. – М.: Наука, 1965.






Умеренность в жизни похожа на воздержание в еде: съел бы еще, да страшно заболеть. Франсуа Ларошфуко
ещё >>