Nada

Nadas institutionssymbol

^ Upp till kursens hemsida

In English

Studiehandbokstext 1997/98 för

2D1353 Algoritmer, datastrukturer och komplexitet

Poäng6Föreläsning48
KursnivåCÖvning24
Betygsskala, KTHU, 3, 4, 5Lab-
Obligatorisk förDÖvrigtEget arbete
Valbar förEPerioder3-4
SpråkEnglish

Kursansvarig

Rand Waltzman, 08 - 790 6337, rand@nada.kth.se

Kortbeskrivning

En fortsättningskurs i datalogi med inriktning på algoritmer, datastrukturer och komplexitet.

Mål

Kursens mål är att för att eleverna ska

Kursinnehåll

Konstruktionsprinciper för algoritmer: dekomposition, giriga algoritmer, dynamisk programmering. Algoritmanalys. Tillämpningar med algoritmer för problem på mängder, grafer, aritmetik och geometri.

Beräkningsbarhet och komplexitet: reduktionsbegreppet, komplexitetsklasserna P (polynomisk tid) och NP (ickedeterministisk polynomisk tid), NP-fullständiga problem, oavgörbara problem.

Förkunskaper

Motsvarande kurserna 2D1340 (eller 2D1341) Introduktion till datalogi och 5B1203 Diskret matematik (kan läsas parallellt).

Påbyggnad

2D1440 Avancerade algoritmer, 2D1443 Parallella beräkningar och 2D1446 Komplexitetsteori

Examination

En skriftlig tentamen (TEN1; 4 p).
Laborationsuppgifter (LAB1; 2 p).

Kurslitteratur

Enligt förteckning på institutionen. Läsåret 96/97 användes T. Cormen, D  Leiserson & R. Rivest: Introduction to algorithms, MIT Press, 1994.

Länk till studiehandbokstexten 1996/97

^ Upp till kursens hemsida


Sidansvarig: <www-kurs@nada.kth.se>
Senast ändrad 9 juni 1997
Tekniskt stöd: <webmaster@nada.kth.se>