Анализ и алгоритмы

МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Московский  государственный технический университет  радиотехники, электроники и автоматики" МГТУ МИРЭА
Факультет информационных технологий
Кафедра вычислительной техники

 

КУРСОВАЯ РАБОТА
по дисциплине
«Дискретная математика»
Тема курсовой работы «Анализ и алгоритмы»
Студент группы ИВБ-4-12	Абаев Р. Г.
Руководитель курсовой работы доцент кафедры ВТ	Антик М. И.

 

Работа представлена к защите	«__»_______2013 г.	(подпись студента)
Допущен к защите	«__»_______2013 г.	(подпись руководителя)
Оценка	«__»_______2013 г.

 

 

 

 

Москва 2013

Задание 1.1

Выяснить взаимное расположение множеств D, E, F, если A, B, C – произвольные подмножества U. Указать расположение множеств на карте Карно.

 

D:

	BC	00	01	11	10
A
0		×	×
1		×	×	×	×

 

E:

	BC	00	01	11	10
A
0					×
1				×	×

 

F:

	BC	00	01	11	10
A
0		×	×	×
1				×	×

 

Вывод: ;

 

Задание 1.2

Проверить, что для любых множеств A, B, C выполнение включения α влечет выполнение включения β. Проверить другие возможные импликации.

 

α:

β:

 

Вывод: α β

Задание 1.3

Для произвольных множеств A, B, H проверить, является ли выполнение включения α необходимым и достаточным условием выполнения равенства β. Проверить другие возможные импликации.

 

α:

β:

 

Проверим отношение α к β с помощью таблицы истинности:

A	B	H	α	β
0	0	0	1	1
0	0	1	1	1
0	1	0	0	0
0	1	1	1	1
1	0	0	0	0
1	0	1	1	1
1	1	0	0	0
1	1	1	1	1

 

Вывод: α ≡ β

 

Задание 1.4

Выяснить, верно ли равенство α для произвольных A, B, C.

α:

 

a:

b:

 

 

a = b

 

Вывод: равенство α выполняется.

 

 

 

 

 

 

Задание 3

Добавить от 1 до 3 сущностей к заданным сущностям («Воспитательница» и «Детский сад»). Создать ER-модель предметной области. По ER-модели предметной области построить схему реляционной базы данных.

 

Атрибуты:

 

Детский сад

Индекс Директор Адрес Телефон

Воспитатель

Индекс Полное имя Возраст Стаж

Группа

Индекс Год обучения

Ребенок

Индекс Полное имя Возраст Адрес проживания

 

 

 

 

 

 

 

 

 

 

 

 

Схема:

 

Генерация подмножеств для заданного множества.

 

//Генерация подмножеств  заданного множества

//с ограниченным числом  элементов

#include <iostream>

using std::cin;

using std::cout;

 

int main()

{

//Ввод размера множества

int n;

cin >> n;

if(n<=0)

return 0;

 

//Ввод предела размера  подмножества

int size;

cin >> size;

if(size<=0 || size>n)

return 0;

 

//Создание и ввод множества

int *A = new int[n];

for(int l=0;l<n;l++)

cin >> A[l];

 

//Создание массива для  кода Грея

short *B = new short[n];

for(int l=0;l<n;l++)

B[l]=0;

 

//Генерация всех подмножеств

int i=0,p,j,count;

do

{

//Подсчет количества элементов  в подмножестве

count=0;

for(int l=0;l<n;l++)

if(B[l]==1)

count++;

//Вывод подмножества, если  количество его элементов равно  size

if(count==size)

{

for(int l=0;l<n;l++)

{

if(B[l]==1)

cout << A[l] << ' ';

}

cout << '\n';

}

//Генерация следующего  кода Грея

i++;

p=0;

j=i;

while (j%2==0)

{

j=j/2;

p++;

}

if(p<n)

B[p]=1-B[p];

}

while (p<n);

delete[] B;

delete[] A;

 

return 0;

}

 

Генерация всех разбиений множества

 

//Генерация всех разбиений  множества

#include <iostream>

using std::cin;

using std::cout;

 

//Вывод разбиения на  экран

//a - исходное множество

//b - разбиение

void PrintPartition(int size, int *a, int* b)

{

//Проверка на существование  массивов

if(a==NULL || b==NULL)

return;

//Вычисляем количество  подмножеств в данном разбиении

int blocks=1;

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

if(b[i]>blocks)

blocks=b[i];

//Выводим каждое подмножество

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

{

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

if(b[j]==i+1)

cout << a[j] << ' ';

if(i!=blocks-1)

cout << "| ";

}

cout << '\n';

}

 

//Помещает в элемент  массива b с номером pos элементы от 1 до max

//и для каждого значения  вызывает сама себя для следующей  позиции массива

//а - исходное множество

//size - размер множества

void Partition(int pos, int max, int size, int *a, int *b)

{

//Проверка на существование  массивов

if(a==NULL || b==NULL)

return;

//Если достигнут конец массива, то вывести разбиение

if(pos>=size)

{

PrintPartition(size,a,b);

return;

}

//Цикл по всем возможным  вариантам для данной позиции  массива

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

{

b[pos]=i+1;

//Переход к следующей  позиции массива

//При этом, если данная позиция достигла максимума, то максимум следующей увеличивается на 1

if(i+1==max)

Partition(pos+1,max+1,size,a,b);

else

Partition(pos+1,max,size,a,b);

}

}

 

int main()

{

//Ввод размера множества

int n;

cin >> n;

if(n<=0)

return 0;

//Ввод множества

int *A = new int[n];

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

cin >> A[i];

cout << '\n';

 

int *B = new int[n];

 

//Генерация разбиений

//Начальное значение: нулевой  элемент массива, максимальный индекс - 1

Partition(0,1,n,A,B);

 

delete[] A;

delete[] B;

 

return 0;

}

Генерация всех перестановок множества

 

//Генерация всех перестановок  множества

#include <iostream>

using std::cin;

using std::cout;

 

//Множество

int* A;

//Размер множества

int size;

 

//Вывод множества

void Output()

{

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

       cout<<A[i]<<" ";

    cout<<"\n";

}

 

//Поменять местами два  элемента множества

void Swap(int x,int y)

{

    int temp = A[x];

    A[x] = A[y];

    A[y] = temp;

}

 

//Сгенерировать следующее  разбиение

void Generate(int k)

{

//Генерация завершена, вывести  множество

    if (k==size)

    {

        Output();

    }

    else

    {

//Продолжить генерацию

        for(int j=k;j<size;j++)

        {

            Swap(k,j);

            Generate(k+1);

            Swap(k,j);

        }

    }

}

 

int main()

{

    std::cout<<"Size: ";

    std::cin>>size;

if(size<=0)

return 0;

 

//Заполнение множества

A = new int[size];

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

        A[i] = i+1;

 

    Generate(0);

 

delete[] A;

return 0;

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Алгоритм Дейкстры

 

 

//Алгоритм Дейкстры

#include <iostream>

#include <string>

using std::cin;

using std::cout;

using std::string;

 

//Количество вершин

int n;

//Матрица стоимостей

//Расстояние между вершинами - положительное число

//Отсутствие ребра между  вершинами - 0

int **C;

 

//Число, превышающее максимальный  элемент матрицы(аналог бесконечности)

int max;

 

//Вычисление max

void SetMax()

{                               

max=0;

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

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

max=max+C[i][j];

max=max+1;

}

 

//Проверка на наличие  числа num  в массиве

bool in_arr(int num, int *arr)

{

bool result=false;

for (int i=0; i<n-1; i++)

if (arr[i]==num)

result=true;

return result;

}

 

//Перевод числа в строку

string inttostr(int num)

{

char buf[10];

itoa(num, buf, 10);

return string(buf);

}

 

int main()

{

cout << "Number of vertexes:" << "\n";

cin >> n;

//Номер вершины-источника

int a;

cout << "Main vertex: " << "\n";

cin >> a;

a--;

cout << "Vertexes: " << "\n";

 

//Ввод матрицы стоимостей

C = new int*[n];

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

C[i] = new int[n];

 

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

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

cin >> C[i][j];

 

cout << "\n";

 

SetMax();

 

//Вершины, помеченные, как  посещенные

int *S=new int[n-1];

//Кратчайшие расстояния  к вершинам из вершины-источника

int *D=new int[n];

//Последние промежуточные  вершины на маршруте

int *P=new int[n];

//Вспомогательные переменные

int w,min;

 

//Инициализация S(Ни одна вершина еще не посещена)

for (int k=0; k<n-1; k++)

{                   

S[k]=-1;                               

}

S[0]=a;

 

//Инициализация P и D

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

{                      

if (C[a][i]==0)

D[i]=max;

else

D[i]=C[a][i];

P[i]=a;

}

 

//Алгоритм Дейкстры

for (int i=1; i<n-1; i++)

{

min=max;

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

{

//Если расстояние до  k меньше текущего минимального и при этом

//k еще не посещена и не является вершиной-источником, то установить

//новый минимум

if (D[k]<min && !in_arr(k,S) && k!=a)

{

w=k;

min=D[k];

}

}

if (min==max) break;

//Вершина i посещена

S[i]=w;

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

{

//Если вершина j не посещена и путь от нее до текущей вершины w существует

//и расстояние от a до j >= сумме расстояний от a до w и от w до j,

//то установить новое  расстояние от a до j

if (!in_arr(j,S) && C[w][j]!=0 && (D[w]+C[w][j])<=D[j])

{

P[j]=w;

D[j]=D[w]+C[w][j];

}

 

}

}

 

//Вывод результатов

int t;

string str;                                                     

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

{

if (i!=a && C[P[i]][i]!=0)

{