Automata and languages, automat10

Kursanalys VT10

Kursdata

• Kurs: DD2372 Automater och språk, 6hp
  
• Omgång:  VT10,  Period 3
  
• Kursledare: Dilian Gurov
  
• Kursformat: 30t lektioner (föreläsningar blandade med övningar)
  
• Antal registrerade elever: 10
  
• Antal direkt avhoppade elever: 0
  
• Kurslitteratur: Hopcroft, Motwani and Ullman: Introduction to Automata theory, Languages and Computation, 3rd Edition, Addison-Wesley, 2007.
• Moment: HEM1 (2hp), LAB1 (2hp), TEN1 (2hp)
  
• Elever som klarat kursen: 8
  
• Prestationsgrad efter första examinationstillfället: A:5, B:3, C:1, D:0, E:1, Fx:0, F:0
  
• Examinationsgrad efter första examinationstillfället: 100%

Mål

Automata are mathematical machines, that is, abstract computing devices. Their purpose is to capture, study and compare different models and views of the abstract notion of computation and its various aspects. The computational power of automata can be characterized through the classes of languages (that is, sets of strings over a finite alphabet of symbols) they can accept/recognize.

Important notions in computer science like state, nondeterminism and minimization are captured in the simple model of finite automata, which recognize the class of regular languages. Automata provide the basis for the implementation of many programming languages, with parsing being a typical application. Another important reason for studying automata is to capture the notion of effective computability, that is, to characterize the notion of computation as a process which can be physically implemented. This allows the important question to be posed: what problems can be decided algorithmically, and where are the limits to this?

Förändringar inför denna kursomgång

Kursen är en uppgraderad version av tidigare kursen DD2371 Automatteori, med ny bok och två nya kursmoment, bestående av två labbuppgifter och sex hemtal som har utvecklats.

Undervisningen

Jag brukar blanda föreläsningar med övningar. Hemtalen utvärderas med hjälp av kamraträttning med projekterad modellösning.

Sammanfattning

Jag är väldig nöjd med hur kursen gick i år. Studenterna visade stor intresse och delaktighet i alla aktiviteter.

Examination

Examinationen består av en skriftlig tenta, med bonuspåäng från hemtalen. De flesta problem är av konstruktionsharaktär. Dessutom testar några problem olika bevistekniker samt förståelsen av två viktiga teorem i kursen: Myhill-Nerode och Chomsky-Schützenberger Theorem. Själva tentan (med lösningar) finns här.

Kurslitteratur

I kursen används boken Introduction to Automata theory, Languages and Computation av Hopcroft, Motwani and Ullman, 3rd Edition, Addison-Wesley, 2007, kompletterad med material från boken Automata and Computability av Dexter Kozen, Springer, 1997, samt tilläggsmaterial i form av scannade noticer.

Elevenkät

Hela kursutvärderingen finns här.

Kursens belastning för eleverna

Enligt min uppfattning är studenterna lagom belastade under kursen.

Förkunskaper

Förkunskaper som är väsentliga för kursen är Diskret Matematik och Logik. De flesta studenter verkade ha tillräckliga förkunskaper.

Verkligt kursinnehåll

Det verkliga kursinnehållet kan ses på följande länk.

Övrigt

En sådan kurs borde vara obligatorisk på varje datalogisk curriculum, men är tyvärr inte obligatorisk här.

Planerade förändringar

Möjligtvis kommer en alternativ till andra labbuppgiften utvecklas och erbjudas.