TDDC76 Programmering och datastrukturer
Föreläsningar
Här hittar du information om vad som är planerat att tas upp på föreläsningarna, och vad som verkligen kom att behandlas på de föreläsningar som varit, dvs en kombination av föreläsningsplan och föreläsningsdagbok.
Period Ht1, vecka 36-42 |
|
Fö 1 4/9 |
Introduktion till kursen [2x2]
Grundläggande programstruktur. Grundläggande datatyper. Typomvandling. Variabler och konstanter. Deklarationer och definitioner. Uttryck och operatorer. Operatorers prioritet och associativitet, beräkningsordning för operander, sidoeffekter. Satser. |
Fö 2 8/9 |
Introduktion till C++, forts. [2x2] Funktioner. Sammansatta datatyper: uppräkningstyper, fält, poster, pekare. Dynamiska datastrukturer, dynamisk minneshantering. De delar av C++ som genomgåtts översiktligt på Fö 1-2 motsvarar Laboration 1.1-1.4 samt delvis 1.5. Underlag för att kunna slutföra Laboration 1.5 kommer att behandlas på Fö 3. Strömbiblioteket överlämnas till eget studium |
Fö 3 18/9 |
Klasser [2x2] [kodexempel String] Grundläggande om syntax och semantik. Medlemmar (data- och funktionsmedlemmar). Åtkomst till klassmedlemmar (public, private). Olika alternativ för att deklarera och definiera medlemsfunktioner (definition i klassen, "in-class", medför underförstått "inline", separat definition, separat definition med uttrycklig "inline"-deklaration. const-deklaration av medlemsfunktioner. Konstruktorer. Destruktor. Defaultkonstruktor. Initierare. this-pekaren, Kopieringskonstruktor, typomvandlande konstruktor, explicit-deklaration av konstruktor. Kompilatorgenererade versioner av defaultkonstruktor, kopieringskonstruktor och kopieringstilldelning (operator=). Vikten av att korrekt kopiering och tilldelning är definierat för icke-triviala klasser (t.ex. klasser med datamedlemmar som är pekare till dynamiskt minne). Typomvandlande operatorfunktioner. |
Fö 4 22/9 |
Klasser, forts. [2x2] [kodexempel String] Operatorer som kan överlagras för klasser (de flesta fördefinierade operatorer). Syntax och semantik (försök normalt efterlikna språkets inbyggda operatorer). Frågan om operator ska/bör/måste vara klassmedlem eller fristående funktion. Exempel på operatorer som måste vara medlem (=, []), som inte kan vara medlem (<<) och som antingen kan vara medlem eller ej (==). Introduktion till undantagshantering [2x2] try-block, throw-uttryck och catch-hanterare. Hantering av undantag. Mall för att definiera egna undantag. |
Fö 5 1/10 |
Härledning, arv, polymorfi [2x2] [kodexempel Person-Employee-Manager-Consultant] Härledning av klasser. protected som åtkomstskydd för ärvd klassmedlem. Olika former av arv (public, protected och private) och dessas innebörd. Virtuella medlemsfunktioner, rent virtuella ("pure virtual") medlemsfunktioner, dynamisk bindning (i detta sammanhang), Överskuggning ("overriding", inte att förväxla med överlagring, "overloading"). Orientering om olika typer av arv: enkelt arv, multipelt arv och repeterad arv samt virtuellt arv. Gränssnittsklasser. |
Fö 6 2/10 |
Härledning, arv, polymorfi, forts. [2x2] [kodexempel Person-Employee-Manager-Consultant] Dynamisk typkontroll och typomvandling RTTI (Run-Time Type Identification). Klassen type_info, typeid-uttryck och dynamic_cast. Undantagshantering, forts. [2x2] |
Period Ht2, vecka 45-51 |
|
Fö 7 3/11 |
Objektorienterad programutvecklingsmetodik.
• Objektorienterad programutveckling i ett nötskal (utdelas ej)
Introduktion till datastrukturer och algoritmer
• Datastrukturer och algoritmer (enkel översikt, utdelas ej) Observera, ovanstående häfte och OH definierar kursens innehåll avseende DoA. |
Fö 8 6/11 |
Sökning i listor
Allmänt om träd
Enkelt binärt sökträd. |
Fö 9 10/11 |
AVL-träd Röd-svarta träd: orientering enpass höjdbalanserat sökträd med "top-down"-balansering. AVL-trädet är tvåpass med "bottom-up"-balansering. Skiplista Tänkt att kunna konkurera med binära sökträd). Perfekt balanserad skiplista. Praktiskt balanserad skiplista. |
Fö 10 12/11 |
Splayträd Orientering om "flytta-till-början-lista" (listornas motsvarighet till splayträd).
B-träd
Introduktion: Definition.
Begrepp: fyllnadsgrad (M och L), överskott, underskott, noddelning,
nodsammanslagning, nodbalansering, lån/adoption. |
Fö 11 17/11 |
B-träd, forts.
Insättning (överskott, noddelning, nodbalansering, lån eller adoption?
Borttagning (underskott, lån, adoption, nodsammanslagning.
Hashtabeller |
Fö 12 19/11 |
Hashtabeller, forts.
Prioritetsköer
Binär heap Sortering med binär heap, Heapsort.
|
Fö 13 20/11 |
Intern sortering.
Introduktion. Olika klassificeringar och begrepp:
intern-extern, jämförande-distributiv, enkel-avancerad, stabil, naturlig.
Tekniker för jämförande sorteringsmetoder: urval, utbyte, insättning, samsortering. |
Fö 14 24/11 |
Intern sortering, forts
Extern sortering |
Sidansvarig: Jonas Lindgren
Senast uppdaterad: 2015-08-18