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

  

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

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

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

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

 
 
 
 
 
 
 
 

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

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

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

  (СТ. 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)