Föreläsning 1: Introduktion till kursen

Mål Läs

Kursinformation, ämnesintroduktion.

KursPM

Kapitel 1 och Kapitel 2 Links to an external site. i kursboken

Kursen och formalia

Kursansvariga studenter sökes!
Gärna en per program/inriktning. Anmäl dig bums till Linda.
  • KursPM
  • Övrig kursinformation på Canvas
  • Repetition av klasser i Python
  • Algoritmer - några exempel
  • Datastrukturer
  • Läranvisningar

Kursinnehåll

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

  • Abstraktion
  • Datastrukturer
  • Algoritmer

 

Vad händer i kursen?

All undervisning i denna kursomgång är på distans, i Zoom.

Vad är obligatoriskt för att klara kursen?

  • Labb 1-10 ska redovisas muntligt vid något av veckans labbtillfällen, och lämnas in i Canvas.
  • E-delen på tentan, dvs KS1 - KS5
  • Undervisningen är inte obligatorisk.

För högre betyg?

  • Den som gör alla E-labbar i tid får göra C-labben och A-labben (under period 2).
  • Munta med C-uppgift och A-uppgift (under period 2).

 

Pythonrepetition: en klass + läsa från fil

bok.py

class Bok:

def __init__(self, datarad):
rensad = datarad.strip()
uppdelad = rensad.split(";")
self.titel = uppdelad[0]
self.sidantal = int(uppdelad[1])
self.typ = uppdelad[2]
self.pris = int(uppdelad[3])

def __str__(self):
return self.titel

def main():
with open("bokdata.csv", encoding = "utf8") as fil:
rubrikrad = fil.readline()
print(rubrikrad)
datarad = fil.readline()
bok = Bok(datarad)
print(bok)

main()
 bokdata.csv

BOKTITEL;SIDANTAL;TYP;PRIS

The Raven Tower;416;inbunden;150

Problem Solving with Algorithms and Data Structures in Python;136;ebok;0

Time and Tide;442;pocket;120

Understanding Philosophy of Science;290;pocket;199

 


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 från en fil (t ex Download island.txt

eller kina.txt) 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, alltså i omvänd ordning.

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
Implementation med for-slinga och append
print("Algoritm 1 med append och reverse")
filnamn = "kina.txt"
rader = []
with open(filnamn, encoding = "utf-8") as landfil:
for rad in landfil:
rader.append(rad.strip())
rader.reverse()

#Kontrollera resultatet
print("Antal rader", len(rader))
for i in range(5):
print(rader[i])
Samma algoritm - implementation med while-slinga
print("Algoritm 1 med append och reverse + while")
filnamn = "kina.txt"
rader = []
with open(filnamn, encoding = "utf-8") as landfil:
rad = landfil.readline()
while rad:
rader.append(rad.strip())
rad = landfil.readline()
rader.reverse()

#Kontrollera resultatet
print("Antal rader", len(rader))
for i in range(5):
print(rader[i])

 
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
Implementation med insert
print("Algoritm 2 med insert")
filnamn = "kina.txt"
rader = []
with open(filnamn, encoding = "utf-8") as landfil:
for rad in landfil:
rader.insert(0,rad.strip())
print("Antal rader", len(rader))

for i in range(5):
print(rader[i])

Tidskomplexitet

Olika algoritmer kan ta olika lång tid för att lösa ett och samma problem. Ofta går det att ange tiden som funktion av indatas storlek, T(n) där n är antalet indata.
Jämför algoritmerna ovan.
  • Vad är n?
  • Vad är T(n) för algoritm 1 respektive algoritm 2?

Datastrukturer

Pythons lista är exempel på en datastruktur. I kursens tar vi upp följande datastrukturer:

  • Länkade listor
  • Vektor/array
  • Stack
  • Deque
  • Allmänna träd
  • Binära sökträd
  • Hashtabeller
  • Bloomfilter
  • Heap
  • Prioritetskö

På labbarna får du skriva egna implementationer av flera av dessa datastrukturer.

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)