De studerende lærer en række fundamentale begreber og teknikker til konstruktion og analyse af effektive algoritmer og datastrukturer. De studerende lærer at forstå principperne for oversættere og virtuelle maskiner. De studerende lærer at bruge og konstruere software-værktøjer til implementering af en funktionsdygtig oversætter.
Læringsmål:
En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:
konstruere iterative og rekursive algoritmer i pseudokode
implementere fundamentale algoritmer og datastrukturer i et programmeringssprog
foretage grundlæggende analyser af algoritmer, især udtrykke køretider i asymptotisk notation
karakterisere forskellige algoritmer med hensyn til essentielle krav
foretage et passende valg af algoritmer og datastrukturer for integration i IT-systemer
forklare de forskellige faser i oversættelse og kørsel
benytte udvalgte værktøjer relateret til oversættelsesfaserne (fx lexers, parsers)
aflede specifikationer for oversættelsesfaserne, givet en tekstuel beskrivelse af syntaksen for et programmeringssprog
implementere en analyse og kodegenereringsfase, givet en tekstuel beskrivelse af semantikken for et programmeringssprog
udvikle en funktionsdygtig oversætter
indfri målene som led i en gruppeindsats, samtidig med bevarelse af individuelt ansvar
kommunikere løsninger til opgaver på en klar og præcis måde
Kursusindhold:
Algoritmedelen af kurset omhandler fundamentale algoritmer til søgning og sortering, teknikker til analyse af algoritmer, asymptotisk notation, søgetræer og hashtabeller, grafalgoritmer.
Oversætterdelen af kurset omhandler principper for virtuelle maskiner og hovedfaserne for oversættere:
(1) Leksikalsk analyse (skanning) og værktøjer til generering af skannere. (2) Syntaktisk analyse (parsing) og værktøjer til generering af parsere. (3) Semantisk analyse. (4) Kodegenerering.
Litteratur:
Lærebog i algoritmedelen oplyses senere.
Andrew W. Appel: Modern Compiler Implementation in Java, Second Edition, Cambridge University Press, 2002.
Bemærkninger:
Den teoretiske del af algoritmelæren vil have undervisningsfællesskab med kurset 02105 torsdag formiddag.
