Контрольная работа по "Математике". 22
Вариант №39
Задание 1.1
Выяснить взаимное расположение множеств D,E,F, если A,B,C – произвольные подмножества U. Указать расположение множеств на карте Карно. Записать минимальные нормальные формы для искомых множеств.
ᴗᴖ
Перейдем от множеств к логическим высказываниям:
a |
b |
c |
|||
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
ДНФ:
Карта Карно:
c ab |
00 |
01 |
11 |
10 |
0 |
||||
1 |
* |
* |
Минимизированная форма:
a |
b |
c |
|||
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
ДНФ:
Карта Карно:
c ab |
00 |
01 |
11 |
10 |
0 |
* |
|||
1 |
* |
* |
* |
Минимизированная форма:
a |
b |
c |
||
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
ДНФ:
Карта Карно:
c ab |
00 |
01 |
11 |
10 |
0 |
* | |||
1 |
* |
* |
* |
Минимизированная форма:
Из карт Карно получаем, что:
Задание 1.2
Проверить, что для любых множеств A,B,C выполнение включения влечет выполнение включения .Проверить другие возможные импликации.
Перейдем от множеств к логическим высказываниям:
a |
b |
c |
||
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
a |
b |
c |
|||||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
Из не следует
Из не следует
Задание 1.3
Для произвольных множеств A,B,H проверить, является ли выполнение включения * необходимым и достаточным условием выполнения равенства *. Проверить другие возможные импликации.
Перейдем от множеств к логическим высказываниям:
a |
b |
h |
||
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
a |
b |
h |
||||||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
Из не следует
Из не следует
Задание 1.4
Выяснить, верно ли равенство для произвольных A,B,C.
Перейдем от множеств к логическим высказываниям:
a b c |
| |||||
0 0 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 0 1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 1 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 1 1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 0 0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 0 1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 1 0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 1 1 |
1 |
1 |
1 |
0 |
0 |
0 |
Равенство не верно для произвольных A,B,C.
Задание 2.
На любом языке процедурного программирования записать алгоритм нахождения для заданного множества:
1)всех множеств
//нахождение всех подмножеств
#include <stdio.h>
#include <math.h>
int main(void)
{
int n; //количество элементов в множестве
printf("Enter the number of elements in set\n");
scanf("%d",&n); //ввод количества элементов в множестве
int m[n]; //массив с элементами множества
int i,j;
printf("Enter elements of set\n");
for(i=0;i<n;i++) //ввод множества
scanf("%d",&m[i]);
for(i=0;i<pow(2,n);i++) //цикл по всем элементам
{
for(j=0;j<n;j++) //цикл по всем битам маски
{
if(i&(1<<j)) //если побитовое умножение маски и j-го бита равно //единице...
{
printf("%d",m[j]); //…выводим j элемент
}
}
printf("\n");
}
return 0;
}
Тесты:
Количество элементов: |
Элементы: |
Подмножества: |
4 |
1 2 3 4 |
{1} {2} {1,2} {3} {1 3} {2 3} {1 2 3} {4} {1 4} {2 4} {1 2 4} {3 4} {1 3 4} {2 3 4} {1 2 3 4} |
3 |
5 7 3 |
{5} {7} {5 7} {3} {5 3} {7 3} {5 7 3} |
2) всех подмножеств с заданным количество элементов
//нахождение всех подмножеств c заданным числом элементов
#include <stdio.h>
#include <math.h>
int main(void)
{
int n; //количество элементов в множестве
int k; //количество элементов в подмножестве
int l,t,f,i,j; //счетчики
printf("Enter the number of elements in set\n");
scanf("%d",&n); //ввод количества элементов в множестве
printf("Enter the number of elements in subset\n");
scanf("%d",&k);
int m[n]; //массив с элементами множества
int d[k]; //массив с элементами подмножества
printf("Enter elements of set\n");
for(i=0;i<n;i++) //ввод множества
scanf("%d",&m[i]);
for(i=0;i<pow(2,n);i++) //цикл по всем элементам
{
for(t=0;t<k;t++) //обнуление
d[t]=0;
l=0;
for(j=0;j<n;j++) //цикл по всем битам маски
{
if(i&(1<<j)) //если побитовое умножение маски и j-го бита равно //единице...
{
d[l]=m[j]; //…добавляем j элемент в массив подмножества
l++;
}
}
if(l==k) //если количество элементов в массиве совпадает и заданным //…числом
{
for(f=0;f<t;f++)
{
printf("%d ",d[f]); //…выводим массив
}
printf("\n");
}
}
return 0;
}
Тесты:
Количество элементов: |
Количество элементов в |
Элементы: |
Подмножества |
3 |
2 |
1 2 3 |
{1 2} {1 3} {2 3} |
4 |
2 |
4 8 15 16 |
{4 8} {4 15} {8 15} {4 16} {8 16} {15 16} |
3) всех разбиений множества
#include <stdio.h>
int n; // количество элементов в множестве
int a[100]; // элементы множества
int p[100];
int i;
void print() //функция вывода
{
int i, j, imax;
imax = 1; // определяем количество блоков в разбиении
for (i = 1; i < n; i++)
if (p[i] > imax)
imax = p[i];
for (i = 1; i <= imax; i++) // цикл по блокам
{
printf("{");
for (j = 0; j < n; j++)
if (p[j] == i)
printf(" %d", a[j]);
printf(" }"); // блок напечатан
}
printf("\n");
}
void partition(int i, int j)//функция разбиения
{
int l;
if (i == n)
print(); // печатаем текущее разбиение
else
for (l = 1; l <= j; l++) // ставим элемент множества в разные блоки
{
p[i] = l;
if (l == j)
partition(i + 1, j + 1);
else
partition(i + 1, j);
}
}
int main(void)
{
printf("Enter the number of elements in set: ");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
a[i] = i + 1;
p[i] = 0;
}
partition(0, 1);
return 0;
}
Тесты:
Количество элементов: |
Подмножества |
3 |
{1 2 3} {1 2} {3} {1 3} {2} {1} {2 3} {1} {2} {3} |
4 |
{1 2 3 4} {1 2 3} {4} {1 2 4} {3} {1 2} {3 4} {1 2}{3}{4} {1 3 4} {2} {1 3}{2 4} {1 3}{2}{4} {1 4}{2 3} {1}{2 3 4} {1}{2 3}{4} {1 4}{2}{4} {1}{2 4}{3} {1}{2}{3 4} {1}{2}{3}{4} |
4)Алгоритм нахождения всех перестановок
#include <stdio.h>
int x[100]; //элементы множества
int n;
void Swap(int a,int b) //перестановка
{
int t=x[a];
x[a]=x[b];
x[b]=t;
}
void Generate(int k) //генерация
{
int i,j;
if (k==n)
{
for(i=0;i<n;i++)
printf("%d ",x[i]);
printf("\n");
}
else
{
for(j=k;j<n;j++)
{
Swap(k,j);
Generate(k+1);
Swap(k,j);
}
}
}
int main()
{
printf("Enter the number of elements in set\n");
scanf("%d",&n); //ввод количества элементов
int i;
for(i=0;i<n;i++)
x[i]=i+1;
Generate(0);
return 0;
}
Тесты:
Количество элементов: |
Подмножества |
3 |
{1 2 3} {1 3 2} {2 1 3} {2 3 1} {3 2 1} {3 1 2} |
4 |
{1 2 3 4}{1 2 4 3}{1 3 2 4}{1 3 4 2}{1 4 3 2}{1 4 2 3}{2 1 3 4}{2 1 4 3}{2 3 1 4}{2 3 4 1}{2 4 3 1}{2 4 1 3}{3 2 1 4}{3 2 4 1}{3 1 2 4}{3 1 4 2}{3 4 1 2}{3 4 2 1}{4 2 3 1}{4 2 1 3]{4 3 2 1}{4 3 1 2}{4 1 3 2}{4 1 2 3} |
Задание 3.
Добавить сущности(от 1 до 3) к двум заданным в таблице сущностям. Создать ER-модель предметной области. По ER-модели предметной области построить схему реляционной базы данных.
Сущности: Ведущий, Телеигра, Телеканал, Зарплата, Телевизор.
Ведущий |
Телеигра |
Телеканал |
Зарплата |
Номер ведущего *K1 |
Название *K2 |
Частота *K3 |
Номер зарплаты *K4 |
ФИО |
Жанр |
Название |
Размер |
Стаж работы |
Целевая аудитория |
Время эфира |
Налоги |
Телекомпания |
Время эфира |
Тип телеканала |
Надбавки |
ER-модель базы данных:
Ведущий
Телеканал
Телеигра
Зарплата
Получает
Ведет
В эфире на
МС
МС
1
1
НС
ОС
О
Н
ОС
Н
МС
МС
Схема реляционной базы данных:
K1 C1 K4
K4 C4
K3 C3
K2 C2
K1 K2
K2 K3
a
b
c
R1(K1 C1 K4)
R2(K4 C4)
- R1(K1 C1)
R2(K2 C2)
R3(K1 K2)
- R1(K2 C2)
R2(K3 C3)
R3(K2 K3)
Задание 4.
На любом языке процедурного программирования записать алгоритм нахождения кратчайшего пути в взвешенном ориентированном графе.
- Код на языке C++
#include <iostream>
using namespace std;
int w[100][100]; //массив вершин
bool used[100]; //массив использованных вершин
int d[100]; //массив длин
int inf=100000;//бесконечность
int main()
{
int n,m,v1,v2;
int x=0, y=0, z=0;
cout << "Enter the number of edges, number of arcs, starting edge and ending edge" << endl;
cin >> n >> m >> v1 >> v2;
v1--;
v2--;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
w[i][j]=0; //заполняем нулями
}
d[i]=inf; //заполняем бесконечностями
used[i]=false; //непосещены
}
cout << "Enter from what edge to what edge you need and length" << endl;
for (int i=0;i<m;i++) //ввод длинн
{
cin >> x >> y >> z;
w[x-1][y-1]=z;
w[y-1][x-1]=z;
}
d[v1]=0;
//алгоритм Дейкстры
while (true)
{
int from, zfrom=inf;
for (int i=0;i<n;i++)
if ((zfrom>d[i]) && !(used[i]))
{
from=i;
zfrom=d[i];
}
if(zfrom>=inf)
break;
used[from]=true;
for(int to=0;to<n;to++)
if (w[from][to]!=0)
if ((!used[to]) && (d[to]>d[from]+w[from][to]))
d[to]=d[from]+w[from][to];
}
if (d[v2]<inf)
cout<<d[v2];
else cout<<"-1";
return 0;
}
Тесты:
Количество вершин |
Количество дуг |
Длины |
Начало |
Конец |
Вывод |
3 |
3 |
1->2 6 1->3 5 2->3 7 |
1 |
3 |
5 |
3 |
3 |
1->2 6 1->3 20 2->3 7 |
1 |
3 |
13 |
- Контрольная работа по "Математике"
- Контрольная работа по "Математике"
- Контрольная работа по "Математике"
- Контрольная работа по "Математике"
- Контрольная работа по "Математике"
- Контрольная работа по "Математике"
- Контрольная работа по "Математике"
- Контрольная работа по "Математике"
- Контрольная работа по "Математике"
- Контрольная работа по "Математике"
- Контрольная работа по "Математике"
- Контрольная работа по "Математике
- Контрольная работа по "Математике"
- Контрольная работа по "Математике"
