|
|
УПП_Дискретная математика-1. Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики
Александров, П.С. Введение в теорию множеств и теорию функций. – М. : Наука, 1977
Балюкевич, Э.Л., Ковалева Л.Ф. Математическая логика и теория алгоритмов : учебное пособие. – М. : МГУЭСИ, 2007.
Гаврилов, Г.П., Сапоженко, А.А. Задачи и упражнения по курсу «Дискретная математика». – М. : Наука, 1992
Грей, П. Логика, алгебра и базы данных. – М. : Машиностроение, 1989
Гиндикин, С.Г. Алгебра логики в задачах. – М. : Наука, 1972.
Ерусалимский, Я.М. Дискретная математика. – М. : Вузовская книга, 2000.
Колмогоров, А.Н., Фомин, С.В. Элементы теории функций и функционального анализа. – М. : Наука, 1989
Клини С. Математическая логика. – М. : Мир, 1973.
Ковалева, Л.Ф., Данков, О.Ю., Горбовцов Г.Я., Мокеева И.К. Дискретная математика. – М. : МЭСИ, 1988.
Нефедов, В.Н., Осипова В.А. Курс дискретной математики. – М. : МАИ, 1992.
Новиков, Н. С. Элементы математической логики. – М. : Наука, 1973.
Под редакцией Скорнякова Л.А. Общая алгебра. II. – М. : Наука, 1990г.
Эдельман, С.Л. Математическая логика. – М. : Высшая школа, 1975.
Яблонский, С.В. Введение в дискретную математику. – М. : Наука, 1979.
Интернет-ресурсы
www.osp.mesi.ru (сайт учебного процесса МЭСИ). Балюкевич Э.Л., Ковалева Л.Ф., Романников А.Н. Дискретная математика.
www.booka.ru/booka_topic_6114?id=97427 Дискретная математика. Курс лекций.
Р уководство по изучению дисциплины
Содержание основных тем.
Множества
1.1. Операции над множествами. Мощность множеств. Отображение множеств.
1.2. Отношения на множествах.
Математическая логика.
2.1. Алгебра высказываний.
2.2. Проблема разрешимости. Нормальные формы.
2.3. Исчисление высказываний.
2.4. Логика предикатов.
Теория графов.
3.1. Графы.
3.2. Деревья.
3.3. Экстремальные задачи на графах.
Тема 1. Множества
При изучении данной темы следует обратить внимание на то, что понятие «множество» является одним из основных во всех математических дисциплинах. Это можно проиллюстрировать большим количеством примеров как из школьной так и из вузовской – высшей математики.
Изучая понятие мощности множества, основные теоремы о счетных множествах, нужно подчеркнуть, что «количество элементов» в бесконечном множестве может быть различным, что дискретные множества – это конечные и счетные множества, дискретная математика – математика дискретных величин, в отличие от математики непрерывных величин.
Изучив данную тему студент должен:
основные понятия теории множеств, понятие мощности множества, операции над множествами, как частный случай алгебры Буля, декартово произведение множеств, отображение множеств, типы отображений, отношения на множествах, специальные бинарные отношения.
иллюстрировать основные понятия примерами из различных математических прикладных дисциплин.
План практических занятий по теме 1.
Алгебра Буля. Операции над множествами (иллюстрация операций диаграммами). Основные равносильные формулы. Преобразования формул.
Эквивалентные множества. Мощность множества. Сравнение мощностей множеств.
Прямое произведение множеств. Отображение множеств. Типы отображений.
Отношения на множествах. Бинарные отношения, свойства отношений. Специальные бинарные отношения.
Рекомендации по выполнению конкретных заданий, вопросы и тесты для самопроверки содержатся в учебно-практическом пособии «Дискретная математика». – М. : МГУЭСИ, 2009 (авторы Э.Л. Балюкевич, Л.Ф. Ковалёва, А.Н. Романников). /Литература 1/
Тема 2. Математическая логика
При изучении данной темы следует обратить внимание на то, что алгебра высказываний является частным примером булевой алгебры и провести аналогию между логическими и теоретико-множественными операциями.
Следует изучить основные логические операции (связки), понятие полной системы связок, понятие формулы алгебры, высказываний, основные равносильные формулы. Показать, как высказываниям в естественном и математическом языке могут быть поставлены в соответствие логические формулы. Рассмотреть основное понятие – понятие логической функции и уяснить связь между формулами и функциями алгебры высказываний. Изучить логические отношения между высказываниями (отношение следования, отношение эквивалентности и отношение несовместимости), а также способы проверки правильности рассуждений.
Рассмотреть, как проблема определения типа формулы (проблема разрешимости) может быть решена с помощью приведения формулы к нормальным формам (НФ) и определить конструктивно понятие совершенной нормальной формы формулы алгебры высказываний (СНФ).
Изучить построение формулы алгебры высказываний по заданной функции.
Выяснить возможность моделирования формул алгебры высказываний релейно-контактными схемами, а также какие задачи при этом могут быть решены.
Рассмотреть формальную аксиоматическую систему, адекватную алгебре высказываний – исчисление высказываний; основные проблемы формальной логической системы, как они решаются и как она может быть применена к конкретной научной области.
Далее изучается логика предикатов, которая включает в себя алгебру высказываний как составную часть. Рассматриваются операции над предикатами, кванторы общности и существования, применение кванторов в математических науках.
Изучив данную тему студент должен:
все понятия, перечисленные выше, связанные с ними свойства, соотношения, теоремы;
рассматриваемые в теории проблемы и способы их решения.
применять язык, методы и средства математической логики в математических дисциплинах и в прикладных дисциплинах.
Планы практических занятий по теме 2
Логические операции. Формулы алгебры высказываний. Равносильность формул. Полные системы связок.
Логические функции. Связь с формулами алгебры высказываний. Существенные и фиктивные переменные.
Логические отношения. Проверка правильности рассуждений.
Нормальные формы алгебры высказываний. Установление типа формулы.
Совершенные нормальные формы. Построение формулы алгебры высказываний по заданной функции.
Алгебра высказываний и релейно-контактные схемы. Упрощение схем.
Исчисление высказываний: алфавит, формулы, аксиомы, правила вывода. Проблемы непротиворечивости, полноты и независимости системы аксиом.
Логика предикатов. Операции над предикатами. Кванторы.
Рекомендации по выполнению конкретных заданий, вопросы и тесты для самопроверки содержатся в учебно-практи-ческих пособиях:
Дискретная математика. – М. : МГУЭСИ, 2009. (Авторы Э.Л. Балюкевич, Л.Ф. Ковалёва, А.Н. Романников.) / Литература 1 /
Математическая логика и теория алгоритмов. – М. : МГУЭСИ, 2009. (Гриф УМО Минобрнауки РФ.) (Авторы Э.Л. Балюкевич, Л.Ф. Ковалёва.) / Литература 2 /
Тема 3. Теория графов
В этой теме рассматриваются основные понятия, связанные с конечными графами.
Даются определения ориентированных и неориентированных графов, способы их задания и представления. Рассматриваются теоремы, связанные с путями на графе, понятия связности, изоморфизма и планирности графов. Изучаются числа, характеризующие граф: цикломатическое, хроматическое число, числа внутренней и внешней устойчивости.
Далее излагаются операции над графами: объединение, пересечение, прямое произведение графов. Рассматриваются матрицы для графов и выполнение с помощью матриц смежности основных операций над графами.
Значительная часть темы рассматривает графы типа – дерево. Необходимо изучить свойства деревьев, теоремы о них. Рассматривается задача нахождения кратчайшего дерева и её экономическая интерпретация. Для отыскания кратчайшего дерева используется алгоритм Краскала.
Отдельный раздел посвящен некоторым экстремальным задачам на графах: нахождению путей минимальной и максимальной длины на графе. Дается экономическая интерпретация каждой из этих задач. Рассматривается алгоритм Форда для их решения. Для задачи нахождения пути максимальной длины на графе рассматривается её применение в сетевом планировании.
Изучив данную тему студент должен:
определения основных понятий, теоремы и их доказательства;
рассматриваемые в теории задачи и методы их решения.
применять язык, методы и средства теории графов в дисциплинах прикладного характера.
Планы практических занятий по теме 3:
Способы представления графов.
Числа, характеризующие граф.
Операции над графами.
Деревья, их свойства.
Задачи нахождения кратчайшего дерева, её технико-экономическая интерпретация.
Задача нахождения пути максимальной длины на графе, её применении в сетевом планировании.
Рекомендации по выполнению конкретных заданий, вопросы и тесты для самопроверки содержатся в учебно-практическом пособии:
Дискретная математика. – М. : МГУЭСИ, 2009 (авторы Э.Л. Балюкевич, Л.Ф. Ковалёва, А.Н. Романников). / Литература 1 /
Список литературы
Балюкевич Э.Л., Ковалёва Л.Ф., Романников А.Н. Дискретная математика : учебно-практическое пособие. – М. : МГУЭСИ, 2009.
Балюкевич Э.Л., Ковалёва Л.Ф. Математическая логика и теория алгоритмов : учебно-практическое пособие. – М. : МГУЭСИ, 2009 (гриф УМО Минобрнауки РФ).
(Расширенные списки литературы с указанием интернет-ресурсов имеются в указанных выше учебно-практических пособиях.)
|
|
|
Скачать 6.65 Mb.
