Övning 6

Ta en titt på Labb 6

1.  Skriv ett program som läser in glassar från en fil: glass.txt Download glass.txt och ta tid på listoperationerna:

  • sort
  • index

med hjälp av Pythons modul timeit

Lösning

2. Fyll i tabellen:

Komplexitet

(värsta fallet)

Algoritmer
                            binärsökning
bubbelsortering
hashtabell - sökning
heapsort
insättningssortering
linjärsökning
mergesort
quicksort
räknesortering
urvalssortering

 

​Förberedelse för KS5. Mål:

  • Kunna konstruera en KMP-automat
  • Kunna beskriva hur textsökning med KMP, Rabin Karp och Boyer Moore fungerar,
  • känna till tidskomplexiteten för textsökning med dessa metoder,
  • och kunna avgöra för vilka fall respektive metod är lämplig
  • Kunna avgöra vilka strängar ett reguljärt uttryck matchar,
  •  samt formulera ett reguljärt uttryck som matchar givna strängar

Textsökning

  1. KMP-automat

    >>>Reglerna för hur next-vektorn bildas kan sammanfattas så här:

    • next[1]=0.
    • Annars är next[i]=1 om sökordet inte innehåller upprepningar.
    • ...men om de j senaste bokstäverna vi sett bildar början på sökordet sätts next[i]=j+1.
    • ...men om bokstav j+1 är samma som bokstav i sätts i stället next[i]=next[j+1].<<< Föreläsning 11

    a) Konstruera en KMP-automat som söker efter texten "ABRAKADABRA". Ange även den next-vektor som definierar automaten.

    b) Ungefär hur många jämförelser behövs för att automaten ska se att ordet inte finns med i "Harry Potter och Fenixorden", en bok på 1.8 Mbyte?

    Download lösning

  2. Reguljära uttryck

    a) Skriv ett reguljärt uttryck (regex) som letar upp alla namn i en text. Kan detta regex råka matcha även andra ord i texten?

    b) Skriv ett regex som matchar filnamnen på alla pythonfiler. När skulle man kunna behöva ett sådant regex?

    c) Givet det reguljära uttrycket s(a|o)nd-?låda:
    Skriv upp tre strängar som matchas av det reguljära uttrycket och ett som inte gör det.

    d) Skriv ett reguljärt uttryck som matchar alla tänkbara sätt att stava namnet Kronskog (Crounskog, Krohnskoog, etc).

    Download lösning

  3. Automat på olika format

    Rita den graf som beskrivs av övergångsmatrisen
    "#" "%" "&" "?"
    1 2 1 1 1
    2 2 3 1 1
    3 2 1 4 1
    4 2 1 1 5
    lösning
  4. Rabin Karp

    På vilket sätt används en hashfunktion i textsökning med Rabin Karp? Visa med ett exempel.
    lösning
  5. Boyer Moore

    Vad är tidskomplexiteten för Boyer Moore? Berätta vad de ingående variablerna representerar, och förklara "bästa fallet".
    lösning