Тема 4. Логика предикатов
Понятие
-
местного предиката. Кванторы общности
и существования. Операция квантификации,
свободные и связанные переменные в
высказывательных формах
.
Запись математических утверждений с
использованием кванторов. Отрицание
предложений с кванторами.
Тема 5. Элементы теории графов
Основные понятия теории графов. Ориентированные и неориентированные графы. Формы представления графов (диаграммы, матрицы смежности и инциденций). Операции над графами. Степень вершины. Маршруты, цепи, циклы. Эйлеровы и гамильтоновы графы. Теоремы существования эйлеровых и гамильтоновых циклов. Алгоритмы построения эйлеровых циклов. Иные основные типы графов: связные, полные, двудольные, плоские, деревья, леса и др. Понятие остова графа. Алгоритм Краскала построения кратчайшего остова графа. Понятия раскраски графа и хроматического числа. Понятие нечеткого графа, способ его задания. Операции над нечеткими графами. Носитель нечеткого графа, первая, вторая и глобальная проекции.
Тема 6. Элементы теории алгоритмов
Интуитивное понятие алгоритма и его свойства. Формализация понятия алгоритма. Рекурсивные функции. Вычислимые функции.Понятие о примитивно-рекурсивной функции. Тезис Черча. Машина Тьюринга. Алгоритмически разрешимые и алгоритмически неразрешимые проблемы. Понятие сложности вычислений.
4.4. Разделы, темы дисциплины и виды занятий
№ п/п |
Наименования раздела и темы |
час / зач.ед. |
Всего, часов |
||
Лекции |
Практич. занятия |
Самостоят. работа |
|||
1. |
Тема 1. Элементы комбинаторного анализа |
1 |
1 |
20 |
22 |
2. |
Тема 2. Множества и отображения |
2 |
2 |
20 |
24 |
3. |
Тема 3. Элементы математической логики |
2 |
2 |
20 |
24 |
4. |
Тема 4. Логика предикатов |
1 |
1 |
20 |
22 |
5. |
Тема 5. Элементы теории графов |
1 |
1 |
20 |
22 |
6. |
Тема 6. Элементы теории алгоритмов |
1 |
1 |
13 |
15 |
|
Итого: |
8 |
8 |
113 |
129 |
4.5. Примерная тематика курсовых проектов (работ) -
НЕ ПРЕДУСМОТРЕНЫ.
4.6. Контрольная работа по дисциплине
«ДИСКРЕТНАЯ МАТЕМАТИКА»
В течение семестра студент выполняет одну контрольную работу по программе курса, при этом номер варианта должен совпадать с последней цифрой его учебного шифра. Соответствующие номера задач приведены в табл. 1. Например, в контрольную работу студента, имеющего учебный шифр 1108574, включены задачи 4, 14, 24, 34, 44, 54, а в контрольную работу студента, имеющего учебный шифр 1108570, – задачи 10, 20, 30, 40, 50, 60.
Табл. 1.
Вариант |
Контрольная работа |
|||||
1 |
1 |
11 |
21 |
31 |
41 |
51 |
2 |
2 |
12 |
22 |
32 |
42 |
52 |
3 |
3 |
13 |
23 |
33 |
43 |
53 |
4 |
4 |
14 |
24 |
34 |
44 |
54 |
5 |
5 |
15 |
25 |
35 |
45 |
55 |
6 |
6 |
16 |
26 |
36 |
46 |
56 |
7 |
7 |
17 |
27 |
37 |
47 |
57 |
8 |
8 |
18 |
28 |
38 |
48 |
58 |
9 |
9 |
19 |
29 |
39 |
49 |
59 |
10 |
10 |
20 |
30 |
40 |
50 |
60 |
Контрольную работу следует выполнять в отдельной тетради, оставив в ней поля для замечаний преподавателя-рецензента. На обложке тетради должны быть указаны: дисциплина, номер контрольной работы, номер (или название) учебной группы, шифр, курс, фамилия, имя, отчество студента,фамилия и инициалы преподавателя-рецензента. Контрольную работу необходимо выполнять аккуратно, чернилами любого цвета, кроме красного. Если работа выполнена неаккуратно, без соблюдения оговоренных ниже правил оформления или подчерком, не поддающимся прочтению, она возвращается студенту без проверки.
Задачи должны полностью соответствовать предусмотренным заданиями, решения должны быть выполнены в той же последовательности, что и в заданиях. Если в заданиях формулировка задачи дана для нескольких различных условий, то в контрольной работе задача должна быть сформулирована с конкретными данными строго индивидуально.
Решения всех задач должны быть подробно объяснены, все вычисления и преобразования должны быть показаны. Приближённые вычисления должны выполняться по соответствующим правилам. Для каждой задачи нужно записать ответ. Каждое новое задание оформляется с чистой страницы. В конце работы студент ставит дату выполнения и свою подпись.
Выполненная работа сдаётся для последующей проверки.
Если в контрольной работе после проверки отмечены ошибки и недочёты, сделаны замечания или указание что-то исправить, переделать, но контрольная работа допущена к зачёту, то студент должен в этой же тетради провести работу по устранению ошибок и недочётов. Выполнив это, студент может приходить на сдачу зачёта по работе.
Если контрольная работа не допущена к зачёту, студент должен в этой же тетради выполнить работу над ошибками и опять сдать работу для её повторной проверки.
На зачёт по дисциплине студент должен прибыть только с контрольной работой, которая зачтена.