Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
1.1. Объект изучения — дискретная математика.
1.2. Предмет изучения — логика высказываний, теория множеств, алгоритмы и методы логических алгебр, основы комбинаторики, теория автоматов, основы теории информации и кодирования, алгоритмы на графах, основы общей алгебры.
1.3. Целью обучения является овладение основами математической логики, основами алгебры логики, методами формализации записи сложных выражений, методами минимизации логических выражений, операциями над множествами, методами оптимизации на графах, аксиомами и правилами вывода, общей алгебры, комбинаторики; овладение методами минимизация состояний конечного и частичного автоматов, теории кодирования информации, алгоритмами оптимизации на графах.
1.4. Задачи дисциплины
1.4.1. В результате изучения курса «Дискретная математика» студенты должны знать:
— основные положения алгебры множеств, понятие двойственности, типы соответствий, отношения эквивалентности, порядка и толерантности;
— законы алгебры логики, минимизацию логических выражений, способы представления логических функций, понятия полноты и замкнутости логических систем;
— аксиомы и правила вывода для исчисления высказываний;
— основные формулы комбинаторики;
— основные определения теории графов, способы задания графов, изоморфизм и гомеоморфизм графов;
— некоторые оптимизационные алгоритмы на графах;
— основные определения теории абстрактных автоматов Мили и Мура;
— классификацию основных алгоритмов сжатия и кодирования информации, основные положения теории информации и кодирования;
— основы общей алгебры: группы, подгруппы, кольца поля;
— основы модулярной арифметики.
1.4.2. В результате изучения курса «Дискретная математика» студенты должны уметь:
— выполнять операции над множествами, пользоваться тождественными преобразованиями над множествами, представлять множества кругами Эйлера, определять тип соответствия;
— представлять логические выражения в нормальных формах, минимизировать логические формулы табличными методами и с помощью карт Карно, выбирать функционально полную систему логических функций;
— решать задачи комбинаторного типа;
— оперировать матрицами инцидентности и смежности, выполнять оптимизацию на графах в рамках изученных алгоритмов;
— построить граф абстрактной модели полного автомата (Мили или Мура) и минимизировать его, найти покрывающий автомат частичного автомата;
— составлять кодировочные таблицы Хаффмена и Фано, находить цену кода, кодировать информацию методами LZW, RLE, BWT;
— определять место алгебраической системы в классификационной таблице;
1.4.3. В результате изучения курса «Дискретная математика» студенты должны иметь представление о:
— задачах математической логики;
— двойственности и самодвойственности, булеане множества, о разбиениях и покрытиях, об отношениях в теории множеств, прямом произведении множеств, графах соответствий;
— суперпозиции функций алгебры логики;
— правилах формального вывода в теории логического вывода;
— композиции и декомпозиции автоматов, синтезе автоматных сетей;
— алгоритмах сжатия информации;
— модулярной арифметике.
1.5. Связь «Дискретной математики» с другими науками. Изучение данной дисциплины базируется на знаниях и навыках, полученных по математике в средней школе, на дисциплине «Введение в специальность» и является основой для дисциплин «Программирование», «Структуры данных», «Системный анализ», «Компьютерная электроника и компьютерная системотехника», «Прикладная теория цифровых автоматов».
Ознакомление с терминологией. Основные логические операции и их свойства. Равносильность высказываний. Закон контрапозиции. Тавтологии и противоречия. Понятие логического следствия. Основные законы математической логики.
Понятие предикативной переменной и предиката. Кванторы. Формализация записей с помощью кванторов. Операции, уменьшающие местность предикатов. Доказательство правильности метода математической индукции.
Множества и элементы. Множества и подмножества. Мощность множества. Способы задания множеств. Операции на множествах. Системы множеств (разбиения и покрытия). Булеан множества (мощность булеана множества). Алгебра множеств. Принцип двойственности. Понятие вектора. Прямое произведение множеств. Понятие алфавита. Понятие отношения. Соответствие (типы соответствий).
Логические переменные и логические функции. Способы задания логических функций. Существенные и фиктивные переменные. Основные логические функции. Суперпозиция формулы логических функций. Формула Шеннона.
Эквивалентные преобразования и упрощения логических формул. Двойственность. ДНФ, интервалы и покрытия. Минимизация дизъюнктивных форм логических функций. Частичные булевы функции и их минимизация. Алгебра Жегалкина (полином Жегалкина). Полнота и замкнутость систем функций.
Понятие группы. Кольца и поля. Классификация алгебраических систем. Элементы модулярной арифметики.
Основные определения: вершины, ребра, дуги, инцидентность, смежность, связность, способы задания графа, цикличность, взвешенность, степень, полнота, двудольность, изоморфизм, гомеоморфизм, части графа, клика графа, планарность, деревья, способы задания дерева (алгоритм построения символа дерева, алгоритм восстановления дерева из его символа), дерево графа, алгоритм порождения полных подграфов (нахождение клик графа), алгоритм поиска в глубину для топологической сортировки.
Алгоритмы оптимизации на графах: нахождение минимального остовного дерева графа (алгоритм Прима), нахождение кратчайшего расстояния от заданной вершины во все достижимые (алгоритм Дейкстры), нахождение кратчайшего расстояния от заданной вершины в заданную (метод ветвей и границ), нахождение максимального потока в сети (алгоритм пометок Форда и Фалкерсона), задача о максимальном паросочетании в двудольном графе.
Абстрактные автоматы. Состояния автоматов. Условия автоматности. Автоматы Мили и Мура. Построение эквивалентных автоматов. Понятие k–эквивалентности. Минимизация состояний полных автоматов. Частичные автоматы. Минимизация частичных автоматов (нахождение покрывающего автомата). Композиция и декомпозиция автоматов. Последовательные и параллельные автоматы.
Проблема кодирования и декодирования. Разделимые схемы. Префиксные схемы. Алфавитное кодирование. Цена кодирования. Экономное кодирование Фано. Оптимальное кодирвание Хаффмена. Классификация алгоритмов кодирования (сжатия): алфавитное, групповое, словарное, адаптивное, полуадаптивное, неадаптивное. Примеры алгоритмов кодирования: группового — RLE, словарного — LZW. Прямое и обратное преобразование BWT.
Формальные математические теории или исчисления. Правило построения исчисления высказываний.
Построение таблиц истинности. Доказательство эквивалентности выражений. Определение логического следствия.
Формализация записей с помощью кванторов.
Операции на множествах. Алгебра множеств. Тождественные преобразования. Определение типа соответствий.
Решение и составление задач на правила и формулы комбинаторики.
Способы задания логических функций. Нахождение существенных и фиктивных переменных. Определение суперпозиций формул логических функций. Разложение по формуле Шеннона. Эквивалентные преобразования и упрощения логических формул. Определение двойственных функций. Нахождение сокращенной ДНФ методами Квайна Мак-Класки и Блейка-Порецкого. Нахождение тупиковых ДНФ методом Петрика, определение ядровых импликант. Минимизация частичных булевых функций. Построение полинома Жегалкина различными способами. Понятия полноты и замкнутости системы логических функций.
Понятие группы. Кольца и поля. Классификация алгебраических систем. Элементы модулярной арифметики.
Основные определения: и способы задания графа. Нахождение частей графа, определение планарности графа. Маршруты в графе.
Построения символа дерева и восстановления дерева из его символа, дерево графа.
Алгоритм порождения полных подграфов (нахождение клик графа), алгоритм поиска в глубину для топологической сортировки.
Нахождение минимального остовного дерева графа (алгоритм Прима).
Нахождение кратчайшего расстояния от заданной вершины во все достижимые (алгоритм Дейкстры).
Нахождение кратчайшего расстояния от заданной вершины в заданную (метод ветвей и границ).
Нахождение максимального потока в сети (алгоритм пометок Форда и Фалкерсона).
Задача о максимальном паросочетании в двудольном графе.
Построение автоматов. Преобразование автомата Мили в автомат Мура и наоборот. Минимизация состояний полных автоматов.
Частичные автоматы. Минимизация частичных автоматов (нахождение покрывающего автомата).
Построение кодировочной таблицы алгоритмом Фано и алгоритмом Хаффмена по заданной (найденной) частоте встречаемости символов. Нахождение цены кода.
Кодирование с помощью RLE. Кодирование с помощью — LZW.
Прямое и обратное преобразование BWT.
1. Алгебра множеств. Тождественные преобразования (4 часа) [4, стр. 45].
2. Булева алгебра и теория множеств (2 часа) [3, стр. 23].
3. Конъюнктивные нормальные формы (2 часа) [3, стр. 50].
4. Выполнение заданий по темам практических занятий (44 часа).
5. Выполнение итогового домашнего задания № 1 — триместр 1.1 (18 часов).
6. Выполнение итогового домашнего задания № 2 — триместр 1.2 (26 часов).
I.1. Для данной в виде формулы (F1) логической функции четырех переменных построить таблицу истинности (получить СДНФ). Начертить схему исходной логической функции.
2. Данную логическую функцию (F1) преобразовать в булеву функцию (F2) и получить таблицу истинности аналитически.
3. Получить сокращенную ДНФ методом Квайна Мак-Класки.
4. Получить сокращенную ДНФ методом Блейка-Порецкого.
5. Найти все тупиковые ДНФ методом Петрика. Выделить минимальную ДНФ.
6. Минимизировать исходную логическую функцию с помощью карты Карно.
7. Начертить схему полученной минимизированной функции.
8. Найти минимальную КНФ для исходной логической функции.
II. Минимизировать данную, частично определенную булеву функцию от четырех переменных.
1. Начертить данный граф без пересечения дуг (по возможности).
2. Для заданного графа построить минимальное остовное дерево — МОД (продемонстрировать алгоритм Прима). Направление дуг не учитывать, т. е. считаем, что задан неориентированный граф.
3. Для полученного дерева найти его символ. Восстановить дерево по символу.
4. Для заданного графа продемонстрировать алгоритм Дейкстры, т. е. найти кратчайшие расстояния из заданной вершины во все остальные алгоритмом Дейкстры (заданная вершина указана). Направление дуг учитывать, т. е. задан орграф.
5. Для заданного графа продемонстрировать МВГ (метод ветвей и границ), т. е. Построить дерево решений для нахождения кратчайшего расстояния из заданной вершины в заданную с помощью МВГ (заданные вершины указаны). Указать критерии отсечения. Направление дуг учитывать, т. е. задан орграф.
1. Начертить данный граф без пересечения дуг (по возможности).
2. Осуществить ТС (топологическую сортировку) методом «поиск в глубину». Отмечать время начала обработки вершины, и — время окончания обработки вершины.
3. Начертить отсортированный граф с временем обработки вершин.
I. Построить автомат, согласно варианта:
— указать входной алфавит;
— указать выходной алфавит;
— указать функции перехода и выхода — таблично;
— начертить диаграмму автомата.
2. Минимизировать число состояний, полученного автомата, используя k-эквивалентные разбиения при помощи таблиц.
3. Начертить диаграмму минимизированного автомата
4. Написать программу, реализующую действия данного автомата.
3. Представьте в предикативной форме следующие суждения:
а) ни один судья несправедлив;
б) некоторые судьи добры, но несправедливы.
Предикаты определить на множестве людей, ввести признаки — «быть судьей», «быть добрым» и «быть справедливым».
4. Получить СКНФ формулы:
5. Получить Сокр.ДНФ формулы методом Квайна (Мак-Класки):
6. Доказать равенство:
(XY)(XZ) X=XYZ
7. Является ли функция G логическим следствием функции H, если:
8. Выразить операцию «объединение» через операции «симметрическая разность» и «пересечение».
9. Методом Петрика найти МДНФ из сокращенной ДНФ:
10. В отделе научно-исследовательского института работают несколько человек, причем каждый из них знает хотя бы один иностранный язык, 6 человек знают английский, 6 — немецкий, 7 — французский, 4 знают английский и немецкий, 3 — немецкий в французский, 2 — французский и английский, 1 человек знает все три языка. Сколько человек работает в отделе? Сколько из них знают только английский язык? Только французский? Сколько человек знает ровно 1 язык? Проиллюстрировать решение кругами Эйлера.
11. Найти число способов распределения 28-ти человек в группы по 3 и 5 человек.
12. Взвешенный неориентированный граф задан списком ребер (AD-2, AF-5, AG-4, BC-1, BE-2, BF-5, BG-1, CD-3, CE-2, CG-4, DE-1, DH-1, FG-3, FH-4, GH-1). Показать на данном графе алгоритм нахождения МОД.
13. Взвешенный ориентированный граф задан списком ребер (AD-1, AС-2, AВ-5, BF-2, CB-1, CF-2, CE-3, DE-1, DC-4, FE-4). Найти кратчайшие пути из вершины А во все остальные алгоритмом Дейкстры.
14. Взвешенный ориентированный граф задан списком ребер (AD-3, AС-1, AВ-1, BF-2, CB-4, CF-1, CE-1, DE-3, DC-1, EF-5). Найти кратчайшие пути из вершины А в вершину F методом «ветвей и границ».
15. Восстановить деревья по символам: (A, A, B, A,C, D),
(A, C, B, D, A, Н), (A, B, A, C, D, D).
16. Построить и минимизировать, если можно, автомат Мура с входным алфавитом {"а", "b", "*", " "}, который считает все слова, начинающиеся на b и заканчивающиеся на а.
17. Построить и минимизировать, если можно, автомат Мили, который допускает все слова длиной три символа из алфавита {"1", "2", "3", "0"} с суммой элементов больше 3.
18. Дана строка текста L = "ккннаа", преобразованного алгоритмом BWT и i = 3. Найти исходную строку текста. Провести прямое преобразование BWT.
19. Построить кодировочные таблицы с помощью алгоритмов Хаффмана и Фано для следующего текста: "НА МЕЛИ МЫ НАЛИМА ЛОВИЛИ.". Сравнить и пояснить результаты.
20. Дана строка текста L = "ааааа bbb aabbaaаа aaa bbb ccc". Сжать её с помощью алгоритма LZW и RLE. Сравнить и пояснить результаты.
21. Запишите таблицы сложения и умножения класса вычетов по модулю 5. Определите симметричные элементы для обеих таблиц.
Учебную программу дисциплины разработала
старший преподаватель кафедры 503 Холодная З.Б.