In English

DD2440 Avancerade algoritmer 6,0 hp

Advanced Algorithms

En avancerad kurs i gränsområdet datalogi/diskret matematik som behandlar moderna tekniker för konstruktion av effektiva algoritmer.

  • Utbildningsnivå

    Avancerad nivå

  • Kursnivå (A-D)

    D

  • Huvudområde

    Informationsteknik

  • Betygsskala

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

Kurstillfällen/kursomgångar

HT12 TCSCM1 för programstuderande

HT13 avalg13 för programstuderande

Lärandemål

Efter fullgjord kurs ska en kursdeltagare kunna

  • analysera, välja, använda, designa och implementera effektiva algoritmer och datastrukturer för centrala beräkningsproblem

i syfte att

  • konstruera och utvärdera datorprogram som effektivt utnyttjar datorresurser.

Kursens huvudsakliga innehåll

Kursen kommer att beskriva och analysera ett antal algoritmer för diskreta beräkningsproblem och är avsedd för studenter med ett intresse inom gränstrakterna datalogi/diskret matematik. Några av nedanstående begrepp och beräkningsproblem kommer att diskuteras.

Primalitet hos heltal.

Faktorisering av heltal.

Snabb multiplikation av stora heltal.

Flöden i nätverk.

Matchning i grafer.

Sökning och sortering i olika beräkningsmodeller.

Handelsresandens problem.

Amorterad tidskomplexitet.

Kvantberäkningar.

Snabba Fouriertransformen.

Behörighet

För fristående kursstuderande krävs 90 högskolepoäng varav 45 högskolepoäng inom matematik eller informationsteknik. Dessutom krävs engelska B eller motsvarande.

Rekommenderade förkunskaper

5B1204/SF1631 Diskret matematik samt en av kurserna 2D1352/DD1352 Algoritmer, datastrukturer och komplexitet och 2D1354/DD2354 Algoritmer och komplexitet eller motsvarande kunskaper.

Litteratur

Meddelas senast 4 veckor före kursstart på kursens hemsida. Föregående läsår användes material producerat vid institutionen.

Examination

  • ÖVN1 - Inlämningsuppgifter, 6,0 hp, betygsskala: A, B, C, D, E, FX, F

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

Krav för slutbetyg

Inlämningsuppgifter (ÖVN1; 6 hp).

Ges av

CSC/Datalogi

Kontaktperson

Stefan Nilsson, e-post: snilsson@kth.se

Examinator

Stefan Nilsson <snilsson@kth.se>

Påbyggnad

Diskuteras med kursledaren.

Versionsinformation

Kursplan giltig från och med HT09.
Examinationsinformation giltig från och med HT07.