Учебно-методическое обеспечение курса
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение высшего профессионального образования
“ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ”
УТВЕРЖДАЮ
Декан факультета прикладной математики и кибернетики
______________ А.М.Горцев
«____» ____________ 2007 г.
А.Ю. Матросова, С.А. Останин
Дискретная математика
Методические рекомендации для педагогов
Рекомендовано
методической комиссией
факультета прикладной математики и кибернетики
Председатель методической
комиссии
______________ С.Э. Воробейчиков
«____» ____________ 2007 г.
Томск
2007
I. Организационно-методический раздел
1. Пояснительная записка – электронный образовательный ресурс (ЭОР) «Дискретная математика» предназначен для обеспечения современным учебным пособием одноименной дисциплины, специальности 010200 – “Прикладная математика и информатика” (федеральный компонент). Дискретная математика является одной из базовых дисциплин при подготовке специалистов в области информационных технологий и программирования. Литература, ориентированная на классические университеты, относится к 80 – 90-м годам прошлого столетия и практически не отражает связи между результатами дискретной математики и технологическими идеями проектирования компьютеров. Этот же недостаток присутствует в учебниках, вышедших в последние годы и предназначенных для аналогичных специалистов, выпускаемых в бывших технических вузах. В настоящее время курс представляет собой совокупность разделов дискретной математики, читаемых на принятом в классическом университетах уровне строгости изложения и в то же время обсуждения приложений результатов дискретной математики к задачам анализа и синтеза дискретных систем, решаемых при проектировании компьютеров. Такой способ изложения, с одной стороны, повышает мотивацию студентов к изучению дискретной математики, о чем свидетельствуют получаемые на протяжении многих лет высокие оценки по этому предмету. С другой стороны, связь с приложениями заставляет вводить в курс новые результаты дискретной математики, отвечающие современному уровню ее развития. Такой подход к чтению курса связан с тем, что в Томском университете на протяжении многих лет успешно развиваются научные направления в области приложений дискретной математики: криптографии, диагностики дискретных систем, а также в развитии ее разделов: теории недетерминированных автоматов, теории автоматов на полурешетках и др. По этим направлениям защищены 5 докторских диссертаций и около 20 кандидатских.
|
|
|
2. Цель курса – ознакомить студентов с основными понятиями дискретной математики, доказательствами важнейших теорем, развивая тем самым их логическое мышление и подготавливая к освоению современных информационных технологий.
|
|
|
3. Задачи учебного курса – усвоить основные понятия дискретной математики, знать основные алгоритмы, уметь использовать полученные знания при решении практических задач.
4. Требования к уровню освоения курса сводятся к следующему:
Студент должен знать:
– основные понятия дискретной математики, основные алгоритмы.
Студент должен уметь:
– использовать полученные знания при решении практических задач.
II. Принципы построения программы курса.
Материал курса изложен в форме лекций, с использованием большого количества примеров.
Курс имеет модульную структуру, студенты могут использовать различные схемы изучения материала. Различные разделы могут быть интересны преподавателям вузов и учителям школ.
III. Методические рекомендации к основным темам курса
Общие методические рекомендации
При проведении лекций преподаватель
1) формулирует тему и цель занятия;
2) излагает основные теоретические положения;
|
|
|
3) под запись дает определения основных понятий, теорем, алгоритмов;
4) проводит примеры для наглядного и образного представления изучаемого материала;
5) в конце занятия дает вопросы для самостоятельного изучения.
Распределение часов курса по темам и видам работ
| № | Тема | Всего часов | Аудиторные занятия | Самостоятельная работа | ||
| В том числе | ||||||
| лекции | семинары | лабораторные занятия | ||||
| 1 | Функции алгебры логики | 11 | 4 | 6 | 1 | |
| 2 | Принцип двойственности | 8 | 2 | 4 | 2 | |
| 3 | Полнота и замкнутость | 18 | 10 | 6 | 2 | |
| 4 | Минимизация ДНФ | 18 | 8 | 8 | 2 | |
| 5 | Элементы теории автоматов | 16 | 8 | 6 | 2 | |
| 6 | Элементы теории кодирования | 13 | 8 | 4 | 1 | |
| 7 | Исчисление высказываний | 10 | 4 | 4 | 2 | |
| 8 | Исчисление предикатов | 8 | 2 | 4 | 2 | |
| Итого | 144 | 62 | 62 | 20 | ||
Темы и краткое содержание
Тема 1. Функции алгебры логики (булевы функции). Табличное представление. Число функций от n переменных. Элементарные функции. Индуктивное определение формулы над множеством булевых функций. Формулы над множеством элементарных функций. Соседние наборы. Существенные и фиктивные переменные. Добавление и исключение фиктивных переменных. Равенство функций и эквивалентность формул. Основные тождества алгебры логики. Операции поглощения и склеивания.
|
|
|
Тема 2. Принцип двойственности. Теорема о двойственной функции. Разложение функции по подмножеству переменных. Теорема о разложении по m переменным. Частные случаи разложения по одной и всем переменным. Вывод формул СДНФ и СКНФ.
Тема 3. Полнота и замкнутость. Определение полной системы. Теорема о полной системе. Примеры полных систем. Определение замыкания. Свойства замыканий. Определение полной системы через замыкание. Определение замкнутого класса. Свойства замкнутых классов, сохраняющих константы. Замкнутый класс самодвойственных функций и его свойства. Лемма о не самодвойственной функции. Сравнимые наборы. Замкнутый класс монотонных функций и его свойства. Лемма о немонотонной функции. Полином Жегалкина. Теорема о единственности полинома для функции. Линейный полином. Замкнутый класс линейных функций и его свойства. Лемма о нелинейной функции. Теорема о необходимых и достаточных условиях полноты систем булевых функций. Теорема о числе функций полных систем. Функции к-значной логики (определение, табличное задание).
Тема 4. Минимизация ДНФ. Теорема о числе ДНФ функций n переменных. Определения минимальной и кратчайшей ДНФ. Тривиальный алгоритм их построения. Геометрическая интерпретация булевой функции (n-мерный куб, матрица в коде Грея). Определение интервала. Свойства интервала. Допустимый и максимальный интервалы. Покрытие множества единичных наборов функции интервалами. Кратчайшее и минимальное покрытия. Импликанта, простая импликанта, их свойства. Сокращенная ДНФ. Теорема Квайна о сокращенной ДНФ. Троичные векторы и операции над ними. Алгоритм Квайна–МакКласки построения сокращенной ДНФ. Таблица Квайна и ее кратчайшие и минимальные покрытия. Теорема Блейка. Алгоритм Блейка построения сокращенной ДНФ. Общая схема построения минимальных и кратчайших ДНФ. Теорема о сокращенной ДНФ монотонной функции. Ортогональные конъюнкции. Ортогональные ДНФ. Теорема о поглощении конъюнкции дизъюнктивной нормальной формой. Использование теоремы для построения безызбыточной ДНФ. Объединение и пересечение безызбыточных (тупиковых) ДНФ. Ядро ДНФ. Теорем Квайна о ядре и ее следствие. Упрощение ДНФ. Минимизация частичных булевых функций. Реализация частичной функции. Допустимый и максимальный интервалы частичной функции. Сокращенная ДНФ и ее построение. Построение минимальной и кратчайшей реализации частичной функции по таблице Квайна.
Тема 5. Элементы теории автоматов. Представление о дискретном устройстве, комбинационном и последовательностном. Простейшие логические элементы. Описание поведения комбинационного устройства. Пример. Проблема анализа и синтеза комбинационного устройства. Анализ комбинационного устройства. Синтез комбинационного устройства в базисе ДНФ, НЕ ИЛИ, НЕ И. Определение автомата. Его представление таблицами переходов-выходов. Диаграммы переходов. Полностью определенные и частичные автоматы. Автономные автоматы, автоматы без выходов, комбинационные автоматы, автоматы Мили, Мура. Триггеры. Канонические уравнения и их получение. Формальные языки и настроенные диаграммы. Конечно-автоматные языки и операции над ними. Замкнутость конечно-автоматных языков.
Тема 6. Элементы теории кодирования. Алфавитное кодирование. Префикс и окончание. Свойство префикса. Теорема. Нетривиальное разложение элементарных кодов в схеме кодирования. Алгоритм проверки однозначности кодирования. Неравенство МакМилана (теорема). Свойства взаимно-однозначных кодов. Теорема. Коды с минимальной избыточностью. Дерево однозначного кодирования. Операции на нем. Насыщенное и приведенное деревья. Алгоритм построения кода с минимальной избыточностью.
Тема 7. Исчисление высказываний. Алфавит, синтаксис и семантика исчисления высказываний. Проблема вывода. Дерево частичных интерпретаций и его построение. Анализ КНФ на невыполнимость резольвентным методом. Связь метода Блейка и резольвентного метода.
Тема 8. Исчисление предикатов. Алфавит, синтаксис и семантика исчисления предикатов. Предваренная нормальная форма. Проблема вывода. Хорновские дизъюнкты.
Темы практических занятий
1. Булевы функции. Существенные и фиктивные переменные.
2. Элементарные булевы функции. Формульное представление булевых функций.
3. СДНФ и СКНФ.
4. Полином Жегалкина.
5. Двойственные функции.
6. Полнота и замкнутость систем булевых функций.
7. Минимизация ДНФ.
8. Элементы теории автоматов.
9. Элементы теории кодирования.
10. Исчисление высказываний.
11. Исчисление предикатов.
Перечень контрольных вопросов по курсу
1. Определение булевой функции, табличное задание, число функций от n переменных. Элементарные функции. Существенные переменные. Равенство функций.
2. Понятие формулы, эквивалентные формулы. Основные тождества алгебры логики.
3. Двойственные функции и способы их получения. Теорема о двойственной функции.
4. Определение полной системы, примеры полных систем. Теорема о полных системах.
5. Замыкание. Свойство замыканий. Замкнутые классы. Свойства классов T0, T1.
6. Класс самодвойственных функций и его свойство.
7. Лемма о несамодвойственной функции.
8. Класс монотонных функций, его замкнутость.
9. Лемма о немонотонной функции.
10. Полином Жегалкина. Теорема о единственности полинома.
11. Линейные функции. Лемма о нелинейной функции.
12. Теорема о необходимых и достаточных условиях полноты систем булевых функций.
13. Теорема о числе функций полных систем.
14. Определение ДНФ. Понятие минимальной и кратчайшей ДНФ булевой функции. Тривиальный способ их нахождения.
15. Геометрическое представление булевых функций. Интервал, допустимый интервал, максимальный интервал. Покрытие множества единичных наборов булевой функции интервалами. Кратчайшее и минимальное покрытия. Сокращенная ДНФ.
16. Импликанта, простая импликанта, их свойства.
17. Матричное представление булевой функции в коде Грея. Визуально-матричный метод минимизации булевых функций.
18. Теорема Квайна о построении сокращенной ДНФ. Троичные векторы. Алгоритм Квайна–МакКласки.
19. Булева матрица и ее покрытия. Нахождение всех безызбыточных покрытий.
20. Теорема Блейка о построении сокращенной ДНФ булевой функции. Алгоритм Блейка.
21. Общая схема получения минимальных и кратчайших ДНФ.
22. Ортогональные конъюнкции и ортогональные ДНФ. Теорема о поглощении конъюнкции дизъюнктивной нормальной формой.
23. Теорема о сокращенной ДНФ монотонной функции.
24. Объединение и пересечение тупиковых и минимальных ДНФ.
25. Ядро ДНФ. Теорема Квайна о ядре и ее следствие.
26. Частичные булевы функции и их представления.
27. Реализация частичной функции. Импликанта и простая импликанта частичной функции. Сокращенная ДНФ.
28. Построение сокращенной ДНФ. Использование таблицы Квайна для получения кратчайших и минимальных ДНФ.
29. Визуально-матричный метод минимизации частичной функции.
30. Понятие о дискретном устройстве, комбинационном и последовательностном.
31. Анализ и синтез дискретных устройств.
32. Элементарные комбинационные устройства.
33. Синтез комбинационных устройств в базисе ДНФ.
34. Синтез комбинационных устройств в базисе НЕ И.
35. Синтез комбинационных устройств в базисе НЕ ИЛИ.
36. Определение автомата. Классификация автоматов.
37. Таблицы переходов-выходов и диаграммы переходов.
38. Триггеры.
39. Канонические уравнения и их получение из таблиц переходов-выходов.
40. Формальные языки и настроенные диаграммы.
41. Конечно-автоматные языки и их свойства.
42. Алфавитное кодирование. Однозначность кодирования.
43. Свойство префикса. Теорема.
44. Нетривиальное разложение кодов в схеме кодирования. Алгоритм проверки кодирования на однозначность.
45. Неравенство МакМилана. Теорема.
46. Теорема о существовании взаимно-однозначного кодирования, обладающего свойством префикса.
47. Понятие о кодах с минимальной избыточностью.
48. Дерево взаимно однозначного кодирования и операции на нем.
49. Насыщенное и приведенное кодовые деревья.
50. Алгоритм построения кода с минимальной избыточностью.
51. Алфавит исчисления высказываний.
52. Синтаксис исчисления высказываний.
53. Семантика исчисления высказываний.
54. Общезначимые, невыполнимые и нейтральные формулы.
55. Полная и частичная интерпретации. Модель. Дерево интерпретаций.
56. Проблема вывода. Ее сведение к анализу КНФ на невыполнимость.
57. Резольвентный метод анализа КНФ на невыполнимость. Метод Блейка.
58. Алфавит исчисления предикатов.
59. Синтаксис исчисления предикатов.
60. Семантика исчисления предикатов.
61. Проблема вывода.
62. Предваренная нормальная форма.
63. Сколемова форма.
Учебно-методическое обеспечение курса
a) Рекомендуемая литература (основная)
1. Яблонский С.В. Введение в дискретную математику. - М.:Наука, 1979. – 279 с.
2. Агибалов Г.П., Оранов А.М. Лекции по теории конечных автоматов. Томск: Изд. Том. ун-та, 1984. – 189 с.
3. Новиков Ф.А. Дискретная математика для программистов. - СПб.: Питер, 2000. – 304 с.
4. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. - М.: Наука, 1977. – 268 с.
5. Останин С.А., Матросова А.Ю. Функции алгебры логики: Учебное пособие. Изд. Том. ун-та, - 2004. – 36 с.
6. Останин С.А. Элементы теории графов: Учебное пособие. Изд. Том. ун-та, - 2005. – 38 с.
b) Рекомендуемая литература (дополнительная)
1. Судоплатов С.В., Овчинникова Е.В.Элементы дискретной математики. М.: ИНФРА-М; Новосибирск: Изд. НГТУ, - 2002.
Дата добавления: 2023-01-08; просмотров: 84; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!