Göm menyn

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.

Föreläsningsplan år 2017

DatumInnehållÖvrigt
29/8 & 4/9 Introduktion till kursen samt grundläggande C++,
exempelvis ingår grundläggande satser, IO, datatyper och funktioner, operatoröverlagring, strömhantering och övrigt stoff inför lab 1
Föreläsningsbilder
12/9 & 13/9 Klasser, dynamiskt minne (pekare) och undantag (exception) Föreläsningsbilder:Klasser | Pekare och Listor | Speciella medlemsfunktioner
Föreläsningsexempel: Undantagshantering | Initierarlistor | Copy och Move
22/9 & 25/9 Arv, polymorfi och objektorienterad programmering Föreläsningsbilder: Arv och polymorfi 2017 | Arv och polymorfi 2016 | Iteratorer
Föreläsningsexempel: Figurer | Dynamisk typkontroll | Summera tal (vector med indexering) | Summera tal (vector med iterator) | Frekvenstabell (v1) | Frekvenstabell (v2) | Smartpekare
3/10 Inför projekt Föreläsningsbilder: Grunder objektorienterad programutveckling | Versionshantering med Git
30-31 Okt Git, SFML, Toplist Föreläsningsbilder: Make och Git
Kodexempel: SFML | Toplist




Nedanstående material användes under 2015 och tidigare och är inte helt aktuellt för kursen. Det lämnas dock kvar som extra läsning vid intresse då det till innehåll fortfarande är vettigt.

Period Ht1, vecka 36-42 -- år 2015



Fö 1 
3/9

Introduktion till kursen  [2x2]

Introduktion till C++  [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 
7/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 
17/9

Klasser  [2x2]  [kodexempel String]
Kort orientering om objektorienterad programmering och objektorienterade konstruktioner: klass/objekt, arv/härledning, polymorfi/dynamisk bindning. Föreläsning 7 tar upp mer om objektorienterad programutvecklinling.

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]

Operatoröverlagring  [2x2]

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 
30/9

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 
1/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]
Lite med om felhantering och undantagshantering. Repetition: try-block, catch-hanterare, throw-uttryck. Design av standardundantagen, att härleda egna undantagsklaser från standardundantagen.


Period Ht2, vecka 45-51 -- år 2015



Fö 7 
2/11

Objektorienterad programutvecklingsmetodik.
Metodik, begrepp, notation (UML), CRC-kort, mm.

•  Objektorienterad programutveckling i ett nötskal (utdelas ej)
•  Visade dia OOP (utdelas ej):  fullformat  |  2x2

Introduktion till datastrukturer och algoritmer
Orientering om innehållet i datastrukturer och algoritmer (Fö 8-14). Implementering av listor och träd, begreppen "header" och "sentinel". Olika länkningsalternativ för länkade listor (enkel, dubbel, cirkulär) och länkade träd (binära träd med sentinel-nod, "threaded trees").

•  Datastrukturer och algoritmer (enkel översikt, utdelas ej)
•  DoA-OH, Fö 8-14 (utdelas):  fullformat  |  2x2

Observera, ovanstående häfte och OH definierar kursens innehåll avseende DoA.


Fö 8 
5/11

Sökning i listor
Linjärsökning, binärsökning, interpolationssökning.

Allmänt om träd
Terminologi, begrepp. Trädtraversering, med uttrycksträd som exempel.

Enkelt binärt sökträd.
Princip. Sökning. Insättning och borttagning.


Fö 9 
9/11

AVL-träd
Princip. Höjdbalanserat binärt sökträd. Sökning, insättning och borttagning.
Fibonacciträ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 
11/11

Splayträd
Introduktion - splayning - splayrotationer - amorterad analys - 90/10-principen.
Två varianter: "bottom-up"-splayning (tvåpass) och "top-down"-splayning (enpass).

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 
16/11

B-träd, forts.

Insättning (överskott, noddelning, nodbalansering, lån eller adoption? Borttagning (underskott, lån, adoption, nodsammanslagning.

Hashtabeller
Allmänt om begrepp, problem, lösningar, kollisionshanteringsmetoder: linjär sondering, kvadratisk sondering, dubbelhashning. Separat länkning. Omhashning. Borttagning ur hashtabell. Linjär hashning.


Fö 12 
18/11

Hashtabeller, forts.
Linjär hashning.

Prioritetsköer
Prioritetsköer allmänt. Definition av heap (heapordningsegenskapen).

Binär heap
Definition. Avbildning på fält. Två alternativ att sätta in i en binär heap, insert och toss+fixheap. Borttagning. "percolate-up" och "percolate-down".

Sortering med binär heap, Heapsort.


Fö 13 
19/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.
Enkla metoder: Bubblesort, Shakersort, Selectionsort, Insertionsort (linjär insättning eller binär insättning).
Avancerade metoder: Heapsort, Shellsort, Mergesort, Quicksort.


Fö 14 
23/11   

Intern sortering, forts

Extern sortering
Samsortering. Två grundläggande samsorteringsmetoder: balanserad 2-vägs resp. naturlig 2-vägs samsortering; "Simple Merge". Polyphase Merge (avancerad balanserad samsorteringsmetod). (Replacement Selection; generering av initiala sorterade delsekvenser).



Sidansvarig: Eric Elfving / Klas Arvidsson
Senast uppdaterad: 2017-11-02