Методические рекомендации по освоению учебной дисциплины 17 1 Самостоятельная работа студента 17 2 Оценочные средства для контроля успеваемости и результатов освоения учебной дисциплины 20

4.2 Оценочные средства для контроля успеваемости и результатов освоения учебной дисциплины

5. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

6. МАТЕРИАЛЫ К ПРОМЕЖУТОЧНОМУ И ИТОГОВОМУ КОНТРОЛЮ

Вариант аудиторной контрольной работы №1.

1. 
   В студенческой группе 25 человек. Чтобы получить допуск на экзамен по данному курсу необходимо защитить курсовую работу, выполнить лабораторную работу и сдать зачет. 15 студентов защитили курсовую работу, 20 — выполнили лабораторную работу, 17 — сдали зачет. Защитили курсовую работу и выполнили лабораторную работу 12 человек. Защитили курсовую работу и сдали зачет 13 человек. Выполнили лабораторную работу и сдали зачет 16 человек. Сколько студентов допущено к экзамену?
   
2. 
   Изобразить с помощью диаграмм Венна:
   
   1. 
      
      
   2. 
      
      
3. 
   Даны множества: A = {1, 2, 3}; B = {2, 3, 4}; С = {1, 2, 3, 4, 5, 6}. Найдите элементы множеств:; ; ; ;
   

4. 
   . Изобразите Р₁ и Р₂ графически. Найдите . Проверьте с помощью матрицы , является ли отношение Р₂ рефлексивным, симметричным, антисимметричным, транзитивным?
   

5. 
   Номер автомашины состоит из трех букв русского алфавита (30 букв) и трех цифр. Сколько существует различных номеров автомашин?
   
6. 
   Из колоды в 36 карт наудачу берутся 6 карт. Найти число различных способов выбора 6 карт, содержащих 3 туза.
   
7. 
   Местком состоит из 7 человек. Из своей среды он выбирает президиум в составе трех человек: председателя месткома, заместителя председателя месткома, секретаря месткома. Сколько существует различных способов образования президиума месткома?
   
8. 
   Семнадцать девушек водят хоровод. Сколькими различными способами они могут встать в круг?
   
9. 
   На 10-ти карточках написаны буквы так, что из этих карточек можно составить слово МАТЕМАТИКА. Сколько существует различных 10-
   

10. 
    Сколькими способами можно выбрать 4 краски из имеющихся 7 различных?
    

Вариант аудиторной контрольной работы № 2

1. 
   Для заданной булевой функции трех переменных:
   

2. 
   Выяснить, является ли система функций A функционально полной.
   

Вариант аудиторной контрольной работы № 3.

1. 
   Даны графы G₁ и G₂. Найдите . Для графа найдите матрицы смежности, инцидентности, сильных компонент, маршрутов длины 2 и все маршруты длины 2, исходящие из вершины 1.
   

2. 
   Найдите матрицы фундаментальных циклов, фундаментальных разрезов, радиус и диаметр, минимальное множество покрывающих цепей графа G. Является ли изображенный граф эйлеровым? Является ли изображенный граф планарным?
   

3. 
   Для графа представленного следующей матрицей смежности, определить матрицу инцидентности и изобразить его графически.
   

4. 
   Для графа представленного следующей матрицей инцидентности, определить матрицу смежности и изобразить его графически.
   

1. 
   Множество. Задание множеств. Сравнение множеств.
   
2. 
   Операции над множествами (объединение, пересечение, дополнение, разность).
   
3. 
   Универсальное множество. Разбиения и покрытия. Булеан.
   
4. 
   Свойства операций над множествами.
   
5. 
   Прямое произведение. Бинарное отношение.
   
6. 
   Способы задания бинарных отношений. Композиция бинарных отношений.
   
7. 
   Свойства бинарных отношений и их распознавание.
   
8. 
   Свойства матриц бинарных отношений.
   
9. 
   Рефлексивные, симметричные, транзитивные бинарные отношения.
   
10. 
    Отношение эквивалентности.
    
11. 
    Отношения порядка. Упорядоченные пары.
    
12. 
    Простейшие комбинаторные конфигурации и их свойства.
    
13. 
    Логические переменные. Логические связки. Таблицы истинности.
    
14. 
    Булева функция. Вектор значений булевой функции. Эквивалентность формул.
    
15. 
    Основные эквивалентности.
    
16. 
    Выполнимая и опровержимая формула. Тождественно-истинная формула. Тождественно-ложная формула.
    
17. 
    Понятие литеры. Дизъюнкт. Конъюнкт. ДНФ. КНФ. Конституента единицы. Конституента нуля.
    
18. 
    Алгоритм приведения формулы к ДНФ и КНФ.
    
19. 
    Совершенная дизъюнктивная и конъюнктивная нормальные формы. Алгоритмы нахождения СДНФ и СКНФ.
    
20. 
    Минимизация булевых функций в классе ДНФ. Матрица Квайна.
    
21. 
    Замкнутые классы. Классы T0 , T1 , S , M, L.
    
22. 
    Полные системы булевых функций. Теорема Поста.
    
23. 
    Свойства суммы по модулю 2. Теорема Жегалкина. Алгоритмы построения полинома Жегалкина.
    
24. 
    Предикаты. Кванторы. Формулы логики предикатов
    
25. 
    Понятие графа, простого графа, полного графа, однородного графа, мультиграфа, псевдографа. Подграф, надграф, частичный граф. Степень вершины.
    
26. 
    Операции над графами: дополнение, объединение, пересечение, сумма по модулю два, произведение.
    
27. 
    Способы задания графов: аналитический, графический, матричный. Матрица смежности. Матрица инцидентности.
    
28. 
    Понятия маршрута, цепи, простой цепи, цикла, простого цикла.
    
29. 
    Связный граф. Степень связности.
    
30. 
    Матрица расстояний, эксцентриситеты вершин, радиус, диаметр, центр графа. Переферийные и центральные вершины.
    
31. 
    Эйлеров цикл. Критерий Эйлера. Алгоритм построения эйлерова цикла.
    
32. 
    Гамильтонов цикл. Двудольные графы.
    
33. 
    Плоский граф. Изоморфизм. Внутрення и внешняя грани в двудольном графе. Теорема Эйлера о плоских графах.
    
34. 
    Гомеоморфизм. Подразбиение и надразбиение ребра Критерий Понтрягина-Куратовского.
    
35. 
    Дерево и лес. Цикломатическое число. Мост. Разделяющее множество. Разрез.
    
36. 
    Понятие орграфа. Матрица смежности вершин и дуг.Матрица инциденций. Степень вершин орграфа. Изоморфизм.
    
37. 
    Маршруты, цепи, циклы в орграфах.
    
38. 
    Связность орграфа: сильно связный, слабосвязный и несвяхный орграф.
    
39. 
    Эйлеровы цепи и циклы в орграфе.
    
40. 
    Полный орграф.
    

7. СПИСОК ОСНОВНОЙ И ДОПОЛНИТЕЛЬНОЙ ЛИТЕРАТУРЫ, ДРУГИЕ ИНФОРМАЦИОННЫЕ ИСТОЧНИКИ

1. 
   Глухов М. М., Шишков А. Б. Математическая логика. Дискретные функции. Теория алгоритмов / М. М. Глухов, А. Б. Шишков – СПб.: «Лань», 2012 – 409.
   
2. 
   Шевелев Ю.П., Писаренко Л. А., Шевелев М. Ю. Сборник задач по дискретной математике (для практических занятий в группах)/ Ю.П. Шевелев, Л. А. Писаренко, М. Ю. Шевелев - СПб.: «Лань», 2013 – 523.
   
3. 
   Шевелев Ю.П. Дискретная математика / Ю.П. Шевелев. - СПб.: «Лань», 2008 – 592.
   

1. 
   Виленкин Н.Я. Комбинаторика./ Н. Я. Виленкин, А.Н Виленкин.,П. А. Виленкин - М.: ФИМА, МЦНМО, 2006. - 400 с.
   
2. 
   Галкина В.А. Дискретная математика: комбинаторная оптимизация на графах: Учеб. Пособие/ В.А. Галкина -М.: Гелиос АРВ, 2003. 232c.
   
3. 
   Гончарова, Г. А. Элементы дискретной математики: Учебное пособие для среднего профессионального образования по специальностям информатики и вычислительной техники / Г. А. Гончарова, А. А. Мочалин - М, 2003, 128 с.
   
4. 
   Горбатов В. А. Фундаментальные основы дискретной математики. Информационная математика. /В. А. Горбатов, А. В. Горбатов, М.В. Горбатова - Наука, 2000.- С.- 544c.
   
5. 
   Москинова, Г.И. Дискретная математика: Математика для менеджера в примерах и упражнениях / Г.И. Москинова. - М.: Логос, 2003 - 240c.
   
6. 
   Овчинникова Е. В. Математическая логика и теория алгоритмов: учебник / Е. В. Овчинникова, С. В. Судоплатов. - Новосибирск: НГТУ, 2012. - 280 c.
   
7. 
   Овчинникова Е.В. Элементы дискретной математики: учебник / Е. В. Овчинникова, С. В.Судоплатов -М. 2002, 280 с.
   
8. 
   Плотников А.Д. Дискретная математика: учеб. пособие /А.Д. Плотников. — М.: Новое знание, 2005. — 288 с.
   
9. 
   Соболева Т.С. Дискретная математика: учебник для студ. вузов / Т. С.Соболева, А. В.Чечкин; под ред. А. В.Чечкина. — М.: Издательский центр «Академия», 2006. — 256 с.
   
10. 
    Спирина М. С. Дискретная математика: Учебник для студ. учреждений сред. проф. образования / М. С. Спирина, П. А. Спирин. — М.: Издательский центр «Академия», 2004. — 368 с.
    
11. 
    Яблонский С.В. Введение в дискретную математику: Учеб. пособие / С. В. Яблонский -М.: Высшая школа, 2003. - 384c.
    

1. 
   Единое окно доступа к образовательным ресурсам. Электронная библиотека [Электронный ресурс]: инф. система. – М.: ФГАУ ГНИИ ИТТ "Информика", 2005-2012. – Режим доступа: //www. http://window.edu.ru, свободный. – Загл. с экрана (дата обращения 11.04.2012)
   
2. 
   Образовательный математический сайт http://www.exponenta.ru/
   
3. 
   Поисковые системы: Яндекс, Rambler, Google
   
4. 
   Свободная энциклопедия Википедия (http://ru.wikipedia.org)