Informatyka UJ forum

ostoj

moglby ktos ladnie przystepnie i zrozumiale napisac co to jest maksymalny antylancuch w sensie inkluzji? i od razu pokazac to na przykladzie, powiedzmy drzewa? porzadek na slowach skladajacych sie z zer i jedynek no i jedno slowo jest pod drugim gdy jest jego prefiksem? bylbym bardzo wdzieczny.

Skrobocik

No chyba najprostrzym przykładem będzie kratka

a
/ \
b c
\ /
d

Antyłańcuchy maksymalne to będą { a } , { d } , { b , c }.
Maksymalna antyłańcuchowość 8) polega na tym, że po dodaniu jakiegokolwiek elementu do maksymalnego antyłańcucha przestanie on być już antyłańcuchem - dlatego maksymalnymi antyłańcuchami nie mogą być { b } , ani { c } bo dodajesz ten drugi i też masz antyłańcuch.
............a przynajmniej tak mi się wydaje. :D
Jak źle to sorka :D

Makros

ja też tak to rozumiem...

Paweł Str. · Gość

Zgadzam się z Marcinem.

chlebek

Zad. 1
Musze sie upewnic tej kwestii z lancuchami i antylancuchami, dlatego jesli gdzie mam źle to krzyczec:
a kracie powyzej jest:
-11 lancuchow
-2 lancuchy max {a,b,d},{a,c,d}
-5 antylancuchow
-3 antylancuchy max
Zad. 2
Zadania z 2 kolokwium dotyczace lancuchow i antylancuchow:
a) lancuchow max jest 4: {0,1,5},{0,1,3,6},{0,1,2,6},{0,1,2,4}
b) antylancuchow max jest 5: {0},{1},{6,5,4},{5,4,3},{5,4,2}

teraz co jest źle??

hansu

chlebek

hansu

Masz calkowita racje... Silly me :oops:

oinopion

a łańcuch pusty?

Gość

zad. 1.
Zb. pusty jest też antyłańcuchem: (kto się zgadza niech dalej nie czyta)

oto def. antyłańcucha: ;)
dla każdych a, b, należących do X: ~(a<b) ^ ~(b<a), inaczej mówiąc:
dla każdych a, b, jeżeli a, b należą do X, to ~(a<b) ^ ~(b<a)

dla zb. pustego:
dla każdych a, b, jeżeli a, b należą do pustego, to ~(a<b) ^ ~(b<a)
poprzednik implikacji fałszywy, więc implikacja prawdziwa; pusty spełnia def. antyłańcucha

Krótko mówiąc:
żadne dwa elementy nie mogą ze sobą 'kooperować' (pzdr. dla dr Zaionca)... no to nie 'kooperują'

Po prostu chciałem powiedzieć, że antyłańcuchów jest 6, a nie 5.[/list]

Pawel Str.

Zgadzam się, jest ich 6, podobno było to u nas na którymś kolokwium poprawkowym.

hansu

Dobra, no to teraz jeszcze zostaje pytanie czy pusty jest takze lancuchem? :D

ostoj

pusty jest lancuchem i antylancuchem

oinopion

Tak na prawdę zbiór pusty to alias na Chucka Norrisa.

Gość

Jest. Otóż ;) :

def. łańcucha:
dla każdych a, b, należących do X: a<b lub b<a, inaczej mówiąc:
dla każdych a, b, jeżeli a, b należą do X, to a<b lub b<a

dla zb. pustego:
dla każdych a, b, jeżeli a, b należą do pustego, to a<b lub b<a
poprzednik implikacji fałszywy, więc implikacja prawdziwa; pusty spełnia def. łańcucha

Krótko mówiąc:
każde dwa elementy muszą spełniać relację, a że jest ich dość mało, to nie trudno o to ;)

PS. Pusty i jednoelementowe są jednocześnie łańcuchami i antyłańcuchami.

hansu

flower

oinopion

Ostoj, takie zadania, to my z Waszkiewiczem trzaskaliśmy; śmiał się z nas, że o najbardziej oczywistych łańcuchach i antyłańcuchach nie pomyśleliśmy (było wtedy głosowanie ile tych łańcuchów w końcu jest...).

ostoj

dokladnie :) dlatego teraz sie pamieta takie rzeczy :)