Föreläsning 1: Introduktion till kursen

Mål Läs

Kursinformation, ämnesintroduktion.

KursPM

Kapitel 1 och Kapitel 2 Länkar till en extern sida. i kursboken

Länkar till dagens frågor och quiz

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?

  • Föreläsningar     genomgång av algoritmer och datastrukturer.
  • Övningar     kodexempel inför labben och träning inför KS:ar.
  • Labbar     ni implementerar ni datastrukturer och algoritmer.
  • Kontrollskrivningar    ges på schemalagd tid som obevakade Canvas-quiz 

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).   *Kontakta kursledaren om du blir sjuk
  • Munta med C-uppgift och A-uppgift (under period 2).

 

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

seedsF1.py

#Frödata från https://github.com/javierigea/seed_size/blob/master/data/AllKewdata.txt

import csv

class Seed:

    def __init__(self, seed):
        self.name = seed[0] + " " + seed[1]
        try:
            self.weight = float(seed[2].strip("g"))
        except ValueError:
            self.weight = 0.5

    def __str__(self):
        return self.name + " " + str(self.weight)

def read_file(filename):
    with open(filename, mode="r") as seedfile:
        csvfile = csv.reader(seedfile, delimiter = "\t")
        next(csvfile)
        for line in csvfile:
            print(line)

def read_file_to_list(filename):
    seedlist = []
    with open(filename, mode="r") as seedfile:
        csvfile = csv.reader(seedfile, delimiter = "\t")
        next(csvfile)
        for line in csvfile:
            if len(line) == 3:
                newseed = Seed(line)
                seedlist.append(newseed)
    return seedlist

def find_max(seedlist):
    maximum = 0
    for seed in seedlist:
        if seed.weight > maximum:
            maximum = seed.weight
            maxseed = seed
    return maxseed
def main():
    seedlist = read_file_to_list("AllKewdata.txt")
    print("Det finns", len(seedlist), "fröer")
    print("Det tyngsta fröet är", find_max(seedlist), "g")

main()
 AllKewdata.txt

Genus    Species    SeedWeight_g
Ambavia    gerrardii    699.3513514g
Amborella    trichopoda    3.675g
Anaxagorea    panamensis    92.7g
Anemopsis    californica    0.364g

 


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.
Titta på algoritmen ovan.
  • Vad är n?
  • Vad är T(n) för maxberäkningen?

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)