- •Санкт-Петербургский государственный морской технический университет
- •2. Основы теории графов
- •4. Список использованной литературы
- •Задание 3.
- •4. Написать таблицу значений функции. Найти фиктивные переменные для данной функции. Преобразовать данную формулу в эквивалентную ей, но не содержащую фиктивных переменных.
- •1.4. Совершенные дизъюнктивные и конъюнктивные формы булевых функций. Двойственные функции.
- •6. Проверить, являются ли равносильными формулы a и b двумя способами а) составлением таблиц значений; б) приведением формул к сднф или скнф с помощью эквивалентных преобразований
- •1.5. Построение и упрощение формул, задаваемых различными схемами.
- •7. Построить формулы, задаваемые данными схемами. Упростить их. Построить схемы, соответствующие упрощенным формулам.
- •8. Представить функцию в виде дизъюнктивного разложения по переменным, коэффициенты разложения (функции двух переменных) представить соответствующими формулами над множеством связок|,
- •9. С помощью сднф установить, являются ли равносильными следующие днф:
- •1.7. Минимизация булевых функций методом Квайна–Мак-Класки и матричным методом Карно.
- •10. Минимизировать функцию методом Квайна-Мак-Класки и графическим методом Карно. Найти индекс простоты функции.
- •1. Метод Квайна-Мак-Класки.
- •1.8. Представление булевых функций полиномами Жегалкина.
- •11. Представить функцию полиномом Жегалкина.
- •1.9. Проверка принадлежности булевых функций классам Поста. Полные системы булевых функций. Базисы. Задание 12. Проверить, принадлежат ли функции ик классамT0, t1, l, s, m.
- •14. Являются ли полными следующие системы булевых функций Какие из указанных систем образуют базис?
- •1.10. Представление булевых функций в базисе Шеффера и в базисе Вебба .
- •15. Записать функцию в базисе «не и» и в базисе «не или».
- •1.11. Производные булевой функции.
- •16. Найти частные производные булевой функции по каждой переменной и их вес, если .
- •18. Заданы графы g1 и g2. Найти Для графанайти матрицы смежности, инцидентности, достижимости, контрдостижимости, сильных компонент и все маршруты длины 2, исходящие из вершины 1.
- •2.4 Матрицы фундаментальных циклов и матрицы фундаментальных разрезов графа.
- •3.Элементы теории кодирования.
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
Санкт-Петербургский государственный морской технический университет
Кафедра математики
РЕШЕНИЕ НЕКОТОРЫХ ЗАДАЧ БУЛЕВОЙ АЛГЕБРЫ,
ТЕОРИИ ГРАФОВ И ТЕОРИИ КОДИРОВАНИЯ
Курсовая работа
по дискретной математике
Выполнил:
студент группы 2250
Разживин Никита Сергеевич
Руководитель:
доцент кафедры математики
Володичева Маргарита Ивановна.
Дата защиты:
Оценка за курсовую работу
Санкт-Петербург 2013
Содержание.
1. Алгебра логики
1.1. Перевод чисел из одной системы счисления в другую.
1.2. Различные формы задания булевых функций. Переход от одной формы задания к другой. Карта Карно.
1.3. Суперпозиция булевых функций. Существенные и несущественные переменные.
1.4. Совершенные дизъюнктивные и конъюнктивные формы булевых функций. Двойственные функции.
1.5. Построение и упрощение формул, задаваемых различными схемами.
1.6. Дизъюнктивное разложение булевых функций по совокупности переменных.
1.7. Минимизация булевых функций методом Квайна–Мак-Класки и матричным методом Карно.
1.8. Представление булевых функций полиномами Жегалкина.
1.9. Проверка принадлежности булевых функций классам Поста. Полные системы булевых функций. Базисы.
1.10. Представление булевых функций в базисе Шеффера и в базисе Вебба .
1.11. Производные булевой функции.
2. Основы теории графов
2.1. Операции над графами.
2.2. Матрицы смежности и инцидентности.
2.3. Матрицы достижимости, контрдостижимости, сильных компонент.
2.4 Матрицы фундаментальных циклов и матрицы фундаментальных разрезов графа.
2.5. Эйлеровы и планарные графы.
2.6. Нахождение кратчайших маршрутов для взвешенных графов с помощью алгоритма Форда–Беллмана и алгоритма Дейкстры.
3.Элементы теории кодирования.
3.1.Построение плоского дерева по его коду.
3.2. Построение кодового дерева для заданной схемы алфавитного кодирования.
3.3. Построение оптимального кодового дерева Хаффмена и кодовой схемы для заданных алфавита сообщений и кодирующего алфавита.
3.4. Декодирование кодовых слов, построенных методом Хэмминга и содержащих ошибки не более чем в одном разряде.
4. Список использованной литературы
1.Алгебра логики.
1 Перевод чисел из одной системы счисления в другую.
Задание 1. Перевод числа из одной системы счисления в другую.
Различные формы задания булевых функций. Переход от одной формы задания к другой. Карта Карно.
Задание 2. Построить таблицы значений для функций.
Вычисления с помощью Wolfram Mathematica:
- следование
! - отрицание
- штрих Шеффера
- сложение по модулю 2
- умножение
x |
y |
f1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
x |
y |
z | |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |