Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
Greda Forumaš(ica)
Pridružen/a: 01. 07. 2006. (14:00:26) Postovi: (44)16
Spol:
|
|
[Vrh] |
|
lena Forumaš(ica)
Pridružen/a: 09. 12. 2005. (21:21:59) Postovi: (4C)16
Spol:
|
|
[Vrh] |
|
kika Forumaš(ica)
Pridružen/a: 11. 02. 2005. (09:36:12) Postovi: (188)16
|
|
[Vrh] |
|
Zvone Forumaš(ica)
Pridružen/a: 01. 07. 2003. (13:09:44) Postovi: (9D)16
|
|
[Vrh] |
|
Zvone Forumaš(ica)
Pridružen/a: 01. 07. 2003. (13:09:44) Postovi: (9D)16
|
|
[Vrh] |
|
andreao Forumaš(ica)
Pridružen/a: 10. 02. 2005. (12:08:18) Postovi: (46F)16
Lokacija: SK
|
|
[Vrh] |
|
kkarlo Forumaš(ica)
Pridružen/a: 19. 05. 2010. (08:43:59) Postovi: (1B2)16
Spol:
|
|
[Vrh] |
|
Tomislav Forumaš(ica)
Pridružen/a: 04. 10. 2010. (20:18:25) Postovi: (181)16
Spol:
|
|
[Vrh] |
|
pravipurger Forumaš(ica)
Pridružen/a: 11. 07. 2009. (10:29:44) Postovi: (128)16
Spol:
|
|
[Vrh] |
|
meda Forumaš(ica)
Pridružen/a: 09. 01. 2010. (09:29:23) Postovi: (A0)16
|
|
[Vrh] |
|
Tomislav Forumaš(ica)
Pridružen/a: 04. 10. 2010. (20:18:25) Postovi: (181)16
Spol:
|
|
[Vrh] |
|
Sekanta Forumaš(ica)
Pridružen/a: 13. 09. 2009. (10:14:33) Postovi: (48)16
|
|
[Vrh] |
|
ceps Forumaš(ica)
Pridružen/a: 08. 10. 2010. (13:03:07) Postovi: (13A)16
|
Postano: 13:34 sub, 28. 1. 2012 Naslov: |
|
|
Evo, ja sam dobio sve bodove iz toga... al ipak provjeri duplo jer ima šansa da sad napravim neku grešku koju na kolokviju nisam :D
Što znači da je relacija tranzitivna?
[b]Ako je a R b i b R c, mora biti a R c.[/b]
Primijeti da je funkcija oblika RELATION zatvarac (RELATION R), znači vraća posve novu relaciju (ne modificira staru). (*)
Trebat će nam i pomoćna funkcija
[code:1]
int EMPTY (SET A)
{
int i, test = 0;
for(i = 1; i <= N; i++)
{
if(MEMBER(i, A))
{
test = 1;
break;
}
}
return test;
}[/code:1]
koja provjerava da li je skup prazan.
E sad, unutar funkcije MAKE_NULL-amo novu relaciju, nazovimo je L (stara je R)...
Onda za svaki a = 1, ...., N radimo ovo:
Pomoću COMPUTE2(R, a, &A) u skup A stavimo sve (pogledaj def. tranzitivnosti gore!) ''b-ove'' za koje vrijedi a R b.
Trebamo istu stvar napraviti i za b-ove, tj. za svaki element b iz tog skupa A pogledati s kojim je on sve c-ovima u relaciji b R c i onda:
ako [b]vrijedi[/b] a R c - nikome ništa, tranzitivnost je već ispoštovana
ako [b]ne vrijedi [/b] a R c - onda moramo RELATE(&L, a, c).
Također, pošto je L posve nova (na početku prazna) relacija, u nju moramo ubaciti i one elemente koji su već u relaciji u R.
Kako to izvesti?
Znači, imamo taj skup A u kojem su svi elementi b za koje vrijedi a R b.
Napravimo njegovu ''kopiju'' [b]A2 koja će biti statična[/b], dok ćemo iz originalnog A micati elemente.
I onda, sve dok ne ispraznimo A ([i]while (!EMPTY(A)[/i] ), čupamo jedan po jedan element iz skupa A (npr., to možemo pomoću b = MIN(A), DELETE(b, &A)) i onda:
1. u relaciji L povežemo ono što je već povezano u relaciji R:
RELATE(&L, a, b)
2. ''Napravimo'' skup B pomoću COMPUTE2(R, b, &B) koji sadrži sve one elemente (nazovimo ih [b]c[/b], u skladu sa onom def. tranzitivnosti gore)
takve da je b R c i onda opet otvorimo još jednu while petlju:
while(!EMPTY(B))
i isto kao sa A, iz nje čupamo jedan po jedan element. Ako za njega vrijedi a R c (tj ako je MEMBER(c, A2) == 1) ne trebamo ništa napraviti, tranzitivnost je već ispoštovana.
U suprotnom, treba RELATE(&L, a, c).
I to je više manje to. :)
Ako ti treba neko dodatno pojašnjenje, samo pitaj... ili ako ti se čini da sam nešto pogriješio.
Nisam pisao kod jer mislim da je ovako lakše shvatiti, a netko tko je prošao Prog 1 & Prog 2 bi trebao ovo brzo staviti u for i while petlje... nije to neka znanost.
Evo, ja sam dobio sve bodove iz toga... al ipak provjeri duplo jer ima šansa da sad napravim neku grešku koju na kolokviju nisam
Što znači da je relacija tranzitivna?
Ako je a R b i b R c, mora biti a R c.
Primijeti da je funkcija oblika RELATION zatvarac (RELATION R), znači vraća posve novu relaciju (ne modificira staru). (*)
Trebat će nam i pomoćna funkcija
Kod: |
int EMPTY (SET A)
{
int i, test = 0;
for(i = 1; i <= N; i++)
{
if(MEMBER(i, A))
{
test = 1;
break;
}
}
return test;
} |
koja provjerava da li je skup prazan.
E sad, unutar funkcije MAKE_NULL-amo novu relaciju, nazovimo je L (stara je R)...
Onda za svaki a = 1, ...., N radimo ovo:
Pomoću COMPUTE2(R, a, &A) u skup A stavimo sve (pogledaj def. tranzitivnosti gore!) ''b-ove'' za koje vrijedi a R b.
Trebamo istu stvar napraviti i za b-ove, tj. za svaki element b iz tog skupa A pogledati s kojim je on sve c-ovima u relaciji b R c i onda:
ako vrijedi a R c - nikome ništa, tranzitivnost je već ispoštovana
ako ne vrijedi a R c - onda moramo RELATE(&L, a, c).
Također, pošto je L posve nova (na početku prazna) relacija, u nju moramo ubaciti i one elemente koji su već u relaciji u R.
Kako to izvesti?
Znači, imamo taj skup A u kojem su svi elementi b za koje vrijedi a R b.
Napravimo njegovu ''kopiju'' A2 koja će biti statična, dok ćemo iz originalnog A micati elemente.
I onda, sve dok ne ispraznimo A (while (!EMPTY(A) ), čupamo jedan po jedan element iz skupa A (npr., to možemo pomoću b = MIN(A), DELETE(b, &A)) i onda:
1. u relaciji L povežemo ono što je već povezano u relaciji R:
RELATE(&L, a, b)
2. ''Napravimo'' skup B pomoću COMPUTE2(R, b, &B) koji sadrži sve one elemente (nazovimo ih c, u skladu sa onom def. tranzitivnosti gore)
takve da je b R c i onda opet otvorimo još jednu while petlju:
while(!EMPTY(B))
i isto kao sa A, iz nje čupamo jedan po jedan element. Ako za njega vrijedi a R c (tj ako je MEMBER(c, A2) == 1) ne trebamo ništa napraviti, tranzitivnost je već ispoštovana.
U suprotnom, treba RELATE(&L, a, c).
I to je više manje to.
Ako ti treba neko dodatno pojašnjenje, samo pitaj... ili ako ti se čini da sam nešto pogriješio.
Nisam pisao kod jer mislim da je ovako lakše shvatiti, a netko tko je prošao Prog 1 & Prog 2 bi trebao ovo brzo staviti u for i while petlje... nije to neka znanost.
|
|
[Vrh] |
|
Sekanta Forumaš(ica)
Pridružen/a: 13. 09. 2009. (10:14:33) Postovi: (48)16
|
|
[Vrh] |
|
ceps Forumaš(ica)
Pridružen/a: 08. 10. 2010. (13:03:07) Postovi: (13A)16
|
|
[Vrh] |
|
Sekanta Forumaš(ica)
Pridružen/a: 13. 09. 2009. (10:14:33) Postovi: (48)16
|
|
[Vrh] |
|
nuala Forumaš(ica)
Pridružen/a: 20. 02. 2011. (14:26:29) Postovi: (33)16
|
|
[Vrh] |
|
ivanaaaa Forumaš(ica)
Pridružen/a: 24. 10. 2011. (19:36:26) Postovi: (31)16
|
|
[Vrh] |
|
kiara Forumaš(ica)
Pridružen/a: 15. 11. 2011. (23:22:57) Postovi: (55)16
|
|
[Vrh] |
|
PermutiranoPrase Forumaš(ica)
Pridružen/a: 10. 09. 2011. (16:08:19) Postovi: (F4)16
Spol:
|
|
[Vrh] |
|
|