Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
Национальный исследовательский университет
"Высшая школа экономики"
Факультет Бизнес-информатики
отд. Прикладной математики и информатики
Программа дисциплины
Дискретная математика
для направления 010500.62 «Прикладная математика и информатика»
подготовки бакалавра
Автор программы:
Одобрена на заседании кафедры высшей математики на факультете экономики 29.08.2011 г.
Зав. кафедрой
Рекомендована секцией УМС [Введите название секции УМС] «___»____________ 20 г
Председатель
Утверждена Ученым Советом факультета экономики «___»_____________20 г.
Ученый секретарь
Москва, 2012
Настоящая программа не может быть использована другими подразделениями
университета и другими вузами без разрешения кафедры-разработчика программы.
2 Область применения и нормативные ссылки
Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности.
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 010500.62 «Прикладная математика и информатика», подготовки бакалавра, изучающих дисциплину «Дискретная математика».
Программа разработана в соответствии с:
· Образовательным стандартом государственного образовательного бюджетного учреждения высшего профессионального образования «Государственный университет – Высшая школа экономики», в отношении которого установлена категория «Национальный исследовательский университет»;
· Рабочим учебным планом университета подготовки магистра по направлению 010500.62 «Прикладная математика и информатика» подготовки бакалавра, утвержденным в 2011 г.
3 Цели освоения дисциплины
Целями освоения дисциплины «Дискретная математика» являются
· ознакомление студентов с основами современной дискретной математики;
· формирование навыков работы с абстрактными понятиями математики;
· знакомство с прикладными задачами дисциплины.
4 Компетенции обучающегося, формируемые в результате освоения дисциплины
В результате освоения дисциплины студент должен:
· Знать основы дискретной математики, необходимые для дальнейшего изучения последующих дисциплин, предусмотренных базовым и рабочим учебными планами;
· Уметь применять идеи и методы современной дискретной математики для решения задач, возникающих в дисциплинах, их использующих;
· Владеть навыками применения современного инструментария дискретной математики.
В результате освоения дисциплины студент осваивает следующие компетенции:
Компетенция | Код по ФГОС / НИУ | Дескрипторы – основные признаки освоения (показатели достижения результата) | Формы и методы обучения, способствующие формированию и развитию компетенции |
Общенаучная | ОНК-1 | Способность к анализу и синтезу на основе системного подхода | Стандартные (лекционно-семинарские) |
Общенаучная | ОНК-2 | Способность перейти от проблемной ситуации к проблемам, задачам и лежащим в их основе противоречиям | Стандартные (лекционно-семинарские) |
Общенаучная | ОНК-3 | Способность использовать методы критического анализа, развития научных теорий, опровержения и фальсификации, оценить качество исследований в некоторой предметной области | Стандартные (лекционно-семинарские) |
Общенаучная | ОНК-4 | Готовность использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы дискретной математики и моделирования, теоретического и экспериментального исследования при работе в какой-либо предметной области | Стандартные (лекционно-семинарские) |
Общенаучная | ОНК-5 | Готовность выявить естественнонаучную сущность проблем, возникающих в ходе профессиональной деятельности, привлечь их для решения соответствующий аппарат дисциплины | Стандартные (лекционно-семинарские) |
Общенаучная | ОНК-6 | Способность приобретать новые знания с использованием научной методологии и современных образовательных и информационных технологий | Стандартные (лекционно-семинарские) |
Общенаучная | ОНК-7 | Способность порождать новые идеи (креативность) | Стандартные (лекционно-семинарские) |
Инструментальные | ИК-2 | Умение работать на компьютере, навыки использования основных классов прикладного программного обеспечения, работы в компьютерных сетях, составления баз данных | Стандартные (лекционно-семинарские) |
Профессиональные | ПК-1 | Способность демонстрации общенаучных базовых знаний естественных наук, математики и информатики, понимание основных фактов, концепций, принципов теорий, связанных с прикладной математикой и информатикой | Стандартные (лекционно-семинарские) |
Профессиональные | ПК-2 | Способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат | Стандартные (лекционно-семинарские) |
Профессиональные | ПК-4 | Способность критически оценивать собственную квалификацию и её востребованность, переосмысливать накопленный практический опыт, изменять при необходимости вид и характер своей профессиональной деятельности | Стандартные (лекционно-семинарские) |
Профессиональные | ПК-8 | Способность решать задачи производственной и технологической деятельности на профессиональном уровне, включая разработку математических моделей, алгоритмических и программных решений | Стандартные (лекционно-семинарские) |
5 Место дисциплины в структуре образовательной программы
Настоящая дисциплина относится к циклу дисциплин ОПД.00 «Общие профессиональные дисциплины направления» и блоку дисциплин СД.00 «Специальные дисциплины» и является базовой.
Изучение данной дисциплины базируется на следующих дисциплинах:
· Начала математического анализа;
· Геометрия;
· Алгебра;
· Начала информатики.
Для освоения учебной дисциплины, студенты должны владеть следующими знаниями и компетенциями в рамках программы средней школы:
· Знаниями основных определений и теорем перечисленных выше дисциплин;
· Навыками решения типовых задач этих дисциплин.
Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин:
· Математический анализ;
· Линейная алгебра и аналитическая геометрия;
· Теория вероятностей и математическая статистика.
6 Тематический план учебной дисциплины
№ | Название раздела | Всего часов | Аудиторные часы | Самостоятельная работа | ||
Лекции | Семинары | Практические занятия | ||||
1 курс | ||||||
1. | Алгебра высказываний, предикаты и кванторы, логические и булевы функции. | 8 | 2 | 2 | 4 | |
2. | Множества, соответствия, отношения. | 46 | 12 | 10 | 24 | |
3. | Комбинаторика. | 19 | 4 | 5 | 10 | |
4. | Математическая логика (алгебраический подход) | 15 | 4 | 3 | 8 | |
5. | Логика предикатов. Логический вывод в логике предикатов. | 20 | 6 | 4 | 10 | |
Всего часов | 108 | 28 | 24 | 56 | ||
2 курс | ||||||
6. 1 | Теория графов. | 54 | 14 | 14 | 26 | |
7. | Теория алгоритмов. | 38 | 10 | 10 | 18 | |
8. | Теория автоматов. | 16 | 4 | 4 | 8 | |
Всего часов | 108 | 28 | 28 | 52 |
7 Формы контроля знаний студентов
Тип контроля | Форма контроля | 1 год | 2 год | Параметры | ||
3 | 4 | 1 | 2 | |||
Текущий (неделя) | Контрольная работа | 6 | Письменная работа 80 минут | |||
12 | Письменная работа 80 минут | |||||
6 | Письменная работа 80 минут | |||||
12 | Письменная работа 80 минут | |||||
Промежуточный | Зачет | 4 | Письменный зачет | |||
Итоговый | Экзамен | 2 | Письменный экзамен |
7.1 Критерии оценки знаний, навыков
Для прохождения контроля студент должен, как минимум, продемонстрировать знания основных определений и формулировок теорем; умение решать типовые задачи, разобранные на семинарских занятиях.
Оценки по всем формам текущего контроля выставляются по 10-ти балльной шкале.
8 Содержание дисциплины
1. Алгебра высказываний, предикаты и кванторы, логические функции.
Понятие высказывания. Логические операции на высказываниях. Предикаты и кванторы. Булевы (логические) функции и способы их задания. Эквивалентные преобразования логических формул.
Основная литература:
1. Кузнецов математика для инженера, изд. 3. Спб: Лань, 2004. (глава 3)
2. , Максимова по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 2001. (часть 2, пп.1-2.)
Дополнительная литература:
1. Яблонский в дискретную математику. – М. : Наука, 1975. (глава 1)
2. , Сапоженко задач по дискретной математике. М., Наука, 1977. (главы 1, 2)
2. Множества, соответствия, отношения.
Множества - основные понятия. Диаграммы Венна. Операции над множествами: объединение, пересечение, дополнение. Прямое произведение множеств. Соответствия и их свойства. Взаимно-однозначные соответствия. Понятие функции. Обратные функции. Суперпозиции и формулы. Способы задания функций.
Общее понятие отношения. Бинарные отношения и их свойства (рефлексивность, симметричность, транзитивность). Отношение эквивалентности и классы эквивалентности. Отношение толерантности. Отношение порядка. Диаграммы Хассе. Линейный порядок и частичный порядок. Квазипорядок. Рещетки.
Основная литература:
1. Кузнецов математика для инженера, изд. 3. Спб: Лань, 2004.(глава 1)
2. Шрейдер , сходство, порядок. – М.: Наука, 1971. (главы 1-4)
3. , Максимова по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 2001. (часть 1, пп.1-3)
Дополнительная литература:
1. , , Шварц отношения, графы и коллективные решения. - М.: Издательский дом ГУВШЭ, 2006. (глава 3)
3. Комбинаторика.
Предмет комбинаторики. Правило суммы и правило произведения. Принцип включения и исключения. Размещения, перестановки, сочетания без повторений и с повторениями. Биномиальные коэффициенты и соотношения для них. Задачи перечисления. Подсчет числа функций с конечными областями определения. Задача Муавра.
Основная литература:
1. , , Виленкин . М.: ФИМА, МНЦМО, 2006. (главы 1,2)
4. Математическая логика (алгебраический подход).
Алгебраический подход к логике. Функциональная полнота. Булева алгебра и ее законы. Дизъюнктивные и конъюнктивные нормальные формы. Алгебра Жегалкина. Линейные и монотонные функции. Теорема о функциональной полноте. Логические методы синтеза схем.
Основная литература:
1. Кузнецов математика для инженера, изд. 3. Спб: Лань, 2004. (глава 3)
2. , Максимова по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 2001. (часть 2, пп. 1, 2, 4)
Дополнительная литература:
1. , Сапоженко задач по дискретной математике. М., Наука, 1977. (главы 1 и 2)
2. Яблонский в дискретную математику. – М. : Наука, 1975. (глава 1)
5. Логика предикатов. Логический вывод в логике предикатов.
Логика предикатов. Предметная область и предметные переменные. Кванторы общности и существования. Свободные и связанные переменные. Общезначимые и противоречивые формулы. Запись утверждений естественного языка в логике предикатов. Логический вывод в логике предикатов на основе правила резолюции.
Основная литература:
1. Кузнецов математика для инженера, изд. 3. Спб: Лань, 2004. (глава 3)
2. Кузин кибернетики. Том 2. М.: Энергия, 1979. (гл. 15.)
Дополнительная литература:
1. Искусственный интеллект. Методы поиска решений. М.: Мир, 1973. (гл. 6)
5. Теория графов.
Основные определения: неориентированные и ориентированные графы, мультиграфы и кратные ребра. Смежность и инцидентность. Локальные степени вершин. Способы представления графов. Матрицы смежности и инцидентности. Графы и бинарные отношения. Изоморфизм графов. Части графов, суграфы и подграфы.
Пути, циклы, цепи, простые цепи в неориентированных графах. Связность и компоненты связности. Шарниры мосты и блоки графа. Расстояния. Центр, радиус, диаметр графа.
Виды связности в ориентированных графах: сильная связность, односторонняя связность. Задачи о цепях: эйлеровы циклы, гамильтоновы циклы.
Основные числа теории графов: цикломатическое число, хроматическое число. Бихроматические (двудольные) графы. Число внутренней устойчивости. Число внешней устойчивости. Метод Магу для отыскания всех максимальных внутренне устойчивых множеств, а также минимальных внешне устойчивых множеств. Метод Магу для нахождения хроматического числа графа.
Деревья. Алгоритмы нахождения связных суграфов заданного графа с взвешенными ребрами с минимальной стоимостью.
Плоские графы, формула Эйлера, необходимые и достаточные условия того, что граф является плоским (теорема Понтрягина-Куратовского).
Транспортные сети. Потоки в транспортных сетях. Алгоритм Форда-Фалкерсона для нахождения максимального потока. Теорема Форда-Фалкерсона.
Алгоритм Дейкстры поиска наикратчайшего пути на орграфе с взвешенными дугами.
Основная литература:
1. Кузнецов математика для инженера, изд. 3. Спб: Лань, 2004. (глава 4)
2. Введение в прикладную комбинаторику. – М.: Наука, 1975. (глава 3)
3. Теория графов и ее применения. – М.: Изд-во иностранной литературы, 1964. (главы 1, 4, 20-21).
Дополнительная литература:
1. Теория графов. Алгоритмический подход. - М.: Мир, 1978.
2. , , Шварц отношения, графы и коллективные решения. - М.: Издательский дом ГУВШЭ, 2006. (глава 1)
3. Теория графов. - М.: Наука, 1980. (главы 1-4, 13-14)
7. Теория алгоритмов.
Общее понятие алгоритма. Требования к алгоритмам. Емкостная и вычислительная сложность алгоритмов. Понятие рекурсии. Рекурсивные функции. Тезис Черча. Машины Тьюринга. Нормальные алгоритмы Маркова. Алгоритмические неразрешимости. Разрешимые и перечислимые множества. Иерархия неразрешимостей.
Основная литература:
1. Кузнецов математика для инженера, изд. 3. Спб: Лань, 2004. ( глава 5)
2. Алферова алгоритмов. - М.: Издательство статистика, 1973. (глава 1)
Дополнительная литература:
1. , Максимова по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 2001. (часть 3, пп.1-3)
2. Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. (глава 1, глава 3)
8. Конечные автоматы
Понятие конечного автомата Мили и автомата Мура. Примеры применения. Автоматные функции, способы их задания. Теорема о преобразовании периодической последовательности автоматной функцией. Теорема Мура.
Основная литература:
1. Кузнецов математика для инженера, изд. 3. Спб: Лань, 2004. ( глава 6)
9 Оценочные средства для текущего контроля и аттестации студента
9.1 Тематика заданий текущего контроля
Примерные вопросы/ задания для [Укажите название текущего контроля, проводимого в письменной форме - контрольной работы, коллоквиума, домашнего задания]:
1. Вопрос
2.
Тематика [Укажите название текущего контроля - курсовые, эссе или другое] :
1. Тема
2.
Тема [Укажите название текущего контроля - эссе, рефераты или другое] для каждого студента утверждается преподавателем в индивидуальном порядке.
9.2 Вопросы для оценки качества освоения дисциплины
Примерный перечень вопросов к зачету (экзамену) по всему курсу или к каждому промежуточному и итоговому контролю для самопроверки студентов.
9.3 Примеры заданий промежуточного /итогового контроля
По желанию автора программы, приводятся примеры билетов с вопросами и задачами, заданий для зачета или экзамена, тренировочные тесты по дисциплине.
10 Порядок формирования оценок по дисциплине
Оценки за работу на семинарских и практических занятиях преподаватель выставляет в рабочую ведомость. Накопленная оценка по 10-ти балльной шкале за работу на семинарских занятиях определяется перед промежуточным или итоговым контролем - Оаудиторная.
Оценки за самостоятельную работу студента преподаватель выставляет в рабочую ведомость. Накопленная оценка по 10-ти балльной шкале за самостоятельную работу определяется перед промежуточным или итоговым контролем – Осам. работа.
Накопленная оценка за текущий контроль учитывает результаты студента по текущему контролю следующим образом:
Отекущий = 0,6·Оаудиторная + 0,4·Осам. работа .
Способ округления накопленной оценки текущего контроля производится по правилам арифметики округления.
Результирующая оценка за промежуточный контроль в форме зачета выставляется по следующей формуле, где Озачет – оценка за работу непосредственно на зачете:
Опромежуточный = 0,6·Озачет + 0,3·Одз + 0.1·Отекущий .
Способ округления накопленной оценки промежуточного контроля производится по правилам арифметики округления.
Результирующая оценка за итоговый контроль в форме экзамена выставляется по следующей формуле, где Оэкзамен – оценка за работу непосредственно на экзамене:
Оитоговый = 0,5·Оэкзамен + 0,2·Окр1 + 0,2·Окр2 + 0,1· Отекущий.
Способ округления накопленной оценки итогового контроля производится по правилам арифметики округления.
На пересдаче студенту не предоставляется возможность получить дополнительный балл для компенсации оценки за текущий контроль.
В диплом выставляется результирующая оценка по учебной дисциплине, которая формируется по следующей формуле:
Одисциплина = 0,5·Опромежуточный + 0,5·Оитоговый .
Способ округления результирующей оценки по учебной дисциплине производится по правилам арифметики округления.
11 Учебно-методическое и информационное обеспечение дисциплины
11.1 Базовый учебник
1. Кузнецов математика для инженера, изд. 3. Спб: Лань, 2004.
11.2 Основная литература
1. , Максимова по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 2001.
2. Шрейдер , сходство, порядок. – М.: Наука, 1971.
3. , , Виленкин . М.: ФИМА, МНЦМО, 2006.
4. Кузин кибернетики. Том 2. М.: Энергия, 1979.
5. Введение в прикладную комбинаторику. – М.: Наука, 1975.
6. Теория графов и ее применения. – М.: Изд-во иностранной литературы, 1964.
7. Алферова алгоритмов. - М.: Издательство статистика, 1973.
11.3 Дополнительная литература
1. Яблонский в дискретную математику. – М. : Наука, 1975.
2. , , Шварц отношения, графы и коллективные решения. - М.: Издательский дом ГУВШЭ, 2006.
3. Искусственный интеллект. Методы поиска решений. М.: Мир, 1973.
4. Теория графов. Алгоритмический подход. - М.: Мир, 1978.
5. Теория графов. - М.: Наука, 1980.
6. Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
