[Zk] 26. 1. 2012

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.
peci1
Matfyz(ák|ačka) level II
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

[Zk] 26. 1. 2012

Příspěvek od peci1 »

1) Dokazte, ze inverze k rekurzivni permutaci je take rekurzivni permutace.
2) Produktivni mnozina ma produktivni ORF.

Dvojku v pohode, u 1 jsem se dlouho motal, nez me dokopal k triku s postupnou minimalizaci, tak mi nabidl za 2 nebo dalsi vec. Vzal jsem dalsi, to byla existence simple mnoziny. Co jsem slysel, dalsimu bojovnikovi o 1 dal taky tu simple mnozinu.

Pri odchodu jsem videl cca 6 jednicek, par dvojek, trojku snad zadnou, a par, co to vzdali.

Celkem prijemna zkouska.
Kubees
Matfyz(ák|ačka) level II
Příspěvky: 65
Registrován: 12. 1. 2007 22:22
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: [Zk] 26. 1. 2012

Příspěvek od Kubees »

Jak je prosim definovana rekurzivni permutace? Nenasel jsem to v zadnych skriptech...
peci1
Matfyz(ák|ačka) level II
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

Re: [Zk] 26. 1. 2012

Příspěvek od peci1 »

Kubees píše:Jak je prosim definovana rekurzivni permutace? Nenasel jsem to v zadnych skriptech...
Tady to mas: http://wiki.matfyz.cz/index.php?title=S ... rmutace.29. Definice je prekvapive jednoducha :-D

Ty rekurzivni permutace zminil letos na prednasce... Ale tohle tvrzeni jsme k nim IMHO nedokazovali. Je to ale jednoduchy cviceni na trojuhelnikove prochazeni dvojic cisel (zkousene cislo, max. pocet kroku).
Odpovědět

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