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

Скачать 150.06 Kb.

Название	Программа дисциплины «Дискретная математика» для направления 010500. 62 «Прикладная математика и информатика»
Дата публикации	17.01.2015
Размер	150.06 Kb.
Тип	Программа дисциплины

100-bal.ru > Экономика > Программа дисциплины

Национальный исследовательский университет «Высшая школа экономики»
Программа дисциплины «Дискретная математика»
для направления 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Тематика заданий текущего контроля

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

Вопросы:

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

Тема

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

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.

Добавить документ в свой блог или на сайт

	Программа дисциплины «Модели корпусной лингвистики» для направления... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010400. 68 "Прикладная...		Программа дисциплины Современные методы принятия решений для направления... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 010400....
	Программа дисциплины «Герменевтика» для направления 010400. 68 «Прикладная... Программа предназначена для преподавателей, ведущих данную дисциплину, и студентов направления подготовки 010400. 68 "Прикладная...		Пояснительная записка рабочая программа дисциплины «Иностранный язык... «Математика и компьютерные науки», 010500. 62 «Математическое обеспечение и администрирование информационных систем», 230100. 62...
	Программа дисциплины «История» для направления 231300. 62 и 230700.... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 231300....		Программа дисциплины «Теория индивидуального и коллективного выбора»... Современные международные отношения: Учебно-методический комплекс./ Л. В. Володина. – Спб.: Ивэсэп, 2006
	Программа дисциплины “Философия науки“ для направления 010400. 62... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010400. 62 «Прикладная...		1. Цели и задачи дисциплины, ее место в учебном процессе Нанотехнология; 080801 Прикладная информатика в экономике; 230105 Программное обеспечение вычислительной техники и автоматизированных...
	Программа дисциплины «Система управления качеством» для направления... Повышение достоверности оценки качества подготовки водителей общественного транспорта		«Сети ЭВМ и телекоммуникации» для направления 010500 «Прикладная... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
	Бизнес-информатики программа дисциплины Вероятностно-статистические... Образовательная дать знания о Кибертерроризме, путях их распространения, об антивирусных программах и способах их использования на...		Программа дисциплины для направления 010400. 62 «Прикладная математика... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления для направления...
	Программа дисциплины Архитектура ЭВМ для направления 010400. 68 «Прикладная... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направлений подготовки 010400....		Бизнес-информатики программа дисциплины Вероятностно-статистические... Пспо; продолжить знакомство учащихся с текстами задач егэ, ориентированными на математические ситуации повседневной жизни
	Рабочая программа дисциплины Решение задач математической физики... Государственное образовательное учреждение высшего профессионального образования «Дальневосточный государственный университет путей...		Программа дисциплины Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направлений 231300. 62 «Прикладная...