KTH

Skolan för datavetenskap och kommunikation

KTH / Nada / Utbildning / Teknologer / Specialiseringar / Teoretisk datalogi

Teoretisk datalogi

Kompetensinriktning för D

Information våren 2003

Val av inriktning görs på hösten i årskurs 3

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

Området

Forskning inom teoretisk datalogi har bedrivits vid Nada sedan början av 1980-talet och forskargruppen består nu av ett trettiotal 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, approximationsalgoritmer och algoritmer för språkliga problem såsom stavningskontroll och avstavning. Tillämpningar finns inom kryptografi, inferens, systemanalys och bioinformatik.

I alla tillämpningar där beräkningseffektivitet ä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.

Må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äkning-problem.

Examensarbete

Examensarbeten finns på Nada, inom industrin och vid utländska högskolor. Exempel: Språkgranskning med reguljära uttryck (Nada), Algoritmer för att hitta konserverade regioner i DNA-sekvenser (Nada), Optimala besättningsgrupper -- en heuristik för kolumngenerering till ett kombinatoriskt optimeringsproblem (Carmen Consulting), Formell analys av protokoll som hanterar elektroniska biljetter (Sonera Smart Trust Inc).

Kurser

Kursdelen ska utformas i samråd med den ansvariga för kompetensinriktningen. Välj minst 25 poäng från nedanstående kurser, eller andra kurser. Inom varje grupp anges kurserna i nummerordning, utan prioritering. Observera att varje kurs har vissa förkunskapskrav och att vissa kurser inte ges varje år.

2D1373 Artificiella språk och syntaxanalys, 4p (per. 3)
2D1450 Algoritmisk bioinformatik, 4p (per. 4)
2D1458 Problemlösn. & progr. under press, 4p (per. 1-2)
2E1423 Signalteori, 4p
2G1117 Semantik för programspråk, 4p
2G1121 Logikprogrammering, 4p
2G1506 Progr. med processer, 5p
2G1516 Formella metoder, 4p
2I1140 Artificiell intelligens, 6p
5B1305 Tillämpad kombinatorik, 4p
5B1750 Optimeringslära för E och D, 4p

Minst två av kurserna nedan ska ingå: Poängen från dessa räknas med i de 25 poäng som ska ingå i inriktningen
2D1440 Avancerade algoritmer, 4p (per. 2)
2D1441 Seminariekurs i teoretisk datalogi, 4p (ges vartannat år, ges ej 03/04)
2D1446 Komplexitetsteori, 4p (ges vartannat år, ges 03/04 per. 4)
2D1449 Kryptografins grunder, 4p (per. 3)
5B1309 Algebra gk
5B1475 Kombinatorik fk, 5p

Ingen platsbegränsning

Ansvarig

Johan Håstad, 7906289, johanh@nada.kth.se
Stefan Arnborg, 790 7194, stefan@nada.kth.se

Mer information

www.nada.kth.se/utbildning/grukth/kompinriktning/
www.nada.kth.se/theory/

Gamla inriktningsbeskrivningar

Gamla kompetensinriktningsbeskrivningar från 1999/2000, 2000/2001, 2001/2002 och 2002/2003.
 

 
Sidansvarig: Kerstin Frenckner <kfrenck@nada.kth.se>
Uppdaterad: 2004-02-18