Ö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
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
-
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?
-
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).
-
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 -
Rabin Karp
På vilket sätt används en hashfunktion i textsökning med Rabin Karp? Visa med ett exempel.
lösning -
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