Исследование алгоритмов решения задач дискретной математики

  

Министерство  образования и науки РФ

ФГБОУ ВПО «Сибирский государственный технологический университет»

      Факультет автоматизации и информационных технологий

     Кафедра информационных технологий

 
 
 
 
 
 
 
 

ИССЛЕДОВАНИЕ  АЛГОРИТМОВ

РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОЙ МАТЕМАТИКИ 

  Пояснительная записка

  (СТ. 000000. 035 ПЗ) 
 
 
 

                                                 Руководитель 

                                                 Иванилова Т.Н.

                                                 ___________________

                                                 дата               оценка          роспись 

                                                 Выполнил

                                                 студент группы 230100

                                                 Нагельман И. Ю.

                                                 ___________________

                                                 дата сдачи                    роспись 
 
 
 
 
 
 
 
 
 
 
 

  Красноярск, 2011

 

  Сибирский государственный  технологический университет

  Кафедра системотехники  

  ЗАДАНИЕ

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

  Студент    Нагельман Илья Юрьевич

  Факультет ЗХТ_ Группа 230100

  Тема  КР: Исследование алгоритмов решения задач дискретной математики

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

     Задание 1

1.  
2.  

     Задание 2

     

     Задание 3

     

     Задание 4

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

произведения  .

     Задание 5

  ρ1-"x и y кратны 4";    ρ2-"x и y кратны 20"

     Задание 6

 

   ,

     Задание 7

 

1. «Служить  моделью» на множестве произвольных объектов;

 

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

   Задание 1

 
 
 
 

 

 

Календарный план выполнения работы 

  1 – 5.10.11 -          формализация задачи

  6 – 10.10.11 -             уточнение входной и выходной информации

  11 – 18.10.11 –          решение заданий 1,2,3,4,5,6,7 по множествам и отношениям

  19 – 30.10.11 –            решение заданий по ориентированному графу

  1 - 10.12.11 –            решение заданий по неориентированному графу

  11 - 20.12.11 -             работа с обучающими программами

  23.12.11 – защита КР

                         Задание выдано 01.10.11

                         Руководитель___________Иванилова Т.Н.

 

   Содержание

    
 

       Реферат…………………………………………………………………………..5 

       Введение…………………………………………………………………………6 

       Вариант 23. Задания………………….…………………………………………7 

       Решение. Множества и отношения..…………………………………………...8 

       Решение. Теория графов………………………………………………………..11 

       Заключение……………………………………………………………………...15 

       Список  использованных источников………………………………………… 16 
 
 
 

 

Реферат 

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

          Пояснительная записка  включает в себя __ страниц текста, __ использованных литературных источника, 1 приложение.

          Ключевые слова: ДИСКРЕТНАЯ МАТЕМАТИКА, МНОЖЕСТВО, БИНАРНЫЕ ОТНОШЕНИЯ, ГРАФ (до 10 ключевых слов).

          Цель работы - выполнение расчетов для решения задач по разделам дисциплины «Дискретная математика».

    Данная  работа представляет решение следующих  задач:

1. графическое представление операций над множествами;
2. доказательство равенства множеств с использованием диаграмм Эйлера-Венна и основных тождеств дискретной математики;
3. нахождение геометрического места точек прямого произведения множеств;
4.  графическое представление бинарного отношения;
5. определение свойств бинарного отношения;
6. определение степеней и полустепеней вершин графа;
7. расчет матричных представлений графа;
8. нахождение путей и маршрутов в графе;
9. определение остовных деревьев графа.

 

Введение

     Дискретная  математика заявила о себе уже  адвно, более 200 лет назад. Тем не менее высокая востребованность в дискретной математике, как в  самостоятельном , существенно важном разделе математики, проявилась лишь в послевоенные годы.  И связано это было с появлением первых вычислительных машин.

       Поскольку работа и функционирование  компьютера это дискретный процесс,  роль дискретной математики, как самостоятельной дисциплины очень велика. 
ВАРИАНТ 23

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

     Задание 1

1 

2 

     Задание 2

     

     Задание 4

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

произведения  .

     Задание 6

 

   ,

     Задание 7

 

2. «Служить  моделью» на множестве произвольных объектов;

 

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

   Задание 1

   Задание 2

 
 
 
 

 

Решение

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

     Задание 1

     №1

 
 

1)

2)  

      №2  

1) С\B\A    3)

2)  

 

 

Задание 2

   Покажем выполнение равенства на диаграммах Эйлера-Венна. 

По закону дистрибутивности   

1) Левая часть  равенства.

В+С       

2) Правая часть

             

Задание 2

 

   Покажем выполнение равенства на диаграммах Эйлера-Венна.

   1) Левая часть равенства: 
 
 
 

   

   

   2) Правая часть равенства: 
 
 
 
 
 
 
 
 

 

  Задание 4

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

произведения .

{1.4}{2.6}{2.4}={122}{124}{162}{164}{422}{424}{462}{464} 

   Задание 6

,

a) p= {<1,1><1.2><1.3><1.4><1.5><1.6><<2.1><2.2><2.3><2.4><2.5><3.1><3.2><3.3><3.4><4.1><4.2><4.3><5.1><5.2><6.1>}|

b)

c) Cсимметрично, т.к. на пару <1.6> есть пара <6.1>

Рефлексивно, т.к. для найдется пара <x,x>. Например, <1,1>, <2,2>, <3,3> и т.д.;

Не  транзитивно, т.к. для пар <6,1> ,<1,6> не существует пара <6,6>;

Не  антисимметрично, т.к. есть симметричные пары

 

    Задание 7

«Служить  моделью» на множестве произвольных объектов;

не  рефлексивно т.к. X не может быть моделью сам для себя.

Не  симметрично т.к X является моделью для Y => Y не может являться моделью для X

транзитивно т.к X является модель для Y, а Y является моделью для Z следовательно X является моделью для Z

антисимметрично т.к есть только пары где X модель для Y.

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

   Задание 1

1. Ориентированный псевдограф D=(V,X). V={v₀,v₁,v₂,v₃,v₄,v₅}, X={x₀,x₁,x₂,x₃,x₄,x₅,x_6,x₇,x₈,x₉,x₁₀}. x₀=<v₁,v₄>, x₁=<v₀,v₂>, x₂=<v₂,v₄>, x₃=<v₂,v₃>, x₄=<v₃,v₅>, x₅=<v₅,v₅>, x₆=<v₅,v₄>, x₇=<v₅,v₄>, x₈=<v₃,v₁>, x₉=<v₁,v₂>, x₁₀=<v₁,v₀>.

 

2. X₅ – петля, x₆,x₇ – кратные ребра

 

3. Полустепени вершин: d⁺(v₀)=2, d^-(v₀)=1, d⁺(v₁)=2, d^-(v₁)=1, d⁺(v₂)=2, d^-(v₂)=2, d⁺(v₃)=2, d^-(v₃)=1, d⁺(v₄)=0, d^-(v₄)=4, d⁺(v₅)=3, d^-(v₅)=2

    

     4.Матрица смежности

Матрица инцидентности

 
 

Матрица связности:

 

Матрица достижимости:

 
 

5. Простой цикл: V₀X₁V₂X₃V₃X₈V₁X₁₀V₀   V₁X₉V₂X₃V₃X₈V₁

Цикл: нет циклов

   Простая цепь : V₀X₁V₂X₂V₄

   Цепь: V₀X₁V₂X₃V₃X₄V₅X₅V₅

   Задание 2

 

2. Неориентированный граф G=(V,X). V={v₀,v₁,v₂,v₃,v₄,v_5, v₆}, X={x₀,x₁,x₂,x_3,x₄,x₅,x_6,x₇,x₈}. x₀={v₀,v₀}, x₁={v₀,v₂}, x₂={v₀,v₃}, x₃={v₃,v₁}, x₄={v₄,v₁}, x₅={v₁,v₅}, x₆={v₂,v₄}, x₇={v₄,v₆}, x₈={v₃,v₃}.

 

3. v₅ и v₆– висячие вершины.

 

4. Степени вершины 

d(v₀)=3, d(v₁)=3, d(v₂)=2, d(v₃)=3, d(v₄)=3, d(v₅)=1, d(v₆)=1. 

Матрица смежности

Матрица инцидентности