Высшая школа экономики



Скачать 178.11 Kb.
Дата11.10.2012
Размер178.11 Kb.
ТипПрограмма дисциплины
Министерство экономического Министерство образования

развития и торговли Российской Федерации

Российской Федерации

Государственный университет -

Высшая школа экономики




Факультет Экономики




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



ДИСКРЕТНАЯ МАТЕМАТИКА
для направления 080500.62 – «Бизнес-информатика» подготовки бакалавра

Авторы программы: д.т.н., профессор О.П.Кузнецов,

к.т.н., доцент В.А.Кохов

Рекомендована секцией УМС Одобрена на заседании

Математические и статистические кафедры высшей математики


методы в экономике на факультете экономики
Председатель Зав. кафедрой

__________А.С.Шведов __________Ф.Т.Алескеров

“___” __________ 200_ г. “___” _____ _____ 200_ г.

Утверждена УС факультета

экономики


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

________________________

“___” __________ 200_ г.

Москва

Требования к студентам: Изучение курса «Дискретная математика» не требует предварительных знаний, выходящих за пределы программ общеобразовательной средней школы.

Аннотация курса:

Дискретная математика - одна из важнейших составляющих современной математики. С одной стороны, она включает фундаментальные основы математики - теорию множеств, математическую логику, теорию алгоритмов; с другой стороны, является основным математическим аппаратом информатики и вычислительной техники и потому служит базой для многочисленных приложений в экономике, технике, социальной сфере. В отличие от традиционной математики (математического анализа, линейной алгебры и др.), методы и конструкции которой имеют в основном числовую интерпретацию, дискретная математика имеет дело с объектами нечисловой природы: множествами, логическими высказываниями, алгоритмами, графами. Благодаря этому обстоятельству дискретная математика впервые позволила распространить математические методы на сферы и задачи, которые ранее были далеки от математики. Примером могут служить методы моделирования различных социальных и экономических процессов.

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


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

Учебные задачи курса.

В результате изучения курса «Дискретная математика» студенты должны

  • иметь представление о теоретических основах современных дискретных моделей и об областях их практического приложения;

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

  • демонстрировать знание и понимание основных определений, теорем, алгоритмов и методов решения задач;

  • уметь строить логически выверенные рассуждения;

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

  • обладать навыками самостоятельной работы и умением находить и перерабатывать дополнительную информацию в данной предметной области;

  • иметь представление о теоретических основах современных информационных технологий.


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


п/п

Название темы

(с разбивкой по модулям)

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

Контр. работы

Самост. занятия

Всего часов







Лек-ции

Семи-нары

Всего










Первый модуль (28 часов)

1

Множества, функции, отношения

6

6

12




12

24

2

Комбинаторика

4

4

8




12

20

3

Элементы общей алгебры

4

4

8




8

16

Второй модуль (32 часа)

4

Математическая логика

(алгебраический подход)

4

4

8

2

8

18

5

Теория графов

12

12

24




27

51

Третий модуль (28 часов)

6

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

8

8

16

2

16

34

7

Математическая логика

(аксиоматический подход)

4

4

8




10

18

8

Формальные системы

2

2

4




4

8




Итого

44

44

88




101

189


Содержание программы

Тема 1. Множества, функции, отношения.

Множества - основные понятия. Диаграммы Венна. Операции над множествами: объединение, пересечение, дополнение. Векторы, их проекции. Прямое произведение множеств.

Соответствия и их свойства. Взаимно-однозначные соответствия. Мощности бесконечных множеств. Понятие функции. Обратные функции. Суперпозиции и формулы. Способы задания функций.

Общее понятие отношения. Бинарные отношения и их свойства. Отношение эквивалентности и классы эквивалентности. Отношение порядка. Линейный и частичный порядок. Диаграммы Хассе. Лексикографический порядок. Ранжирование и проблема выбора. Отношения и реляционные базы данных.

Литература:

  1. Базовый учебник: [1] (гл.1).

  2. Дополнительная литература: [3] (гл.3), [19] (гл.1), [9] (гл. 1).

Тема 2. Комбинаторика.

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

Литература:

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

  2. Дополнительная литература: [19] (гл.5), [13] (гл.1), [8] (гл.3), [7] (гл.1,2), [16] (гл.1).

Тема 3. Элементы общей алгебры.

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

Литература:

  1. Базовый учебник: [1] (гл.2).

  2. Дополнительная литература: [19] (гл.2).

Тема 4. Математическая логика (алгебраический подход).


Основные понятия логики: высказывания и рассуждения. Основные логические связки. Алгебра высказываний. Логические функции и способы их задания - таблицы и формулы. Алгебраический подход к логике. Функциональная полнота. Булева алгебра и ее законы. Дизъюнктивные и конъюнктивные нормальные формы. Алгебра Жегалкина. Линейные и монотонные функции. Теорема о функциональной полноте.

Логика предикатов. Предметная область и предметные переменные. Кванторы общности и существования. Свободные и связанные переменные. Эквивалентные соотношения в логике предикатов. Общезначимые и противоречивые формулы. Запись утверждений естественного языка в логике предикатов.

Литература:

  1. Базовый учебник: [1] (гл.3).

  2. Дополнительная литература: [19] (гл.3), [8] (гл.1), [9] (гл.2).

Тема 5. Теория графов.

Основные определения: неориентированные и ориентированные графы, мультиграфы и кратные ребра. Смежность и инцидентность. Способы представления графов. Матрица смежности. Графы и бинарные отношения. Изоморфизм графов. Клики, устойчивость, покрытия и паросочетания.

Пути, циклы, цепи, простые цепи в неориентированных графах. Связность и компоненты связности. Расстояния. Центр, радиус, диаметр графа. Обходы графов.

Симметрия графов. Графы и их группы автоморфизмов.

Сравнительный анализ графов. Сложность и сходство графов.

Виды связности в ориентированных графах: сильная связность, односторонняя связность. Ациклические графы и топологическая сортировка. Конденсация.

Матрицы графов и операции над ними.

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

Деревья и их свойства. Цикломатическое число. Приложения деревьев: иерархии, классификации. Обходы деревьев.

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

Литература:

  1. Базовый учебник: [1] (гл.4).

  1. Дополнительная литература: [19] (гл.7), [3] (гл.7), [9] (гл. 3), [2] (гл.6,7), [13] (гл.1), [16] (гл.2-4).

Тема 6. Теория алгоритмов.

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

Конечные автоматы. Основные определения. Примеры автоматных алгоритмов. Эквивалентность автоматов. Логические автоматы и логические схемы. Программная реализация автоматных алгоритмов.

Сети Петри и примеры их использования.

Литература:

  1. Базовый учебник: [1] (гл. 5, 8).

  2. Дополнительная литература: [19] (гл.7), [8] (гл.7,8), [18] (гл.6,7,10).

Тема 7. Математическая логика (аксиоматический подход).

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

Литература:

  1. Базовый учебник: [1] (гл.5).

  2. Дополнительная литература: [19] (гл.3,4).

Тема 8. Формальные системы.

Общие понятия о формальных системах и методах формализации. Понятие вывода в формальной системе.

Литература:

  1. Базовый учебник: [1] (гл.6).

  2. Дополнительная литература: [19] (гл. 4), [8] (гл.4).


Литература

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

Кузнецов О.П. Дискретная математика для инженера, изд. 3. Спб: Лань, 2004.
Дополнительная литература

  1. Алгоритмы и программы решения задач на графах и сетях //Нечепуренко М.И., Попков В.К., Кохов В.А. и др. Новосибирск: Наука, 1990.

  2. Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А. Бинарные отношения, графы и

коллективные решения. – М.: Издательский дом ГУ ВШЭ, 2006.

  1. Басакер Р., Саати Т. Конечные графы и сети, М.: Наука,1974.

  2. Берж К. Теория графов и ее приложения, М.:, ИЛ,1962.

  3. Биркгоф Г. Теория решеток, М.: Наука, 1984.

  4. Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. М.: ФИМА, МЦНМО, 2006.

  5. Галушкина Ю.И., Марьямов А.Н. Конспект лекций по дискретной математике. М. Айрис пресс, 2007.

  6. Горбатов В.А. Фундаментальные основы дискретной математики. – М.: Наука. Физматлит, 1999.

  7. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. М.: Лаборатория базовых знаний, 2003.

  8. Кофман А. Введение в прикладную комбинаторику, Москва, Наука, 1975.

  9. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. БХВ-Петербург, 2003.

  10. Кохов В.А. Концептуальные и математические модели сложности графов. М.: Издательство МЭИ, 2002.

  11. Кохов В.А., Ткаченко С.В. Решатель базовых задач структурной информатики. М.: Издательство МЭИ, 2006.

  12. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 2001.

  13. Липский В. Комбинаторика для программистов. М.: Мир, 1988.

  14. Мендельсон Э. В. Ведение в математическую логику, М.: Наука, 1984.

  15. Минский М. Вычисления и автоматы. М. Мир, 1971.

  16. Новиков Ф.А. Дискретная математика для программистов. изд. 3. СПб.: Питер, 2008.

  17. О.Оре. Теория графов. М., Наука, 1968.

  18. Робертс Ф. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М., Наука, 1986.

  19. Столл Р. Множество, логика, аксиоматические теории, М.: Просвещение, 1968.

  20. Харари Ф. Теория графов, М.: Мир, 1973.

  21. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений., 2-е изд., : Пер. с англ. - М.: Издательский дом "Вильямс", 2002.

  22. Черч А. Введение в математическую логику, М.: Изд-во иностр.лит., 1961.

  23. Шрейдер Ю.А. Равенство, сходство, порядок, М.: Наука, 1971.



Формы контроля. Формирование итоговой оценки
Итоговый контроль - экзамен в конце курса.

Промежуточный контроль - дифференцированный зачет в конце второго модуля.

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

Итоговая оценка складывается из следующих элементов:

  • работа на семинарах;

  • 2 письменные аудиторные контрольные работы (290 мин);

  • домашнее задание;

  • письменный дифференцированный зачет (90 мин);

  • письменный экзамен (180 мин).

Итоговая оценка по 10-балльной шкале формируется как взвешенная сумма:



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

Таблица соответствия оценок по десятибалльной и пятибалльной системам


По десятибалльной шкале

По пятибалльной шкале

  1. очень плохо

  2. плохо

  3. неудовлетворительно


неудовлетворительно - 2

  1. удовлетворительно

  2. весьма удовлетворительно

удовлетворительно - 3


  1. хорошо

  2. очень хорошо

хорошо - 4


  1. почти отлично

  2. отлично

  3. блестяще

отлично - 5


Типовой вариант контрольной работы 1

(темы 1 – 3 программы)

  1. Упростите выражение: .

  2. Докажите, что .

  3. Пусть множество M содержит 3 элемента, а N  4. Сколько существует функций из в N?

  4. Верно ли что, если бинарное отношение P транзитивно, то транзитивно?

  5. Сколько слов получится при перестановке букв в слове ГИПЕРБОЛА, если слова должны начинаться и заканчиваться гласной буквой?

  6. Сколькими способами можно разместить 8 различных пакетов акций в трех банках, если первые два банка приобретают по 3 пакета акций, а третий банк приобретает 2 пакета акций?

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

  8. Постройте 2 пары орграфов, одна из которых эквивалентна по числу циклов длины 3 и 4, а другая не эквивалентна по числу циклов длины 3 и 4.

  9. Приведите пример орграфа с числом вершин не менее 6, задающего симметричное, транзитивное, но не рефлексивное бинарное отношение?

  10. Приведите пример характеристики вершины графа, на основе которой можно построить разбиение множества вершин на подмножества множества вершин. Являются ли данные подмножества классами эквивалентности вершин? Обоснуйте ответ.


Каждый вопрос оценивается в зависимости оп полноты ответа как 0.25 или 0.4 или 1 балл.
Типовой вариант контрольной работы 2

(темы 4 – 5 программы)


  1. Приведите определение эйлерова цикла в графе и постройте регулярный граф степени 4, эйлерова цикла не имеющий.

  2. Сформулируйте критерий планарности графа (теорема Понтрягина-Куратовского) и постройте 2 регулярных графа степени 3, один из которых планарен, а другой нет.

  3. Рассмотрим логическую функцию от 4 переменных, истинную, если истинны ровно 0, 1 или 3 переменные.

  4. Верно ли, что два следующих графа изоморфны?



  1. Приведите определение ядра графа и найдите все ядра в графе, заданном списком ребер: . Используйте метод МАГУ.

  2. Найдите диаметр, радиус и центры дерева, заданного списком ребер: (1,2),(2,5), (3,4),(3,6),(5,6),(5,7),(7,8),(7,11),(9,10),(10,11),(10,13),(11,12),(11,14),(12,15),(13,16),(16,17).

  3. Граф представляет G собой несвязное объединение графов K1, K3, K5. Существует ли в дополнительном графе эйлеров цикл? А гамильтонов цикл?

  4. Опишите все симметрии графа, заданного списком ребер: . Определите число элементов в стабилизаторе вершины .

  5. Вычислите значение индекса сложности для графа в п.8.

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


Каждый вопрос оценивается в зависимости оп полноты ответа как 0.2 или 0.3 или 0.8 балла.
Типовой вариант экзаменационной работы

(темы 1 – 8 программы)


  1. Какие функции называются примитивно-рекурсивными? Докажите, что примитивно-рекурсивна.

  2. Дайте определение неориентированного дерева. Приведите пример дерева с 6 листьями и 2 вершинами степени 3.

  3. Докажите, что тогда и только тогда, когда для любого множества С .

  4. Из двух математиков и десяти экономистов надо составить комиссию из 8 человек. Сколькими способами можно составить комиссию, если в нее должен входить хотя бы один математик?

  5. Докажите, что связное и ацикличное бинарное отношение есть линейный порядок.

  6. Сколькими способами можно написать в ряд цифры от 0 до 9 так, чтобы четные цифры шли в порядке возрастания, а нечетные – в порядке убывания?

  7. Постойте минимальный автомат со входным алфавитом распознающий слова, содержащие хотя бы одну букву ровно один раз.

  8. Постройте минимальный автомат, эквивалентный данному.




    0

    1

    2

    1

    4,1

    6,0

    1,0

    2

    2,0

    2,0

    6,1

    3

    4,1

    2,0

    3,0

    4

    4,1

    3,0

    3,0

    5

    6,0

    6,0

    5,1

    6

    5,0

    6,0

    2,1

  9. В дереве 10 вершин степени 3 и нет вершин больших степеней. Сколько в этом дереве листьев?

  10. Найдите все ядра в графе, заданном списком ребер: .

  11. Сформулируйте задачу ВЕРШИННОЕ ПОКРЫТИЕ в форме задачи распознавания свойств и приведите определение ВРЕМЕННОЙ СЛОЖНОСТИ АЛГОРИТМА.

  12. Приведите определение для следующих понятий: а) группа автоморфизмов вершин графа; б) ассоциативное исчисление.


Каждый вопрос оценивается от 0,25 до 0,8 балла.
Вопросы для оценки качества освоения дисциплины

  1. Может ли отношение эквивалентности быть одновременно и отношением порядка?

  2. Может ли быть покрытие множества элементов разбиением этого множества?

  3. Как доказать, что множество рациональных чисел счетно?

  4. Каковы свойства графов, представляющих отношения эквивалентности.

  5. Что такое диаграммы Хассе и к какому виду относятся их графы?

  6. Каково число различных функций типа АВ3С, если А= 3, В= 4, С= 2?

  7. Какова мощность множества логических функций 5 переменных, которые принимают значение 1 только на тех наборах значений переменных (но необязательно на всех), которые содержат ровно 2 единицы?

  8. Обоснуйте справедливость утверждения о том, что алгебра подмножеств по двуместным операциям È, Ç не является кольцом.

  9. Приведите определение понятия изоморфизм групп?

  10. Приведите пример графа с группой автоморфизмов, изоморфной тождественной группе.

  11. Приведите пример графа с группой автоморфизмов, изоморфной симметрической группе.

  12. Может ли радиус графа равняться его диаметру?

  13. Приведите формализованную постановку задачи определения изоморфизма двух графов.

  14. Приведите формализованное определение понятия инвариант графа. Приведите примеры инвариантов.

  15. Является ли задача распознавания изоморфизма двух графов алгоритмически разрешимой задачей?

  16. Является ли система кратчайших цепей в связном графе метрическим пространством? Приведите обоснование.

  17. Какие виды связности возможны в ориентированных графах?

  18. Приведите пример регулярного графа, вершинная связность которого меньше степени вершины.

  19. Приведите пример регулярного графа, реберная связность которого меньше степени вершины.

  20. Можно ли представить неориентированное дерево в виде двудольного графа?

  21. Какими методами можно определить сходство графов?

  22. Как найти все ядра в графе без циклов?

  23. Какими методами можно вычислить сложность графов?

  24. Может ли разрешимое множество не быть перечислимым?

  25. Можно ли автомат Мили представить автоматом Мура?

  26. Что такое вывод в формальной системе?

  27. Каким формальным языкам соответствуют автоматы?

  28. Возможен ли полиномиальный алгоритм для NP-полной задачи?

  29. Приведите формализованную постановку задачи «изоморфизм подграфу» в форме задач теории вычислительной сложности задач.

  30. Что такое сбалансированный знаковый граф? Приведите примеры.

Авторы программы: О.П. Кузнецов,

В.А. Кохов

О.П. Кузнецов, В.А. Кохов, 2008

Похожие:

Высшая школа экономики iconВысшая школа юриспруденции Национального исследовательского университета «Высшая школа экономики» (ниу вшэ)
Высшая школа юриспруденции Национального исследовательского университета «Высшая школа экономики» (ниу вшэ) (Учредитель: Правительство...
Высшая школа экономики icon«высшая школа экономики»
Категория слушателей: студенты Национального исследовательского университета "Высшая школа экономики", студенты других вузов
Высшая школа экономики iconНоминация 'Великая Держава'
Государственного университета Высшая школа экономики; Соколов Павел Сергеевич, студент 4 курса Государственного университета Высшая...
Высшая школа экономики iconБакалавриат: Высшая школа экономики (год окончания: 2008, специальность: Менеджмент)
Магистратура: Высшая школа экономики (год окончания: 2010, специальность: Менеджмент)
Высшая школа экономики icon«Высшая школа экономики»
...
Высшая школа экономики iconГиппиус алексей Алексеевич Ведущий научный сотрудник Лаборатории лингвосемиотических исследований Национального исследовательского университета «Высшая школа экономики»
Ведущий научный сотрудник Лаборатории лингвосемиотических исследований Национального исследовательского университета «Высшая школа...
Высшая школа экономики iconВысшая школа экономики

Высшая школа экономики iconР. М. Нуреева; Гос ун-т Высшая школа экономики. М.: Изд дом гу вшэ, 2006. 406, [2] с. (Экономическая теория: традиции и современ­ность). Свед об авт.: с. 400-401. Content: с. 402-406. 1000 экз Сборник
Карла Поланьи: прошлое, настоящее, будущее [Текст] / под общ ред проф. Р. М. Нуреева; Гос ун-т — Высшая школа экономики. — М.: Изд...
Высшая школа экономики iconО востребованности публикаций исследователей
Нестеров А. В. профессор Национального исследовательского университета Высшая школа экономики
Высшая школа экономики iconЭксперт это … (Препринт июль, 2012)
Нестеров А. В., профессор Национального Исследовательского Университета Высшая Школа Экономики
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org