Matematické Fórum

Petrrrrr · 26. 11. 2009 22:31

Ahoj,
potřebuji zapsat něco formálně s využitím kvantifikátoru $\forall$ .
Pokud mám $\forall A \in P_1 \forall B \in P_2$ a mám provádět nějaký cyklus.
Zaručí mi to že budu zpracovávat všechny možná dvojice?

Nebo je nutné to rozepsat do jednoho cyklu, do kterého vložím cyklus další?

Dík za odpověď (čím dřív, tím líp ;-) )

Kondr · 26. 11. 2009 23:08

Ano, takto probereš všechny dvojice.

Petrrrrr · 26. 11. 2009 23:20

Díky moc, už jsem z toho totiž zblblý :S
Ještě bych se zeptal, jestli je dobré si počítat ty dvojice nějak takto...
1. dvojice ... udělám něco
2. dvojice ... udělám něco
poslední dvojice, která bude bude mít velikost $|(P_1 x P_2)|$ //x je jako kartézský součin

Nebo mi to pořád zajistí ty dva $\forall$ , že když projdu všechny dvojice, tak automaticky skončí?

abych naznačil, protože nevím, jestli jsem to dobře napsal, tak mám něco takového:

1. $\forall A \in P_1, \forall A \in P_2$
2. Dělej něco
3. Jestli vyjde něco tak se vrať do bodu 1. jinak pokračuj dál.

Zajistí mi ten bod 3., že když se vrátím do bodu jedna, že budu pracovat s těmi dvojicemi od začátku (za jistých podmínek potřebuju pracovat s těmi dvojicemi znovu)

Ještě jednou dík za radu

Kondr · 26. 11. 2009 23:47

↑ Petrrrrr:Moc tomu nerozumím, můžeš trochu upřesnit, co program dělá? Jinak nevím co píšeš za práci, ale nebál bych se použít klasické konstrukce while a for.

Petrrrrr

Klidně upřesním. Má to být formální zápis algoritmu pro výpočet nějaké relace. Takže to je "program"
O tom while a for jsem uvažoval, ale nevím jak to správně matematicky zapsat, abych prošel všechny dvojice...

Popíšu svůj postup... jakmile ho nacvakám do Pc, tak tento příspěvěk zedituju
takže snad se v tom bude dát orientovat. Momentálně to goto tam mám protože nevím jak dobře a formálně zapsat ten cyklus

1) inicializace $M = \emptyset, N = \emptyset$
2) $\forall A \in P_1$ , $\forall B \in P_2$ , $i=0$
3)
\IF { $(A,B) \notin M$ }
\IF {podmínka}
\STATE i++ //je v relaci
\IF { $i=|P_1 \times P_2|$ } //jestli to byla posledni dvojice
   \STATE $goto$ 4)
\ENDIF
\ELSE
   \STATE $M = M \cup \{(A,B)\}$ // přidám do M dvojici, co není v relaci
   \STATE i++
\IF { $i=|P_1 \times P_2|$ } //jestli to byla posledni dvojice
   \STATE $goto$ 4)
\ENDIF
\STATE $goto$ 2) // vrací se zpět na bod 2 a prochází znovu všechny dvojice
   \ENDIF
\ENDIF
4) $N=\overline{M}$ // v N jsou dvojice v relaci

To, že na konci přehazuji ber prosím jako fakt, na konkrétní řešení to je vhodnější.

Kondr · 27. 11. 2009 01:01

↑ Petrrrrr:To $\forall A \in P_1$ , $\forall B \in P_2$ se postará o to, aby se odsazené příkazy provedly pro všechny dvojice A,B, a to tak, že po dokončení odsazených příkazů se skočí na 3) právě když nám zbývá nějaká dvojice k testování. Nerozumím ale algoritmu: mám relaci M, pokud najdu dvojici, která v ní není, nedělám nic (jen zvětším počítadlo), pokud tam daná dvojice je, přidám ji do relace (tj. neudělám zase nic) a zvětším počítadlo. Navíc M je od začátku prázdná relace, takže se ELSE větev ani neprovede, M zůstane prázdná. Na konci do N uložíme $\overline{M}$ -- to je doplněk relace $M$ ?

Co má algoritmus dělat?

Petrrrrr

můžu zkusit přeposlat zadání do SZ? nebo zkusit popsat co mám tím algoritmem na mysli? (kopírovat sem zadání "pro všechny" se mi moc nechce)
Co se týká toho bodu 4) proč to přehazuji bych popsal až při konkrétním přeposlání celýho zadání, abych k tomu mohl vysvětlit víc "co a jak".
edit mebo bych se zadáním mohl poslat průchod algoritmem, pro nějaký konkrétní případ. Právě podle toho vzorového průchodu jsem se snažil vytvořit nějaký ten algoritmus... :)

Petrrrrr

Obecně vzato hledám ty dvojice, které v relaci nejsou (na první pohled je to kostrbaté řešení, ale vzhledem k zadání a radě kantora je to doporučený postup)

Kondr napsal(a):
To $\forall A \in P_1$ , $\forall B \in P_2$ se postará o to, aby se odsazené příkazy provedly pro všechny dvojice A,B, a to tak, že po dokončení odsazených příkazů se skočí na 3) právě když nám zbývá nějaká dvojice k testování.

Tak nějak jsem to myslel.

Kondr napsal(a):
Nerozumím ale algoritmu: mám relaci M, pokud najdu dvojici, která v ní není, nedělám nic (jen zvětším počítadlo), pokud tam daná dvojice je, přidám ji do relace (tj. neudělám zase nic) a zvětším počítadlo.

Tady jsem to myslel tak, že když (A,B) není v relaci (je v M) (minimálně jeden krok se provede, když na začátku je M prázdná), tak vezmu jinou dvojici, jestli tahle dvojice je v relaci, tak nedělám nic, jen zvýším počítadlo, jestli v relaci není, přidám ji do množiny M, která obsahuje dvojice, které nejsou v relaci, zvýším počítadlo a jestli to byl poslední prvek, tak jdu do 4) jinak se vrátím do 2) a znovu procházím všechna A a všechna B, takto mám v úmyslu cyklit, dokud neproberu všechny dvojice
Jakmile se dostanu do 4) do N dám doplněk M -- tedy všechny dvojice, které v relaci jsou.

Kondr napsal(a):
Navíc M je od začátku prázdná relace, takže se ELSE větev ani neprovede, M zůstane prázdná. Na konci do N uložíme $\overline{M}$ -- to je doplněk relace $M$ ?

Co má algoritmus dělat?

Tady nevím, co přesně myslíš. K podmínce \IF { $(A,B) \notin M$ } větev \ELSE není. Když je M na začátku prázdná, tak (A,B) tam určitě není, tak je podmínka \IF pravdivá, tak se provede tělo té podmínky. A nebo blbě chápu prázdnou množinu (což je ale možné...)

edit jak tak koukám, tak jsem asi moc nenapsal co má být výsledkem... Výsledkem má být množina dvojic, které jsou v relaci

Kondr · 27. 11. 2009 02:06

↑ Petrrrrr:Mohlo by fungovat něco takového:

$M = \emptyset, N = \emptyset$
opakuj=true;
while(opakuj)
opakuj=false;
$\forall A \in P_1$ $\forall B \in P_2$
if(not podmínka)
$M = M \cup \{(A,B)\}$ ;
opakuj=true;
$N=\overline{M}$

Bohužel pokud přidáváme dvojici do relace, neukončíme hned forcyklus. Pokud bys ho zapisoval slovně jako "for" dalo by se použít příkazu "break". Při kvantifikátorovém zápise to asi není korektní.

Petrrrrr

však z cyklu "while" se dá taky vyskočit "breakem"..., ale to bych si musel počítat ty dvojice, což by za mě řešil ten for
$M=\emptyset, N=\emptyset$
i=0
for ( $A_i \in P_1, i<|P_1|, i++$ )
j=0
for ( $B_j \in P_2, j<|P_2|, j++$ )
if(not podmínka)
$M = M \cup \{(A_i,B_j)\}$
i=0
break
$N=\overline{M}$

Jenže tohle už se blíži spíš programátorskýmu zápisu algoritmu než matematickýmu... Ale nevím jestli to jde považovat za korektní

Matematické Fórum

#1 26. 11. 2009 22:31

kvantifikátor "pro všechna"

#2 26. 11. 2009 23:08

Re: kvantifikátor "pro všechna"

#3 26. 11. 2009 23:20

Re: kvantifikátor "pro všechna"

#4 26. 11. 2009 23:47

Re: kvantifikátor "pro všechna"

#5 26. 11. 2009 23:57 — Editoval Petrrrrr (27. 11. 2009 00:13)

Re: kvantifikátor "pro všechna"

#6 27. 11. 2009 01:01

Re: kvantifikátor "pro všechna"

#7 27. 11. 2009 01:10 — Editoval Petrrrrr (27. 11. 2009 01:43)

Re: kvantifikátor "pro všechna"

#8 27. 11. 2009 01:23 — Editoval Petrrrrr (27. 11. 2009 01:54)

Re: kvantifikátor "pro všechna"

Kondr napsal(a):

Kondr napsal(a):

Kondr napsal(a):

#9 27. 11. 2009 02:06

Re: kvantifikátor "pro všechna"

#10 27. 11. 2009 10:10 — Editoval Petrrrrr (27. 11. 2009 10:12)

Re: kvantifikátor "pro všechna"

Zápatí