2D1353 Algoritmer, datastrukturer och komplexitet, 6 poäng, för D och (E)

Mål

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

Förkunskaper

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

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.

Kursuppläggning

Föreläsningar
48 h period 3-4
Övningar
24 h period 3-4

Examination

En skriftlig tentamen (TEN1; 4 p).
Laborationsuppgifter (LAB1; 2 p).
Betygsskala: 3, 4, 5.
Fördjupningsnivå: C

Kurslitteratur

Enligt förteckning på institutionen.

2D1353 Algorithms, Data Structures, and Complexity, 6 credits

Goals

The goals of the course are to give the students so that they will be able to

Prerequisites

2D1340 (or 2D1341) Introduction to Computer Science and 5B1203 Discrete Mathematics (can be taken concurrently) or the equivalent.

Contents

Principles for construction of algorithms: Decomposition, greedy algorithms, dynamic programming. Algorithm analysis. Selected applications to sets, graphs, arithmetic, and geometry.
Computability and complexity: Reduction. Complexity classes P (polynomial time), NP (non-deterministic polynomial time). NP-complete problems. Undecidable problems.

Examination

A written examination (TEN1; 4 cr.).
Laboratory assignments (LAB1; 2 cr.).
Grades: 3, 4, 5.

Required Reading

Reading list available at the department.

^ Upp till kursens hemsida.


Senast ändrad 1996-04-16 <www-kurs@nada.kth.se>