Áætlað námsefni í
Formleg mál og reiknanleiki, Haust 1998


Gróf skipting námsefnis

Fyrstu 6 vikurnar:
Inngangur, endanlegar stöðuvélar, reglulegar segðir, dælusetning, staflavélar, samhengisóháð mál, dælusetning, ýmsar gerðir Turing véla, rekjanleg mál.
Næstu 5 vikurnar:
Reiknanleiki, Church-Turing tilgátan, leysanleiki, Stöðvunarvandamálið, yfirfærsla vandamála, óleysanleg vandamál.
Síðustu 4 vikurnar:
Flækjustigsflokkar, P, NP, PSPACE, margliðutíma yfirfærsla, NP-fullkomin vandamál, minnisflækja vandamála og aðrir flækjustigsflokkar eftir því sem tími vinnst til.


hh@rhi.hi.is, 20. ágúst, 1998.