Föreläsning 1: Introduktion till kursen

Kursen och formalia

Kursen examineras med labbar och tentamen (betyget ges av tentan). Förra året var det 86% som klarade kursen. Läs kurs-PM och titta ofta på kursens webbsida för dagsaktuell information!

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

Datastrukturer
Abstraktion
Algoritmer

Preliminär kursplan med läsanvisningar

Läsanvisningarna är till kursboken "Problem Solving with Algorithms and Data Structures using Python" av Bradely N. Miller and David L. Ranum.

Föreläsning 1 - Introduktion till kursen: kap 1 (utom 1.4.4.2)
Föreläsning 2 - Abstrakta datatyper: kap 2 och 7.2
Föreläsning 3 - Komplexitetsanalys, sökning, rekursion: kap 3 (men vänta med 3.2.3 och 3.4.3) och 4.1-4.3.2
Föreläsning 4 - Binära träd, binära tal: kap 5.1-5.6 (men vänta med 5.5.1) och 3.2.3
Föreläsning 5 - Problemträd: kap 6.1-6.4.2
Föreläsning 6 - Hashning: kap 4.3.3
Föreläsning 7 - Sortering: kap 4.4
Föreläsning 8 - Prioritetskö, trappa (heap): kap 5.7, 6.4.5
Föreläsning 9 - Automater, textsökning: kap 7.6
Föreläsning 10 - Syntax, rekursiv medåkning: kap 5.5.1
Föreläsning 11 - Datakomprimering: kap 7.5
Föreläsning 12 - Dokumentering, testning, kryptering: kap 3.4.3
Föreläsning 13 - Repetition inför tentan
Föreläsning 14 - Tentagenomgång

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.
Hemtalen ligger ibland lite före, för att uppmuntra till att läsa i förväg!

Datastrukturer i Python

Strängar

Metoder och operationer:

center(b) Returnerar strängen centrerad i b positioner.
count(x) Returnerar antalet x i strängen.
ljust(b) Vänsterjusterar i b positioner.
lower() Gör om till gemena.
rjust(b) Högerjusterar i b positioner.
find(x) Returnerar index för första förekomsten av x.
split() Returnerar en lista med delsträngar (t ex ord i en mening).
[i] Returnerar i:te tecknet i strängen.
[:] Plockar ut en delsträng.
+ Konkatenerar två strängar.
* Flerdubblar strängen.
in Kolla om ett tecken finns med i strängen.
len Returnerar strängens längd.

Listor

Metoder och operationer:

append(x) Lägger till x sist i listan.
insert(i,x) Lägger till x på plats i.
pop() Plockar bort sista elementet från listan.
sort() Sorterar listan.
reverse() Vänder på listan.
index(x) Returnerar index för första förekomsten av x.
count(x) Räknar antalet x i listan.
remove(x) Tar bort första förekomsten av x.
[i] Returnerar i:te elementet i listan.
[:] Plockar ut en dellista.
+ Konkatenerar två strängar.
* Flerdubblar listan.
in Kolla om ett tecken finns med i listan.
len Returnerar listans längd.

Uppslagslistor (dictionary)

Metoder och operationer:

keys() Returnerar lista med nycklarna (det man slår upp på).
values() Returnerar lista med värdena.
items() Returnerar en lista med nyckel-värde-par.
get(k) Returnerar värdet för nyckeln k.
has_key() Kollar om nyckeln k finns med.
[k] Returnerar värdet för nyckeln k.
in Kollar om en nyckel finns med.
len Returnerar uppslagslistans längd.

Abstraktion

Vi har ingen aning om hur strängar, listor och uppslagslistor är definierade i Python, ändå kan vi använda dom. Det här är ett exempel på abstraktion. Om implementationen av insert() ä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.

Andra datastrukturer

Räcker det med strängar, listor och uppslagslistor? Hur lagras t ex Facebook? Se kursmålen i KursPM!

I kursen ska vi implementera egna datastrukturer. Exempel:

# -*- coding: Latin-1 -*-
# Fraction-klassen från Miller & Ranums bok, s 35

def gcd(m,n):
    while m%n != 0:
        oldm = m
        oldn = n
        m=oldn
        n=oldm%oldn
    return n


class Fraction:

    def __init__(self, top, bottom):
        self.num = top
        self.den = bottom

    def __str__(self):
        return str(self.num)+"/"+str(self.den)

    def show(self):
        print self.num,"/",self.den

    def __add__(self,otherfraction):
        newnum = self.num*otherfraction.den + \
                 self.den*otherfraction.num
        newden = self.den * otherfraction.den
        common = gcd(newnum,newden)
        return Fraction(newnum/common,newden/common)

    def __cmp__(self,otherfraction):
        num1 = self.num*otherfraction.den
        num2 = self.den*otherfraction.num
        if num1 < num2:
            return -1
        else:
            if num1 == num2:
                return 0
            else:
                return 1

Algoritmer

Exempel: Vi vill hitta alla Core-pass på de närmaste av F och S lokaler.
Indata: Önskat pass och tänkbara lokaler.

Algoritm:

För varje webbsida bland tänkbara lokaker:
- Gå igenom html-koden på webbsidan:
  - Om passet hittas:
    - Spara i en lista.
Skriv ut listan med funna pass.

Hur lång tid tar det här? Det beror förstås på hur många webbsidor vi vill titta på. Lite finare uttryckt: Tidskomplexiteten beror av indatas storlek.

I kursen ska vi titta på många algoritmer, t ex för sökning och för parsning (att tolka html-kod). Se KursPM igen!

Labbar

Det här är inte en programmeringskurs. Men den innehåller sju labbar där man måste programmera en hel del. Första labben kräver inte mer förkunskaper än du har nu, så du kan sätta igång bums!

Om du har glömt bort ditt lösenord eller inte har konto på CSC:s datorer så måste du kontakta Delfi (Osquars backe 2, plan2) snarast.