KTH / Skolan / Utbildning / Inriktningar / Teoretisk datalogi

Teoretisk datalogi

Den teoretiska datalogin har många spännande och aktuella tillämpningsområden, t.ex. kryptografi, bioinformatik, stöd för språkbehandling och programanalys.

Forskning inom teoretisk datalogi har bedrivits vid Nada sedan början av 1980-talet och forskargruppen består nu av ett tjugotal personer. Målet med forskningen är att undersöka metoder för att effektivt utföra datorberäkningar och att finna undre gränser för de beräkningsresurser som krävs för olika beräkningar. Olika typer av beräkningar har studerats såsom: algoritmer för algebraiska beräkningar, beräkningar för Gröbner-baser, grafer, kryptografi, programanalys, approximationsalgoritmer och algoritmer för språkliga problem såsom stavningskontroll och avstavning. Tillämpningar finns inom kryptografi, inferens, systemanalys, programanalys och bioinformatik.

I alla tillämpningar där beräkningseffektivitet eller programkorrekthet är en väsentlig aspekt kommer denna fördjupning väl till pass -- med andra ord, algoritmutveckling inom beräkningstunga tillämpningar. En annan karriärväg är forskarutbildning.

Utbildningsmål

Kompetensinriktningens mål är att ge fördjupade kunskaper om lösning av resurskrävande beräknings-problem och relaterade kombinatoriska/statistiska analysmetoder. Kurserna syftar till att ge ökad förståelse för existens och ickeexistens av effektiva algoritmer för olika beräkningsproblem. En delinrikting är programanalys bland annat syftande till att med algoritmiska och logiska medel studera programs beteenden, till exempel med avseende på säkerhet.

Kurser

Se lista över kurser.

Examensarbete

Examensarbeten finns på CSC, inom industrin och vid utländska högskolor. Exempel: Snabb division av stora heltal -- en jämförelse av algoritmer (Swox AB), Utbrottsdetektering av smittsamma sjukdomar -- Design, analys och utvärdering av tre statistiska modeller för att detektera utbrott i epidemiologiska data för smittsamma sjukdomar (Smittskyddsinstitutet), Anonyma elektroniska pengar. Studie av ett system (Nada), Språkgranskning med reguljära uttryck (Nada), En säkerhetsanalys av mobila identiteter för autentisering (Icon Medialab), Bilineära hard-core-funktioner och listavkodning (ETHZ, Tekniska högskolan i Zürich), Formell analys av trådad Java bytekod (KTH)

Platsbegränsning

Nej

Ansvariga

Stefan Arnborg och Johan Håstad och är inriktningsansvariga.