1. Цели освоения дисциплины
Дисциплина «Теория графом и математическая логика» относится к учебному циклу Б2.Б.4 (Математический и естественнонаучный цикл) и входит в состав базовой части ООП. Обязательный курс для студентов 2 курса, читается в 3 и 4 семестрах
Целями дисциплины «Теория графов и математическая логика» являются освоение студентами основных понятий и теорем теории графов и математической логики, а также приобретение практических навыков решения прикладных задач, связанных с графами, логическими функциями и предикатами.
Для достижения поставленных целей в рамках дисциплины решаются следующие задачи:
- ознакомление студентов с понятиями графа, орграфа, способами задания графов, основными теоремами теории графов. отработка навыков работы с классификацией графов, идентификации их свойств, решение прикладных вычислительных задач на графах. ознакомление студентов с основами математической логики: логическая функция, булева алгебра, предикаты, кванторы. отработка навыков работы с высказываниями, логическими функциями, СДНФ, СКНФ, методы минимизации логических форм, предикатами.
2. Тематический план по изучению дисциплины
Раздел 1. Основы теории множеств
Тема 1.1. Множества, функции, отношения
Интуитивные принципы абстракции и объемности. Операции над множествами: объединение, пересечение, относительное и абсолютное дополнения, симметрическая разность. Отношения и функции, бинарное и n-арное отношения, прямое произведение, обратное отношение, композиция отношений, инъекция, сюръекция, биекция, их свойства. Специальные бинарные отношения: рефлексивное, симметричное, транзитивное, эквивалентное. Матрицы бинарных отношений и их свойства. Отношение порядка.
Раздел 2. Теория графов
Тема 2.1. Основные понятия теории графов
Определение и способы задания графа. Виды графов. Матрицы инцидентности и смежности. Идентификация графа, теоремы о геометрической реализации графа на плоскости и в пространстве. Формула Эйлера для графа. Степени вершин графа. Подграф. Хроматическое число и хроматический многочлен графа. Теорема Кёнига. Маршруты, цепи и циклы. Эйлеров граф. Теорема Эйлера о цикле. Итерационный метод поиска кратчайшего маршрута на графе.
Тема 2.2. Оргафы
Пути и связность в орграфе. Компоненты связности орграфа. Ациклический граф. Топологическая сортировка. Теорема о топологической сортировке. Матрицы орграфов и их связь с путями.
Тема 2.3. Деревья и остовы
Дерево. Свойства деревьев. Ориентированное дерево. Остов.
Тема 2.4. Задачи оптимизации на графах
Минимальное покрывающее дерево. Кратчайшие пути. Сетевой план. Потоки в сетях. Увеличивающая цепь. Максимальный поток в сети.
Раздел 3. Математическая логика: высказывания и булева алгебра
Тема 3.1. Логика высказываний.
Высказывания. Логические операции. Формулы логики высказываний. Равносильность формул. Тождественно истинные и тождественно ложные формулы. Двойственность. Нормальные формы формул. Разрешимость.
Тема 3.2. Булевы функции.
Двоичная система исчисления. Понятие булевой алгебры. Способы задания булевых функций. Представление булевой функции формулой логики высказываний. Нормальные формы булевых функций. Двойственность, самодвойственность, монотонность булевых функций. Минимизация в классе дизъюнктивных нормальных форм. Контактные схемы. Логические задачи.
Раздел 4. Математическая логика: исчисление высказываний и предикат
Тема 4.1. Исчисление высказываний.
Аксиоматические теории. Исчисление высказываний: определение, система аксиом, основные правила вывода. Производные правила вывода. Вывод из совокупности формул. Правила выводимости из совокупности. Теорема дедукции. Законы и правила перестановки, соединения и разъединения посылок. Связь логики высказываний и исчисления высказываний. Вывод формулы или ее отрицания из соответствующей совокупности формул. Полнота, независимость и непротиворечивость исчисления высказываний.
Тема 4.2. Логика и исчисление предикатов.
Предикаты. Область истинности предикатов. Логические операции над предикатами. Кванторные операции. Формулы логики предикатов, их равносильность. Выполнимость, общезначимость. Исчисление предикатов: аксиомы и правила вывода.
Раздел 5. Комбинаторный анализ.
Тема 5.1. Элементы комбинаторики.
Общие правила комбинаторики, формула включений и исключений. Размещения, перестановки, сочетания. Комбинаторные задачи с ограничениями. Задачи на разбиения. Производящая функция.
Тема 5.2. Целочисленные уравнения.
Целочисленные линейные уравнения в натуральных числах.
Тема 5.3. Рекуррентные соотношения.
Решение рекуррентных соотношений.
3. Указания по изучению дисциплины
3.1. Общие методические указания
Важнейшей частью образовательного процесса дисциплины «Теория игр» являются учебные занятия. В ходе занятий осуществляется теоретическое обучение студентов, привитие им необходимых умений и практических навыков по дисциплине.
Учебные занятия начинаются и заканчиваются по времени в соответствии с утвержденным режимом СПб ГУГА в аудиториях согласно семестровым расписаниям теоретических занятий. Допуск в аудиторию опоздавших студентов запрещается. Никакие вызовы студентов и преподавателей с занятий не допускаются. На занятиях, предусмотренных расписанием, обязаны присутствовать все обучающие. Освобождение студентов от занятий может проводиться только деканатом. Преподаватель обязан лично контролировать наличие студентов на занятиях.
Основными видами учебных занятий по дисциплине являются лекции, практические занятия, консультации, все виды практик, выполнение курсовых работ. Виды учебных занятий определяются рабочей программой дисциплины.
Лекции являются одним из важнейших видов образовательных технологий и составляют основу теоретической подготовки студентов по дисциплине. Они должны давать систематизированные основы научных знаний по дисциплине, концентрировать внимание студентов на наиболее сложных, проблемных вопросах, стимулировать их активную познавательную деятельность и способствовать формированию творческого мышления.
Каждая лекция должна представлять собой устное изложение лектором основных теоретических положений изучаемой дисциплины или отдельной темы как логически законченное целое и иметь конкретную целевую установку. Лекции должны носить, как правило, проблемный характер. Основным методом в лекции выступает устное изложение лектором учебного материала, сопровождающееся демонстрацией схем, плакатов, моделей.
Порядок изложения материала лекции отражается в плане ее проведения.
Особое место в лекционном курсе по дисциплине занимают вводная и заключительная лекции.
Вводная лекция должна давать общую характеристику изучаемой дисциплины, подчеркивать новизну проблем, указывать ее роль и место в системе (структурно-логической схеме) изучения других дисциплин, раскрывать учебные и воспитательные цели и кратко знакомить студентов с содержанием и структурой курса, а также с организацией учебной работы по нему.
Заключительная лекция должна давать научно-практическое обобщение изученной дисциплины, показывать перспективы развития изучаемой области знаний, навыков и практических умений.
Практические занятия по дисциплине имеют целью:
- углубление, расширение и конкретизацию теоретических знаний, полученных на лекции, до уровня, на котором возможно их практическое использование;
- экспериментальное подтверждение положений и выводов, изложенных в теоретическом курсе, и усиление доказательности обучения;
- отработку навыков и умений в пользовании графиками, схемами, матрицами информационно-аналитической работы;
- отработку умения использования ПК;
- проверку теоретических знаний.
Основу практических занятий составляет работа каждого обучаемого (индивидуальная и (или) коллективная, по приобретению умений и навыков использования закономерностей, принципов, методов, форм и средств, составляющих содержание дисциплины в профессиональной деятельности и в подготовке к изучению дисциплин, формирующих компетенции выпускника). Практическим занятиям предшествуют лекции и целенаправленная самостоятельная подготовка студентов, поэтому практические занятия нужно начитать с краткого обзора цели занятия, напоминания о его связи с лекциями, и формирования контрольных вопросов-заданий, которые должны быть решены на данном занятии.
По результатам контроля знаний и умений преподаватель должен провести анализ хода и итогов практических занятий, отметить успехи студентов в решении учебной задачи, а также недостатки и ошибки, разобрать их причины и дать методические указания к их устранению. Таким образом, практические занятия являются важной формой обучения, в ходе которых знания студентов превращаются в профессиональные необходимые умения, навыки и компетенции.
Консультации являются одной из форм руководства работой студентов и оказания им помощи в самостоятельном изучении учебного материала. Они проводятся регулярно в процессе всего периода обучения (по мере возникновения потребности) по предварительной договоренности студентов с лектором (преподавателем) в часы самостоятельной работы и носят в основном индивидуальный характер. При необходимости разъяснения общих вопросов нескольким или всем обучающимся учебной группы проводятся групповые консультации.
Преподаватель имеет право вызывать на консультацию тех студентов, которые не показывают глубоких знаний и не пользуются консультациями по своей инициативе. В этих случаях, преподаватель выясняет, работает ли студент систематически над учебным материалом, в какой степени усваивает его, в чем встречает наибольшие трудности. Установив фактическое положение дела, преподаватель дает рекомендации по самостоятельному изучению материала, решению трудных вопросов и при необходимости назначает срок повторной консультации.
Все сопутствующие материалы, а именно: задания на контрольные работы, перечень вопросов для подготовки к экзамену (зачету), задания на курсовые работы и рекомендации по их выполнению приведены в соответствующих разделах УМК.
3.2. Указания по работе с литературой
Предмет изучается студентами путем самостоятельной работы над учебниками и учебными пособиями. Кроме того, обязательным элементом учебного процесса являются лекции.
При самостоятельной работе над учебниками и учебными пособиями рекомендуется придерживаться определенной последовательности. Читая и конспектируя тот или иной раздел учебника, необходимо твердо усвоить основные определения и понятия и те закономерности, которыми определяется связь и зависимость одних величин от других. Формулировки законов и методику вывода их математических выражений надо знать на память. После усвоения соответствующих понятий и закономерностей следует решить примеры и задачи, закрепляя тем самым проработанный теоретический материал, а затем приступить к выполнению контрольных или расчетно-графических работ.
а) Основная литература
, Овчинникова математика. М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2005 , Математическая логика. СПб, Изд. Лань, 1999 г. Кузнецов метематика для инженера. – СПб: Изд. Лань, 2005 г. Игошин и упражнения по математической логике и теории алгоритмов. М.: Изд. Ценр «Академия», 2005 Виленкин . М.: Наука, 1969 г. рафы и их применение. Н: ИО НФМИ, 2000 г.б) Дополнительная литература
, Осипова дискретной математики. М.: Изд. МАИ, 1992 г. , Максимова по теории множеств, математической логике и теории алгоритмов. М.: Наука, 1984 г. еория графов.