Detail předmětu
Vyčíslitelnost a složitost
SVSL FEKT SVSL Ak. rok 2002/2003 zimní semestr 6 kreditů
Základní vlastnosti Turingových strojů, modulární stavba. TS jako akceptory jazyků, vícepáskové a universální TS. Problém zastavení, Postův korespodenční problém. Vyčíslitelnost, primitivní rekurzívní funkce, parciální rekurzívní funkce. Základní problém rozhodnutelnosti. Algoritmická slo itost, slo itost problému, polynomická redokce. Modely RAM a RASP, vztah Turingův stroj - RAM. Hierarchie tříd složitosti. Please continue on / Další informace o kursu jsou na<br><a href="http://www.fee.vutbr.cz/UIVT/courses/VSL/">http://www.fee.vutbr.cz/UIVT/courses/VSL/</a><br>
Garant předmětu
Jazyk výuky
Zakončení
Rozsah
- 39 hod. přednášky
- 12 hod. cvičení
Zajišťuje ústav
Požadované prerekvizitní znalosti a dovednosti
Jedná se o předmět nestrukturovaného dobíhajícího studijního programu
Zařazení předmětu ve studijních plánech