Національний університет ”Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра “Інформаційні системи та мережі”
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторних робіт
з курсу “Математична логіка і теорія алгоритмів”
для студентів, що навчаються за напрямком
6.040303 Системний аналіз
Затверджено на засіданні кафедри ІСМ
Протокол №__ від “___” _________ 2012 р.
Львів - 2012
Лабораторна робота № 1
Операції над множинами
Мета лабораторної роботи полягає у вивченні способів комп’ютерного представлення множин та виконання комп’ютерних операцій над ними.
Теоретичний вступ
Існують різні способи зображення множин у комп’ютері. Один із способів – залишати елементи множини у невпорядкованому вигляді. Проте, якщо так зробити, то операції із множинами вимагатимуть значних витрат часу через необхідність щоразу здійснювати перегляд елементів.
Ми
розглянемо інший спосіб зображення
множин у комп’ютері. Упорядкуємо
довільним способом елементи універсальної
множини. Нехай універсальна множина
містить
елементів. Тоді
.
Підмножина
зображатиметься у комп’ютері бітовим
рядком, що складається із 0 та 1 та має
довжину
,
де
-й
біт цього рядка дорівнює 1, якщо
,
та дорівнює 0, якщо
.
Приклад 1. Нехай
задана універсальна множина
та її підмножини
,
.
Тоді підмножина
зображається рядком
,
а підмножина
– рядком
.
Тепер
на комп’ютері легко здійснити операції
над множинами. Такі операції є
порозрядними логічними операціями над
елементами відповідних рядків
(символ “1” відповідає значенню „істина”
–
,
а символ “0” – значенню „фальш” –
,
див. таблицю 1).
Таблиця 1 |
||||
|
|
|
|
|
|
|
AND |
OR |
XOR |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
Неважко
переконатись, що перетину множин
відповідає порозрядна кон’юнкція,
операція
над бітовими рядками, а обєднанню
множин – порозрядна диз’юнкція, операція
над відповідними бітовими рядками.
Приклад
2. Знайдемо
перетин
множин
та
з прикладу 1
Отже,
.
Приклад 3.
Знайдемо об’єднання
множин
та
з прикладу 1
Отже,
.
Приклад 4.
Знайдемо доповнення
множини
з прикладу 1
Отже,
Приклад 5.
Знайдемо різницю
(SUB)
множин
та
Отже,
Якщо універсальна множина дуже велика (або нескінченна), а підмножини універсальної множини, які розглядаються, не дуже великі, то зображення з допомогою бітових рядків не є ефективним з точки зору витрат пам’яті. У такому випадку для зображення множин доцільно використовувати інші методи та структури даних.
Завдання на лабораторну роботу
Написати програму, яка дозволяє реалізувати базові операції над множинами без врахування дужок
Множини та вирази, які будуть використані для ілюстрації роботи програми під час захисту лабораторної роботи, будуть надані викладачем.
Приклад програми:
program zviri_zooparky;
uses CRT;
label menu;
var
zoopark1: array [1..33] of string;
zoopark2: array [1..33] of string;
zpark1: array [1 ..33] of string;
zpark2: array [1..33] of string;
j, i:integer;
x, y:integer;
d, k, t:integer;
v, w:integer;
str: string;
rezultat: array [1..75] of string;
wiborka: char;
procedure peretyn;
begin
for x:=1 to v do
for y:=1 to w do
begin
if zoopark1[x]=zoopark2[y] then
rezultat[x] :=zoopark2 [y] ;
end;
clrscr;
writeln ('Rezultat dorivnye->> ');
for i:=1 to v+w do
begin
if rezultat[i] <> ' ' then
writeln (rezultat[i]);
end;
end;
procedure objednannya;
begin
for x:=1 to v do
for y:=1 to w do
begin
if zoopark1[x]=zoopark2[y] then
zoopark1[x]:=' ';
end;
for j:=1 to v do
begin
rezultat[j]:=zoopark1[j];
end;
t:=0;
for d:=j+1 to v+w do
begin
t:=t+1;
rezultat[d] :=zoopark2[t];
end;
clrscr;
writeln ('Rezultat dorivnye->>');
for i:=1 to v+w do
begin
if rezultat[i] <> ' ' then
writeln (rezultat[i]);
end;
end;
procedure simmetrichna_riznytsia;
begin
for x:=1 to v do
for y:=1 to w do
begin
if zoopark1[x]=zoopark2[y] then
begin
zoopark1[x]:=' ';
zoopark2[y]:=' ';
end;
end;
for j:=1 to v do
begin
rezultat[j]:=zoopark1[j];
end;
t:=0;
for d:=j+1 to v+w do
begin
t:=t+1;
rezultat[d] :=zoopark2[t];
end;
clrscr;
writeln ('Rezultat dorivnye->>');
for i:=1 to v+w do
begin
if rezultat[i] <> ' ' then
writeln (rezultat[i]);
end;
end;
procedure riznytsia;
begin
for x:=1 to v do
begin
rezultat[x] :=zoopark1 [x] ;
for i:=1 to v do
for j:=1 to w do
begin
if rezultat[i]=zoopark2[j] then
rezultat[i]:=' ';
end;
clrscr;
writeln ('Rezultat dorivnye->>');
for i:=1 to w do
begin
if rezultat[i] <> ' ' then
writeln (rezultat[i]);
end;
end;
end;
procedure dekartovyj_dobytok;
begin
i:=0;
for x:=1 to v do
for y:=1 to w do
begin
inc (i);
str:=' ';
if zoopark1[x]<>zoopark2[y] then rezultat[i]:=zoopark1[x]+' * '+zoopark2[y];
end;
clrscr;
writeln ('Rezultat dorivnye->>');
for i:=1 to v*w do
begin
if rezultat[i] <> ' ' then
writeln (rezultat[i]);
end;
end;
begin
clrscr;
textbackground(white);
textcolor(black);
writeln ('Wwedit kilkist zviriv 1 zooparka:');
readln(v);
writeln ('Wwedit kilkist zviriv 2 zooparka:');
readln(w);
write('Wwedit zviriv 1 zooparka ');
writeln(',w kinci Enter:');
for k:=1 to v do
begin
readln (zoopark1[k]);
end;
write('Wwedit zviriv 2 zooparka ');
writeln(',w kinci Enter:');
for i:=1 to w do
begin
readln (zoopark2[i]);
end;
for i:=1 to v do
zpark1[i] :=zoopark1[i];
for i:=1 to w do
zpark2[i] :=zoopark2[i];
menu:
writeln ('Wwesty nomer operacii:');
writeln ('1->>Peretyn');
writeln ('2->>Objdnannya');
writeln ('3->>Simmetrichna riznytsa');
writeln ('4->>Riznytsa');
writeln ('5->>Dekartovyj dobytok');
writeln ('6->>Wyhid');
writeln ('Wu Wuralu:');
readln (wiborka);
case wiborka of
'1': peretyn;
'2': objednannya;
'3': simmetrichna_riznytsia;
'4': riznytsia;
'5': dekartovyj_dobytok;
'6': exit;
end;
readln;
clrscr;
for i:=1 to v*w do
rezultat[i]:= ' ';
for i:=1 to v do
begin
zoopark1[i]:= zpark1[i];
end;
for i:=1 to w do
begin
zoopark2[i]:=zpark2[i];
end;
goto menu;
end.