Введение. Студент Вензель Александр Андреевич

ЗАДАНИЕ

НА КУРСОВУЮ РАБОТУ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

Студент Вензель Александр Андреевич

Факультет АИТ Группа 2101-11с

Тема курсовой работы: « Исследование методов решения задач дискретной математики»

Требуется:

Задание 1

Изобразить на диаграммах Эйлера-Венна. При необходимости выражение упростить, используя тождества алгебры множеств.

Задание 2

Доказать с помощью основных тождеств и показать на диаграммах Эйлера-Венна.

Задание 4

Схематично изобразить геометрическое место точек прямого произведения множеств.

Задание 6

Дано отношение.

a) Построить примеры пар отношения.

b) Построить графическое представление.

c) Выяснить свойства отношения: рефлексивность, симметричность, транзитивность, антисимметричность.

Теория графов

Задание 1. Ориентированный граф

1. Охарактеризовать граф.

2. Назвать специальные вершины и рёбра.

3. Рассчитать полустепени вершин.

4. Выписать матрицы смежности, инцидентности, достижимости, связности.

5. Выписать цикл, цепь, простой цикл, простую цепь.

Задание 2. Неориентированный граф

1. Начертить граф по матрице длин дуг. Самостоятельно обозначить ребра.

2. Охарактеризовать граф.

3. Назвать специальные вершины и рёбра.

4. Рассчитать степени вершин.

5. Выписать матрицы смежности, инцидентности, достижимости, связности.

6. Выписать цикл, цепь, простой цикл, простую цепь.

7. Рассчитать ОД и МОД.

Содержание

Реферат. 5

Введение. 6

1 Основные понятия теории множеств. 7

2.Основные понятия теории графов. 8

1Множества и отношения. 10

Задание 1. 10

Задание 2. 11

Задание 3. 12

Задание 4. 12

Задание 5. 12

Задание 6. 13

Задание 7. 14

2. Теория графов. 15

Задание 1. Ориентированный граф.. 15

Задание 2. Неориентированный граф.. 17

Курсовая работа представляет собой выполнение заданий по темам «Множества и отношения» и «теория графов»

Цель курсовой работы – ознакомится с основными понятиями и методами решения по дискретной математике, уметь применить полученные знания при решении практического задания

Пояснительная записка включает в себя 19 страниц текста, 9 таблиц и 15 диаграмм.

Введение

Проблемы, связанные с понятиями бесконечности, дискретности и непрерывности, рассматривались в математике, как и в философии, древнегреческими мыслителями, начиная с 6 века до нашей эры. Под влиянием сочинений Аристотеля они широко обсуждались средневековыми учеными и философами в странах Европы и Азии. Через всю историю математики проходит идея преодоления между актуальной и потенциальной бесконечностью, с одной стороны, между дискретным характером числа и непрерывной природой геометрических величин – с другой. Впервые проблема математической бесконечности и связанных с нею понятий была широко поставлена в наиболее общем виде в теории множеств, основы которой были разработаны в последней четверти 19 века Георгом Кантором.

Основные понятия теории множеств

Понятие " множество" является первичным и неопределяемым. Множество можно представить себе как совокупность элементов, обладающих некоторым общим свойством.

Объекты любой природы (числа, люди, вещи и т. д.), составляющие множество, называют его элементами. Например, студент Иванов является элементом множества студентов IV курса,

март – элементом множества месяцев в году и т.д.

Для того чтобы некоторую совокупность элементов можно было назвать множеством, необходимо, чтобы выполнялись следующие условия:

- должно существовать правило, позволяющее определить, принадлежит ли указанный элемент данной совокупности;

- должно существовать правило, позволяющее отличать элементы друг от друга (это означает, что множество не может содержать двух одинаковых элементов).

Тот факт, что элемент a принадлежит множеству А записывается так: a A, в противном случае пишем a A. Для однозначного описания некоторого множества мы будем пользоваться следующими способами:

– перечислением всех его элементов. Например, множество A, состоящее из объектов: a, b, c, d записывают так: A = {a, b, c, d}. Данный способ применим только для конечных множеств, число элементов которых невелико;

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

Например, множество K натуральных чисел, меньших 5 можно записать: K= {1, 2, 3, 4} или

K={х | х N и х < 5}.

Множества могут быть конечными или бесконечными. Например, множество работников предприятия – конечно, а множество точек прямой – бесконечно.

Пустым множеством называют единственное множество, не содержащее ни одного элемента (обозначается символом). Например, это множество транзисторов, изготовленных в 1930 году.2

Множества A и B считают равными, если они состоят из одних и тех же элементов (записывают A = B). Например, равны следующие множества: А={>, $, @,! } и B={!, >, @, $}.

Множество B называют подмножеством множества A тогда и только тогда, когда каждый элемент B принадлежит множеству A (записывается: В А). Например, А – множество студентов вуза, В – подмножество первокурсников этого вуза.

Свойство подмножеств: если В А и А В, то А=В.

Достаточно часто для наглядного изображения множеств и операций над ними используют так называемые круги Эйлера (диаграммы Венна). На следующем рисунке

показаны множества А и B такие, что В А.

Часто бывает, что рассматриваются только подмножества одного и того же множества.

Такое множество называют универсальным множеством, по предположению содержит все используемые нами множества (обозначают U и изображают на кругах Эйлера в виде прямоугольника).

Основные понятия теории графов

Граф – система, которая интуитивно может быть рассмотрена

как множество кружков и множество соединяющих их линий

(геометрический способ задания графа – см. рисунок 1). Кружки

называются вершинами графа, линии со стрелками – дугами, без

стрелок – ребрами. Граф, в котором направление линий не выделя-

ется (все линии являются ребрами), называется неориентирован-

ным; граф, в котором направление линий принципиально (линии

являются дугами) называется ориентированным.

Теория графов может рассматриваться как раздел дискретной

математики (точнее – теории множеств), и формальное определе-

Начало теории графов датируют 1736 г., когда Л. Эйлер решил популярную вто время «задачу о кенигсбергских мостах». Термин «граф» впервые был введенспустя 200 лет (в 1936 г.) Д. Кенигом. 2

ние графа таково: задано конечное множество X, состоящее из n

элементов (X = {1, 2,..., n}), называемых вершинами графа, и

подмножество V декартова произведения X ¥ X, то есть V Õ X

называемое множеством дуг, тогда ориентированным графом G

называется совокупность (X, V) (неориентированным графом назы-

вается совокупность множества X и множества неупорядоченных

пар элементов, каждый из которых принадлежит множеству X).

Дугу между вершинами i и j, i, j Œ X, будем обозначать (i, j). Число

дуг графа будем обозначать m (V = (v1, v2,..., vт)).

Язык графов оказывается удобным для описания многих фи-

зических, технических, экономических, биологических, социаль-

ных и других систем.

Приведем ряд примеров приложений теории графов.

1. «Транспортные» задачи, в которых вершинами графа явля-

ются пункты, а ребрами – дороги (автомобильные, железные и др.)

и/или другие транспортные (например, авиационные) маршруты.

Другой пример – сети снабжения (энергоснабжения, газоснабже-

ния, снабжения товарами и т.д.), в которых вершинами являются

пункты производства и потребления, а ребрами – возможные

маршруты перемещения (линии электропередач, газопроводы,

дороги и т.д.). Соответствующий класс задач оптимизации потоков

грузов, размещения пунктов производства и потребления и т.д.,

иногда называется задачами обеспечения или задачами о размеще-

нии. Их подклассом являются задачи о грузоперевозках [7, 12].

2. «Технологические задачи», в которых вершины отражают

производственные элементы (заводы, цеха, станки и т.д.), а дуги – 3

потоки сырья, материалов и продукции между ними, заключаются

в определении оптимальной загрузки производственных элементов

и обеспечивающих эту загрузку потоков [7, 12].

3. Обменные схемы, являющиеся моделями таких явлений как

бартер, взаимозачеты и т.д. Вершины графа при этом описывают

участников обменной схемы (цепочки), а дуги – потоки матери-

альных и финансовых ресурсов между ними. Задача заключается в

определении цепочки обменов, оптимальной с точки зрения, на-

пример, организатора обмена и согласованной с интересами участ-

ников цепочки и существующими ограничениями [6, 9, 17].

4. Управление проектами

. С точки зрения теории графов про-

ект – совокупность операций и зависимостей между ними (сетевой

график – см. ниже). Хрестоматийным примером является проект

строительства некоторого объекта. Совокупность моделей и мето-

дов, использующих язык и результаты теории графов и ориентиро-

ванных на решение задач управления проектами, получила назва-

ние календарно-сетевого планирования и управления (КСПУ)

[7, 10]. В рамках КСПУ решаются задачи определения последова-

тельности выполнения операций и распределения ресурсов между

ними, оптимальных с точки зрения тех или иных критериев (вре-

мени выполнения проекта, затрат, риска и др.).

5. Модели коллективов и групп, используемые в социологии,

основываются на представлении людей или их групп в виде вер-

шин, а отношений между ними (например, отношений знакомства,

доверия, симпатии и т.д.) – в виде ребер или дуг. В рамках подоб-

ного описания решаются задачи исследования структуры социаль-

ных групп, их сравнения, определения агрегированных показате-

лей, отражающих степень напряженности, согласованности

взаимодействия и др.

6. Модели организационных структур, в которых вершинами

являются элементы организационной системы, а ребрами или

дугами – связи (информационные, управляющие, технологические

и др.) между ними