Учебно-методическое обеспечение дисциплины Список основной литературы

1. Шапорев, С.Д. Дискретная математика / С.Д. Шапорев. СПб.: БХВ-Петербург, 2006, 396 с., 742 экз.

Список дополнительной литературы

1. Акимов, О.Е. Дискретная математика: логика, группы, графы / О.Е. Акимов, М.: Лаборатория Базовых Знаний, 2003. 376 с., 30 экз.

2. Лавров, И.А. Задачи по теории множеств, математической логике и теории алгоритмов / И.А. Лавров, Л.А. Максимова. М.: ФИЗМАТЛИТ, 2004. 256 с., 30 экз.

3. Новиков, Ф.А. Дискретная математика для программистов / Ф.А. Новиков. СПб.: Питер, 2003. 301 с., 31 экз.

Методические рекомендации (материалы) для преподавателя

Основным в идеологии дисциплины «Дискретная математика» является усвоение основных понятий, формул разделов дискретной математики, включённых в данный курс, овладение навыками решения типовых задач и приёмами алгоритмического и комбинаторного мышления.

В разделе I «Элементы теории множеств» достаточно изложить основы канторовской («наивной») теории множеств. Во введении можно дать сведения о становлении теории множеств в конце XIX века, о её современной проблематике и тенденциях исследования. Основные понятия канторовской теории множеств достаточно просты и сразу усваиваются студентами. Очень полезны в методическом аспекте круги Эйлера (диаграммы Эйлера-Венна), ими следует активно пользоваться для разъяснения операций над множествами и решения задач. Вместе с тем студенты должны понимать, что эти круги являются не более, чем наглядным средством знакомства с теорией множеств. Строгие математические доказательства и решения задач они должны проводить на основе логических рассуждений, используя круги Эйлера как вспомогательное средство. На практикуме по теме студенты должны научиться доказывать тождества с множествами аналитическими (по определению равенства множеств) и алгебраическими (используя формулы алгебры множеств) методами. Решение таких задач способствует развитию навыков формальных логических рассуждений.

При изложении темы 2 «Отношения и функции» для лучшего усвоения вводимых конструкций следует на лекции доказать хотя бы по одному свойству декартова произведения, бинарного отношения, функции. При этом ещё раз будет продемонстрирован метод формальных логических рассуждений. Специальные бинарные отношения и отношения порядка нужно иллюстрировать примерами, лучше из элементарной арифметики или геометрии. На практическом занятии по теме студенты должны научиться находить область определения, область значений данного бинарного отношения, обратное бинарное отношение, композиции, доказывать или опровергать рефлексивность (иррефлексивность), симметричность, антисимметричность, транзитивность, для эквивалентностей находить фактор-множество.

В теме 3 «Мощность множеств» нужно, чтобы студенты осознали канторовскую идею отождествления «величины» множеств по их эквивалентности (взаимнооднозначному соответствию). Теорию кардинальных чисел можно дать обзорно, но с обязательным описанием шкалы кардинальных чисел с иерархией бесконечностей. На практических занятиях студенты должны научиться доказывать равенства с кардинальными числами.

При изложении раздела II «Комбинаторика» следует в полной мере продемонстрировать метод комбинаторных рассуждений для доказательства формул и решения задач. В начале раздела нужно перечислить основные области комбинаторики, кратко описать её проблематику, подчеркнуть сложность задач при их элементарной формулировке. Следует также дать краткий исторический очерк развития комбинаторики и сказать о её бурном развитии в связи с распространением цифровых технологий и возросшей сложности и объёмности вычислений. При выводе формул нужно отдавать предпочтение чисто комбинаторным методам.

Основная трудность для студентов в этом разделе – решение задач. На практических занятиях рекомендуется решать задачи на типичные комбинаторные схемы с выводом соответствующих формул. Настаивать на запоминании формул (кроме основных) не нужно, важно овладение навыками комбинаторных рассуждений. Здесь рекомендуется давать по 8 – 10 для самостоятельного решения с обязательной сверкой ответов. Для демонстрации принципа включений и исключений можно решить на лекции некоторые задачи: подсчёт количества элементов в объединении множеств, беспорядочных перестановок, вывод формулы функции Эйлера и другие по выбору преподавателя.

При изложении теории графов нужно с самого начала подчеркнуть, что граф - абстрактный теоретико-множественный объект, а не «фигура из точек и соединяющих их дуг». Все определения следует давать в терминах теории множеств, иллюстрируя их для наглядности диаграммами. Студенты должны твёрдо усвоить, что диаграмма – это всего лишь наглядная геометрическая интерпретация, один из способов задания графа, причём не самый важный, а не сам граф. Соответственно, все теоремы нужно формулировать и доказывать строго аналитически, привлекая диаграммы только для наглядной иллюстрации рассуждений. Сначала строгое доказательство, а потом, если надо, рисунок.

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

Практические занятия, посвящённые графам, состоят в выдаче и разборе задач первой части индивидуального домашнего задания (ИДЗ). Варианты задания берутся из [1] в списке основной литературы для студентов. Преподаватель сам определяет включаемые задачи. Для каждой кратко излагается алгоритм по шагам и разбирается один пример. Следует помнить, что алгоритм построения потока минимальной стоимости очень трудоёмкий, поэтому нужно иметь заранее решённый пример (можно взять из [1] в списке основной литературы) и изложить его на лабораторном занятии, опуская вспомогательные вычисления.

Задачи раздела IV «Элементы сетевого планирования» легко решаются студентами. Для получения правильного решения необходимо лишь внимание. Задачи этого раздела можно использовать как тестовые для решения вопроса о положительной оценке на экзамене. Если студент не в состоянии решить такую задачу, то он категорически на готов к ответу.

Раздел V «Элементы теории кодирования» следует дать подробно, поскольку это совершенно новая сложная тема. С самого начала нужно обозначить различие между криптографией и криптоанализом и теорией кодирования. Именно теория кодирования, занимающаяся методами преобразования данных для оптимальной их передачи по каналам связи, будет предметом изучения. Можно в начале лекции для привлечения интереса аудитории сделать краткий экскурс в историю криптографии. При изучении темы 12 нужно подробно рассмотреть методы распознавания однозначности кодирования (теорема Маркова, неравенство Макмиллана). Для введения понятия оптимального кода следует вспомнить основные определения теории вероятностей. Процедура построения кода Хаффмена легко усваивается студентами, поэтому на лекции достаточно привести один пример, однако утверждения, на которых он базируется, требуют подробного разъяснения. Некоторые из них нужно доказать. Для наглядности можно пользоваться изображением кодов графами. Процедура построения кода Хемминга, исправляющего одну ошибку сложна, поэтому желательно разобрать несколько примеров.

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

В библиотеке БГТУ пока нет в достаточном количестве задачников по данной дисциплине. Поэтому преподаватель должен иметь свой сборник задач, из которого будет давать задачи для аудиторного и домашнего решения. Из наиболее известных задачников можно рекомендовать [2] из списка дополнительной литературы для студентов и [7] из списка дополнительной литературы для преподавателя. Варианты ИДЗ разрабатывает преподаватель. Можно использовать как образцы задачи из [7] (теория кодирования), [13] (теория графов) в списке дополнительной литературы для преподавателя.