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

Содержание



Задание 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-3-4

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();

}




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



	Нефедов В.Н., Осипова В.А. Курс дискретной математики / МАИ. М., 1992. 

	Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 

	Уилсон Р. Введение в теорию графов. М.: Мир, 1977. 

			Берзтисс А.Т.Структуры данных.1974