Рабочая программа дисциплины дискретная математика (наименование) Направление подготовки: 230100. 62 «Информатика и вычислительная техника»

«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Разработчик

Кавчук Альбина Андреевна, к.т.н., доцент

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

Рецензент(ы) __________________________________________________________

1. Цели и задачи освоения дисциплины

Цели освоения дисциплины:

• 
  овладение математическим аппаратом дискретной математики, необходимым для применения математических методов при проведении фундаментальных и прикладных научных исследований, а также для решения практических задач в рамках своей специализации;
  
• 
  развитие логического мышления, освоение приемов исследования и решения математически формализованных задач.
  

Задачи дисциплины:

• 
  получение знаний по основам теории множеств, теории графов, алгебры высказываний и комбинаторики;
  
• 
  теоретическое освоение современных концепций и моделей дискретной математики;
  
• 
  приобретение практических навыков применения аппарата дискретной математики;
  
• 
  развитие математической культуры в области дискретных математических знаний;
  
• 
  ознакомление с основными направлениями развития дискретной математики.
  

• 
  использует основные законы естественнонаучных дисциплин в профессиональной деятельности, применяет методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10).
  

• 
  Основные определения, понятия, термины, стандартную символику и стандартные обозначения, используемые теорией множеств; способы задания множеств, теоретико-множественные операции, тождества алгебры множеств; соответствия, отображения, функции; бинарные отношения и их виды.
  
• 
  Основные определения, понятии, элементы теории графов; способы задания графов; числовые характеристики графа; операции над графами; постановку и решение задачи о нахождении кратчайшего пути; постановку и решение задачи о нахождении максимального потока в транспортной сети.
  
• 
  Основные понятия алгебры высказываний: высказывания простые и сложные, основные логические связки; формулы алгебры высказываний, равносильные преобразования; функции алгебры логики, способы их задания, нормальные формы представления.
  
• 
  Основные определения и понятия комбинаторики; постановку комбинаторной задачи, правило суммы и произведения; основные формулы вычисления количества перестановок, размещений, сочетаний без повторений и с повторениями.
  

• 
  Задавать множества различными способами; применять аппарат теории множеств для решения задач, как с помощью преобразований, так и теоретико-множественным путем, используя диаграммы Венна; выполнять операции над множествами; определять тип бинарного отношения и его свойства.
  
• 
  Представлять графы различными способами; находить характеристики графов, выполнять операции над графами; находить кратчайший путь в графе, находить максимальный поток в заданной транспортной сети.
  
• 
  Представлять логической формулой сложное высказывание; строить таблицы истинности функций алгебры логики; представлять функции алгебры логики в виде формул заданного типа, выполнять тождественные преобразования, находить нормальные и совершенные нормальные дизъюнктивную и конъюнктивную формы;
  
• 
  Решать задачи, связанные с нахождением числа комбинаций определенного типа, применять на практике основные принципы организации перебора вариантов.
  

• 
  формальными методами дискретной математики, используемыми для описания и исследования свойств объектов;
  
• 
  навыками применения базового инструментария дискретной математики для решения прикладных задач;
  
• 
  методикой построения, анализа и применения моделей дискретной математики в информатике и вычислительной техники для оценки состояния и прогноза развития.
  

Курсовой проект (курсовая работа) учебным планом не предусмотрен.

Самостоятельное изучение разделов дисциплины не предусмотрено.

• 
  компьютерные презентации лекций,
  
• 
  опосредованное взаимодействие с обучающимися в электронной информационно-образовательной среде «Цифровой кампус».
  

• 
  проведение рейтинговых контрольных работ;
  
• 
  проверку знаний теоретического материала на практических занятиях;
  
• 
  оценку знаний при защите индивидуального задания.
  

• 
  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. 
   Приведите пример частичного графа G₁(X, U₁) графа G(X, U).
   
10. 
    Приведите пример подграфа G₁(X₁, U₁) графа 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. К разделу «Алгебра высказываний»
  

9. Представте логическими формулами следующие высказывания:

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?
    

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 на множестве X={1,2,3,4,5}. Представьте R в виде матрицы.
   
10. 
    Докажите, обладает ли свойствами рефлексивности, симметричности и транзитивности отношение «y имеет тех же родителей, что и x» на множестве людей.