Распределение часов курса по темам и видам работ

I. Организационно-методический раздел

1. Пояснительная записка – электронный образовательный ресурс (ЭОР) «Дискретная математика» предназначен для обеспечения современным учебным пособием одноименной дисциплины, специальности 010200 – “Прикладная математика и информатика” (федеральный компонент). Дискретная математика является одной из базовых дисциплин при подготовке специалистов в области информационных технологий и программирования. Литература, ориентированная на классические университеты, относится к 80 – 90-м годам прошлого столетия и практически не отражает связи между результатами дискретной математики и технологическими идеями проектирования компьютеров. Этот же недостаток присутствует в учебниках, вышедших в последние годы и предназначенных для аналогичных специалистов, выпускаемых в бывших технических вузах. В настоящее время курс представляет собой совокупность разделов дискретной математики, читаемых на принятом в классическом университетах уровне строгости изложения и в то же время обсуждения приложений результатов дискретной математики к задачам анализа и синтеза дискретных систем, решаемых при проектировании компьютеров. Такой способ изложения, с одной стороны, повышает мотивацию студентов к изучению дискретной математики, о чем свидетельствуют получаемые на протяжении многих лет высокие оценки по этому предмету. С другой стороны, связь с приложениями заставляет вводить в курс новые результаты дискретной математики, отвечающие современному уровню ее развития. Такой подход к чтению курса связан с тем, что в Томском университете на протяжении многих лет успешно развиваются научные направления в области приложений дискретной математики: криптографии, диагностики дискретных систем, а также в развитии ее разделов: теории недетерминированных автоматов, теории автоматов на полурешетках и др. По этим направлениям защищены 5 докторских диссертаций и около 20 кандидатских.

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

3. Задачи учебного курса – усвоить основные понятия дискретной математики, знать основные алгоритмы, уметь использовать полученные знания при решении практических задач.

4. Требования к уровню освоения курса сводятся к следующему:

Студент должен знать:

– основные понятия дискретной математики, основные алгоритмы.

Студент должен уметь:

– использовать полученные знания при решении практических задач.

II. Принципы построения программы курса.

Материал курса изложен в форме лекций, с использованием большого количества примеров.

Курс имеет модульную структуру, студенты могут использовать различные схемы изучения материала. Различные разделы могут быть интересны преподавателям вузов и учителям школ.

III. Методические рекомендации к основным темам курса

Общие методические рекомендации

При проведении лекций преподаватель

1) формулирует тему и цель занятия;

2) излагает основные теоретические положения;

3) под запись дает определения основных понятий, теорем, алгоритмов;

4) проводит примеры для наглядного и образного представления изучаемого материала;

5) в конце занятия дает вопросы для самостоятельного изучения.

Распределение часов курса по темам и видам работ

3. Темы и краткое содержание

Тема 1. Функции алгебры логики (булевы функции). Табличное представление. Число функций от n переменных. Элементарные функции. Индуктивное определение формулы над множеством булевых функций. Формулы над множеством элементарных функций. Соседние наборы. Существенные и фиктивные переменные. Добавление и исключение фиктивных переменных. Равенство функций и эквивалентность формул. Основные тождества алгебры логики. Операции поглощения и склеивания.

Тема 2. Принцип двойственности. Теорема о двойственной функции. Разложение функции по подмножеству переменных. Теорема о разложении по m переменным. Частные случаи разложения по одной и всем переменным. Вывод формул СДНФ и СКНФ.

Тема 3. Полнота и замкнутость. Определение полной системы. Теорема о полной системе. Примеры полных систем. Определение замыкания. Свойства замыканий. Определение полной системы через замыкание. Определение замкнутого класса. Свойства замкнутых классов, сохраняющих константы. Замкнутый класс самодвойственных функций и его свойства. Лемма о не самодвойственной функции. Сравнимые наборы. Замкнутый класс монотонных функций и его свойства. Лемма о немонотонной функции. Полином Жегалкина. Теорема о единственности полинома для функции. Линейный полином. Замкнутый класс линейных функций и его свойства. Лемма о нелинейной функции. Теорема о необходимых и достаточных условиях полноты систем булевых функций. Теорема о числе функций полных систем. Функции к -значной логики (определение, табличное задание).

Тема 4. Минимизация ДНФ. Теорема о числе ДНФ функций n переменных. Определения минимальной и кратчайшей ДНФ. Тривиальный алгоритм их построения. Геометрическая интерпретация булевой функции (n -мерный куб, матрица в коде Грея). Определение интервала. Свойства интервала. Допустимый и максимальный интервалы. Покрытие множества единичных наборов функции интервалами. Кратчайшее и минимальное покрытия. Импликанта, простая импликанта, их свойства. Сокращенная ДНФ. Теорема Квайна о сокращенной ДНФ. Троичные векторы и операции над ними. Алгоритм Квайна–МакКласки построения сокращенной ДНФ. Таблица Квайна и ее кратчайшие и минимальные покрытия. Теорема Блейка. Алгоритм Блейка построения сокращенной ДНФ. Общая схема построения минимальных и кратчайших ДНФ. Теорема о сокращенной ДНФ монотонной функции. Ортогональные конъюнкции. Ортогональные ДНФ. Теорема о поглощении конъюнкции дизъюнктивной нормальной формой. Использование теоремы для построения безызбыточной ДНФ. Объединение и пересечение безызбыточных (тупиковых) ДНФ. Ядро ДНФ. Теорем Квайна о ядре и ее следствие. Упрощение ДНФ. Минимизация частичных булевых функций. Реализация частичной функции. Допустимый и максимальный интервалы частичной функции. Сокращенная ДНФ и ее построение. Построение минимальной и кратчайшей реализации частичной функции по таблице Квайна.

Тема 5. Элементы теории автоматов. Представление о дискретном устройстве, комбинационном и последовательностном. Простейшие логические элементы. Описание поведения комбинационного устройства. Пример. Проблема анализа и синтеза комбинационного устройства. Анализ комбинационного устройства. Синтез комбинационного устройства в базисе ДНФ, НЕ ИЛИ, НЕ И. Определение автомата. Его представление таблицами переходов-выходов. Диаграммы переходов. Полностью определенные и частичные автоматы. Автономные автоматы, автоматы без выходов, комбинационные автоматы, автоматы Мили, Мура. Триггеры. Канонические уравнения и их получение. Формальные языки и настроенные диаграммы. Конечно-автоматные языки и операции над ними. Замкнутость конечно-автоматных языков.

Тема 6. Элементы теории кодирования. Алфавитное кодирование. Префикс и окончание. Свойство префикса. Теорема. Нетривиальное разложение элементарных кодов в схеме кодирования. Алгоритм проверки однозначности кодирования. Неравенство МакМилана (теорема). Свойства взаимно-однозначных кодов. Теорема. Коды с минимальной избыточностью. Дерево однозначного кодирования. Операции на нем. Насыщенное и приведенное деревья. Алгоритм построения кода с минимальной избыточностью.

Тема 7. Исчисление высказываний. Алфавит, синтаксис и семантика исчисления высказываний. Проблема вывода. Дерево частичных интерпретаций и его построение. Анализ КНФ на невыполнимость резольвентным методом. Связь метода Блейка и резольвентного метода.

Тема 8. Исчисление предикатов. Алфавит, синтаксис и семантика исчисления предикатов. Предваренная нормальная форма. Проблема вывода. Хорновские дизъюнкты.