Файл: Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики.doc

Международный консорциум «Электронный университет»
Московский государственный университет экономики,

статистики и информатики
Евразийский открытый институт

Э.Л. Балюкевич

Л.Ф. Ковалева

А.Н. Романников


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

Учебно-практическое пособие

М осква 2009

---

С ведения об авторах
Балюкевич Эдуард Людвигович, к.э.н., с.н.с., профессор кафедры прикладной математики МГУЭСИ.
Перечень работ по данной дисциплине, изданных автором:

1. 
   Балюкевич Э.Л. (в соавторстве) Дискретный анализ : учебное пособие. – М. : МЭСИ, 1980. 5,5 п/л.
   
2. 
   Балюкевич Э.Л. Математические методы в проектировании АСУ. – М. : МЭСИ, 1984, 3 п/л.
   
3. 
   Балюкевич Э.Л. (в соавторстве) Сборник задач по курсу «Дискретный анализ» : учебное пособие. – М. : МЭСИ, 1987, 4,1 п/л.
   
4. 
   Балюкевич Э.Л. (в соавторстве) Методические указания к выполнению курсовой работы по курсу «Дискретный анализ». – М. : МЭСИ, 1991, 1 п/л.
   
5. 
   Балюкевич Э.Л. (в соавторстве) Дискретная математика : учебное пособие. – М. : МГУЭСИ, 2003. 16 п/л.
   
6. 
   Балюкевич Э.Л. Учебно-практическое пособие. – М. : МГУЭСИ, 2009, 10 п/л (электронная версия).
   

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

1. 
   Ковалева, Л.Ф. Дискретная математика. – ч. I. – М. : МЭСИ, 2000 (электронное).
   
2. 
   Ковалева, Л.Ф. (в соавторстве). Дискретная математика. – М. : МЭСИ, 1988.
   
3. 
   Ковалева, Л.Ф. Применение дискретной математики в экономических задачах. – М. : МЭСИ, 1979.
   
4. 
   Ковалева, Л.Ф. (в соавторстве). Применение теории графов в экономических задачах. – М. : МЭСИ, 1977.
   
5. 
   Ковалева, Л.Ф. Математическая логика и теория графов. – ч. I, II. – М. : МЭСИ, 1976, 1977.
   
6. 
   Ковалева, Л.Ф. (в соавторстве) Дискретный анализ. – М. : МЭСИ, 1980.
   
7. 
   Ковалева, Л.Ф. Методические указания и контрольные работы по курсу «Дискретная математика» (специальность – «информатика», заочная форма обучения). – М. : МЭСИ, 1998.
   
8. 
   Ковалева, Л.Ф Методические указания по изучению курса «Дискретная математика» с упражнениями. Задачник. – М. : МЭСИ, 1986.
   
9. 
   Ковалева, Л.Ф. (в соавторстве). Методические указания и контрольные задания по курсу «Дискретный анализ» для студентов заочного обучения, специальность – экономическая кибернетика. – М. : МЭСИ, 1992.
   
10. 
    Ковалева, Л.Ф. (в соавторстве). Методические указания по изучению курса «Дискретная математика» (с упражнениями), специальность прикладная математика, АСУ. – М. : МЭСИ, 1986.
    
11. 
    Ковалева, Л.Ф. (в соавторстве). Методические указания по изучению курса «Дискретный анализ» для студентов заочной формы обучения, специальность - механизированная обработка экономической информации. – М. : МЭСИ, 1987.
    
12. 
    Ковалева, Л.Ф. (в соавторстве). Методические указания к выполнению курсовой работы.
    

---

а) по курсу «Дискретный анализ» для студентов специальности – экономическая кибернетика и АСУ (0715). – М. : МЭСИ, 1991, 1989.

б) по курсу «Дискретная математика» для студентов специальности – прикладная математика (0102). – М. : МЭСИ, 1989.
Цели и задачи дисциплины и её место
в учебном процессе
«Дискретная математика» является математической основой курсов, изучающих современные прикладные экономико-математические методы.

Целью изучения данной дисциплины является прочное усвоение студентами теоретических основ дискретной математики, составляющих фундамент ряда математических дисциплин и дисциплин прикладного характера. Содержание курса «Дискретной математики» используется в курсах: «Теория систем и системный анализ», «Информатика и программирование», «Теория вероятностей и математическая статистика», «Исследование операций и методы оптимизации», «Математическое и имитационное моделирование», «Управление проектом».
Задачей дисциплины является формирование у обучающихся следующих компетенций:

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

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

Знать:

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

Уметь:

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

Владеть:

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

---

Форма активных методов обучения:

использование учебно-методических комплексов и информационно-компьютерных образовательных технологий, включающих оценочные средства для текущего контроля успеваемости и промежуточной аттестации, разработанных в Московском Государственном Университете Экономики, Статистики и Информатики.
Список дисциплин, знание которых необходимо для изучения дискретной математики:

1. 
   Курс школьной математики.
   

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

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

Данное пособие не претендует на исчерпывающую полноту и абсолютную строгость изложенного материала.

Т ема 1.

---

Множества

1.1. Операции над множествами.
Мощность множеств.
Отображение множеств

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

Объекты, объединенные одним общим свойством, называют элементами множества и обозначают a, b, c, ... x, y, z. Множества обозначают A, B, C, ... X, Y, Z. Запись a A означает, что элемент «a» принадлежит множеству А, bA означает, что элемент «b» не принадлежит множеству А.

Множество, число элементов которого конечно, называют конечным и бесконечным в противном случае.

Бесконечные множества разделяются на счетные и несчетные. Если элементы бесконечного множества можно пронумеровать с помощью натурального ряда чисел, то оно называется счетным и несчетным в противном случае. Так, множество четных чисел – счетное, множество действительных чисел – несчетное.

Бесконечные и счетные множества называются дискретными множествами.

Дискретная математика – математика дискретных множеств.

Если каждый элемент множества А есть вместе с тем элемент множества В, то множество А называется частью, или подмножеством множества В и обозначается А  В.

Если А  В и В  А, то множества А и В называются равносильными и обозначаются А=В.

Множество, не содержащее ни одного элемента, называется пустым и обозначается V, . Пустое множество считают конечным множеством и подмножеством любого множества.

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

Пусть А={а₁, а₂, а₃}. Подмножества {а₁, а₂, а₃} и V – несобственные подмножества А. Собственные: {а₁}, {а₂}, {а₃}, {а₁, а₂}, {а₁, а₃}, {а₂, а₃}.

Число подмножеств любого конечного множества, содержащего «n» элементов, равно 2ⁿ.

Множество всех элементов, которые могут встретиться в данном исследовании, называют универсальным и обозначают «U».

На множествах определены следующие операции.

Объединением, или суммой множеств А и В называется множество С, элементы которого принадлежат хотя бы одному из множеств А или В.

---