Hoppa till huvudinnehållet
Inför kursvalDD2372 Automater och språk 6,0 hpAdministrera Om kursen

Automater är matematiska maskiner, det vill säga abstrakta beräkningsapparat. Deras syfte är att fånga, studera och jämföra olika modeller och syn på det abstrakta begreppet beräkning och dess olika aspekter. Automaternas beräkningsstyrka kan karakteriseras genom språkklasserna (det vill säga mängderna av strängar över ett ändligt alfabet av symboler) som de kan känna igen.

Viktiga begrepp inom datavetenskapen som tillstånd, ickedeterminism och minimering fångas med den enkla modellen av ändliga automater, som känner igen klassen av reguljära språk. Automater utgör grunden för implementeringen av många programmeringsspråk, varvid parsning är en typisk applikation. En annan viktig orsak till att studera automater är att fånga upp begreppet effektiv beräkningsförmåga, det vill säga att karakterisera begreppet beräkning som en process som kan implemeneras fysiskt. Detta gör att den viktiga frågan kan ställas upp: vilka problem kan avgöras på ett algoritmiskt sätt och var är gränserna för detta?

Välj termin och kursomgång

Välj termin och kursomgång för att se information från rätt kursplan och kursomgång.

* Informationen tillhör Kursplan DD2372 (VT 2019–)

Innehåll och lärandemål

Kursinnehåll

Del I. Ändliga automater och reguljära språk: determinering, modellprovning, reguljära uttryck, tillståndsminimering, pumpningslemma, Myhill-Nerodes teorem, reguljär slutledning.

Del II. Stackautomater och kontextfria språk: kontextfria grammatiker och språk, parsning, Chomsky-Schützenbergers teorem, modellering av program med rekursion, pumpningslemma, stackautomater.

Del III. Turingmaskiner och effektiv beräkningsförmåga: Turingmaskiner, rekursiva mängder, universella Turingmaskiner, avgörbara och oavgörbara problem, Rices teorem, andra modeller för effektiv beräkning.

Lärandemål

Kursens övergripande syfte är att ge eleverna en djupgående förståelse för beräkning och effektiv beräkningsbarhet genom abstrakta begreppet av automater och språkklasserna de känner igen. Tillsammans med detta kommer studenterna att bekanta sig med de viktiga begreppen tillstånd, ickedeterminism och minimering.

Efter kursen kommer studenterna att kunna:

1) redogöra för huvudklasserna av automater och strukturella representationer (reguljära uttryck och grammatiker) och de motsvarande språkklasserna: konstruera en automat eller en grammatik från en informell språkbeskrivning [för betyg E].

2) relatera de olika klasserna med hjälp av språkbevarande transformationer; applicera transformationerna för att lösa konkreta problem: applicera transformationerna på konkreta exempel [E], definiera nya transformationer [C], visa att transformationerna är språkbevarande [A].

3) för varje språkklass förklara huvudkarakteriseringsteoremen; tillämpa teoremen för att lösa konkreta problem: förklara enklare teorem på konkreta exempel [E], förklara svårare teorem på konkreta exempel [C], tillämpa teoremen för att bevisa olika språkegenskaper [A].

Kursupplägg

Ingen information tillagd

Kurslitteratur och förberedelser

Särskild behörighet

Ingen information tillagd

Rekommenderade förkunskaper

Motsvarande SF1610/SF1630/SF1688 Diskret matematik och DD1350 Logik för dataloger.

Utrustning

Ingen information tillagd

Kurslitteratur

Hopcroft, Motwani and Ullman "Introduction to Automata theory, Languages and Computation", 3rd Edition, Addison-Wesley, 2007, ISBN: 0-321-47617-4.

Examination och slutförande

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

Betygsskala

A, B, C, D, E, FX, F

Examination

  • HEMA - Hemuppgifter, 2,5 hp, betygsskala: P, F
  • LABA - Laborationer, 2,0 hp, betygsskala: P, F
  • TENA - Tentamen, 1,5 hp, betygsskala: A, B, C, D, E, FX, F

Examinator beslutar, baserat på rekommendation från KTH:s samordnare för funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

I denna kurs tillämpas skolans hederskodex, se: http://www.kth.se/csc/student/hederskodex.

Övriga krav för slutbetyg

Laborationer (LAB1), hemuppgifter inklusive workshop (HEMA) samt tentamen (TENA).

Möjlighet till komplettering

Ingen information tillagd

Möjlighet till plussning

Ingen information tillagd

Examinator

Profile picture Dilian Gurov

Etiskt förhållningssätt

  • Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
  • Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
  • Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.

Ytterligare information

Kurswebb

Ytterligare information om kursen kan hittas på kurswebben via länken nedan. Information på kurswebben kommer framöver flyttas till denna sida.

Kurswebb DD2372

Ges av

EECS/Datavetenskap

Huvudområde

Datalogi och datateknik

Utbildningsnivå

Avancerad nivå

Påbyggnad

Ingen information tillagd

Kontaktperson

Dilian Gurov, e-post: dilian@csc.kth.se, tel: 790 8198

Övrig information

Kursen har ersatt DD2371 Automatteori.

I denna kurs tillämpas EECS hederskodex, se:
http://www.kth.se/eecs/utbildning/hederskodex