Сборник задач по дискретной математике (для практических занятий в группах)

Description

В сборнике отражено содержание пяти разделов дискретной математики, таких как теория множеств, булева алгебра логики, теория конечных автоматов, комбинаторика и теория графов, изложенных в учебном пособии Ю. П. Шевелева «Дискретная математика» (СПб.: Изд-во «Лань», 2008). Для данного сборника это пособие является базовым. Однако базовым может быть и любое другое учебное пособие, где соответствующие темы рассматриваются достаточно полно. В сборнике 14 глав. Каждая глава состоит из нескольких тем (от 2 до 8). Общее число тем во всех 14 главах равно 54. По каждой теме приведено 50 дидактически эквивалентных заданий. Даны образцы их выполнения. Пятидесяти вариантов заданий достаточно для того, чтобы проводить аудиторные занятия в группах и выдавать индивидуальные задания для самостоятельной работы во внеаудиторное время. Всего в сборнике 7450 задач и 112 вопросов. Предусмотрено два вида контроля: автоматизированный и при помощи открытых ответов (они приведены ко всем задачам и вопросам). ПРЕДИСЛОВИЕ 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ 1.1. ОСНОВНЫЕ ОПЕРАЦИИ НАД МНОЖЕСТВАМИ 1.2. ПОДМНОЖЕСТВА 1.3. ДИАГРАММЫ ВЕННА 1.4. ОТНОШЕНИЯ ВКЛЮЧЕНИЯ 2. БУЛЕВЫ ФУНКЦИИ 2.1. НОРМАЛЬНЫЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ 2.2. РАЗЛОЖЕНИЕ БУЛЕВЫХ ФОРМУЛ ПО ТЕОРЕМЕ ШЕННОНА 2.3. СОВЕРШЕННЫЕ ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ 2.4. МЕТОД КВАЙНА. СОКРАЩЕННЫЕ ДНФ 2.5. МЕТОД ПЕТРИКА 2.6. СОКРАЩЕННЫЕ КНФ 3. ПРИМЕНЕНИЕ КАРТ ВЕЙЧА ДЛЯ МИНИМИЗАЦИИ БУЛЕВЫХ ФОРМУЛ 3.1. МИНИМИЗАЦИЯВ КЛАССЕ ДНФ БУЛЕВЫХ ФУНКЦИЙ, ЗАДАННЫХ В СДНФ 3.2. МИНИМИЗАЦИЯ В КЛАССЕ КНФ БУЛЕВЫХ ФУНКЦИЙ, ЗАДАННЫХ В СДНФ 3.3. МИНИМИЗАЦИЯ В КЛАССЕ НОРМАЛЬНЫХ ФОРМ 3.4. ДНФ, КНФ И ФОРМЫ ВЫСШИХ ПОРЯДКОВ 3.5. МИНИМИЗАЦИЯ В КЛАССЕ ДНФ С УЧЕТОМ НЕОПРЕДЕЛЕННЫХ СОСТОЯНИЙ 3.6. МИНИМИЗАЦИЯ В КЛАССЕ КНФ С УЧЕТОМ НЕОПРЕДЕЛЕННЫХ СОСТОЯНИЙ 4. СИММЕТРИЧЕСКИЕ БУЛЕВЫ ФУНКЦИИ 4.1. РАСПОЗНАВАНИЕ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ 4.2. ОПЕРАЦИИ НАД СИММЕТРИЧЕСКИМИ ФУНКЦИЯМИ 5. АЛГЕБРА ЖЕГАЛКИНА 5.1. ОПЕРАЦИЯ «НЕРАВНОЗНАЧНО» (СУММА ПО МОДУЛЮ 2) 5.2. ПРЕДСТАВЛЕНИЕ БУЛЕВЫХ ФОРМУЛ В ВИДЕ ПОЛИНОМА ЖЕГАЛКИНА 5.3. ПРЕДСТАВЛЕНИЕ ПОЛИНОМА ЖЕГАЛКИНА В МИНИМАЛЬНОЙ ДНФ 6. ОПЕРАЦИЯ ИМПЛИКАЦИИ 6.1. ПРЕОБРАЗОВАНИЕ ФОРМУЛ, СОДЕРЖАЩИХ ОПЕРАЦИЮ ИМПЛИКАЦИИ 6.2. ТАВТОЛОГИИ 7. БУЛЕВЫ ДИФФЕРЕНЦИАЛЬНОЕ И ИНТЕГРАЛЬНОЕ ИСЧИСЛЕНИЯ 7.1. ОСТАТОЧНЫЕ ФУНКЦИИ 7.2. ДИФФЕРЕНЦИРОВАНИЕ БУЛЕВЫХ ФУНКЦИЙ ПОДСТАНОВКОЙ НАБОРОВ ЗНАЧЕНИЙ ПЕРЕМЕННЫХ 7.3. АНАЛИТИЧЕСКОЕ ДИФФЕРЕНЦИРОВАНИЕ БУЛЕВЫХ ФУНКЦИЙ 7.4. ИНТЕГРИРОВАНИЕ БУЛЕВЫХ ФУНКЦИЙ 8. ФУНКЦИОНАЛЬНАЯ ПОЛНОТА СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ (ТЕОРЕМА ПОСТА) 8.1. ФУНКЦИОНАЛЬНО ЗАМКНУТЫЕ КЛАССЫ БУЛЕВЫХ ФУНКЦИЙ 8.2. ФУНКЦИОНАЛЬНО ПОЛНЫЕ СИСТЕМЫ 9. ЧИСЛОВОЕ ПРЕДСТАВЛЕНИЕ БУЛЕВЫХ ФУНКЦИЙ 9.1. ИЗОБРАЖАЮЩИЕ ЧИСЛА БУЛЕВЫХ ФУНКЦИЙ 9.2. МИНИМИЗАЦИЯ В КЛАССЕ ДНФ БУЛЕВЫХ ФУНКЦИЙ, ЗАДАННЫХ ИЗОБРАЖАЮЩИМИ ЧИСЛАМИ 9.3. РЕШЕНИЕ БУЛЕВЫХ УРАВНЕНИЙ С ПОМОЩЬЮ ИЗОБРАЖАЮЩИХ ЧИСЕЛ 10. ПОРОГОВЫЕ ФУНКЦИИ 10.1. ПРЕДСТАВЛЕНИЕ ПОРОГОВЫХ ФУНКЦИЙ В ВИДЕ ДНФ 10.2. ПРЕДСТАВЛЕНИЕ ПОРОГОВЫХ ФУНКЦИЙ В ВИДЕ КНФ 11. КОМБИНАЦИОННЫЕ СХЕМЫ 11.1. ДИОДНО-РЕЗИСТОРНЫЕ СХЕМЫ — ОСНОВА ЛОГИЧЕСКИХ ЭЛЕМЕНТОВ 11.2. СИНТЕЗ КОМБИНАЦИОННЫХ СХЕМ 11.3. СИНТЕЗ КОМБИНАЦИОННОГО ПРЕОБРАЗОВАТЕЛЯ КОДОВ 11.4. АНАЛИЗ ЛОГИЧЕСКИХ СХЕМ 11.5. АНАЛИЗ ПРЕОБРАЗОВАТЕЛЯ ДВОИЧНЫХ КОДОВ 11.6. ЛОГИЧЕСКИЕ СХЕМЫ НА ЭЛЕМЕНТАХ ШЕФФЕРА 12. МНОГОТАКТНЫЕ АВТОМАТЫ 12.1. АСИНХРОННЫЙ АВТОМАТ НА ТРИГГЕРАХ ТИПА Т 12.2. СИНТЕЗ СИНХРОННЫХ АВТОМАТОВ НА T-ТРИГГЕРАХ 12.3. СИНТЕЗ СИНХРОННЫХ АВТОМАТОВ НА JK-ТРИГГЕРАХ 12.4. АНАЛИЗ СИНХРОННОГО АВТОМАТА, ПОСТРОЕННОГО НА JK-ТРИГГЕРАХ 13. КОМБИНАТОРИКА 13.1. ЗАДАЧИ НА ПРИМЕНЕНИЕ ОСНОВНЫХ ФОРМУЛ КОМБИНАТОРИКИ 13.2. КОМБИНАТОРИКА В ТЕОРИИ ВЕРОЯТНОСТЕЙ 14. ТЕОРИЯ ГРАФОВ 14.1. МАТРИЦА СМЕЖНОСТИ НЕОРИЕНТИРОВАННОГО ГРАФА 14.2. МАТРИЦА ИНЦИДЕНТНОСТИ 14.3. ЭЙЛЕРОВЫ ГРАФЫ 14.4. ДВОЙСТВЕННЫЕ ГРАФЫ 14.5. НАХОЖДЕНИЕ ВСЕХ ПРОСТЫХ ЦЕПЕЙ, СОЕДИНЯЮЩИХ ДВЕ ВЕРШИНЫ ГРАФА 14.6. ПРОСТЫЕ ЦЕПИ В ОРИЕНТИРОВАННОМ ГРАФЕ 14.7. КОДИРОВАНИЕ ДЕРЕВЬЕВ МЕТОДОМ ПРУФЕРА 14.8. ПОСТРОЕНИЕ ДЕРЕВА ПО ЕГО КОДУ 15. ДОПОЛНИТЕЛЬНЫЕ ВОПРОСЫ 15.1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ 15.2. АЛГЕБРА ЛОГИКИ (БУЛЕВА АЛГЕБРА) 15.3. ТЕОРИЯ КОНЕЧНЫХ АВТОМАТОВ 15.4. КОМБИНАТОРИКА 15.5. ТЕОРИЯ ГРАФОВ ОТВЕТЫ ЛИТЕРАТУРА