кр спец. разд. матем.. Методические указания и контрольные задания по дисциплине Специальные разделы математики для студентов заочного факультета
 Скачать 0.51 Mb.
|
Федеральное агентство связи Федеральное государственное бюджетное образовательное учреждение высшего образования «Поволжский государственный университет телекоммуникаций и информатики» Кафедра математических и естественно-научных дисциплин Методические указания и контрольные задания по дисциплине «Специальные разделы математики» для студентов заочного факультета Оренбург, 2017 Программа зачета по специальным разделам математики. 1. Высказывания и операции над ними. Основные законы логики высказываний. Примеры. 2. Виды формул логики высказываний. Основные типы формул. Проблема разрешимости. Понятия, приводящие к СДНФ и СКНФ. Примеры. 3. СКНФ и СДНФ. Алгоритмы построения СКНФ и СДНФ. Примеры. 4. Контактные схемы. Примеры. 5. Исчисление высказываний. Аксиомы, правила вывода (подстановки и заключения). Примеры. 6. Связь исчисления высказываний с логикой высказываний. Свойства аксиом исчисления высказываний. 7. Выводимость формулы из произвольного списка формул исчисления высказываний. Теорема дедукции и ее следствия. Примеры. 8. Предикаты и операции над ними. Теоретико-множественный смысл предикатов. Примеры. 9. Формулы логики предикатов и их виды. Интерпретация формул логики предикатов. Примеры. 10. Равносильные формулы логики предикатов. Основные равносильности. 11. Предваренные нормальные формы (ПНФ). Приведение формул логики предикатов к ПНФ. Примеры. 12. Формальный язык первого порядка. Понятие ППФ (правильно построенная формула) и терм. Интерпретация формального языка первого порядка. Примеры. 13. Исчисление предикатов и его аксиомы. Основные правила исчисления предикатов. Примеры. 14. Какие способы записи конечных сумм вы знаете? 15. Какие суммы называются кратными? 16. Понятие рекуррентного соотношения. 17. Числа Фибоначчи, числа Каталана. 18. Запишите формулу Стирлинга. 19. Какая структура называется графом и мультиграфом? 20. Какие способы задания графа и мультиграфа вы знаете? 21. Сформулируйте теорему о сумме степеней вершин графа и ее следствие. 22. Дайте понятие Подграф. Путь, цепь, простая цепь, цикл, простой цикл. 23. Какие графы называются связными? 24. Как определить изоморфизм графов? 25. Эйлеровы графы. Критерий эйлеровости. 26. Приведите примеры гамильтоновых графов. 27. Дайте определение дерева. 28. Непланарность графов К5 и К3,3. 29. Раскраска вершин графа. Раскрашиваемость вершин планарного графа пятью красками. 30. Какие функции называются целочисленными? 31. Сформулируйте теорему Эйлера и ее следствие. 32. Законы булевой алгебры. Принцип двойственности. 33. ДНФ, КНФ. Алгоритмы построения СДНФ и СКНФ. 34. Булевы функции от 2-х и 3-х переменных. Многочлен Жегалкина. 35. Полином Жегалкина. Алгоритмы построения полинома Жегалкина. 36. Классы функций. Полнота системы булевых функций. Теорема Поста. 37. Минимизация булевых функций с помощью карт Карно. 38. Операции над множествами. Диаграммы Эйлера-Венна. Законы теории множеств. Декартово произведение множеств, его свойства. 39. Мощность множества. Счетные и несчетные множества. 40. Основы комбинаторики: правила суммы и произведения, перестановки, сочетания, размещения. 41. Рекуррентные соотношения. Числа Фибоначчи. 42. Неориентированные и ориентированные графы. Основные понятия теории неориентированных графов (степень вершины, смежные вершины, смежные ребра, изолированные вершины, кратные ребра). 43. Способы задания графов (диаграмма; функциональный; матрица смежности; матрица инцидентности). 44. Виды графов (простой, полный, правильный, двудольный). Подграф. Операции над графами. Изоморфизм графов. 45. Пути, циклы в графах. Связные и несвязные графы. Деревья. Лес. 46. Алгоритм нахождения числа каркасных деревьев. Дерево экономичности и его построение. 47. Коды и шифры. 48. Код исправляющий одну ошибку. 49. Код БЧХ. 50. Машина Тьюринга и нормальный алгоритм Маркова (Н.А.М.) Литература. ОСНОВНАЯ 1. Новиков, Ф.А. Дискретная математика для программиста/ Ф.А. Новиков. – СПб.: Питер, 2004.-368 с. 2. Белоусов, А.И., Ткачев, С.В., Дискретная математика/ А.И. Белоусов и др.. – М., Издательство МГТУ им. Н.Э.Баумана, 2001. –744 с. 3. Кузнецов, О.П. Дискретная математика для инженера/ О.П. Кузнецов. – М., Лань, 2004, 400 с. 4. Иванов, Б.Н. Дискретная математика. Алгоритмы и программы./Б.Н. Иванов – М., Лаборатория базовых знаний, 2001. –288 с. 5. Яблонский, С.В. "Введение в дискретную математику"/ Яблонский С.В., - М, Наука, 1986г. ДОПОЛНИТЕЛЬНАЯ 1. Евстигнеев, В. А. Применение теории графов в программировании/ В.А. Евстигнеев - М.: Наука, 1985. 2. Гаврилов, Г.П., Сапоженко, А.А. Задачи и упражнения по курсу дискретной математики/ Г.П. Гаврилов, А.А. Сапоженко. - М.: Физматлит, 2004. - 416 с. 3. Кузнецов, О.П., Адемсон-Вельский, Г.М. Дискретная математика для инженера/ О.П. Кузнецов, М. Адемсон-Вельский. – М: "Энергоатомиздат", 1988г. 4. Ершов, Д.Л., Палютин, Е.А. Математическая ложка/ ДЛ. Ершов, Е.А. Палютин. М.: Наука. - 1987г. 5. Зыков, А.А. Основы теории графов/ А.А. Зыков. - М.: Наука. - 1987г. 6. Сачков, В.Н. Введение в комбинаторные методы дискретной математики/ В.Н. Сачков.- М.: Наука. - 1982г. Контрольная работа. Номер Вашего варианта совпадает с последней цифрой номера Вашей зачетной книжки. Например, если последняя цифра номера Вашей зачетной книжки – 4, то Вы решаете задачи 1.4, 2.4, 3.4, 4.4. Если номер зачетной книжки заканчивается нулем, то Ваш вариант – 10. 1. Используя таблицы истинности, проверить эквивалентность булевых формул. Определить существенные и фиктивные переменные. 1.1. y x y x y x y x y x )) ( ( ) ( 1.2. ). ( ) ( )) ) (( ( ) ( x y y x x z y y x z y x 1.3. x z y x z y x z y x ) ( )) ( ( ) ) (( 1.4. ) ( ) ( ) ( z x y x z y x 1.5. ) ( ) ( ) ( z x y x z y x 1.6. x z x y x z y x )) ( ) (( ) ( 1.7. ) ( ) ( ) ( z x y x z y x 1.8. ) ( ) ( ) ( z x y x z y x 1.9. ) ( ) ( ) ( z x y x z y x 1.10. ) ( ) ( ) ( z x y x z y x 2. Для булевой функции, заданной вектором значений, определить: 1) СДНФ, 2) СКНФ, 3) полином Жегалкина, 4) МДФ, 5) МКФ. 2.1. (10110111). 2.4. (00111011). 2.7. (10110011). 2.2. (00110111). 2.5. (00110101). 2.8. (11101001). 2.3. (11101011). 2.6. (01101011). 2.9. (11100111). 2.10. (11001011). 3. Выяснить, является ли система функций A функционально полной. 3.1. zx yz xy y x y x xy A , , , 3.2. z y x yz z y x x A , ) ( , 3.3. 1 , , z y x y x xy A 3.4. 1 , 0 , , y x z y x A 3.5. y x z y x z y x x A ), ( ) ( , , 1 3.6. xz xy y x y x A , , , 0 3.7. yz z y x x A ) ( , , 0 3.8. yz x y x x z x xy A , 0 , , , 3.9. x y x y x z xy A , , 1 , 3.10. z y x z y z y x x A ), ( ) ( , 4. 1)Используя теорему о редукции, построить двоичный код с минимальной избыточностью для набора вероятностей Р, 2) построить код Фано: 4.1. Р=(0,3;0,2;0,15;0,1;0,08;0,07;0,05;0,05). 4.2. Р=(0,25;0,2;0,2;0,1;0,08;0,07;0,05;0,05). 4.3. Р=(0,3;0,18;0,17;0,1;0,08;0,07;0,05;0,05). 4.4. Р=(0,3;0,2;0,15;0,1;0,09;0,06;0,05;0,05). 4.5. Р=(0,25;0,2;0,15;0,1;0,08;0,08;0,08;0,06). 4.6. Р=(0,3;0,2;0,15;0,15;0,08;0,07;0,03;0,02). 4.7. Р=(0,3;0,25;0,15;0,1;0,05;0,05;0,05;0,05). 4.8. Р=(0,35;0,15;0,15;0,1;0,08;0,07;0,05;0,05). 4.9. Р=(0,3;0,2;0,1;0,1;0,1;0,1;0,05;0,05). 4.10. Р=(0,4;0,1;0,1;0,1;0,1;0,09;0,06;0,05). Методические указания к выполнению контрольной работы. Эквивалентность булевых функций. Булевы функции могут быть заданы либо с помощью таблиц истинности (единственным образом), либо с помощью логических формул (неединственным образом). Если таблицы истинности двух булевых формул совпадают, то эти формулы эквивалентны и определяют одну и ту же булеву функцию. Пример. Проверить эквивалентность булевых формул: z x y x z y x Решение. Построим таблицу истинности для функции z y x y x f , x y z z y z y x 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 Построим таблицу истинности для функции z x y x y x g , x y z y x z x z x y x 0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 0 1 0 1 1 1 1 0 1 0 0 1 1 1 1 1 1 Результирующие столбцы в таблицах истинности совпадают, следовательно, формулы эквивалентны. Существенные и фиктивные переменные. Переменная n i x i 1 булевой функции n i i i x x x x x f ,..., , , ,..., 1 1 1 называется фиктивной, если имеет место равенство n i i x x x x f ,..., , 0 , ,..., 1 1 1 = n i i x x x x f ,..., , 1 , ,..., 1 1 1 для любых значений переменных n i i x x x x ,..., , ,..., 1 1 1 . В противном случае переменная i x называется существенной. Наборы значений переменных в последнем равенстве называются соседними по переменной i x . Пример. Определить существенные и фиктивные переменные функции (11110011). Решение. Для удобства приведем таблицу истинности. x y z z y x f , , 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 Проверим, является ли переменная x существенной или фиктивной. Рассмотрим значения функции на наборах, соседних по переменной x : 0 , 0 , 1 0 , 0 , 0 0 0 , 0 , 1 , 1 0 , 0 , 0 f f f f . Значит, переменная x – существенная. Рассмотрим теперь значения функции на наборах, соседних по переменной y : 1 0 , 1 , 1 , 0 0 , 0 , 1 , 1 1 , 1 , 0 , 1 1 , 0 , 0 , 1 1 , 1 , 0 , 1 0 , 0 , 0 f f f f f f 0 , 1 , 1 0 , 0 , 1 f f Следовательно, переменная y – существенная. Рассмотрим теперь значения функции на наборах, соседних по переменной z : 1 1 , 1 , 1 , 1 0 , 1 , 1 , 0 1 , 0 , 1 , 0 0 , 0 , 1 , 1 1 , 1 , 0 , 1 0 , 1 , 0 , 1 1 , 0 , 0 , 1 0 , 0 , 0 f f f f f f f f На всех парах соседних по переменной z наборов значений переменных функция принимает разные значения, следовательно, переменная z – фиктивная. Представления булевых функций разложениями по переменным. Совершенная дизъюнктивная нормальная форма (СДНФ) для булевой функции n x x f ,..., 1 , не равной тождественно нулю, имеет вид: n n f n n n x x x x f 1 1 , , 1 1 1 : , , 1 ,..., , где символ x определяется следующим образом: 0 , x 1, если , если x x Алгоритм построения СДНФ. 1. Построить таблицу истинности данной булевой функции. 2. Каждому единичному значению булевой функции будет соответствовать элементарная конъюнкция n n x x x 2 1 2 1 , где n , , 2 1 – соответствующий набор значений переменных. В конъюнкции записываем i x , если 1 i , и i x , если 0 i . Конъюнкции соединяются знаком дизъюнкции Совершенная конъюнктивная нормальная форма (СКНФ) для булевой функции n x x f ,..., 1 , отличной от тождественной единицы, имеет вид: n n f n n n x x x x f 1 0 , , 1 1 1 : , , 1 ,..., , где символ x определяется следующим образом: 0 , x 1, если , если x x Алгоритм построения СДНФ. 1. Построить таблицу истинности данной булевой функции. 2. Каждому нулевому значению булевой функции будет соответствовать элементарная дизъюнкция n n x x x 2 1 2 1 , где n , , 2 1 – соответствующий набор значений переменных. В дизъюнкции записываем i x , если 0 i , и i x , если 1 i . Дизъюнкции соединяются знаком конъюнкции Всякая булева функция может быть представлена в виде полинома Жегалкина: n n n n n x x x a x x a x a x a a x x f n 2 1 1 2 2 1 1 1 1 0 1 ,..., , где 1 , 0 , , , , , 1 2 1 0 n a a a a n , где знак обозначает сумму по модулю 2. Алгоритм построения полинома Жегалкина. 1. Построить таблицу истинности данной булевой функции. 2. Каждому единичному значению булевой функции будет соответствовать конъюнкция n n x x x 2 1 2 1 , где n , , 2 1 – соответствующий набор значений переменных. Конъюнкция соединяется знаком 3. Заменить выражения i x по формуле 1 i i x x . Раскрыть скобки и привести подобные слагаемые по правилу: 0 x x Пример. Построить СДНФ, СКНФ и полином Жегалкина для функции (11110011). Решение. Таблица истинности данной булевой функции имеет вид: x y z z y x f , , 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 СДНФ имеет вид: z y x z y x z y x z y x z y x z y x z y x f , , СКНФ имеет вид: z y x z y x z y x f , , Построим полином Жегалкина: 1 1 1 1 1 1 1 1 1 1 1 , , x xy xyz xy xyz yz xyz y yz xy xyz z yz xz xyz y x xy z xz yz xyz xyz z xy yz x z y x z y x z y x xyz z xy yz x z y x z y x z y x z y x f Минимизация логических функций. Процесс упрощения формул с целью получить минимальную форму представления логической функции называют минимизацией логических функций. Для минимизации логических функций от небольшого числа переменных используют запись таблиц истинности в виде карт Карно. Ниже показаны примеры условного размещения переменных на минимизирующих картах для трех и четырех переменных. 2 1 x x 3 x 00 01 11 10 0 0 , 0 , 0 f 0 , 1 , 0 f 0 , 1 , 1 f 0 , 0 , 1 f 1 1 , 0 , 0 f 1 , 1 , 0 f 1 , 1 , 1 f 1 , 0 , 1 f 2 1 x x 4 3 x x 00 01 11 10 00 0 , 0 , 0 , 0 f 0 , 0 , 1 , 0 f 0 , 0 , 1 , 1 f 0 , 0 , 0 , 1 f 01 1 , 0 , 0 , 0 f 1 , 0 , 1 , 0 f 1 , 0 , 1 , 1 f 1 , 0 , 0 , 1 f 11 1 , 1 , 0 , 0 f 1 , 1 , 1 , 0 f 1 , 1 , 1 , 1 f 1 , 1 , 0 , 1 f 10 0 , 1 , 0 , 0 f 0 , 1 , 1 , 0 f 0 , 1 , 1 , 1 f 0 , 1 , 0 , 1 f В каждой клетке таблицы условно указан набор значений переменных, который складывается из кода столбца и кода строки. При этом коды двух соседних рядов могут отличаться только в одной позиции, но соседними нужно считать первый и последний ряды. Процесс минимизации СДНФ представляет собой склеивание кодов наборов значений переменных для каждого сплошного участка из единичных значений функции, причем, количество единиц на таком сплошном участке должно быть степенью двойки. Пример. Построить МДФ для функции (11110011). Решение. Заполним карту Карно 2 1 x x 3 x 00 01 11 10 0 1 1 1 0 1 1 1 1 0 Найдем МДФ. Первый контур состоит из элементов первых двух столбцов, второй – из элементов второго и третьего столбцов. Каждый из выделенных контуров содержит по четыре единицы. Для первого контура склеятся переменные 3 2 x x , получится 1 x , для второго контура склеятся переменные 3 1 x x , получится 2 x . Следовательно, МДФ 2 1 x x Аналогично получим для МКФ 2 1 x x Замкнутые классы функций. Обозначим через n P 2 – множество всех булевых функций n переменных. 1. Класс 0 T функций, сохраняющих нуль. 0 0 , , 0 , 0 2 0 f n P f T 2. Класс 1 T функций, сохраняющих единицу. 1 1 , , 1 , 1 2 1 f n P f T 3. Класс S самодвойственных функций составляют функции, на противоположных наборах принимающие противоположные значения: n n f f n P f S , , , , , , 2 1 2 1 2 4. Класс M монотонных функций. Для двоичных векторов n n , , , 2 1 и n n , , , 2 1 , где 1 , 0 , i i , n i , , 2 , 1 , вводится следующее отношение частичного порядка. Считается, что n n , если i i для n i , , 2 , 1 . Класс M определяется следующим образом: n n f f n P f M 2 , если n n 5. Класс линейных функций L составляют функции, которые представляются полиномом Жегалкина первой степени. Проверка принадлежности булевой функции замкнутым классам 1-4 осуществляется по таблице истинности. Проверка принадлежности булевой функции классу L осуществляется путем построения полинома Жегалкина. Функциональная полнота. Система булевых функций называется функционально полной, если любая булева функция представляется суперпозицией функций данной системы. Теорема Поста. Система булевых функций функционально полна, если она не содержится целиком ни в одном из пяти замкнутых классов. Для проверки функциональной полноты системы булевых функций строится так называемая таблица Поста, в которой отмечается принадлежность функций замкнутым классам. Если в каждом столбце таблицы Поста есть хотя бы один минус, система полна, в противном случае – нет. Пример. Проверить функциональную полноту системы булевых функций 1 , , y x y x A Решение. Проверим принадлежность замкнутым классам функции y x y x f , Построим таблицу истинности данной функции. x y y x 0 0 0 0 1 1 1 0 1 1 1 0 0 0 , 0 f , следовательно, 0 , T y x f 0 1 , 1 f , следовательно, 1 , T y x f 1 , 1 0 , 0 f f , следовательно, S y x f , 1 , 1 0 1 0 , 1 f f , следовательно, M y x f , Функция представляет собой полином Жегалкина первой степени, следовательно, L y x f , Результаты можно занести в первую строку таблицы Поста. Остальные функции исследуются аналогично. Построим таблицу Поста. 0 T 1 T S M L y x + - - - + y x + + - + - 1 - + - + + В каждом столбце таблицы имеется минус, следовательно, система A функционально полна. Минимальная функционально полная система функций называется базисом пространства булевых функций. Коды с минимальной избыточностью. Оптимальное кодирование Хаффмена. Предположим, что задан алфавит 2 , , 1 r a a A r и набор положительных вероятностей r i i r p p p 1 1 1 , , появлений символов r a a , , 1 в сообщениях. Пусть далее задан алфавит 2 , , 1 q b b B q . Тогда можно построить целый ряд схем алфавитного кодирования , , : 1 1 r r b a b a обладающих свойством взаимной однозначности. Для каждой схемы можно ввести среднюю длину ср l , определяемую как математическое ожидание длины элементарного кода. Пусть ср * inf l l , где нижняя грань берется по всем схемам , обеспечивающим свойство взаимной однозначности. Коды, определяемые схемой с * ср l l , называются кодами с минимальной избыточностью или оптимальными кодами Хаффмена. Положим теперь, что источник сообщений S выдает сообщения в алфавите r a a A , , 1 и для вероятностей r p p , , 1 появления символов r a a , , 1 в сообщениях справедливо соотношение 0 2 1 r p p p . Рассмотрим источник S , полученный из S отождествлением символов 1 r a и r a . Он выдает символы 2 1 , , r a a с прежними вероятностями 2 1 , , r p p , а новый символ a – с вероятностью r r p p p 1 . Такой источник S называется редуцированным. 0,3 00 0,48 0,18 01 0,14 100 0,28 0,14 101 0,11 110 0,52 0,06 1110 0,24 0,13 0,05 11110 0,07 0,02 11111 Теорема (о редукции). Если префиксный код b b b b r , , , , 2 2 1 для редуцированного источника S является оптимальным, то и префиксный код 1 , 0 , , , , 2 2 1 b b b b b r для исходного источника S , построенный указанным способом, также является оптимальным. Теорема дает алгоритм построения оптимальных кодов. В этом алгоритме сначала производится свертывание искомого кода в соответствии с правилами перехода от источника S к редуцированному источнику S . В процессе свертывания один за другим получаются все более простые (короткие) коды и в конце концов – код из однобуквенных элементарных кодов. Фактически это означает преобразование набора вероятностей до тех пор, пока не получится набор вероятностей (из двух чисел), для которого оптимальный код находится тривиально. После этого найденный код развертывается в соответствии с теоремой о редукции в последовательность оптимальных кодов, которая заканчивается искомым кодом. Пример. Построить оптимальный код для набора вероятностей 05 , 0 ; 05 , 0 ; 1 , 0 ; 15 , 0 ; 25 , 0 ; 4 , 0 P Решение. Процесс построения оптимального кода представлен в таблице A P I P II P III P IV P IV III II I 1 a 2 a 3 a 4 a 5 a 6 a 0,4 0,4 0,4 0,4 0,6 0 1 1 1 1 0,25 0,25 0,25 0,35 0,4 1 00 01 01 01 0,15 0,15 0,2 0,25 01 000 001 001 0,1 0,1 0,15 001 0000 0000 0,05 0,1 0001 00010 0,05 00011 Рассмотрим метод построения кодов, близких к оптимальному, принадлежащий Фано. Он заключается в следующем. Упорядоченный (в порядке убывания вероятностей) список букв делится на две (последовательные) части так, чтобы суммы вероятностей входящих в них букв как можно меньше отличались друг от друга. Буквам из первой части приписывается символ 0, а буквам из второй части – символ 1. Далее точно так же поступают с каждой из полученных частей, если она содержит по крайней мере две буквы. Этот дихотомический процесс продолжается до тех пор, пока весь список не разобьется на части, содержащие по одной букве. Каждой букве ставится в соответствии последовательность символов, приписанных в результате этого процесса данной букве. Легко видеть, что полученный код является префиксным. Пример. Построить код Фано для данного набора вероятностей 02 , 0 ; 05 , 0 ; 06 , 0 ; 11 , 0 ; 14 , 0 ; 14 , 0 ; 18 , 0 ; 3 , 0 P Решение. Процесс построения кода Фано представлен ниже: P 1 a 0,3 2 a 0,18 3 a 0,14 4 a 0,14 5 a 0,11 6 a 0,06 7 a 0,05 8 a 0,02 |