skuska 22.2.08

Základní přednáška z teorie algoritmů a efektivní vyčíslitelnosti. Turingovy stroje. Částečně rekurzivní funkce. Rekurzivní a rekurzivně spočetné množiny. Algoritmicky nerozhodnutelné problémy. Věta o rekurzi. Kreativní množiny.
Uživatelský avatar
macbeth
Matfyz(ák|ačka) level III
Příspěvky: 201
Registrován: 11. 2. 2005 14:48
Typ studia: Informatika Mgr.
Bydliště: PPraha
Kontaktovat uživatele:

skuska 22.2.08

Příspěvek od macbeth »

1.) KxK' = {<x,y> : x patri do K & y patri do K' }
Je mnozina rs? Je jej doplnok rs?

2.) Obor hodnot CRF je RS mnozina

3.) zostrojte n0 : fin0 (w) = n0

Uspech bol asi dost velky :)

...a vraj bude mozno este jeden termin
Nieco, co by nejavilo ziadne znamky bytia, teda by sa nijak neprejavovalo ako sucno, by nebolo niecim, ale prave nicim...
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: skuska 22.2.08

Příspěvek od hippies »

macbeth píše: Uspech bol asi dost velky :)
Nemam ten pocit :oops:
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
Uživatelský avatar
macbeth
Matfyz(ák|ačka) level III
Příspěvky: 201
Registrován: 11. 2. 2005 14:48
Typ studia: Informatika Mgr.
Bydliště: PPraha
Kontaktovat uživatele:

Re: skuska 22.2.08

Příspěvek od macbeth »

hippies píše:Nemam ten pocit :oops:
preto ten smajl... neviem, ci viac ako 5 ludi dostalo nejaku znamku...

ale inak by ma celkom zaujimalo, co si o nas pan Kucera mysli, ked nam dava take trivialne veci a 2/3 z terminu odidu dobrovolne... vlastne to radsej asi ani nechcem vediet :oops:
Nieco, co by nejavilo ziadne znamky bytia, teda by sa nijak neprejavovalo ako sucno, by nebolo niecim, ale prave nicim...
chucky
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 17. 5. 2007 16:20
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: skuska 22.2.08

Příspěvek od chucky »

aha, oni ti ludia teda odchadzali vacsinou bez znamok... sa mi to zdalo nejake podozrive, ze ako sa vsetci rozbehli :D (pohruzeny do dokazovania som nestihal sledovat, ci odchadzaju so zapisom v indexe. vsimol som si akurat toho, co vzal dvojku, lebo sa ponahlal na rande :) )

inak fakt vdaka za tieto otazky, ziadne zlozite vety (aj tak som 2. mal na prvykrat zle :oops: )
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: skuska 22.2.08

Příspěvek od hippies »

ja to jako vymyslel vsechno, jen jsem mezitim vymyslel spoustu nesmyslu a postupne jsem to skrtal i stim co bylo dobre, .. kdyz pak po nahledu do me prace pronesl ze nas nechce premlouvat, ale ze navzajem se trapit mu prijde zbytecne, usoudil jsem, ze jsem uplne mimo misu a vzdal, pritom kdyby sedel vedle me, tak by to na 2 verim dopadlo:/ .. mno nic, pouceni pro priste a je fakt, ze kdyz jsem to tam mel napsany a neuvedomil si to, ze si to asi potrebuju opravdu jeste projit.

tedy: uvidime se zase v patek:D
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
qk_

Re: skuska 22.2.08

Příspěvek od qk_ »

Muzete mi nekdo upresnit co to je ta treti otazka? to ma sestrojit funkci co vypisuje svuj kod?
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: skuska 22.2.08

Příspěvek od hippies »

presne to znamena: kod funkce, ktera vypise svuj kod
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
t2
Matfyz(ák|ačka) level I
Příspěvky: 49
Registrován: 22. 1. 2006 15:19

Re: skuska 22.2.08

Příspěvek od t2 »

Mohli by ste niekto povedat ako sa ten posledny priklad riesi? Ja nejak ani netusim co je vysledok (cislo, program, mnozina, funkcia, ... :? )
hippies^

Re: skuska 22.2.08

Příspěvek od hippies^ »

JJ^

Re: skuska 22.2.08

Příspěvek od JJ^ »

A ty zbyle dva? ( hlavne prvni, i kdyz to vysvetleni pro druhy, co je ve Strojilovo skriptech mi taky neprijde moc dostatecne )
chucky
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 17. 5. 2007 16:20
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: skuska 22.2.08

Příspěvek od chucky »

1) majme nejake pevne a z K a b z K'

definujme
f(x) = <x, b>
g(x) = <a, x>

f(x) i g(x) su proste ORF.

K je 1-preveditelne na KxK' pomocou f, tj. K' je preveditelne na (KxK')' pomocou f => keby (KxK')' bola r.s. bola by i K' r.s., co je spor.
K' je 1-preveditelne na KxK' pomocou g => keby KxK' bola r.s., bola by i K' r.s., co je spor.

Teda ani jedna nie je r.s.
chucky
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 17. 5. 2007 16:20
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: skuska 22.2.08

Příspěvek od chucky »

2) mame CRF f a jej obor hodnot range(f).
Chceme najst CRF h t.ž. dom(h) = range(f).

definujme h(y) = prva zlozka z min<x,s>{f(x) konverguje za s krokov a je rovne y}
vysvetlenie:
  • ak pre y neexistuje x, ze f(x)=y, tak program neskonci, co je ok, lebo y je mimo range(f) a teda mimo dom(h)
  • ak pre y existuju nejake x, ze f(x)=y, tak nejake najdeme. Predpokladame, ze kody dvojic <x,s> su usporiadane tak, ze sa na kazdu dostane, teda nie napr. ze najskor preberiem <x,1> pre vs. x, potom <x,2> pre vs. x; ani nie najskor <0,s> pre vs. s, potom <1,s> pre vs. s; to by az na specialne pripady nikdy nekonvergovalo. Vhodne poradie preberania dvojic je napr. nasledovne:

    Kód: Vybrat vše

      s|
    x  | 0 1 2 3 4 ...
    ----------------------
      1| 1 2 4 7 11 ...
      2| 3 5 8 12 ...
      3| 6 9 13 ...
      4| 10 ...
      ...
    
    Tak budeme verit, ze nase zvolene kodovanie dvojic usporiada dvojice v nejakom podobnom poradi
Poznamka: nemozeme definovat h jednoducho takto:
h(y) = minx{f(x) = y}
Povedzme, ze najmensie x, ze f(x)=y je 1 a ze f(0) nie je definovane.
Skusame postupne x od 0 do nekonecna, ci f(x)=y. ale uz na f(0) program diverguje, takze sa ani nedostaneme k tomu, aby sme otestovali f(1). Takze minx{f(x) = y} nedokazeme efektivne vycislit 8) a teda sa nam nepodari skonstruovat takuto h tak, aby bola CRF.
Uživatelský avatar
JJ
Matfyz(ák|ačka) level II
Příspěvky: 99
Registrován: 28. 1. 2005 14:03
Typ studia: Informatika Mgr.

Re: skuska 22.2.08

Příspěvek od JJ »

Diky moc
Odpovědět

Zpět na „TIN064 Vyčíslitelnost I“