Главная страница 1



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

Факультет Математики



Программа дисциплины Спецкурс «Избранные главы дискретной математики»

для направления 010100.62 «Математика» подготовки бакалавра

и направления 010100.68 «Математика» подготовки магистра

Автор программы: Артамкин И.В., доктор ф.-м. наук, artamkin@mail.ru


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

Председатель С.М. Хорошкин
Утверждена УС факультета математики «___»_____________2012 г.

Ученый секретарь Ю.М. Бурман ________________________

Москва, 2012

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

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


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

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



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

  • ГОС ВПО;

  • Образовательными программами: 010100.62 «Математика» подготовки бакалавра и 010100.68 «Математика» подготовки магистра.

  • Рабочими учебными планами университета: по направлению 010100.62 «Математика» подготовки бакалавра и по направлению 010100.68 «Математика» подготовки магистра, специализации Математика, утвержденными в 2011 г.


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


Целями освоения дисциплины «Избранные главы дискретной математики» являются знакомство с наиболее распространенными и востребованными конструкциями и алгоритмами дискретной математики, относящимся к булевым функциям и графам.


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


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

  • Знать основные определения и результаты теории булевых функций и теории графов.

  • Уметь применять основные алгоритмы теории булевых функций и теории графов.

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


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


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

  • Введение в дискретную математику и курс алгебры 1 курса.

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

  • Основными понятиями теории графов и всем курсом алгебры за 1 курс, особенно линейной алгеброй.


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


1 курс магистратуры



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

Всего часов

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

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

Лекции

Семинары

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

1

Булевы функции

20

8

0

0

12

2

Теорема Поста

20

8

0

0

12

3

Графы

32

16

0

0

16




Итого:

72

32







40

2 курс магистратуры






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

Всего часов

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

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

Лекции

Семинары

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

1

Булевы функции

38

8

0

0

30

2

Теорема Поста

38

8

0

0

30

3

Графы

50

16

0

0

34




Итого:

126

32







94



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





Тип контроля

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

1 год

Параметры **

1

2

3

4

Текущий

(неделя)


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

*

8







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

Итоговый

Зачет




v







Устный зачет


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


  1. Раздел 1 Булевы функции

Булевы функции, способы их задания. Дизъюнктивно нормальные формы (ДНФ). Совершенная ДНФ. Грани булева куба. Сокращенная ДНФ. Задача минимизации. Ядровая ДНФ и тупиковые ДНФ. Полиномы Жегалкина. Различные алгоритмы построения полинома Жегалкина.

  1. Раздел 2 Теорема Поста

Полные системы функций. Замкнутые классы. Классы Т0 и Т1. Линейные функции. Необходимое условие линейности. Самодвойственные функции. Монотонные функции. Достаточное условие монотонности в терминах сокращенной ДНФ. Доказательство теоремы Поста.

  1. Раздел 3 Графы

    Потоки в сетях. Теорема Форда-Фалкерснона. Вершинная и ребрная теоремы Менгера. Двудольные графы. Паросочетания. Теорема Холла. Венгерский алгоритм. Задача об оптимальном назначении. Пространства циклов и разрезов. Остовные деревья. Решетки простых циклов и простых разрезов; их дискриминанты. Теорема Кирхгофа. Многогранники простых циклов и разрезов, их рефлексивность. Производящие функции графов.




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


Традиционный лекционный курс.

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

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


Примерные задания для контрольной работы

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

  2. Проверить полноту заданного набора булевых функций и выразить через них константы, отрицание, дизъюнкцию и конъюнкцию.

  3. Решить задачу оптимального назначения для данной матрицы эффективностей.



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


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

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


Оценка за текущий, промежуточный и итоговый контроль выставляется по 10 балльной шкале.
Результирующая оценка за итоговый контроль складывается из результатов накопленной результирующей оценки за текущий контроль, удельный вес которой составляет k1 = 0,5 и оценки за зачет, удельный вес k2 = 0,5.

Оитоговый = 0,5 * Отекущий + 0,5 * Озачет

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


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

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

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


Сирота А.И., Худак Ю.И. Дискретная математика. Москва Издательство МИРЭА 2010:

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


  1. Харири Ф. Теория графов М., УРСС 2003

  2. Дональд Кнут, Роналд Грэхем, Орен Паташник. Конкретная математика. Основания информатики.–М.:Мир; Бином. Лаборатория знаний, 2006.

  3. Ландо С.К. Лекции о производящих функциях. – Изд. 3–е.– М.: МЦНМО, 2007

  4. Свами М., Тхулалираман К. Графы, сети и алгоритмы. М: Мир, 1984.

  5. Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов — М.: Высш. школа, 1976



Смотрите также:
Программа дисциплины Спецкурс «Избранные главы дискретной математики» для направления 010100. 62 «Математика»
77.22kb.
1 стр.
Программа дисциплины Спецкурс «Дополнительные главы теории чисел 2» для направления 010100. 62 «Математика»
145.45kb.
1 стр.
Программа дисциплины Спецкурс «Многообразия флагов» для направления 010100. 62 «Математика»
93.71kb.
1 стр.
Программа дисциплины «Выпуклые многогранники»
91.82kb.
1 стр.
Программа дисциплины Квантовая механика для направления 010100. 62 "Математика" подготовки бакалавра
255.72kb.
1 стр.
Программа дисциплины Алгебраическая геометрия для направления 010100. 62 «Математика» подготовки бакалавра
202.46kb.
1 стр.
Программа дисциплины Математический анализ для направления 010100. 62 «Математика» подготовки бакалавра
194.94kb.
1 стр.
Программа по дисциплине дискретная математика кузьмина И. П. Для очной формы обучения всего 70
28kb.
1 стр.
Программа дисциплины теория вероятностей, случайные процессы
45.36kb.
1 стр.
Учебная программа По курсу «Основы дискретной математики», для студентов фмф
46.08kb.
1 стр.
Программа дисциплины Микроэкономика (адаптационный) для направления 010400. 68 «Прикладная математика и информатика»
548.14kb.
2 стр.
Программа дисциплины «Финансовая математика»
220.93kb.
1 стр.