DD1320/DD1325 Tillämpad Datalogi

Introduktion till kursen

Kursen och formalia




Kursen examineras med labbar (7 st) och tentamen (betyget ges av tentan).
Forum för nyheter, diskussioner och frågor är KTH Social.

För att få tillgång till nyheter, diskussioner och frågor gå till länken ovanför och prenumerera på er kursomgång.

Kursansvariga studenter sökes!
Gärna en per program/inriktning. Anmäl dig bums till Linda.

Idag:

Datalogikurser världen över är mycket lika varandra. Innehållet är i huvudsak det här.

Kurserna DD1320/DD1325 har följande moment:

DD1325 Tillämpad datalogi med etik (som CLGYM läser) har dessutom

Läranvisningar

För varje datastruktur och algoritm gäller det att kunna:


Betygskriterier - översikt

För betyg E ska man kunna avgöra vilken algoritm som löser ett givet problem, kunna beskriva algoritmen och demonstrera den steg för steg med givna data, samt implementera den. Motsvarande gäller för datastrukturer.

För betyg C ska kraven för betyg E vara uppfyllda, och dessutom ska man kunna jämföra algoritmer och datastrukturer och bedöma dessas lämplighet för ett givet problem. Här ställs också krav på tidsplanering.

För betyg A ska kraven för betyg C vara uppfyllda, och man ska dessutom kunna modifiera/kombinera algoritmer och datastrukturer för att lösa nya problem. Här ställs också höga krav på tydlighet i algoritmbeskrivningar.

Bonus till tentan

För bonus från labbar gäller följande:



Preliminär plan över föreläsningarna

På föreläsningarna går vi igenom algoritmer och datastrukturer.
På övningarna övar vi problemlösning (som på tentan).
På labbarna implementerar ni datastrukturer och algoritmer.
Labbarna görs i grupper om två, med parprogrammering.

Algoritmer

En beskrivning, i ett ändligt antal steg, av hur man löser ett givet problem.

Exempel:
Skriv en algoritm för att läsa in gps-data för platser på island: island.txt från en fil och lagra dom i en lista.
Platserna är ordnade med nordligast latitud först, men i listan vill vi vända på listan så att dom ligger i ordning från sydligaste till nordligaste.

  1. öppna filen
  2. läs in rubrikraden
  3. läs in första deltagaren
  4. lagra deltagaren i en lista
  5. upprepa punkt 3 och 4 tills alla rader i filen lästs in
  6. vänd listan 
infil = open("island.txt","r",encoding = "utf8")
rad = infil.readline()
lista = []
while rad != "":
    rad = infil.readline()
    lista.append(rad)
lista.reverse()
print(len(lista))
Här är en annan algoritm för samma problem:
  1. öppna filen
  2. läs in rubrikraden
  3. läs in första deltagaren
  4. lägg deltagaren först i listan
  5. upprepa punkt 3 och 4 tills alla rader i filen lästs in
  6. nu är listan vänd! 
infil = open("island.txt","r",encoding = "utf8")
rubrikrad = infil.readline()
lista = []
for rad in infil:
    rad = infil.readline()
    lista.insert(0,rad)
print(len(lista))

Datastrukturer

En datastruktur är till för att lagra data (som en variabel), men med plats för flera värden. Exempel som du sett: I den här kursen ska vi titta på datastrukturena:

Abstraktion

Anta att vi vill skriva ett kalenderprogram.
Data: Olika typer av händelser kopplade till datum och tid.

Exempel på operationer:
find_events(start_date, end_date)
add_appointment( parametrar? )
delete_item( parametrar? )

Man behöver inte veta exakt hur data lagras för att använda operationerna.

Likadant i Python - vi vet inte hur strängar, listor och uppslagslistor är definierade, ändå kan vi använda dom. Det här är ett exempel på abstraktion. Om implementationen av listans metoder ändras (i en ny Python-version) behöver vi inte bekymra oss, alla våra program som använder listor fungerar ändå. Vi använder listan som en abstrakt datastruktur.