Ändliga automater och formella språk
Om utbildningen
Kursen handlar huvudsakligen om ändliga automater, reguljära uttryck och kontextfria grammatiker. Den innehåller också en kort introduktion till Turingmaskiner.
Ändliga automater och reguljära uttryck är enkla beräkningsmodeller. De används bland annat för lexikalanalys, mönsterigenkänning, och styrning av trafiksignaler. Vidare kan deras teori illustrera grundläggande begrepp inom mängdlära och läran om diskreta strukturer.
Kontextfria grammatiker används för att parsa och analysera både konstgjorda språk (till exempel programmeringsspråk) och naturliga språk. Turingmaskiner ger en mer uttrycksfull beräkningsmodell. De hjälper dataloger att förstå begränsningarna hos mekaniska beräkningar genom att ge en precis definition av algoritmbegreppet.
Behörigheter och urval
Behörighet
För att vara behörig till kursen ska studenten ha avklarat 45 hp inom datavetenskap eller matematik, inklusive följande kurser:
- 7,5 hp i diskret matematik (till exempel DIT980, MMG200 eller motsvarande)
- 7,5 hp i programmering (till exempel DIT440, DIT143, DIT012, DIT948, DIT953, MVG200 eller motsvarande)
Urval
Högskolepoäng, max 165 hp.
