Målet med dette kursus er at præsentere endelige automater og sprog samt introducere logik og beregnelighedsteori.
Indhold:
Regulære sprog: Regulære grammatikker, regulære udtryk, endelige automater samt ækvivalens mellem disse. Endelige automaters begrænsninger.
Beregnelighed: Turing maskiner, rekursivt nummererbare sprog, afgørlighed - specielt Halting problemet.
Logik: Logiske udtryk, satisfiability og validity, første og anden ordens logik, axiomer og beviser, fuldstændighed, uafgørlighed, Gödels ufuldstandighedssætning.
Forudsætninger:
Undervisningsform:
Evaluering:
Bemanding:
Belastning: