Föreläsning 1 Introduktion till kursen

Kursen och formalia

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.

• Kurskrav
• Läranvisningar
• Kurslitteratur
• KTH Social - kursinformation
• Diagnostiskt prov i Python
• Algoritmexempel med pythonrepetition
• Testning
• Datastrukturer
• Abstraktion

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

• Abstraktion
• Datastrukturer
• Algoritmer

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).
På labbarna implementerar ni datastrukturer och algoritmer.
Labbarna görs helst i grupper om två. Tips: prova 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 i filen ordnade med sydligast latitud först, men i listan vill vi att dom ska ligga i ordning från nordligaste till sydligaste.

Algoritm 1

1. öppna filen
2. läs in rubrikraden
3. läs in första raden
4. lägg raden sist i listan
5. upprepa punkt 3 och 4 tills alla rader i filen lästs in
6. vänd listan

print("Med while-slinga och append")
land = input("Vilket land? ")
filnamn = land + ".txt"
with open(filnamn, encoding = "utf8") as infil:
  rubrikrad = infil.readline()
  lista = []
  rad = infil.readline().strip()
  while rad != "":
    rad = infil.readline().strip()
    lista.append(rad)
lista.reverse()
print("Antal rader =", len(lista))
print("Först ligger nu:")
for plats in lista[0:5]:
    print(plats)

Algoritm 2

Här är en annan algoritm för samma problem:

1. öppna filen
2. läs in rubrikraden
3. läs in första raden
4. lägg raden först i listan
5. upprepa punkt 3 och 4 tills alla rader i filen lästs in

print("Med while-slinga och append")
land = input("Vilket land? ")
filnamn = land + ".txt"
with open(filnamn, encoding = "utf8") as infil:
  rubrikrad = infil.readline()
  lista = []
  for rad in infil:
    #rad = infil.readline()
    lista.insert(0, rad.strip())
lista.reverse()
print("Antal rader =", len(lista))
print("Först ligger nu:")
for plats in lista[0:5]:
    print(plats)

---

---