Содержание
Задание 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
#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:
"; 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:
"; 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!
"; 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:
"; 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
"; cout << "node and cost of edge:
"; 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
(zip - application/zip)
Статистика файлового архива
