Áæ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.