скачать Г О С У Д А Р С Т В Е Н Н Ы Й У Н И В Е Р С И Т Е Т ВЫСШАЯ ШКОЛА ЭКОНОМИКИ ПЕРМСКИЙ ФИЛИАЛ
ПРОГРАММА ДИСЦИПЛИНЫ «Дискретные математические модели»
для направления 080100.62 «Экономика» (вторая ступень высшего профессионального образования)
Утверждена Учебно-методическим Советом ПФ ГУ-ВШЭ Председатель___________________________ «_______»__________________________2007 г.
| Одобрена на заседании кафедры прикладной математики Зав. кафедрой________________ Потапов Д.Б. «______»__________________________2007 г.
|
^
Пояснительная записка Автор программы: к.ф.-м.н, профессор Иванов Анатолий Прокопьевич. Требования к студентам: курс «Дискретные математические модели» не требует дополнительных знаний, выходящих за рамки программы общеобразовательной средней школы. Аннотация: Основная цель курса – изучение математического аппарата, необходимого при изучении курсов экономического профиля, выполнения курсовых и дипломных работ. Представленный курс «Дискретные математические модели» предназначен для слушателей первого курса дневного отделения направления «Экономики». Истоки дискретной математики уходят в глубь веков. Ее спецификой, как говорит название, является дискретность. В широком смысле она включает в себя как уже сложившиеся дисциплины (теория чисел, алгебра, математическая логика, комбинаторный анализ и др.), так и ряд разделов, которые стали развиваться, начиная со второй половины XX столетия в связи с научно-техническим прогрессом благодаря внедрению ЭВМ. В узком смысле дискретная математика ограничивается только новыми разделами (теория функциональных систем, теория сетей, комбинаторика, теория кодирования, целочисленное программирование, теория игр, конфликтных ситуаций, компьютерная дискретная математика и др.) Дискретная математика является сегодня не только фундаментом математической кибернетики, но и важным звеном математического образования. При изучении курса у студентов должно сложиться представление о ней как богатой и содержательной части естественнонаучного знания. Учебный план представляет данный курс в виде четырех относительно самостоятельных разделов, составляющих основу дискретной математики: элементы теории множеств и отношения, основы математической логики, элементы комбинаторики, введение в теорию графов. Предпочтение чтение курса отдается комбинаторике и теории графов, обладающие внутренней целостностью математических дисциплин. Умение математически описывать дискретные конструкции, строить математические и прикладные дискретные модели и успешно применять их является важной составной частью современного специалиста. Курс предназначен для знакомства студентов с содержанием разделов дискретной математики, привития навыков применения аппарата линейной алгебры для математического моделирования экономических явлений. Данная дисциплина направлена на развитие навыков формализации и организации понятий при создании и изучении математических моделей общих и конкретных социально-экономических явлений, при постановке и решении соответствующих математических задач. Основные виды занятий - лекции и практические занятия. На лекциях студенты изучают содержание разделов дискретной математики, рассматривают наиболее сложные теоретические вопросы. На практических занятия в качестве основных учебных вопросов выносится отработка приемов использования математических методов и привитие навыков применения аппарата дискретной математики для математического моделирования экономических явлений. Успешное освоение материала курса возможно лишь при соответствующем программном и методическом обеспечении. Методическое обеспечение (тексты лекций, презентации лекций, методические пособия для проведения практических занятий) опубликованы в сети университета и доступны для всех студентов и преподавателей. В самостоятельную работу студентов входит освоение теоретического материала, подготовка к практическим занятиям, анализ результатов, полученных на практических занятиях, выполнение заданий преподавателя на самостоятельную работу. Курс является базовым как для изучения других математических дисциплин, так и для более глубокого изучения общих и специальных разделов экономики.
^ материал является базовым для учебных дисциплин, связанных с другими курсами: «Теория вероятностей и математическая статистика», «Методы оптимальных решений», «Теория игр» и др. Основная цель курса – изучение математического аппарата, необходимого при изучении курсов экономического профиля, выполнения курсовых и дипломных работ. Основными целями и задачами данного курса являются: Углубление и расширение общего математического образования Овладение теоретическими сведениями, соответствующими программе Развитие практических навыков в области дискретной математики Создание теоретической и практической базы для дальнейшего изучения смежных дисциплин Умение решать несложные задачи из различных разделов изучаемой дисциплины В результате изучения курса студент должен: Знать основы изученных разделов математики; основные правила и формулы, методы решения задач дискретной математики; Уметь квалифицированно применять полученные знания при решении задач, в том числе имеющих экономическую направленность. Иметь представление о логических и комбинаторных конструкциях, методах решения разных типов задач. Обладать навыками решения проблем блочно-схемного типа, теоретико-множественных и логических задач. Формы контроля: Текущий контроль: согласно графику контрольных мероприятий проводятся тематические контрольные работы в форме теста. Промежуточный контроль: выполнение минитестов, микроконтролей, самостоятельных работы по тематике семинарского занятия; обсуждение практических ситуаций перед аудиторией. Результирующая оценка промежуточного контроля (баллы за работу на семинарских занятиях) складывается из результатов минитестов, микроконтролей, самостоятельных работы по тематике семинарского занятия; обсуждение практических ситуаций перед аудиторией. ^ : по завершению дисциплины проводится письменный зачет в форме теста. Итоговая оценка: складывается в соответствии с «Положением о рейтинге…», принятом в ПФ ГУ-ВШЭ.
Содержание программы ^ Основные понятия. Способы задания отношения между множествами. Операции. Законы операций. Применение к решению задач. Отображения их видов. Отношения. Виды. Функции. ^ Высказывания. Их виды. Операции над высказываниями. Свойства. Предикаты их виды. Операции над предикатами. Теоретико-множественный смысл предикатов. Кванторы. Применение языка математической логики. ^ Предмет комбинаторики. Сведения из истории. Классические задачи. Правила суммы и произведения. Упорядоченные и неупорядоченные множества. Соединения без повторения и с повторениями элементов. Свойства. Треугольник Паскаля. Биномиальная теорема. Следствия. Полиномиальная теорема. Следствия. Приложения к решению задач. Методы комбинаторного анализа: полной математической индукции, рекуррентных соотношений; включения и исключения; ветвей и границ; траекторий; производящих функций. Их применения. Конструкции блочно-схемного типа, применение. Понятие об аддитивной и мультипликативной теорией разбиения натуральных чисел. Применение. Сведение о комбинаторных кодах. Приложения комбинаторики. ^ История формирования теории графов (в топологии, физике, алгебре). Графы определения, виды. Основные понятия. Изоморфизм, полные графы. Степень вершин. Число вершин нечетной степени в конечном графе. Различные представления графов. Пути в графе. Циклы. Связность. Подграфы. Графы-деревья. Висячие (концевые) вершины и ребра дерева. Основное дерево, алгоритм его построения. Кратчайшие пути в графе. Эйлеровы и гамильтоновы пути и циклы в графе. Алгоритм построения. Нахождение кратчайших путей. Применение элементов теории графов: оценка структурных компонент графа; максимальный поток в транспортной сети. Задача о потоке минимальной стоимости, минимальной стоимости и спросе и предложении; о многопродуктовых потоках и др.
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. Тематический расчет часов
^ | Аудиторные часы | Самост. работа | ^ | Лекции | практич. занятия | Всего | ^ Множества. Способы задания. Виды. Объединение и пересечение двух множеств. Свойства. Разность двух множеств. Число элементов, входящих в объединение и разность множеств. Решение задач. Кортежи. Декартово произведение 2 и нескольких множеств. Граф и график декартова произведения | 2 | 2 | 4 | 4 | 8 | ^ Высказывания, виды. Отрицание, конъюнкция, дизъюнкция. Свойства Импликация и эквиваленция высказываний. Операции с высказыванием. Предикаты. Основные понятия. Виды. Необходимые и достаточные условия. Теоремы. Виды теорем. | 4 | 4 | 8 | 8 | 16 | ^ Правила суммы и произведений упорядоченные и неупорядоченные множества Соединение без повторений элементов. Биномиальная теорема. Соединение с повторениями (размещение, перестановки, сочетания). Полиномная теорема Методы комбинаторного анализа: полная математическая индукция, включение и исключение. Аддитивная и мультипликативная теория разбиений конструкции блочно-схемного типа. Приложения комбинаторики. | 4 | 4 | 8 | 8 | 16 | ^ Исторические сведения Графы. Основные понятия. Изоморфизм. Связность графов. Деревья. Виды. Теоремы. Решения задач. Эйлеровы и гамильтоновы пути и циклы. Алгоритмы построения. | 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. |
Добавить документ в свой блог или на сайт
|