ZK[8.2.2007]

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.
Enlil

ZK[8.2.2007]

Příspěvek od Enlil »

Kucera opet prekvapil. Dnesni priklady byly:
  • 1. Vztah mezi uplne produktivni a produktivni mnozinou vcetne dukazu lemmatu o zachovani uplnosti pri prevodu
  • Dokazat zda je prunik,sjednoceni a doplnek rek. spoc. mnozin. take rekurzivne spocetny
  • Godelovy vety
johnny
Donátor
Donátor
Příspěvky: 95
Registrován: 13. 12. 2005 00:31
Typ studia: Informatika Mgr.
Bydliště: Trója

Re: ZK[8.2.2007]

Příspěvek od johnny »

Odhadem 8 lidí odešlo dobrovolně a 4 byli odejiti :) Otázka 2. byla nutná i s důkazem (k mojí smůle).
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: ZK[8.2.2007]

Příspěvek od macbeth »

Otazka pre tych, co tu dvojku riesili: Ako ste na to isli? Lebo asi nestaci povedat, ze vidime, ze zlozenim dvoch ORF ziskame opat ORF (pri rekurzivnych mnozinach), resp ze zjednotenie/prienik def. oborov CRF je opat def obor nejakej CRF, ale doplnok def oboru CRF nie je def obor CRF :)
Nieco, co by nejavilo ziadne znamky bytia, teda by sa nijak neprejavovalo ako sucno, by nebolo niecim, ale prave nicim...
johnny
Donátor
Donátor
Příspěvky: 95
Registrován: 13. 12. 2005 00:31
Typ studia: Informatika Mgr.
Bydliště: Trója

Re: ZK[8.2.2007]

Příspěvek od johnny »

Mám množinu A, množinu B, jejich ČRF f_a a f_b. Dostanu prvek x a mám rozhodnout, zda patří do průniku/sjednocení, tak pustím paralelně výpočet f_a(x) a f_b(x). Pro průnik čekám, až zastaví oba (pak x do průniku patří), pro sjednocení čekám, až zastaví některý z těch dvou (pak x patří do sjednocení). Dokud čekám, tak nic nevracím, tj. taky můžu čekat věčně (což nastane pokud x nepatří do průniku/sjednocení). Takže jsem ČRF a průnik/sjednocení je r.s..

Doplněk nezachovává RS. Příklad: K. Ukázat, že K je r.s., kdežto doplněk K není. K je r.s. protože když dostanu x, pustím program x na vstup x a čekám, dokud neskončí. Doplněk K není r.s., protože kdyby byl, pak má nějaký index, třeba y. Takže si označím: doplněk K = W_y. Stačí ukázat spor - y patří do K doplňku právě když program y nad vstupem y nezastaví (z def. K doplněk). y patří do W_y právě když program y nad vstupm y zastaví (z def. W_y) - spor.
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: ZK[8.2.2007]

Příspěvek od macbeth »

Dakujem, myslel som na nieco podobne... :)
Nieco, co by nejavilo ziadne znamky bytia, teda by sa nijak neprejavovalo ako sucno, by nebolo niecim, ale prave nicim...
Odpovědět

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