Algoritmer och komplexitet 7,5 hp

En fortsättningskurs i datalogi med inriktning på algoritmer och komplexitet, mer teoretisk än DD1352.

Kursinnehåll

Konstruktionsprinciper för algoritmer: Dekomposition, giriga algoritmer, dynamisk programmering. Algoritmanalys. Probabilistiska algoritmer. Approximationsalgoritmer. Utvalda tillämpningar inom mängder, grafer, aritmetik och geometri. Implementation av algoritmer.

Beräkningsbarhet och komplexitet: Reduktioner. Komplexitetsklasserna P (polynomisk tid), NP (ickedeterministisk polynomisk tid), PSPACE (polynomiskt minne) och BPP (probabilistisk polynomisk tid med begränsat fel). NP-fullständighet och NP-svårighetsreduktioner. Oavgörbara problem.

Lärandemål

Efter godkänd kurs ska studenten kunna

• utveckla och implementera algoritmer och reduktioner, och analysera dem med avseende på korrekthet och effektivitet
• jämföra alternativa algoritmer med hänsyn till effektivitet
• definiera och förklara centrala begrepp som P, NP, NP-fullständighet och oavgörbarhet
• jämföra problem med hänsyn till komplexitet med hjälp av reduktioner

i syfte att

• självständigt kunna konstruera datorprogram som effektivt utnyttjar tid och minne och därmed kan bidra till ekonomisk och miljömässig hållbar utveckling
• i yrkeslivet kunna identifiera problem som är orealistiskt resurskrävande eller inte alls går att lösa med dator.

Särskild behörighet

Kunskaper i grundläggande datalogi, 6 hp, motsvarande slutförd kurs DD1338/DD1320-DD1328/DD2325/ID1020/ID1021.

Kunskaper och färdigheter i programmering, 6 hp, motsvarande slutförd kurs DD1310-DD1319/DD1321/DD1331/DD1337/DD100N/ID1018.

Kunskaper i envariabelanalys, 7,5 hp, motsvarande slutförd kurs SF1625/SF1673.

Gymnasiekursen Engelska B/6.

Aktivt deltagande i kursomgång vars slutexamination ännu inte är Ladokrapporterad jämställs med slutförd kurs. Den som är registrerad anses vara aktivt deltagande. Med slutexamination avses både ordinarie examination och det första omexaminationstillfället.