B
DD1320 Tillämpad Datalogi
Föreläsning 1: Introduktion till kursen
Kursen och formalia
Kursen examineras med labbar (7 st) och tentamen (betyget ges av tentan).
Förra året var det tre fjärdedelar som var klara med kursen efter höstterminen.
Forum för nyheter, diskussioner och frågor är KTH Social.
Under vårterminen är kursen en fortsättning på DD1321. 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.
|
Diagnostiskt prov i Python
|
Datalogikurser världen över är mycket lika varandra. Innehållet är
i huvudsak det här.
- Abstraktion
- Datastrukturer
- Algoritmer
Kurserna DD1320/DD1325 har följande moment:
- LAB1 3hp (sju laborationer)
- TEN1 3hp (betygsgivande tentamen)
1.5hp motsvarar 40 timmars arbete, så LAB1 och TEN1 tillsammans
motsvarar 160 timmar. Drar man bort de schemalagda timmarna och
fördelar tiden över kursveckorna 34-45 blir det ca 8 timmar
eget arbete per vecka.
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:
- Förstå
- Abstrakt: hur använder man den?
- Implementation: hur funkar den i detalj?
- Analysera
- Hur snabb/effektiv är den? Komplexitet mm.
- Vad har den för fördelar/nackdelar? Begränsningar?
- När är den lämplig/olämplig?
(jämfört med andra algoritmer/datastrukturer)
Preliminär plan över föreläsningarna
-
Föreläsning 1 - Introduktion till kursen
-
Föreläsning 2 - Abstrakta datatyper
-
Föreläsning 3 - Komplexitetsanalys, sökning
-
Föreläsning 4 - Rekursion, binära träd
-
Föreläsning 5 - Mer om binära träd, binära tal
-
Föreläsning 6 - Problemträd
-
Föreläsning 7 - Hashning, bloomfilter
-
Föreläsning 8 - Sortering, prioritetskö, trappa (heap)
-
Föreläsning 9 - Automater, textsökning
-
Föreläsning 10 - Syntax, rekursiv medåkning
-
Föreläsning 11 - Datakomprimering
-
Föreläsning 12 - Kryptering, andra programspråk
-
Föreläsning 13 - Repetition inför tentan
-
Föreläsning 14 - Tentagenomgång, testning, info om labb 6 och 7
På föreläsningarna går vi igenom algoritmer och datastrukturer.
På övningarna övar vi problemlösning (som på tentan) och ni redovisar
hemtalen (bonusgivande men ej obligatoriska).
På labbarna implementerar ni datastrukturer och algoritmer.
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 alla olympiaddeltagare från en
fil och lagra dom i en lista. Deltagarna ska lagras i omvänd ordning
(den första i filen ska hamna sist i listan).
- öppna filen
- läs in första deltagaren
- lagra deltagaren i en lista
- upprepa punkt 2 och 3 tills alla rader i filen lästs in
- vänd listan
Implementation 1:
infil = open("London2012.csv","r")
rad = "start"
lista = []
while rad != "":
rad = infil.readline()
lista.append(rad)
lista.reverse()
print(len(lista))
Implementation 2:
infil = open("London2012.csv","r")
lista = []
for rad in infil:
lista.insert(0,rad)
print(len(lista))
Den andra varianten ser ju onekligen enklare ut. Bägge programmen
går snabbt att köra för den givna infilen med ca 10 000 deltagare.
Men om vi ökar indatas storlek från 10 000 till 100 000 blir det
andra programmet märkbart långsammare.
Den datastruktur vi använder, Pythons inbyggda lista, är implementerad
som en array. Den är bra om man snabbt vill komma till ett element
via index (t ex lista[8941]). Men att lägga in ett element allra först
i en array tar längre tid (övriga element måste flyttas ur vägen först).
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 Python: lista, objekt
- I Matlab: matris, struct
I den här kursen ska vi titta på datastrukturena:
- Objekt
- Länkade listor bestående av noder (objekt) med referens till nästa nod
- Stack
- Kö
- Allmänna träd
- Binära träd
- Hashtabeller
- Booleska hashtabeller och bloomfilter
- Trappa/heap
- Prioritetskön
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.