Реферат: Программа дисциплины «Дискретные математические модели»

Г О С У Д А Р С Т В Е Н Н Ы Й У Н И В Е Р С И Т Е Т
ВЫСШАЯ ШКОЛА ЭКОНОМИКИ
ПЕРМСКИЙ ФИЛИАЛ


ПРОГРАММА ДИСЦИПЛИНЫ

«Дискретные математические модели»


для направления 080100.62 «Экономика»

(вторая ступень высшего профессионального образования)



Утверждена

Учебно-методическим Советом ПФ ГУ-ВШЭ

Председатель___________________________

«_______»__________________________2007 г.


Одобрена на заседании кафедры

прикладной математики

Зав. кафедрой________________ Потапов Д.Б.

«______»__________________________2007 г.




^ Пермь 2008 год



Пояснительная записка




Автор программы: к.ф.-м.н, профессор Иванов Анатолий Прокопьевич.




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

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

Представленный курс «Дискретные математические модели» предназначен для слушателей первого курса дневного отделения направления «Экономики». Истоки дискретной математики уходят в глубь веков. Ее спецификой, как говорит название, является дискретность. В широком смысле она включает в себя как уже сложившиеся дисциплины (теория чисел, алгебра, математическая логика, комбинаторный анализ и др.), так и ряд разделов, которые стали развиваться, начиная со второй половины XX столетия в связи с научно-техническим прогрессом благодаря внедрению ЭВМ. В узком смысле дискретная математика ограничивается только новыми разделами (теория функциональных систем, теория сетей, комбинаторика, теория кодирования, целочисленное программирование, теория игр, конфликтных ситуаций, компьютерная дискретная математика и др.) Дискретная математика является сегодня не только фундаментом математической кибернетики, но и важным звеном математического образования. При изучении курса у студентов должно сложиться представление о ней как богатой и содержательной части естественнонаучного знания. Учебный план представляет данный курс в виде четырех относительно самостоятельных разделов, составляющих основу дискретной математики: элементы теории множеств и отношения, основы математической логики, элементы комбинаторики, введение в теорию графов. Предпочтение чтение курса отдается комбинаторике и теории графов, обладающие внутренней целостностью математических дисциплин. Умение математически описывать дискретные конструкции, строить математические и прикладные дискретные модели и успешно применять их является важной составной частью современного специалиста.

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

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

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

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

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

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


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

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

Основными целями и задачами данного курса являются:

Углубление и расширение общего математического образования

Овладение теоретическими сведениями, соответствующими программе

Развитие практических навыков в области дискретной математики

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

Умение решать несложные задачи из различных разделов изучаемой дисциплины

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

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

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

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

Обладать навыками решения проблем блочно-схемного типа, теоретико-множественных и логических задач.




Формы контроля:

Текущий контроль: согласно графику контрольных мероприятий проводятся тематические контрольные работы в форме теста.

Промежуточный контроль: выполнение минитестов, микроконтролей, самостоятельных работы по тематике семинарского занятия; обсуждение практических ситуаций перед аудиторией. Результирующая оценка промежуточного контроля (баллы за работу на семинарских занятиях) складывается из результатов минитестов, микроконтролей, самостоятельных работы по тематике семинарского занятия; обсуждение практических ситуаций перед аудиторией.

^ Итоговый контроль: по завершению дисциплины проводится письменный зачет в форме теста.

Итоговая оценка: складывается в соответствии с «Положением о рейтинге…», принятом в ПФ ГУ-ВШЭ.




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



^ Раздел 1. Множества и отношения
Основные понятия. Способы задания отношения между множествами. Операции. Законы операций. Применение к решению задач. Отображения их видов. Отношения. Виды. Функции.
^ Раздел 2. Основы математической логики
Высказывания. Их виды. Операции над высказываниями. Свойства. Предикаты их виды. Операции над предикатами. Теоретико-множественный смысл предикатов. Кванторы. Применение языка математической логики.
^ Раздел 3. Элементы комбинаторики
Предмет комбинаторики. Сведения из истории. Классические задачи. Правила суммы и произведения. Упорядоченные и неупорядоченные множества. Соединения без повторения и с повторениями элементов. Свойства. Треугольник Паскаля. Биномиальная теорема. Следствия. Полиномиальная теорема. Следствия. Приложения к решению задач. Методы комбинаторного анализа: полной математической индукции, рекуррентных соотношений; включения и исключения; ветвей и границ; траекторий; производящих функций. Их применения. Конструкции блочно-схемного типа, применение. Понятие об аддитивной и мультипликативной теорией разбиения натуральных чисел. Применение. Сведение о комбинаторных кодах. Приложения комбинаторики.
^ Раздел 4. Элементы теории графов
История формирования теории графов (в топологии, физике, алгебре). Графы определения, виды. Основные понятия. Изоморфизм, полные графы. Степень вершин. Число вершин нечетной степени в конечном графе. Различные представления графов. Пути в графе. Циклы. Связность. Подграфы. Графы-деревья. Висячие (концевые) вершины и ребра дерева. Основное дерево, алгоритм его построения. Кратчайшие пути в графе. Эйлеровы и гамильтоновы пути и циклы в графе. Алгоритм построения. Нахождение кратчайших путей. Применение элементов теории графов: оценка структурных компонент графа; максимальный поток в транспортной сети. Задача о потоке минимальной стоимости, минимальной стоимости и спросе и предложении; о многопродуктовых потоках и др.


III. Учебно-методическое обеспечение дисциплины

Литература

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

Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики М. 2002.

Дискретная математика в заданиях и упражнениях. Части1, 2. / Сост. Малых А.Е. Пермь.: ПФ ГУ ВШЭ, 2003.

Основная:

Москинова Г.И. Дискретная математика М.: Логос, 2002.

Акимов О.Е. Дискретная математика. (Логика, группы, графы). М.: Лаборатория базовых знаний. 2001.

Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. М.: Наука, 1992.

Емеличев В.А., Мельников О.И., Сарванов В.И., Пышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.

Яблонский С.В. Введение в дискретную математику М.: Наука, 2002.

Белоусов А.И., Ткачев С.Б. Дискретная математика. М.: МГТУ им. Баумана, Вып. 19, 2001.

Дополнительная:

Березина Л.Ю. Графы и их применения. М.: Просвещение, 1979.

Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982.

Волков В.А. Элементы теории множеств и развитие понятия числа. Л.: ЛГУ, 1978.

Виленкин Н.Я. Комбинаторика. М.: Наука, 1974.

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

Рыбников К.А. Введение в комбинаторный анализ. М.: МГУ,1972.

Рыбников К.А. Комбинаторный анализ. Задачи и упражнения. М.: Наука, 1982.

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

Форд Л.,Фалкерсан Д. Потоки в сетях. М.: Мир, 1970.




Тематика заданий по различным формам текущего контроля

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

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

Контрольная работа по теме «Множества и отношения. Основы математической логики. Элементы комбинаторики».

^ Перечень вопросов для самоконтроля студентов:

Перечень вопросов для самоконтроля студентов представлен в Приложении 1 «Перечень вопросов для самоконтроля по курсу «Дискретные математические модели».

^ Тематика практических занятий:

Перечень практических занятий с указанием темы, плана семинара, заданиями для работы на семинаре, домашним заданием и списком литературы представлены в Приложении 2 «Планы семинарских занятий по курсу «Дискретные математические модели».


Методические рекомендации преподавателю:

Уделять внимание общим принципам построения курса «Дискретные математические модели» как образца построения научной теории.

Акцентировать внимание на применении методов «Дискретные математические модели» для исследования экономических явлений и систем.

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

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

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




^ Методические указания студентам:

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

проработать конспект лекций;

проанализировать основную и дополнительную литературу, рекомендованную по изучаемому разделу;

изучить решения типовых задач;

решить заданные домашние задания;

при затруднениях сформулировать вопросы к преподавателю.

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




^ Рекомендации по использованию информационных технологий:

Программы Excel, Mathcad и Математика можно использовать для выполнения домашнего задания.


Автор программы _____________________Иванов А.П.


IV. Тематический расчет часов


^ Наименование разделов и тем
Аудиторные часы

Самост. работа

Всего часов

Лекции

практич. занятия

Всего

^ Р.1. Множества и отношения

Множества. Способы задания. Виды. Объединение и пересечение двух множеств. Свойства.

Разность двух множеств. Число элементов, входящих в объединение и разность множеств. Решение задач.

Кортежи. Декартово произведение 2 и нескольких множеств. Граф и график декартова произведения

2

2

4

4

8

^ Р. 2.Основы математической логики

Высказывания, виды. Отрицание, конъюнкция, дизъюнкция. Свойства

Импликация и эквиваленция высказываний. Операции с высказыванием.

Предикаты. Основные понятия. Виды.

Необходимые и достаточные условия. Теоремы. Виды теорем.

4

4

8

8

16

^ Р. 3. Элементы комбинаторики.

Правила суммы и произведений упорядоченные и неупорядоченные множества

Соединение без повторений элементов. Биномиальная теорема.

Соединение с повторениями (размещение, перестановки, сочетания). Полиномная теорема

Методы комбинаторного анализа: полная математическая индукция, включение и исключение.

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

4

4

8

8

16
^ Р.4. Элементы теории графов
Исторические сведения

Графы. Основные понятия. Изоморфизм.

Связность графов. Деревья. Виды. Теоремы. Решения задач.

Эйлеровы и гамильтоновы пути и циклы. Алгоритмы построения.

4

4

8

6

14
Всего
14

14

28

26

54



Автор программы _____________________ А.П. Иванов


Перечень вопросов для самоконтроля

по дисциплине «Дискретные математические модели»


для направления 080100.62 «Экономика»



Множества и отношения. Основные понятия.

Способы задания отношения между множествами.

Операции. Законы операций.

Высказывания. Их виды. Операции над высказываниями. Свойства.

Предикаты их виды. Операции над предикатами. Теоретико-множественный смысл предикатов.

Кванторы. Применение языка математической логики.

Предмет комбинаторики. Сведения из истории. Классические задачи.

Правила суммы и произведения.

Упорядоченные и неупорядоченные множества.

Соединения без повторения и с повторениями элементов. Свойства.

Треугольник Паскаля. Биномиальная теорема. Следствия. Полиномиальная теорема. Следствия.

Методы комбинаторного анализа: полной математической индукции, рекуррентных соотношений; включения и исключения; ветвей и границ; траекторий; производящих функций. Их применения.

Конструкции блочно-схемного типа, применение.

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

Сведение о комбинаторных кодах. Приложения комбинаторики.

История формирования теории графов (в топологии, физике, алгебре).

Графы определения, виды. Основные понятия.

Изоморфизм, полные графы.

Степень вершин. Число вершин нечетной степени в конечном графе.

Различные представления графов.

Пути в графе. Циклы. Связность.

Подграфы.

Графы-деревья. Висячие (концевые) вершины и ребра дерева.

Основное дерево, алгоритм его построения.

Кратчайшие пути в графе. Нахождение кратчайших путей.

Эйлеровы и гамильтоновы пути и циклы в графе. Алгоритм построения.

Применение элементов теории графов: оценка структурных компонент графа; максимальный поток в транспортной сети.

Задача о потоке минимальной стоимости, минимальной стоимости и спросе и предложении; о многопродуктовых потоках и др.



Приложение 2
^ Планы семинарских занятий по дисциплине «Дискретные математические модели»

для направления 080100.62 «Экономика»



Семинар 1


Тема

Способы задания множеств и операции над ними.

Вопросы

Понятие множества, элемента множества. Понятие подмножества.

Виды множеств.

Операции над множествами: пересечение, объединение, разность. Их свойства, основные законы.

Изображение операций над множествами при помощи диаграмм Эйлера-Вена.

Понятие универсального множества.

Умения и навыки

Умение перейти от одного способа задания к другому.

Выполнение операций над множествами.

Изображение результата операций на диаграммах Эйлера-Венна, осуществление доказательства при помощи диаграмм Эйлера-Венна.

Осуществление доказательства путем доказательства двойного включения.

Составление универсального множества по заданному множеству.

Задания для самостоятельного решения

Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. М.: Наука, 1992.

Тема

Декартово произведение множеств. Определение числа элементов для пресечения двух и более множеств.

Вопросы

Определения декартова произведения двух и нескольких множеств.

Табличное задание декартова произведения.

Граф и график декартова произведения.

Формула для определения числа элементов пересечения двух (трех) множеств.

Формула для определения числа элементов разности двух множеств.

Умения и навыки

Умение задать результат выполнения декартова произведения путем перечисления элементов.

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

Определение свойств декартова произведения на примерах.

Сведение содержательных задач к задачам на множества.

Задания для самостоятельного решения

Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. М.: Наука, 1992.




Семинар 2


Тема

Соответствия между множествами, виды отношений. Основные операции алгебры логики.

Вопросы

Определение соответствия между множествами, множества отправления, множества прибытия и графика соответствия.

Обратное соответствие.

Определение отношения.

Виды отношений: симметричное, транзитивное, рефлексивное.

Графы этих отношений.

Отношение эквивалентности.

Свойство антисимметричности.

Понятие высказывания, их виды.

Отрицание, конъюнкция, дизъюнкция. Свойства и таблицы истинности.

Умения и навыки

Задание соответствия между множествами различными способами.

Нахождение обратного соответствия.

Составления отношения по содержательной постановке задачи.

Определения вида отношения.

Содержательная интерпретация сложного высказывания.

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

Задания для самостоятельного решения

Акимов О.Е. Дискретная математика. (Логика, группы, графы). М.: Лаборатория базовых знаний. 2001.

Семинар 3


Тема

^ Основные операции алгебры логики. Применение алгебры логики. Предикаты, операции над предикатами.

Вопросы

Импликация и эквиваленция высказываний. Их выражение через отрицание, конъюнкцию, дизъюнкцию.

Основные законы алгебры логики, законы ди Моргана, законы поглощения.

Понятие тавтологии.

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

Определение предиката.

Виды предикатов.

Операции над предикатами.

Умения и навыки

Составление таблиц истинности для сложных высказывание.

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

Доказательства равенства высказывание путем использование основных эквивалентностей и законов алгебры логики.

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

Составление предикатов, выполнение операций над ними.

Задания для самостоятельного решения

Акимов О.Е. Дискретная математика. (Логика, группы, графы). М.: Лаборатория базовых знаний. 2001.




Семинар 4



Тема

Элементы комбинаторики. Биномиальная теорема.

Вопросы

Правила суммы и произведений.

Перестановки, сочетания и размещения без повторений. Их взаимосвязь.

Перестановки, сочетания и размещения с повторениями.

Основные свойства перестановок, сочетаний и размещений без повторений.

Биномиальная теорема.

Свойства бинома Ньютона, свойства биномиальных коэффициентов.

Треугольник Паскаля.

Формула k-го члена Бинома Ньютона.

Умения и навыки

Сведение содержательных задач к элементам комбинаторики как с повторениями, так и без.

Решение системы уравнений, состоящих из элементов комбинаторики.

Нахождение k-го члена Бинома Ньютона.

Нахождение k-го члена Бинома Ньютона, обладающего определенными свойствами.

Задания для самостоятельного решения

Москинова Г.И. Дискретная математика М.: Логос, 2002.

Тема

Полиномиальная теорема. Метод полной математической индукции.

Вопросы

Полиномиальная теорема.

Полиномиальные коэффициенты.

Метод полной математической индукции.

Умения и навыки

Нахождение разложения степени полинома.

Нахождение полиномиального коэффициента при конкретном члене полинома.

Применение метода полной математической индукции для равенств, неравенств, в тригонометрии.

Задания для самостоятельного решения

Москинова Г.И. Дискретная математика М.: Логос, 2002.

Семинар 5

Тема

Контрольная работа по теме «Элементы комбинаторики»

Вопросы

Представлены в семинарах 1-4

Умения и навыки

Представлены в семинарах 1-4.

Семинар 6


Тема

Основные понятия теории графов.

Вопросы

Понятие графа, множества вершин и множества ребер (дуг).

Виды графов.

Определение инцидентных вершин, изолированных вершин, смежных вершин, степени вершин.

Понятие уникурсальных фигур. Условия уникурсальности Эйлера.

Теорема Эйлера о сумме степеней вершин графа.

Способы задания графов, в том числе матрица инцидентости, матрица смежности.

Понятия полного графа.

Определение графа-дополнение.

Умения и навыки

Умение по графу построить матрицу смежности, матрицу инидентости для неориентированного (ориентированного) графа и обратно.

Определение степеней вершин для неориентированного (ориентированного) графа.

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

Построение различных видов графов.

Построение графа-дополнение.

Задания для работы на семинаре

Приведены в раздаточном материале.

Задания для самостоятельного решения

Емеличев В.А., Мельников О.И., Сарванов В.И., Пышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.

Семинар 7


Тема

Основные понятия теории графов.

Вопросы

Определение пути, цикла, простого пути, цикла.

Определение изоморфизма.

Алгоритм проверки на изоморфизм.

Понятие эйлерова, гамильтова цикла (пути).

Определение дерева, леса.

Умения и навыки

Умение в графе найти все пути, циклы.

Построение всех неизоморфных графов с одинаковым (конкретным) числом вершин.

Определение, является ли два графа изоморфными.

Нахождение эйлерового пути (цикла) в графе.

Нахождение гамильтово пути (цикла) в графе

Составление заданного дерева, леса

Задания для работы на семинаре

Приведены в раздаточном материале.

Задания для самостоятельного решения

Емеличев В.А., Мельников О.И., Сарванов В.И., Пышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.