Материалы к промежуточному и итоговому контролю.
Примерный вариант контрольной работы
В студенческой группе 25 человек. Чтобы получить допуск на экзамен по данному курсу необходимо защитить курсовую работу, выполнить лабораторную работу и сдать зачет. 15 студентов защитили курсовую работу, 20 — выполнили лабораторную работу, 17 — сдали зачет. Защитили курсовую работу и выполнили лабораторную работу 12 человек. Защитили курсовую работу и сдали зачет 13 человек. Выполнили лабора- торную работу и сдали зачет 16 человек. Сколько студентов допущено к экзамену?
Сколько целых чисел между 1 и 401 делятся на 5 или на 7?
Нарисовать диаграммы Эйлера-Венна для следующих множеств:  .
Имеет ли место равенство:  .
Даны множества:A={1, 2, 3}; B={2, 3, 4}; С={1,2,3,4, 5,6}. Найдите элементы множеств:
а)  ; б)  ; c); д);
е) ; ж)  ; з) .
Докажите тождества, используя определения операций над множествами 
 . Изобразите Р1 и Р2 графически. Найдите  . Проверьте с помощью матрицы  , является ли отношение Р2 рефлексивным, симметричным, антисимметричным, транзитивным?
Построить бинарное отношение: рефлексивное, симметричное, не транзитивное.
Найти область определения, область значений отношения Р. Является ли отношение Р рефлексивным, симметричным, антисимметричным, транзитивным?
Пусть  отношения на A={a,b,c,d}, заданные матрицами. Осуществить операции над отношениями :  . Определить свойства исходных и полученных отношей.
Пусть  – множество степеней двойки;  – множества четных чисел,  . Гомоморфны (изоморфны) ли алгебры А и В, если: А=(N;+) и B=( ;+) при отображении 
Гомоморфны (изоморфны) ли алгебры А и В при отображении  , если: А=(N;+), B=( ;) при отображении  (-остаток от деления на 5 суммы чисел)
Номер автомашины состоит из трех букв русского алфавита (30 букв) и трех цифр. Сколько существует различных номеров автомашин?
Из колоды в 36 карт наудачу берутся 6 карт.
1)Найти число различных способов взятия 6 карт.
2)Найти число различных способов взятия 6 карт, содержащих 3 тузов.
Местком состоит из 7 человек. Из своей среды он выбирает президиум в составе трех человек: председателя месткома, заместителя председателя месткома, секретаря месткома. Сколько существует различных способов образования президиума месткома?
Семнадцать девушек водят хоровод. Сколькими различными способами они могут встать в круг?
На 10-ти карточках написаны буквы так, что из этих карточек можно составить слово МАТЕМАТИКА. Сколько существует различных 10-буквенных слов, которые можно образовать при помощи этих десяти карточек?
Сколькими способами можно выбрать 4 краски из имеющихся 7 различных?
По заданному десятичному числу получите номер логической функции в двоичном, восьмеричном и шестнадцатеричном кодах. Составьте таблицу истинности соответствующей логической (переключательной) функции. Определите СДНФ, СКНФ, символическую форму функции в десятичном и двоичном кодах. Минимизируйте функцию по кубу соседних чисел. Определите свойства функции и представьте вектор свойств в двоичном, восьмеричном и шестнадцатеричном кодах. Реализуйте функцию переключательной схемой и функциональными схемами в базисах И-НЕ, ИЛИ-НЕ. Получите булевы производные по всем переменным. Представьте функцию в базисе Жегалкина.
№
|
Десятичное число
|
|
241
|
|
165
|
|
55
|
|
143
|
|
253
|
|
29
|
|
183
|
|
248
|
|
234
|
|
77
|
Для заданной булевой функции трех переменных 
а) построить таблицу истинности, найти двоичную форму булевой функции и привести функцию к СДНФ и СКНФ;
б) найти двумя способами многочлен Жегалкина и ответить на вопрос, является ли данная функция линейной;
с) с помощью эквивалентных преобразований приведите функцию к ДНФ, КНФ, СДНФ и СКНФ.
Даны графы G1 и G2 . Найдите  . Для графа  найдите матрицы смежности, инцидентности, сильных компонент, маршрутов длины 2 и все маршруты длины 2, исходящие из вершины 1.
Найдите матрицы фундаментальных циклов, фундаментальных разрезов, радиус и диаметр, минимальное множество покрывающих цепей графа G. Является ли изображенный граф эйлеровым? Является ли изображенный граф планарным?
Задан неориентированный граф без петель из пяти вершин строками полуматрицы смежности в виде шестнадцатиричного числа, где первая цифра – первая строка, вторая цифра – вторая строка и т.д. Изобразите по заданному шестнадцатиричному числу граф в виде рисунка и определите степени всех вершин, цикломатическое и хроматическое число. Получите матрицу всех путей в графе длиной 2 путем возведения в квадрат соответствующей булевой матрицы (вместо суммирования используйется операция дизъюнкции).
№
|
Шестнадцатиричное число
|
|
9221
|
|
А321
|
|
В331
|
|
С421
|
|
D431
|
|
9431
|
|
F631
|
|
E631
|
|
D521
|
|
C431
|
Вопросы к экзамену:
Множество. Подмножество. Задание множеств. Сравнение множеств. Булеан.
Универсальное множество. Операции над множествами (объединение, пересечение, дополнение, разность, кольцевая сумма). Диаграммы Венна.
Свойства операций над множествами.
Разбиения и покрытия. Мощность множества.
Кортеж. Прямое произведение. Унарное, бинарное, n-местное отношения.
Бинарное отношение. Область определения, область значений бинарного отношения. Обратное отношение. Образ. Прообраз.
Способы задания бинарных отношений. Тождественное и универсальное отношения. Диагональ. Полное отношение. Композиция бинарных отношений.
Свойства бинарных отношений.
Матрица бинарного отношения. Свойства матриц бинарных отношений.
Рефлексивные, симметричные, антисимметричные, транзитивные бинарные отношения.
Отношение эквивалентности и разбиения.
Отношения порядка. Линейный порядок и частичный порядок. Диаграммы Хассе. Лексикографический порядок.
Функции и отображения. Сюръекция, биекция, инъекция. Сложная функция. Обратная функция. Композиция функций.
Правила суммы и произведения.
Размещения, перестановки, сочетания без повторений.
Размещения, перестановки, сочетания с повторениями.
Метод включений и исключений.
Бином Ньютон, биномиальные коэффициенты, треугольник Паскаля.
Рекуррентные соотношения и производящие функции.
Числа Стирлинга и их свойства.
Операции и алгебры.
Морфизмы.
Алгебры с одной и двумя операциями.
Векторные пространства.
Решетки.
Основные понятия: граф, простой граф, полный граф, однородный граф, мультиграф, псевдограф. Степень вершины. Виды вершин. Ребра графа.
Подграф, надграф, частичный граф. Изоморфизм.
Операции над графами: дополнение, объединение, пересечение, сумма по модулю два, произведение.
Способы задания графов: аналитический, графический, матричный. Матрица смежности. Матрица инцидентности.
Понятия маршрута, цепи, простой цепи, цикла, простого цикла.
Связный граф. Степень связности.
Матрица расстояний, эксцентриситеты вершин, радиус, диаметр, центр графа. Переферийные и центральные вершины.
Эйлеров цикл. Критерий Эйлера. Алгоритм построения эйлерова цикла.
Гамильтоновы графы. Задача комивояжора. Двудольные графы.
Плоский граф. Изоморфизм. Планарный граф. Внутрення и внешняя грани в двудольном графе. Теорема Эйлера о плоских графах.
Гомеоморфизм. Подразбиение и надразбиение ребра. Теорема о том, что К5 и К3,3 не планарны. Критерий Понтрягина-Куратовского.
Дерево и лес. Теорема о характеризации деревьев. Остовы графа. Цикломатическое число. Мост. Разделяющее множество. Разрез.
Раскраска графа. Хроматическое число графа.
Понятие орграфа. Матрица смежности вершин и дуг. Матрица инциденций. Степень вершин орграфа. Изоморфизм.
Маршруты, цепи, циклы в орграфах.
Связность орграфа: сильно связный, слабосвязный и несвязный орграф.
Эйлеровы цепи и циклы в орграфе.
Полный орграф.
Операции в орграфе. Орграфы и бинарные отношения. Диаграммы Хассе.
Взвешенный граф. Нахождение кратчайщих маршрутов.
Понятие о переключательных функциях.
Двоичные переключательные функции и способы их задания.
Основные бинарные логические операции (конъюнкция, дизъюнкция, инверсия, импликация, эквиваленция, сумма по модулю два, стрелка Пирсона, штрих Шеффера). Булева алгебра.
Понятие о переключательных схемах и технической реализации ПФ.
Использование логических операций в теории графов.
Основные законы булевой алгебры ПФ.
Равносильные преобразования. Упрощение формул алгебры ПФ.
Дизъюнкт. Конъюнкт. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ).
Алгоритм приведения формулы к ДНФ и КНФ.
Совершенная дизъюнктивная и конъюнктивная нормальные формы (СДНФ и СКНФ). Конституента единицы. Конституента нуля.
Алгоритмы нахождения СДНФ и СКНФ.
Цель минимазации переключательных функций. Основные понятия и определения, используемые при минимизации.
Аналитические методы минимизации ПФ (метод Квайна, Метод Квайна — Мак-Класки).
Минимизация ПФ по картам Карно.
Минимизация ПФ МНК.
Замкнутые классы. Классы T0 , T1 , S , M, L.
Понятие функциональной полноты. Полные системы булевых функций. Теорема Поста.
Многочлены Жегалкина. Теорема Жегалкина. Методики представления булевой функции в виде многочлена Жегалкина.
Базисы представлений ПФ.
Методические рекомендации преподавателю:
При проведении практических занятий по дискретной математике рекомендуется:
уделять внимание разбору теоретических задач, предлагаемых на лекциях и на семинарских занятиях;
уделять внимание краткому повторению теоретического материала, который используется при решении упражнений и задач;
осуществлять регулярную проверку домашних заданий;
ставить проблемные вопросы, по возможности использовать примеры и задачи с практическим содержанием;
использовать при проведении практических занятий активные методы обучения;
развивать математическую интуицию и логику у студентов.
Методические указания студентам:
Учиться преодолевать самый высокий уровень непонимания материала («непонятно, что непонятно»).
При разборе примеров в аудитории или при выполнении домашних заданий целесообразно каждый шаг обосновывать теми или иными теоретическими положениями.
При изучении теоретического материала не задерживать внимание на трудных и непонятных местах, смело их пропускать и двигаться дальше, а затем возвращаться к тому, что было пропущено (часто последующее проясняет предыдущее).
При чтении учебников и лекционных материалов активно отмечать карандашом непонятные места. Карандаш легко стирается, когда вопрос можно снять.
С первых студенческих дней конструировать собственный стиль понимания сути изучаемого материала. Математические дисциплины в этой ситуации являются наиболее успешным полигоном.
Дисциплина «Дискретная математика» изучается в течение одного семестра на первом курсе специальности «Вычислительные машины, комплексы, системы и сети».
Методика изучения дисциплины строиться из следующих элементов:
- теоретическая часть (лекция);
- семинарские занятия;
- самостоятельная работа с дополнительной литературой и конспектами лекций;
- домашние задание;
- промежуточный контроль;
- консультации;
- экзамен.
На лекционных занятиях даются основные понятия, постановки задач, методы их решения и анализа полученных результатов, рассматриваются примеры. Более углубленное изучение предмета выносится на самостоятельную работу.
Самостоятельная работа студентов. Аудиторная самостоятельная работа студентов по дисциплине выполняется на учебных занятиях под непосредственным руководством преподавателя и по его заданию. Она включает: текущие консультации; коллоквиум как форма контроля освоения теоретического содержания дисциплины (в часы консультаций); прием и разбор домашних заданий (в часы практических занятий).
Внеаудиторная самостоятельная работа выполняется студентом по заданию преподавателя, но без его непосредственного участия. Она включает: формирование и усвоение содержания конспекта лекций, а также самостоятельное изучение отдельных вопросов на базе рекомендованной преподавателем учебной литературы, включая информационные образовательные ресурсы (электронные учебники, электронные библиотеки); написание рефератов; подготовка к выступлению на конференции; подготовка к семинарам, их оформление; выполнение микроисследований; выполнение домашних заданий в виде решения отдельных задач, проведения типовых расчетов, расчетно-компьютерных и индивидуальных работ по отдельным разделам содержания дисциплины; компьютерный текущий самоконтроль и контроль успеваемости.
Для того, чтобы заработать то количество баллов, которое вы видите в тематическом плане дисциплины «Дискретная математика» по каждой теме, вам необходимо сделать задание по данной теме на оценку «отлично». В противном случае преподаватель имеет право снять несколько баллов. Снять баллы преподаватель может и за пропущенные семинарские или лекционные занятия.
Баллы, характеризующие успеваемость студента по дисциплине, набираются им в течение всего периода обучения за изучение дидактических единиц.
При выборе критериев оценки освоения студентом программы дисциплины в обязательном порядке учитывается: выполнение программы в части лекционных, практических занятий; выполнение предусмотренных программой аудиторных и внеаудиторных контрольных и иных письменных работ. Преподаватель осуществляет текущий контроль и выставляет рейтинговый балл по каждой контрольной точке модуля.
Максимальная сумма баллов, набираемая студентом по дисциплине (за один семестр), равна 100. Студент, набравший менее 60 баллов получает итоговую оценку – неудовлетворительно, от 61 до 75 – удовлетворительно, от 76 до 90 - хорошо, 91 и выше баллов - отлично.
|
