Целеполагание при проектировании курса «Дискретная математика и математическая логика»

Тема занятия

Цели

Комбинаторика

Принцип Дирихле.

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

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

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

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

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

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

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

Метод включений и исключений.

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

Бином Ньютона.

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

Полиномиальная формула.

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

Рекуррентные соотношения. Линейные рекуррентные уравнения с постоянными коэффициентами.

Формировать представление о рекуррентных соотношениях как форме задания последовательности. Формировать умение решать задачи, сводящиеся к рекуррентным соотношениям. Формировать умения и навыки решения простейших задач, сводящихся к рекуррентным соотношениям. Формировать представление о линейных рекуррентных соотношениях с постоянными коэффициентами (ЛРСПК) как частном случае рекуррентных соотношений. Формировать знание о способах нахождения решения (общего и частного) ЛРСПК, а также умения и навыки поиска таких решений.

Производящие функции.

Формировать представление о методе производящих функций как возможности описания многих сложных последовательностей в комбинаторике, а иногда и возможности найти для них явные формулы.

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

Формировать представление о графе как о паре множеств особого вида. Формировать умение задавать граф различными способами. Формировать представление о связи свойств графа со степенями его вершин. Формировать представление о изоморфизме как отношении эквивалентности. Формировать умение устанавливать изоморфизм графов.

Подграфы, операции над графами.

Формировать представление о порожденных подграфах. Формировать представление об операциях над графами, умения и навыки строить результат операций над графами. Формировать представление об n-мерных кубах как особом классе графов.

Связность. Регулярные графы. Двудольные графы. Метрические характеристики графа.

Формировать представление о метрике в графе. Формировать умение находить количественные характеристики графа. Формировать представление о двудольных графах как особом классе графов.

Деревья. Матричная теорема Кирхгофа. Теорема Кэли. Остов минимального веса. Алгоритмы Краскала и Прима.

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

Плоские и планарные графы. Грани плоского графа. Формула Эйлера. Критерии планарности. Алгоритм укладки графа на плоскости. Характеристики непланарных графов.

Формировать представление о реальных задачах, решение которых сводится к необходимости плоской укладки графа. Формировать умение использовать формулу Эйлера для установления связи между числом вершин, ребер и граней плоского графа. Формировать умение доказывать теорему Эйлера. Формировать умение строить плоскую укладку графа так, чтобы заданное ребро (вершина, грань) принадлежали внешней грани. Формировать умение выводить следствия из теоремы Эйлера и с их помощью доказывать непланарность графов К₅ и К_3,3. Формировать представление о критериях планарности. Формировать умение доказывать непланарность графов К₅, К_3,3 и графа Петерсена с их помощью. Формировать представление о максимально плоских графах и их свойствах. Формировать умение строить триангуляцию графа с прямолинейными ребрами. Формировать представление о характеристиках непланарности: роде, толщине, числе скрещиваний, искаженности графа. Формировать представление о гамма-алгоритме как критерии планарности графа. Формировать умение использования гамма-алгоритма для построения плоской укладки графа или доказательства его непланарности.

Эйлеровы графы. Гамильтоновы графы. Алгоритмы построения обхода графа.

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

Раскраски. Оценки хроматического числа. Хроматический полином. Раскраска планарных графов. Проблема четырех красок.

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

Высказывания, логические операции над высказываниями.

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

Формулы алгебры высказываний, таблицы истинности. Проблема разрешимости.

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

Равносильные формулы алгебры высказываний. Основные равносильности алгебры высказываний.

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

Нормальные формы (ДНФ, СДНФ, КНФ, СКНФ). Проблема разрешимости.

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

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

Формировать представление о структуре логического следствия (ЛС). Формировать умение вычленять посылки и заключение. Формировать умение выяснять правильность ЛС различными способами: с помощью таблиц истинности, используя признак ЛС, методом от противного. Уметь создавать новые правила вывода. Уметь представлять доказательство ЛС в виде цепочки формул.

Энтимемы

Уметь восстанавливать пропущенный элемент (посылку или заключение) в ЛС.

Булевы функции. Релейно-контактные схемы.

Формировать практические навыки в исследовании булевых функций (БФ). Формировать представление о методах минимизации БФ. Формировать представление о применении БФ в технике. Формировать умение по заданной формуле строить переключательную схему.

Предикаты, кванторы. Формулы логики предикатов (ЛП). Значение формулы логики предикатов. Свободные и связанные переменные.

Формировать представление о месте логики предикатов в общем курсе математической логики. Формировать представление о предикате. Уяснить отличие предиката от высказывания и высказывательной формы. Формировать умение записывать предложения с переменными на языке логики предикатов и осуществлять обратный их перевод. Формировать умение определять значения предиката. Формировать умение «превратить» предикат в высказывание, используя операции навешивания кванторов и подстановку конкретных значений переменных, и интерпретировать результат.

Область (множество) истинности предиката.

Формировать умение определять значения предиката. Формировать умение находить множество (область) истинности предиката. Формировать умение изображать область истинности предиката на декартовой плоскости и с помощью диаграмм Эйлера–Венна. Формировать умение выражать множество истинности сложного предиката через множества истинности входящих в него предикатов.

Равносильные формулы логики предикатов. Основные равносильности логики предикатов.

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

Логическое следование предикатов.

Формировать умение устанавливать следование предикатов. Формировать умение устанавливать правильность рассуждений с помощью диаграмм Эйлера–Венна.

Предваренная нормальная форма (ПНФ). Общезначимость и выполнимость формул логики предикатов.

Формировать умение устанавливать выполнимость предикатов. Формировать умение строить НФ и ПНФ формулы, используя равносильные преобразования.

Применение ЛП в математической практике.

Формировать умение записывать математические предложение на языке ЛП. Формировать умение строить отрицание данных предложений, используя аппарат ЛП. Формировать умение понимать структуру математических теорем. Формировать умение формулировать прямую, обратную, противоположную, обратную противоположной теоремы.