Тема 3. Графы и сети.

Определения графов. Смежность, инцидентность, степени вершин графа. Маршруты и пути. Связность. Матричное задание графов. Матрицы смежности и инцидентности. Операции над графами. Задача поиска кратчайшего пути в графе. Алгоритм Дейкстры. Транспортные сети. Поток в транспортной сети. Разрез и его пропускная способность. Алгоритм Форда-Фалкерсона построения максимального потока в транспортной сети.

Литература: [1] – C.189-205; 220-223; 228-232; [2] – С. 195-223.

Тема 4. Теория нечётких множеств. Теория неопределённости. Нечёткие алгоритмы.

Определение нечёткого множества. Функция принадлежности. Основные типы функций принадлежности, способы их построения. Операции над нечёткими множествами. Элементы нечёткой логики: понятие нечёткого высказывания, основные логические операции с нечёткими высказываниями. Понятие нечёткого вывода. Основные этапы и алгоритмы нечёткого вывода.

Литература: [6] – C.33-63; 68-79; 158-167; 185-205.

2.2. Практические занятия, их содержание.

Тема. Комбинаторика. Логика высказываний. Графы. Нечёткие множества.

Комбинаторика: правила суммы и произведения; размещения, перестановки, сочетания, подсчёт их числа. Логика высказываний: основные логические операции, формулы логики высказываний, таблицы истинности формул. Булевы функции: элементарные булевы функции; представление булевой функции в виде формул в СДНФ и СКНФ; минимизация булевых функций. Контактные схемы и их функции проводимости. Графы: матричное задание графов (матрица связности); операции над графами; задача поиска кратчайшего пути в графе (алгоритм Дейкстры). Нечёткие множества, операции над ними.

Литература: [6].- С.51-68, 114-137.

2.3. Виды самостоятельной работы студентов.

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

3. Рекомендуемая литература. Основная литература:

1. Новиков Ф.А. Дискретная математика для программистов. –СПб: Питер, 2000. -304с.

2. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: Учебное пособие. –М.: Логос, 2002. -240с.

Дополнительная литература:

3. Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учеб. пособие. –М.: Изд-во МАИ, 1992. -264с.

4. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. –М.: ИНФРА-М, 2002.-280с.

5. Леоненков А.В. Нечёткое моделирование в среде MATLAB и fuzzyTECH. –СПб.: БХВ-Петербург, 2003.-736с.

4. Методические указания по изучению дисциплины.

В процессе изучения данной дисциплины студенты должны сначала изучить теоретический материал и выработать навыки решения типовых задач, используя рекомендованную литературу, а затем выполнить одну контрольную работу (задания для контрольной работы приведены в разделе 5.1).

При выполнении контрольной работы необходимо придерживаться указанных ниже правил:

1. Контрольная работа должна быть выполнена студентом в отдельной ученической тетради с полями не менее 3 см для замечаний преподавателя.

2. На обложке тетради указываются: название дисциплины; номер варианта и номера решаемых задач; Ф.И.О. студента, выполнившего работу, его номер группы и номер зачетной книжки; Ф.И.О. преподавателя, проверяющего работу (образец оформления обложки приведён в Приложении 3).

3. Номер варианта соответствует номеру студента в списке группы.

4. Номера решаемых задач выбираются из ТАБЛИЦЫ НОМЕРОВ ВЫПОЛНЯЕМЫХ ЗАДАНИЙ (Приложение 4).

5. Условия задач переписываются полностью, без сокращения слов, после чего приводится их подробное решение (чертежи можно выполнять аккуратно от руки). В конце решения приводится ответ.

6. В работу должны быть включены все задачи, указанные в задании, строго по порядку номеров. Контрольные работы, содержащие не все задания, а также задачи не своего варианта, не зачитываются.

7. Если в работе имеются ошибки, студент должен выполнить все требования преподавателя, изложенные в рецензии, и сдать работу с исправлениями на повторную проверку.

8. Никакие исправления в тексте уже проверенной работы не допускаются, все исправления записываются после рецензии преподавателя с указанием номера задачи, к которой относятся дополнения и исправления.

9. Работа может быть выполнена заново в случае выявления серьёзных замечаний и ошибок.

10. В конце тетради рекомендуется оставлять несколько чистых страниц для дополнений и исправлений.

После проверки контрольная работа предъявляется к защите. На защите студент должен показать свое умение решать задачи, подобные тем, что имеются в его контрольной работе.

Образец решения типового варианта контрольной работы приведён в Приложении 1.