|  ;  ;  ;  . |
|  ;  ;  ;  . |
|  ; ;  ;  . |
, 
ПРИМЕРЫ КОНТРОЛЬНЫХ РАБОТ
КОНТРОЛЬНАЯ РАБОТА №1
Вариант 1.
1. С помощью таблицы истинности построить СДНФ и СКНФ следующей формулы:
.
2. Используя равносильные преобразования, найти ДНФ и КНФ следующей формулы: 
.
3. Доказать равносильность следующих формул:
и 
.
4. По следующей функции проводимости построить схему:
.
5. Следующую схему упростить:
Вариант 2.
1. С помощью таблицы истинности построить СДНФ и СКНФ следующей формулы:
.
2. Используя равносильные преобразования, найти ДНФ и КНФ следующей формулы: 
.
3. Доказать равносильность следующих формул:
и 
.
4. По следующей функции проводимости построить схему:
.
5. Следующую схему упростить:
КОНТРОЛЬНАЯ РАБОТА №2
Вариант 1
1. Найти количество делителей числа 272160.
2. Из группы состоящей из 7 мужчин и 4 женщин, нужно выбрать 6 человек так, чтобы среди них было не менее 2 женщин. Сколькими способами это можно сделать?
3. Переплетчик должен переплести 12 книг в красный, зеленый и коричневый переплеты. Сколькими способами он может это сделать, если в каждый цвет должна быть переплетена хотя бы одна книга?
Вариант 2.
1. Сколько четырехбуквенных слов можно составить из букв слова «вероятность».
2. Рота состоит из трех офицеров, шести сержантов и шестидесяти рядовых. Сколькими способами можно выделить из них отряд, состоящий из одного офицера, двух сержантов и двадцати рядовых?
3. Найти сумму чисел, получаемых при всевозможных перестановках цифр 1, 2, 2, 5, 5, 1.
6.3. Перечень вопросов при подготовке к экзамену
Экзаменационная программа по курсу
«Дискретная математика и математическая логика»
направление подготовки – математика 010100,
экзамен – 2 семестр,
АЛГЕБРА ВЫСКАЗЫВАНИЙ
Высказывания, операции над высказываниями. Формулы алгебры высказываний. Принцип двойственности. Закон двойственности. Нормальные формы. Алгоритмы построения ДНФ и КНФ. СДНФ и СКНФ. Основные проблемы алгебры высказываний. Критерий тождественной истинности и тождественной ложности. Реле и его функция проводимости. Схемы и их функции проводимости. Основные задачи теории РКС: задача синтеза, задача анализа и задача упрощения. Машина голосования. Одноразрядный и многоразрядный двоичный сумматор.
АЛГЕБРЫ ПРЕДИКАТОВ И МНОЖЕСТВ
Предикаты. Операции над предикатами. Кванторы, их свойства и применение. Основные равносильности, содержащие кванторы. Множества. Операции над множествами. Подмножество. Свойства подмножеств.
ТЕОРИЯ ОТОБРАЖЕНИЙ
Отображения. Образ и прообраз при отображении. Свойства образов и прообразов. Суперпозиция отображений. Типы отображений. Обратимость и односторонняя обратимость. Критерий обратимости слева. Критерий обратимости справа.
ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
Декартово произведение множеств. Основной принцип комбинаторики. Число элементов во множестве. 
, формула включения-исключения, 
, множества 
Формулы для 
. Сочетания с повторениями. Свойства биномиальных коэффициентов. Бином Ньютона.
АЛГЕБРЫ ОТНОШЕНИЙ И «0-1» МАТРИЦ
Многоместные отношения. Булевы операции над отношениями. Булева алгебра отношений. Двуместные отношения. Композиция двуместных отношений. Булевы матрицы и отношения на конечных множеставах. Бинарные отношения. Свойства бинарных отношений: рефлексивность, симметричность, антисимметричность, транзитивность. Отношения эквивалентности. Классы эквивалентности и их свойства. Фактор-множество. Система различных представителей. Отношения порядка. Упорядоченные, линейно-упорядоченные и частично-упорядоченные множества.
БУЛЕВЫ ФУНКЦИИ
Множества 
. Многочлены Жегалкина и их свойства. Замыкание и его свойства. Замкнутость, полнота. Классы Поста и их свойства. Леммы о функциях, не принадлежащих классам Поста. Теорема Поста и следствия из неё. Предполные классы и их свойства.
ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
Понятие об алгоритме, черты (свойства) алгоритмов. Алфавит, буквы, слова. Запись слова на бесконечной ленте. Операции над словами. Машина Тьюринга – описание и примеры. Композиция машин. Машины с полулентами и теоремы о них. Объединение машин, разветвление машин, итерация машин. Универсальный алфавит и универсальная машина. Тьюрингов подход к понятию "алгоритм" и другие подходы. Алгоритмически разрешимые и неразрешимые проблемы. Существование алгоритмически неразрешимых проблем.
ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Определения графов. Примеры графов. Локальные характеристики графов. Изоморфизм графов. Геометрические графы. Правильная реализация графа. Теорема о правильной реализации в 
. Плоские и неплоские графы. Понятие о критерии Понтрягина-Куратовского. Пути, цепи, контуры, циклы. Компоненты связности и сильной связности. Части графа: подграф, частичный граф. Мосты и точки сочленения. Теорема о мостах. Эйлеровы графы. Критерий эйлеровости. Деревья и леса. Помеченные деревья. Перечисление помеченных деревьев. Алгоритмы на графах: нахождения компонент и бикомпонент, мостов и точек сочленения, конденсации. Алгоритм Краскала, алгоритм Дейкстры. Потоки в сетях. Пространства циклов и разрезов графа.
ПРИМЕРЫ ЭКЗАМЕНАЦИОННЫХ БИЛЕТОВ
Экзаменационный билет № 1
1. Критерий монотонности функции алгебры логики.
2. Теорема о 
.
3. Доказать равенство 
.
Экзаменационный билет № 2
1. Свойства нелинейных функций.
2. Теорема о 
.
3. Доказать равенство 
.
Экзаменационный билет № 3
1. Свойства немонотонных функций.
2. Односторонняя обратимость отображения. Критерии односторонней обратимости.
3. Сколько есть различных трехзначных чисел, в десятичной записи которых не встречаются цифры 0, 2 и 5?
Экзаменационный билет № 4
1. Свойства несамодвойственых функций.
2. Формула включения-исключения.
3. Построить ДНФ и КНФ для формулы 
.
VII. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
7.1. Основная литература.
1. Я. Комбинаторика. –М.: Наука, 1969.
2. Г. Алгебра логики в задачах. –М.: Наука, 1972.
3. М. Дискретная математика: теория, задачи, приложения. –М.: Вузовская книга, 2011. -292 с.
4. М., Б. 35 лекций по дискретной математике. вып. 1-6. УПЛ РГУ, 1992.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
Основные порталы (построено редакторами)