Behörighetskrav

Programkonstruktion 1DL200 eller motsvarande

Mål

För godkänt betyg ska studenten kunna

• analysera körtiden för en (enkel) algoritm/program i relation till indatats storlek, i bästa, sämsta, och genomsnittliga fall,
• besvara frågor för att utvärdera algoritm/program: vad händer med körtiden om indata blir dubbelt så stor? Vilka algoritmer/program ska man välja bland olika alternativ för samma specifikation? Med vilka datastrukturer ska man implementera en algoritm, med tanke på operationerna (lägga till, ändra, ta bort, söka, sortera) på datat. Spelar det någon roll (för stora indata) att byta ut en del av algoritmen/programmet mot ett annat?
• i detalj ange antaganden som ligger till grund för denna analys.
• analysera körtiden för operationerna (lägga till, ändra, ta bort, söka, sortera) för vanliga datastrukturer (listor, arrayer, köer, prioritetsköer, stackar, träd, och heaps).
• förklara fördelar och nackdelar med "giriga algoritmer" (som gör lokalt optimala val utan att ångra sig) för optimeringsproblem som generellt kräver för lång körtid för vanliga indata.

Innehåll

Matematiska grunder: asymptotisk notation,

summationer, rekursionsformler.

Datastrukturer: stackar, köer, träd, prioritetsköer, "heaps". Sökmetoder: binära sökträd, balanserade sökträd, hashtabeller.

Sorteringsmetoder. Enkla grafalgoritmer och "giriga algoritmer". Implementering i ett funktionellt språk (ML).

Undervisning

Föreläsningar, lektioner, laborationer och

obligatoriska inlämningsuppgifter.

Examination

Skriftligt prov (4 hp) samt inlämningsuppgifter (1 hp).

Övriga föreskrifter

Kursen kan inte räknas in i examen med Programkonstruktion II (1IT022) eller

Datastrukturer MN1 (1DL009, 1TD191, 1MB026).