Моделирование систем

контрольная работа: Математика

Документы: [1]   Word-213028.doc Страницы: Назад 1 Вперед

Содержание


Задание 1

Задание 2

Задание 3

Задание 4

Задание 5

Задание 6

Список используемой литературы


Задание 1


Построить таблицу значений функции алгебры логики, найти все существенные переменные:        


Решение

Распишем данную функцию по действиям и для всех наборов значений 3 переменных, посчитаем их результаты:


xyz

x|z

x|y

x V y V z

(x|z)( x|y)

f

000

1

1

0

1

0

001

1

1

1

1

0

010

1

1

1

1

0

011

1

1

1

1

0

100

1

1

1

1

0

101

0

1

1

0

0

110

1

0

1

0

0

111

0

0

1

0

0


Функция тождественно принимает значение 0 при любых значениях переменных x,y,z. Поэтому в данной функции существенных переменных нет.


Задание 2


Построить полином Жегалкина функции:



Решение

Записываем таблицу значений функции


xyz

f

000

0

001

1

010

1

011

0

100

0

101

0

110

1

111

0


Находим СДНФ функции по единицам:

СДНФ функции:        

Полином Жегалкина:



Задание 3


Найти СКНФ и СДНФ функции:



Решение

Найдем с помощью таблицы значений:


xyz

xy

f

000

0

1

0

001

0

0

1

010

0

1

0

011

0

0

1

100

0

1

0

101

0

0

1

110

1

1

1

111

1

0

0


Получим СДНФ (единицы функции) и СКНФ (нули функции):

СДНФ (единицы):        

СКНФ (нули):        


Задание 4


С помощью карт Карно найти минимальную КНФ и ДНФ функции:



Решение

Запишем карту Карно:


      zt

00

01

11

10

xy

00

1

1

0

0

01

1

0

0

0

11

1

0

0

1

10

0

0

1

0


Минимальные формы:

КНФ (покрытия по нулям):        

ДНФ (покрытия по единицам):        


Задание 5


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


Решение



Таблица:


1

2

3

4

5

1

0

1

1

0

0

2

0

0

1

1

0

3

0

0

0

1

1

4

0

0

0

0

1

5

0

0

0

0

0


Пути из 1 в 4:

  1. 1-3-4
  2. 1-2-4


Задание 6


Придумать связный взвешенный граф из восьми вершин и не менее чем 14 ребер (нумерация ребер - слева направо, веса от 1 до 20). Для этого графа построить минимально островное дерево с помощью алгоритма Прима, и найти расстояние между вершинами 1 и 8 с помощью алгоритма Дейкстры. Реализовать алгоритм на любом языке программирования.

алгебра логика граф полином дейкстра

Решение



Текст программы для алгоритма Дейкстра


//---------------------------------------------------------------------------


#include <clx.h>

#pragma hdrstop


//---------------------------------------------------------------------------


#pragma argsused

//Нахождение расстояния от источника до всех вершин в графе

//с неотрицательными весами (метод Дейкстры).

//Нахождение кратчайшего пути из S в T.

#include <iostream.h>

#define MaxNodes 14

#define B 1000  //Машинный эквивалент бесконечности.


//Описание типа узла стека.

typedef struct Zveno *svqz;

struct Zveno

{

  int Element;

  svqz Sled;

};


class Spisok

{

  private:

         int A[MaxNodes][MaxNodes];  //Матрица весов дуг.

         int D[MaxNodes]; //Матрица расстояний от источника до

                          //всех вершин графа.

        svqz Stack; //Указатель на рабочий стек.

         void UDALENIE (svqz *, int *);

         void W_S (svqz *, int);

         int Pusto_Q (int *);

  public:

        Spisok() {Stack = NULL;}

         void Vvod_Ves();

        void Reshenie ();

};


void main ()

{

  Spisok A;

  A.Vvod_Ves();

  A.Reshenie();

}


int Spisok::Pusto_Q (int *Q)

{

  for (int i=0;i<MaxNodes;i++)

    if ( *(Q+i)!=0 ) return 0; //Ложь - не пусто!

  return 1; //Истина - пусто!

}


void Spisok::Reshenie ()

{

  int S; // Начальная вершина пути (источник).

  int T; // Конечная вершина пути.

  int u,v,Min;

  int i,j,k;

  svqz UkZv;

  int Q[MaxNodes];


  cout << "input source : ";

  cin >> S; S--;

  //Инициализация.

  for (i=0;i<MaxNodes;i++) { D[i] = A[S][i]; Q[i] = 0; }

  D[S] = 0;

  for (i=0;i<MaxNodes;i++)  Q[i] = 1;

  Q[S] = 0;

  //Вычисление матрицы расстояний от

  //источника до всех вершин графа.

  while (!Pusto_Q(&Q[0])) //Пока Q не пусто.

  {

    Min = B;

    for (i=0;i<MaxNodes;i++)

     if (Q[i]==1 && D[i]<Min) { Min = D[i]; u = i; }

    Q[u] = 0;

    for (i=0;i<MaxNodes;i++)

     if (Q[i] == 1)

       if ( D[i] > D[u]+A[u][i] ) D[i] = D[u] + A[u][i];

  }

  //Вывод матрицы расстояний от источника

  //до всех вершин графа.

  cout << "matrix of distanses: \n";

  for (i=0;i<MaxNodes;i++) cout << D[i] << " ";

  cout << endl;

  // -----------------------------------------------------

  // Нахождение кратчайшего пути из S в T с использованием

  //            построенной матрицы расстояний.

  // -----------------------------------------------------

  cout << "Inpute finish node: ";

  cin >> T; T--;

  W_S (&Stack,T); v = T;

  while ( v!=S )

  {

    for (i=0;i<MaxNodes;i++)

      if ( D[v]==D[i]+A[i][v] ) u = i;

    W_S (&Stack,u);

    v = u;

  }

  //Вывод кратчайшего пути на экран дисплея.

  cout << "Minimal path: ";

  UkZv = Stack;

  while ( UkZv != NULL )

  {  cout << (UkZv->Element+1) << " ";

     UkZv = UkZv->Sled;  }

  cout << endl;

}


void Spisok::Vvod_Ves()

//Ввод матрицы весов дуг заданного графа.

{

  cout << "Inppute the elements of edge matrix by strings:\n";

  for (int i=0;i<MaxNodes;i++)

   for (int j=0;j<MaxNodes;j++)

     {

       cout << "Inpute A[" << (i+1) << "," << (j+1) << "]: ";

       cin >> A[i][j];

       if ( A[i][j]==0 ) A[i][j] = B;

     }

}


void Spisok::W_S (svqz *stk, int Elem)

//Помещение Elem в стек stk.

{

  svqz q=new (Zveno);

  (*q).Element = Elem;

  (*q).Sled = *stk; *stk = q;

}


void Spisok::UDALENIE (svqz *stk, int *Klad)

//Удаление звена из стека, заданного указателем *stk.

//Значение информационного поля удаляемого звена сохраня-

//ется в параметре Klad.

{

  svqz q;


  if (*stk==NULL) cout<<"try to select from the empty stack!\n";

  else

       { *Klad = (**stk).Element;

         q = *stk; *stk = (**stk).Sled; delete q; }

}


Алгоритм Прима:

//---------------------------------------------------------------------------


#include <clx.h>

#pragma hdrstop


//---------------------------------------------------------------------------


#pragma argsused

#include <iostream.h>

#define TRUE 1

#define FALSE 0

typedef int Boolean;

typedef unsigned int SubInt;

typedef struct Uzel *Ref;


struct Uzel

{

  SubInt X; //Начало дуги.

  SubInt Y; //Конец дуги

  int Pay;  //Стоимость дуги.

  Ref Left; //Указатель на левого сына.

  Ref Right;//Указатель на правого сына.

};


typedef struct zveno *svqz;

struct zveno

{

  unsigned int Element[256];

  svqz Sled;

  zveno();

};


zveno::zveno()

{

  for(int k=0;k<256;Element[k++]=0);

}


class Spisok

{

  private:

        Ref Root;

        void Search (int, int, int, Ref *);

        void Poisk (svqz, SubInt, svqz *);

        void Postroenie (svqz *);

        void Udalenie (svqz *, svqz);

  public:

        Spisok() { Root = NULL;} //Вначале дерево пусто.

        void Reshenie();

        void Postr();

};


void Spisok::Search (int A, int B, int C, Ref *p)

//Добавление вершины, содержащей поля A,B,C, в дерево *p.

{

  if ( (*p) == NULL )

  {

         (*p) = new (Uzel); (**p).X = A; (**p).Y = B; (**p).Pay = C;

         (**p).Left = (**p).Right = NULL;

  }

  else

         if ( C<=(**p).Pay ) Search (A,B,C,&((**p).Left));

         else

                if ( C>(**p).Pay ) Search (A,B,C,&((**p).Right));

}


void Spisok::Postroenie (svqz *UkStr)

//Постpоение линейного однонапpавленного списка

//с заглавным звеном, содержащего вершины графа.

{

  svqz UkZv;

  int el;


  (*UkStr) = new (zveno);

  UkZv = (*UkStr); UkZv->Sled = NULL;

  cout << "Input nodes: \n";

  cin >> el;

  while ( el!=0 )

  {

        UkZv->Sled = new (zveno); UkZv = UkZv->Sled;

        UkZv->Element[el] = 1; UkZv->Sled = NULL;

        cin >> el;

  }

}


void Spisok::Postr()

//Постpоение деpева, содержащего все ребра графа.

{

  int A,B,C;


  cout << "For every nodes input input start and finish\n";

  cout << "node and cost of edge:\n";

  cin >> A >> B >> C;

  while ( A!=0 )

  { Search (A,B,C,&Root);

        cin >> A >> B >> C;

  }

}


void Spisok::Poisk (svqz st, SubInt MENT, svqz *Res)

{

  svqz q;


  (*Res) = NULL; q = st->Sled;

  while  ( q != NULL  &&  (*Res) == NULL )

  {

        if ( q->Element[MENT]==1 ) (*Res) = q;

        else  q = q->Sled;

  }

}


void Spisok::Udalenie (svqz *zv, svqz UkStr)

//Удаление из однонапpавленного списка с заглавным звеном

//элемента, на который указывает указатель zv.

{

       svqz Z;     //"Стаpый" указатель.

       svqz UkZv1; //"Hовый" указатель.


       if ( (*zv)->Sled != NULL ) (**zv) = *((**zv).Sled);

       else

       {  Z = UkStr; UkZv1 = UkStr->Sled;

               while  (UkZv1 != (*zv))

               { Z = UkZv1; UkZv1 = UkZv1->Sled; }

               Z->Sled = NULL; delete UkZv1;

       }

}


void Spisok::Reshenie()

{

  svqz UkStr;  //Указатель на список.

  Ref UkUzel;  //Рабочий указатель на узел дерева.

  Ref UkUzel1; //Рабочий указатель на узел дерева.

  SubInt T1,T2;

  svqz Res1,Res2;


  //Построение первоначальных множеств вершин графа.

  Postroenie (&UkStr);

  cout <<"Edges with minimsl cost: ";

  while ( UkStr->Sled->Sled != NULL )

  {

        UkUzel1 = Root;       //"Отстающий" указатель.

        UkUzel  = Root->Left; //"Опережающий" указатель.

        if ( UkUzel== NULL )

        { //Выбор в дереве ребра наименьшей стоимости и ...

               T1 = Root->X; T2 = Root->Y;

               //... удаление этого ребра из дерева.

               Root = Root->Right; delete UkUzel1;

        }

        else

        { //Выбор в дереве ребра наименьшей стоимости и ...

               while ( UkUzel->Left != NULL )

               {

                 UkUzel1 = UkUzel1->Left;

                 UkUzel  = UkUzel->Left;

               }

               T1 = UkUzel->X; T2 = UkUzel->Y;

               //... удаление этого ребра из дерева.

               UkUzel1->Left = UkUzel->Right;

               delete UkUzel;

        }

        //Если v и w принадлежат различным

        //множествам W1 и W2 из VS ...

        Res1 = Res2 = NULL;

        Poisk (UkStr,T1,&Res1);

        Poisk (UkStr,T2,&Res2);

        if ( Res1!=Res2 )

        {

           for (int k=0;k<256;k++)

            if ( Res1->Element[k]==1 || Res2->Element[k]==1 )

                     Res1->Element[k]=1;

             Udalenie (&Res2,UkStr);

             cout << "(" << T1 << " " << T2 << ")  ";

        }

  }

}


void main ()

{

  Spisok Tree;

  Tree.Postr();

  Tree.Reshenie();

}


Список используемой литературы


  1. Нефедов В.Н., Осипова В.А. Курс дискретной математики / МАИ. М., 1992.
  2. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.
  3. Уилсон Р. Введение в теорию графов. М.: Мир, 1977.
  4. Берзтисс А.Т.Структуры данных.1974

Размещено на Allbest.ru


Страницы: Назад 1 Вперед