Vær opmærksom på at dette website indeholder et arkiv med historiske data. Det aktuelle kursuskatalog findes på kursuskatalog.au.dk

AU kursuskatalog arkiv

[Forside] [Hovedområder] [Perioder] [Udannelser] [Alle kurser på en side]

Regularitet og Automater (Q4) ( forår 2008 - 5 ECTS )

Rammer for udbud

  • Uddannelsessprog: (se under Undervisnings- og arbejdsform)
  • Niveau: Obligatorisk grundkursus
  • Semester/kvarter: Q4 i 2007/2008
  • Timer per uge: 7
  • Deltagerbegrænsning:
  • Undervisningssted: Århus
  • Hovedområde: Det Naturvidenskabelige Fakultet
  • Udbud ID: 7979

Formål

Deltagerne vil efter kurset have indsigt i teori om formelle sprog.

Obligatorisk program

6 obligatoriske opgaver

Indhold

Kurset dækker følgende emner indenfor teori om formelle sprog: Endelige automater, regulære udtryk og regulære grammatikker; egenskaber ved disse, bl.a. ækvivalens og begrænsninger; eksempler på praktiske anvendelser; bevisteknikker, f.eks. induktion; relation til mere generelle beregningsmodeller som kontekstfri grammatikker og Turing-maskiner.

Læringsmål

Deltagerne skal ved afslutningen af kurset kunne:
  • referere den basale terminologi (strenge, sprog, klasser af sprog, samt basale operationer på disse).
  • beskrive basale abstrakte sprogformalismer (regulære udtryk, endelige automater, regulære grammatikker, kontekstfri grammatikker) - fra intuitivt niveau og konkrete eksempler til formel notation og generelle definitioner.
  • beskrive egenskaber ved formalismerne, bl.a. ækvivalens, begrænsninger og beslutningsprocedurer.
  • forklare og udføre algoritmer, der oversætter mellem formalismerne eller afgør beslutningsproblemer - fra konkrete eksempler til generelle og formelle beskrivelser.
  • bevise og analysere egenskaber ved formalismerne (ved hjælp af konstruktive beviser og induktionsbeviser) - fra intuitivt niveau til formelle detaljer.

Faglige forudsætninger

dIntProg

Underviser

Anders Møller

Undervisnings- og arbejdsform

Forelæsninger (3t/uge), øvelser (2t/uge), studiecafe (2t/uge) Dansk

Litteratur

John Martin, Introduction to Languages and the Theory of Computation, 3. udgave, McGraw-Hill, 2002

Kursushjemmeside

http://www.daimi.au.dk/dRegAut

Skemaplacering (forelæsninger)

Blokpar F, Tirsdag 11-14

Udbyder

Datalogisk Institut

Indgår i følgende studieordninger

Bacheloruddannelsen i Datalogi

Tilmelding til undervisning

https://mit.au.dk/da/index.cfm

Studieordning og bedømmelse

1. del af sidefaget i datalogi

  • Mundtlig, bedømt efter 7-skala med ekstern censur

Bacheloruddannelsen i IT

  • Mundtlig, bedømt efter 7-skala med ekstern censur

Bacheloruddannelsen i datalogi

  • Mundtlig, bedømt efter 7-skala med ekstern censur

Bacheloruddannelsen i matematik

  • Mundtlig, bedømt efter 7-skala med ekstern censur

Fagpakke: Datalogi/Teori

  • Mundtlig, bedømt efter 7-skala med ekstern censur

Fagpakke: Overbygningsfagpakke i datalogi

  • Mundtlig, bedømt efter 7-skala med ekstern censur

Grundfaget i datalogi

  • Mundtlig, bedømt efter 7-skala med ekstern censur

Kandidatuddannelsen i datalogi

  • Mundtlig, bedømt efter 7-skala med ekstern censur

Kandidatuddannelsen i softwarekonstruktion (IT-Vest)

  • Mundtlig, bedømt efter 7-skala med ekstern censur

Sidefag i datalogi

  • Mundtlig, bedømt efter 7-skala med ekstern censur

Sidefaget i datalogi

  • Mundtlig, bedømt efter 7-skala med ekstern censur


Mundtlig eksamen uden forberedelse (20 min)
7-skala, ekstern censur