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

http://www..ru/

Задание 1

Задание 2

Задание 3

Задание 4

Задание 5

Задание 6

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

Задание 1

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

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

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

Задание 2

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

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

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

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

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

Задание 3

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

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

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

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

СКНФ (нули):

Задание 4

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

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

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

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

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

Задание 5

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

Пути из 1 в 4:

1. 1−3-4

2. 1−2-4

Задание 6

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

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

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

//—————————————————————————————————————;

#include

#pragma hdrstop

//—————————————————————————————————————;

#pragma argsused

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

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

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

#include

#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

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

D[S] = 0;

for (i=0;i

Q[S] = 0;

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

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

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

{

Min = B;

for (i=0;i

if (Q[i]==1 && D[i]

Q[u] = 0;

for (i=0;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<< 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

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

for (int j=0;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

#pragma hdrstop

//—————————————————————————————————————;

#pragma argsused

#include

#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 finishn» ;

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

}

}

void main ()

{

Spisok Tree;

Tree.Postr ();

Tree.Reshenie ();

}

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

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

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

3. Уилсон Р.

Введение

в теорию графов. М.: Мир, 1977.

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