Лабораторные работы учебным планом не предусмотрены.
4.4. Практические занятия
№ занятия | № раздела | Тема | Кол-во часов |
1 | 1 | Основные понятия теории множеств. Включение и равенство множеств. Способы задания множеств. | 2 |
2 | 1 | Операции над множествами. Диаграммы Эйлера-Венна. | 2 |
3 | 1 | Прямое произведение множеств. | 2 |
4 | 1 | Соответствия, отображения, отношения на множествах. | 2 |
5 | 1 | Закрепление пройденного материала. | 2 |
6 | 1 | Тест рубежного контроля. | 2 |
7 | 2 | Виды графов. Понятия маршрута, цепи, цикла в графах. Связность графов. | 2 |
8 | 2 | Числовые характеристики графа. Раскраска вершин графа. Метрика графов. | 2 |
9 | 2 | Способы задания графов. | 2 |
10 | 2 | Операции над графами. | 2 |
11 | 2 | Нахождение кратчайшего пути в графе. | 2 |
12 | 2 | Транспортные сети. Задача о наибольшем потоке. | 2 |
13 | 2 | Контрольная работа. | 2 |
14 | 3 | Логика. Основные понятия логики высказываний. Основные логические связки. | 2 |
15 | 3 | Формулы алгебры высказываний. Равносильность формул логики высказываний и равносильные преобразования.. | 2 |
16 | 3 | Функции алгебры логики. Полнота и замкнутость систем логических функций. Нормальные формы представления функций алгебры логики. | 2 |
17 | 4 | Правило суммы и произведения. Размещения, перестановки и сочетания без повторений | 2 |
18 | 4 | Размещения, перестановки и сочетания с повторениями. | 2 |
19 | 3,4 | Контрольная работа. | 2 |
4.5. Курсовой проект (курсовая работа)
Курсовой проект (курсовая работа) учебным планом не предусмотрен.
4.6. Самостоятельное изучение разделов дисциплины
Самостоятельное изучение разделов дисциплины не предусмотрено.
5. Образовательные технологии.
Наряду с традиционными образовательными технологиями, методами и средствами обучения, используются:
· компьютерные презентации лекций,
· опосредованное взаимодействие с обучающимися в электронной информационно-образовательной среде «Цифровой кампус».
5.1. Интерактивные образовательные технологии, используемые в аудиторных занятиях.
Учебным планом не предусмотрены.
6. Оценочные средства для текущего контроля успеваемости и промежуточной аттестации
Контроль усвоения материала включает:
– проведение рейтинговых контрольных работ;
– проверку знаний теоретического материала на практических занятиях;
– оценку знаний при защите индивидуального задания.
Методы контроля включают стандартные формы контроля усвоения знаний, авторское формирование содержания экзаменов, систему требований (собрание образцов работ), оценку индивидуального задания по результатам его защиты, устные экзамены.
· 6.1. Контрольные вопросы для самопроверки
· 6.1.1. К разделу «Основы теории множеств»
1. . С чем связывают в обычном смысле слово “множество”?
2. . Из чего состоит множество?
3. . Как обозначают множества, элементы множества?
4. Мощность множества. Мощности числовых множеств.
5. . Что называю пустым множеством?
6. . Перечислите способы задания множества.
7. . В каком случае множества являются равными?
8. . Расскажите об операциях, которые можно осуществлять над двумя множествами.
9. Операции пересечения, объединения и разности, основные тождества для этих операций.
10. Включение множеств, подмножество.
11. Операция дополнения множества.
12. Декартово произведение.
13. Бинарные отношения на множестве.
14. Классификация бинарных отношений (рефлексивность, симметричность, транзитивность, антисимметричность, линейность и т. п.).
15. Способы задания бинарных отношений (графами и их диаграммами, матрицами, списками смежности).
16. Матрица бинарного отношения и связь ее свойств со свойствами отношения.
17. Отношения эквивалентности и их связь с разбиениями множества.
18. Отношения частичного порядка. Частично упорядоченные множества.
19. Минимальные и максимальные, элементы частично упорядоченного множества. Наименьший и наибольший элементы.
20. Отношения линейного и полного порядка.
21. Отображения. Классификация отображений (инъективность, сюръективность, биективность и т. п.).
22. Обратное отношение и критерий существования обратного отношения.
· 6.1.2. К разделу «Основы теории графов»
1. Перечислите известные Вам способы задания графов.
2. Поясните понятие «инцидентность» для графа.
3. Поясните понятие «смежность» для графа.
4. В каком случае граф называется полным?
5. Поясните понятие «нуль-граф».
6. Что определяет степень вершины?
7. Что определяет полустепень захода вершины?
8. Что определяет полустепень исхода вершины?
9. Приведите пример частичного графа G1(X, U1) графа G(X, U).
10. Приведите пример подграфа G1(X1, U1) графа G(X, U).
11. Дайте определение понятиям «маршрут», «цикл» и «цепь»
12. Дайте определение понятиям «путь» и «контур».
13. Как определяется длина маршрута или пути в не взвешенном графе?
14. В каком случае граф называется связным?
15. Определите понятие «компоненты связности» графа.
16. В каком случае ребро связного графа называется мостом?
17. В каком случае граф называется деревом?
18. Какими свойствами обладает вершина дерева, называемая корнем?
19. Что называется ярусом вершины дерева?
20. Дайте определение понятию «остов».
21. Приведите пример графа, являющегося лесом.
22. В каком случае граф является бинарным деревом?
23. Какой граф называют двудольным?
24. В каком случае граф является планарным или плоским?
25. Определите понятие «изоморфизм графов».
26. Приведите пример изоморфных графов.
27. Сформулируйте правило построения матрицы инциденций на основании матрицы смежностей.
28. Определите понятия «достижимость» и «контрдостижимость» на графе.
29. Что представляет собой матрица достижимости?
30. Что представляет собой матрица контрдостижимости?
31. Сформулируйте правило построения матрицы достижимости на основании матрицы смежностей.
32. Что представляет собой граф, полученный в результате применения операции объединения к двум графам?
33. Что представляет собой граф, полученный в результате применения операции пересечения к двум графам?
34. Что представляет собой граф, полученный в результате применения операции «кольцевая сумма» к двум графам?
35. Поясните одноместные (унарные) операции «замыкание» и «стягивание».
36. Правило расстановки пометок в алгоритме нахождения кратчайших путей во взвешенном графе (алгоритме Дейкстра).
37. Формирование и использование массива предков для нахождения кратчайшего пути по расставленным пометкам.
38. Что называется сечением или разрезом транспортной сети? Какой разрез называется минимальным?
39. Правило расстановки пометок при нахождении максимального потока в транспортной сети.
40. Правило изменения потока в транспортной сети, после того как получил пометку сток.
· 6.1.3. К разделу «Алгебра высказываний»
1. Что такое высказывание?
2. Какие высказывания бывают?
3. Какие высказывания называются простыми, а какие - сложными?
5. Какие из приведенных предложений являются высказываниями:
а) 3+2=5.
б) Не шуметь!
в) y2 ³ 0.
г) Окружностью называется множество всех точек на плоскости, расстояние которых до данной точки этой плоскости имеет заданную величину.
д) Число символов в этом предложении равно 7.
е) 3 < 2.
6. Установите: какие из следующих предложений являются истинными, а какие - ложными высказываниями:
а) “Число 123 меньше числа 124”.
б) “Все треугольники равнобедренные”.
в) “Сумма чисел 4 и z равна 15”.
г) “(13-2*4)*4=-7”.
7. Даны высказывания:
A: “Математическая логика - важная наука”, B: “ВТ построена на законах математической логики”. Образуйте из данных высказываний сложные и подчеркните слова, при помощи которых они образованы.
8. Среди приведенных ниже высказываний укажите сложные; выделите в них простые, обозначив каждое из них буквой. Запишите с помощью букв каждое сложное высказывание.
а) “На уроке логики учащиеся отвечали на вопросы учителя и писали самостоятельную работу”.
б) “Мы пойдем кататься на коньках или на лыжах”.
в) “Если в данном четырехугольнике диагонали имеют равную длину, то этот четырехугольник - ромб”.
г) “-17<=0”.
д) “Число 15 делится на 3 тогда и только тогда, когда сумма цифр этого числа делится на 3”.
9. Представте логическими формулами следующие высказывания:
1) «Сегодня понедельник или вторник».
2) «Идет снег или дождь».
3) «Если идет дождь, то крыши мокрые. Дождя нет, а крыши мокрые».
4) «Что в лоб, что по лбу».
10. Докажите равносильность формулы 
, используя логические законы.
· 6.1.4. К разделу «Комбинаторика»
1. Размещения и перестановки. Формулы для вычисления числа перестановок и числа размещений.
2. Числа сочетаний и их свойства.
3. Формулы для вычисления числа сочетаний.
4. Треугольник Паскаля.
5. Бином Ньютона.
6. Перестановки и сочетания с повторениями. Формулы для вычисления числа перестановок с повторениями и числа сочетаний с повторениями.
7. Сколькими способами можно выбрать гласную и согласную буквы из слова "геометрия"?
8. У цветочницы по 10 тюльпанов трех цветов: красного, розового и желтого. Она составляет для продажи букеты из трех цветов разного цвета. Сколько имеется возможностей для составления букета? Сколько возможностей не реализуется?
9. Десять выпускников обменялись фотокарточками. Сколько фотокарточек было сделано?
10. Сколькими способами могут разместиться шесть покупателей в очередь?
11. Сколько различных пятизначных чисел можно составить из цифр 1,3,5,7,9 (без повторений)?
12. Сколькими способами можно посадить на скамейку пять человек?
13. Фотограф размещает группу для фотографирования из 8 человек. Сколькими способами он может это сделать?
14. В соревновании участвуют семь спортсменов. Сколько существует возможностей распределения между ними мест?
15. Сколькими способами можно упорядочить множество X={x,y,z,a,b,c,d} так, чтобы элементы а и b стояли рядом и в алфавитном порядке?
16. Сколькими способами можно посадить за круглый стол 5 человек?
17. На собрании должны выступить студенты А, В, С, Д. Сколькими способами можно составить список выступающих, если С не может выступить раньше, чем А?
18. Студент сдает 5 экзаменов в течение 15 дней, сколькими способами можно составить расписание экзаменов, если перед каждым экзаменом на подготовку дается два дня?
19. Найти сумму цифр во всех четырехзначных числах, составленных без повторений из цифр 1, 2, 5, 7.
20. Сколькими способами из 25 студентов группы можно выбрать делегацию, состоящую из 4 человек?
21. В комнате четыре лампочки. Сколько всего различных способов освещения комнаты возможны?
22. У одного филателиста 10 марок, а у другого - 8. Все марки различны, сколькими способами они могут обменяться четырьмя марками?
23. Студенты изучают 10 предметов. В первый день занятий у них 4 пары. Сколькими способами можно составить расписание занятий на этот день?
24. Сколько существует различных пятизначных чисел с неповторяющимися цифрами?
25. В группе 25 студентов. Необходимо выделить 5 участников эстафеты, состоящей из 5 этапов. Сколькими способами можно это сделать?
26. Найти число перестановок из букв слова "математика"?
27. Ячейка памяти одной ЭВМ содержит 40 двоичных разрядов. Размещая на эти 40 мест цифры 0 или 1, получаем машинное слово. Сколько различных машинных слов возможно разместить в ячейке памяти этой машины?
28. Сколько ожерелий можно составить из 5 красных, 5 синих и 5 желтых бусинок?
29. В почтовом отделении продаются открытки 8 видов. Сколькими способами можно выбрать 10 открыток?
30. Сколько различных четырехзначных чисел, делящихся на 2, можно составить из цифр 3,5,7,8,9?
6.2. Образцы тестов для проведения текущего контроля
6.2.1. Пример теста для 1-го рейтингового контроля
1. Перечислите способы задания множества.
2. Равны ли множества A={7,8,9,10} и B={8,7,9,8,10,9}?
3. Как определяется операция дополнения?
4. Что называется областью значений соответствия?
5. Определите понятие «отображение множества Х в множество Y».
6. Определите свойства отношения: симметричность, несимметричность, асимметричность.
7. В каких отношениях находятся между собой множества A={1, 2, 3}, B={xÎR | x²-3x+2=0}, C={xÎZ | x≤3}.
8. Найти объединение, пересечение, разность и симметрическую разность множеств А={а½аÎ[-7; 1)} и В={b½bÎ[-3,4)}.
9. Перечислить упорядоченные пары, принадлежащие отношению R={(x, y)|x<y} на множестве X={1,2,3,4,5}. Представьте R в виде матрицы.
10. Докажите, обладает ли свойствами рефлексивности, симметричности и транзитивности отношение «y имеет тех же родителей, что и x» на множестве людей.
6.2.2. Пример теста для 2-го рейтингового контроля
1. Поясните понятие «инцидентность» для графа.
2. Приведите пример частичного графа G1(X, U1) графа G(X, U)
3. В каком случае ребро связного графа называется мостом?
4. Сформулируйте правило построения матрицы достижимости по матрице смежности.
5. Постройте граф G=(X, Г), где X={x1, x2, x3, x4, x5}, Г(x1)={x2, x3,), Г(x2)={x1, x4, x5}, Г(x3)={x1, x4},) Г(x4)={x3, x2}, Г(x5)=Æ.
6. Найдите радиус, центр, диаметр графа и диаметральные цепи.
 |
7. Постройте матрицу достижимости графа, предварительно обозначив вершины графа.
8. Правило расстановки пометок в алгоритме нахождения кратчайших путей во взвешенном графе (алгоритме Дейкстра).
6.2.3. Пример теста для 3-го рейтингового контроля
1) Даны два высказывания: р: «Число 3 является делителем числа 174» и q: «конъюнкция коммутативна». Сформулируйте высказывание p® и определите, является данное высказывание истинным или ложным.
2) Составить таблицы истинности для формулы 
и записать в СКНФ.
3) С помощью равносильных преобразований привести формулу алгебры логики 
к дизъюнктивной нормальной форме.
4) Сколько ожерелий можно составить из 5 красных, 5 синих и 5 желтых бусинок?
5) Из группы, состоящей из 7 мужчин и 4 женщин, надо выбрать 6 человек так, чтобы среди них было не менее 3 женщин. Сколькими способами можно это сделать?
6) Определите логическую связку «конъюнкция».
7) Какие соединения элементов называются перестановками с повторениями.
7. Учебно-методическое обеспечение дисциплины
7.1 Основная литература.
1. , Спирин математика: учебник. - М.: Академия,2004.
2. , Овчинникова математика: учебник. - М.: ИНФРА-М, 2005.
7.2 Дополнительная литература.
1.Яблонский в дискретную математику. М.: Лань, 2010.
2. Горбатов дискретной математики. М.: Наука, 1986.
3. Кузнецов математика для инженера. - СПб: Издательство “Лань”, 2004.
4. , Чечкин математика: учебник для студ. Вузов. – М: Академия, 2006.
5. Андерсон Джеймс. Дискретная математика и комбинаторика. - М.: Вильямс, 2006.
8. Материально-техническое обеспечение дисциплины
Для лекционных занятий
Стандартно оборудованные лекционные аудитории для проведения интерактивных лекций: видеопроектор, экран настенный.
Для практических занятий
Стандартно оборудованные аудитории для проведения интерактивных практических занятий: видеопроектор, экран настенный.
9. Учебная карта дисциплины Дискретная математика
Преподаватель А. Кафедра САиТ
Курс 1 Семестр 1 Группа А-59
Направление подготовки (специальность) Информатика и вычислительная техника, код 230100.62
№ | Виды контрольных мероприятий | Количество баллов за 1 контрольное мероприятие | Модуль 1 Основы теории множеств | Модуль 2 Основы теории графов | Модуль 3 Алгебра высказываний | Модуль 4 Элементы комбинаторики |
Количество баллов по модулю | ||||||
Текущий контроль | ||||||
1 | Посещение лекций | |||||
2 | Работа на практических занятиях | |||||
3 | Промежуточное тестирование | |||||
4 | Реферат | |||||
5 | Индивидуальное задание | 18 | 18 | 18 | 19 | |
Рубежный контроль | ||||||
1 | Контрольная работа | |||||
2 | Тестирование | 15 | 15 | 15 | 10 | 5 |
3 | Другое | |||||
Промежуточная аттестация | ||||||
Экзамен | 33 | 33 | 29 | 5 |
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 |
