Файл: Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики.doc
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 26.03.2024
Просмотров: 314
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Изучая понятие мощности множества, основные теоремы о счетных множествах, нужно подчеркнуть, что «количество элементов» в бесконечном множестве может быть различным, что дискретные множества – это конечные и счетные множества, дискретная математика – математика дискретных величин, в отличие от математики непрерывных величин.
Изучив данную тему студент должен:
-
Знать:
-
основные понятия теории множеств, понятие мощности множества, операции над множествами, как частный случай алгебры Буля, декартово произведение множеств, отображение множеств, типы отображений, отношения на множествах, специальные бинарные отношения.
-
Уметь:
-
иллюстрировать основные понятия примерами из различных математических прикладных дисциплин.
План практических занятий по теме 1.
-
Алгебра Буля. Операции над множествами (иллюстрация операций диаграммами). Основные равносильные формулы. Преобразования формул. -
Эквивалентные множества. Мощность множества. Сравнение мощностей множеств. -
Прямое произведение множеств. Отображение множеств. Типы отображений. -
Отношения на множествах. Бинарные отношения, свойства отношений. Специальные бинарные отношения.
Рекомендации по выполнению конкретных заданий, вопросы и тесты для самопроверки содержатся в учебно-практическом пособии «Дискретная математика». – М. : МГУЭСИ, 2009 (авторы Э.Л. Балюкевич, Л.Ф. Ковалёва, А.Н. Романников). /Литература 1/
Тема 2. Математическая логика
При изучении данной темы следует обратить внимание на то, что алгебра высказываний является частным примером булевой алгебры и провести аналогию между логическими и теоретико-множественными операциями.
Следует изучить основные логические операции (связки), понятие полной системы связок
, понятие формулы алгебры, высказываний, основные равносильные формулы. Показать, как высказываниям в естественном и математическом языке могут быть поставлены в соответствие логические формулы. Рассмотреть основное понятие – понятие логической функции и уяснить связь между формулами и функциями алгебры высказываний. Изучить логические отношения между высказываниями (отношение следования, отношение эквивалентности и отношение несовместимости), а также способы проверки правильности рассуждений.
Рассмотреть, как проблема определения типа формулы (проблема разрешимости) может быть решена с помощью приведения формулы к нормальным формам (НФ) и определить конструктивно понятие совершенной нормальной формы формулы алгебры высказываний (СНФ).
Изучить построение формулы алгебры высказываний по заданной функции.
Выяснить возможность моделирования формул алгебры высказываний релейно-контактными схемами, а также какие задачи при этом могут быть решены.
Рассмотреть формальную аксиоматическую систему, адекватную алгебре высказываний – исчисление высказываний; основные проблемы формальной логической системы, как они решаются и как она может быть применена к конкретной научной области.
Далее изучается логика предикатов, которая включает в себя алгебру высказываний как составную часть. Рассматриваются операции над предикатами, кванторы общности и существования, применение кванторов в математических науках.
Изучив данную тему студент должен:
-
Знать:
-
все понятия, перечисленные выше, связанные с ними свойства, соотношения, теоремы; -
рассматриваемые в теории проблемы и способы их решения.
-
Уметь:
-
применять язык, методы и средства математической логики в математических дисциплинах и в прикладных дисциплинах.
Планы практических занятий по теме 2
-
Логические операции. Формулы алгебры высказываний. Равносильность формул. Полные системы связок. -
Логические функции. Связь с формулами алгебры высказываний. Существенные и фиктивные переменные. -
Логические отношения. Проверка правильности рассуждений. -
Нормальные формы алгебры высказываний. Установление типа формулы. -
Совершенные нормальные формы. Построение формулы алгебры высказываний по заданной функции. -
Алгебра высказываний и релейно-контактные схемы. Упрощение схем. -
Исчисление высказываний: алфавит, формулы, аксиомы, правила вывода. Проблемы непротиворечивости, полноты и независимости системы аксиом. -
Логика предикатов. Операции над предикатами. Кванторы.
Рекомендации по выполнению конкретных заданий, вопросы и тесты для самопроверки содержатся в учебно-практи-ческих пособиях:
Дискретная математика. – М. : МГУЭСИ, 2009. (Авторы Э.Л. Балюкевич, Л.Ф. Ковалёва, А.Н. Романников.) / Литература 1 /
Математическая логика и теория алгоритмов. – М. : МГУЭСИ, 2009. (Гриф УМО Минобрнауки РФ.) (Авторы Э.Л. Балюкевич, Л.Ф. Ковалёва.) / Литература 2 /
Тема 3. Теория графов
В этой теме рассматриваются основные понятия, связанные с конечными графами.
Даются определения ориентированных и неориентированных графов, способы их задания и представления. Рассматриваются теоремы, связанные с путями на графе, понятия связности, изоморфизма и планирности графов. Изучаются числа, характеризующие граф: цикломатическое, хроматическое число, числа внутренней и внешней устойчивости.
Далее излагаются операции над графами: объединение, пересечение, прямое произведение графов. Рассматриваются матрицы для графов и выполнение с помощью матриц смежности основных операций над графами.
Значительная часть темы рассматривает графы типа – дерево. Необходимо изучить свойства деревьев, теоремы о них. Рассматривается задача нахождения кратчайшего дерева и её экономическая интерпретация. Для отыскания кратчайшего дерева используется алгоритм Краскала.
Отдельный раздел посвящен некоторым экстремальным задачам на графах: нахождению путей минимальной и максимальной длины на графе. Дается экономическая интерпретация каждой из этих задач. Рассматривается алгоритм Форда для их решения. Для задачи нахождения пути максимальной длины на графе рассматривается её применение в сетевом планировании.
Изучив данную тему студент должен:
-
Знать:
-
определения основных понятий, теоремы и их доказательства; -
рассматриваемые в теории задачи и методы их решения.
-
Уметь:
-
применять язык, методы и средства теории графов в дисциплинах прикладного характера.
Планы практических занятий по теме 3:
-
Способы представления графов. -
Числа, характеризующие граф. -
Операции над графами. -
Деревья, их свойства. -
Задачи нахождения кратчайшего дерева, её технико-экономическая интерпретация. -
Задача нахождения пути максимальной длины на графе, её применении в сетевом планировании.
Рекомендации по выполнению конкретных заданий, вопросы и тесты для самопроверки содержатся в учебно-практическом пособии:
Дискретная математика. – М. : МГУЭСИ, 2009 (авторы Э.Л. Балюкевич, Л.Ф. Ковалёва, А.Н. Романников). / Литература 1 /
Список литературы
-
Балюкевич Э.Л., Ковалёва Л.Ф., Романников А.Н. Дискретная математика : учебно-практическое пособие. – М. : МГУЭСИ, 2009. -
Балюкевич Э.Л., Ковалёва Л.Ф. Математическая логика и теория алгоритмов : учебно-практическое пособие. – М. : МГУЭСИ, 2009 (гриф УМО Минобрнауки РФ).
(Расширенные списки литературы с указанием интернет-ресурсов имеются в указанных выше учебно-практических пособиях.)