Метод релаксации переменных решения СЛАУ

Содержание

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

Ва 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 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

Вместе с этим смотрят:

РЖнварiантнi пiдпростори. Власнi вектори i власнi значення лiнiйного оператора

РЖнтерполювання функцiй

Автокорреляционная функция. Примеры расчётов

Актуальные проблемы квантовой механики

Алгебра и алгебраические системы