DD2350 · Kungliga Tekniska högskolan
Algoritmer, datastrukturer och komplexitet
20 tentor8 ämnen
Kursinnehåll
Algoritmer
12 uppgifter
Datastrukturer
8 uppgifter
Definitioner
11 uppgifter
Glosor
8 uppgifter
Komplexitet
19 uppgifter · 1 teorikapitel
Vad ingår?
0 uppgifter
Sorterat efter ämne och svårighet, direkt från tentor.
20 tentor med lösningar
Alla tidigare tentor samlade, öva på riktiga examensfrågor.
AI-handledare (KAI)
Få steg-för-steg-hjälp dygnet runt, skräddarsydd för den här kursen.
0 studieplaner
Personliga studieplaner som anpassar sig till dina framsteg.
Generera tester
Skapa anpassade övningstester baserat på ämne och svårighet.
Framstegsanalys
Se vad du vet, vad du behöver granska och vad som finns kvar.
HP
9.5
Språk
Svenska
Nivå
Avancerad nivå
Fakultet
Skolan för elektroteknik och datavetenskap
Institution
EECS/Datavetenskap
Lärandemål
Efter godkänd kurs ska studenten kunna
- utveckla och implementera algoritmer med datastrukturer och analysera dem med avseende på korrekthet och effektivitet
- jämföra alternativa algoritmer och datastrukturer med hänsyn till effektivitet och pålitlighet
- definiera och översätta 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
- hantera problem med hög komplexitet
- självständigt kunna konstruera datorprogram som effektivt utnyttjar tid och minne och därmed kan bidra till ekonomiskt och miljömässigt hållbar utveckling
- i yrkeslivet kunna identifiera och angripa problem som är orealistiskt resurskrävande eller inte alls går att lösa med dator.
Kursinnehåll
Konstruktionsprinciper för algoritmer: Dekomposition, giriga algoritmer, dynamisk programmering, lokal och total sökning. Algoritmanalys. Approximationsalgoritmer och heuristiker. Tillämpningar med algoritmer för problem på mängder, grafer, aritmetik, kryptografi och geometri. Implementation av algoritmer. Datastrukturer: Repetition av hashtabeller och heapar; balanserade träd, bloomfilter, beständiga datastrukturer. Användning och implementation av datastrukturer. Beräkningsbarhet och komplexitet: Reduktionsbegreppet, komplexitetsklasserna P (polynomisk tid) och NP (ickedeterministisk polynomisk tid). NP-fullständiga problem, oavgörbara problem. Hur man kan hantera problem med hög komplexitet. Ämnesterminologin på svenska och engelska.
Förutsättningar
- Kunskaper och färdigheter i programmering, 6 hp, motsvarande slutförd kurs DD1337/DD1310-DD1319/DD1321/DD1331/DD1333/DD100N/ID1018.
- Kunskaper i grundläggande datalogi, 6 hp, motsvarande slutförd kurs DD1338/DD1320-DD1328/DD2325/ID1020/ID1021.
- Kunskaper i algebra och geometri, 7,5 hp, motsvarande slutförd kurs SF1624/SF1672.
- Kunskaper i envariabelanalys, 7,5 hp, motsvarande slutförd kurs SF1625/SF1673.
- Kunskaper i diskret matematik, 7,5 hp, motsvarande slutförd kurs SF1688/SF1610/SF1630/SF1662/SF1679, alternativt slutförd kurs SF1671 och deltagande i SF1688 parallellt med DD2350, se även övriga föreskrifter.
- 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.
Litteratur
Saknas
Liknande kurser vid andra universitet
Gör som 15 000+ studenter och ta kontroll över ditt tentaplugg.
Kom igång gratis