Övning 2

Komplexitet

• KÖRTIDER 

  Mål: Öva på att räkna på tidskomplexitet.
  En viss algoritm tar 0.5 ms när antal indata är 100. Hur lång kommer körtiden att bli när antal indata är 500 om man vet att körtiden är:
  1. linjär
  2. O(NlogN)
  3. kvadratisk
  4. kubisk
  lösning
  
  

  ---

• Tidstentan 2014-01-08, uppgift 4 (betyg E + C)

  Mål: Praktiskt exempel på tidskomplexitet.

  • Betyg E

    Antalet binära strängar av längd n är 2ⁿ. Antalet alfanumeriska (ca 32 olika tecken) strängar av längd m är 32^m.

    Vad blir uttrycken ovan om n=10 och m=3?

    Hur mycket större än m måste n vara för att det första uttrycket ska bli större än det andra?

  • Betyg C

    Linda berättar för Alexander att hon bytt till ett lösenord med 45 binära siffror. ''Men herregud!'', säger Alexander, ''Det blir ju alldeles för lätt att knäcka. Själv har jag 9 alfanumeriska tecken i mitt.''

    Vems lösenord är svårast att knäcka med totalsökning?

    Ungefär hur många sekunder tar knäckningen om datorn prövar en miljard lösenord i sekunden?

    Visa dina beräkningar!

  ---

  Binära sökträd

  Mål: Bli säker på att praktiskt genomföra algoritmer för binära sökträd.

• TRÄDBYGGEN

  • Hur ser det binärträd ut som skapas om man puttar in talen 4 2 1 6 3 7 5 i denna ordning?
  • Och hur ser det ut om man sätter in dom i omvänd ordning, alltså 5 7 3 6 1 4 2?
  • Är båda träden binära sökträd?
  • Är de balanserade?

• POSTORDERTRÄD

  • Skriv ut något av träden i inordning och bygg upp ett nytt träd från denna talföljd.
  • Skriv sedan ut dom i preordning och bygg upp nya träd från dessa talföljder.
  • Skriv slutligen ut dom i postorder och bygg upp nya träd från dessa talföljder.

  lösning

  ---

  Rekursion

  Mål: Träna på rekursiva algoritmer för tal och binära sökträd.

• GCD

  För att beräkna största faktorn som två tal m och n har gemensamt kan vi använda Euklides algoritm:
  Om m är jämnt delbar med n så är n den största gemensamma faktorn. Annars är GCD(m, n) = GCD(n, m%n). Skriv en rekursiv funktion!

lösning

• FIBONACCITAL

  Leonardo Fibonacci skrev år 1225 en bok där han beskrev denna intressanta talföljd:
  Sista december föds en kaninpojke och en kaninflicka. Vid två månaders ålder och varje månad därefter producerar varje kaninpar ett nytt kaninpar. Vi kan skriva en rekursiv formel för antal kaninpar:
• \(f(0)=0\)
• \(f(1)=1\)
• \(f(n)=f(n-1) + f(n-2)\) 
  Skriv en rekursiv funktion för att beräkna Fibonaccital. Visa vilka rekursiva anrop den ger upphov till vid beräkningen av f(5). Är det här det effektivaste sättet att beräkna Fibonaccitalen?
  lösning
  
  

• REKURSIV TRÄDSUMMA

  Ge en rekursiv tanke för summan av alla talen i trädet och programmera den så att anropet tree.sum() ger rätt svar.

• REKURSIV TRÄDHÖJD

  Ge en rekursiv tanke för höjden av ett träd. Höjden är den maximala nivån som nån av trädets noder befinner sig på. Ett träd med bara en rotnod har höjden 0, och ett tomt träd har höjden -1.

lösning

• Aliententan 2015-03-20, uppgift 9 (betyg A)

  Samtliga solförmörkelsedatum på jorden under perioden 4000 f.kr. - 4000 e.kr. är insorterade i ett binärt sökträd. Givet en historisk persons födelse och död, beskriv en algoritm som hittar antal solförmörkelser personen potentiellt skulle kunna ha upplevt under sin livstid.
  Algoritmbeskrivningen måste vara välstrukturerad och begriplig.

  lösning

Extra programmeringsuppgift

Tidtagning med timeit

Skriv ett program som läser in glassar från en fil och skriver ut dom i bokstavsordning. Hur lång tid tar inläsningen från filen?

import timeit  #tidtagning

def fil_till_lista():
    """Läser in alla glassar från filen,
    lägger dom i en lista,
    returnerar listan"""
    with open("glass.txt", encoding="utf8") as glassfil:
        rubrikrad = glassfil.readline()
        glasslista = []
        for rad in glassfil:
            glass = rad.strip()
            glasslista.append(glass)
    return glasslista


def main():
    glasslista = fil_till_lista()
    glasslista.sort()

    for glass in glasslista:
        print(glass)

    # Hur lång tid tar det att läsa in från filen?
    t = timeit.Timer(fil_till_lista)
    print("En miljon anrop av fil_till_lista tog", t.timeit(), "sekunder.")

    # Använd lambda för att ta tid på metodanrop eller funktion med parameter
    t = timeit.Timer(lambda: glasslista.sort())
    print("En miljon anrop av sort tog", t.timeit(), "sekunder.")3 5 6 7 8

main()