Hemtal 5
A) Prioritetsköer och bästaförstsökning
Läs om
prioritetsköer och
Dijkstras algoritm i kursboken.
- Vad är heapvillkoret?
- Visa med en serie bilder hur det ser ut när man i tur och ordning
puttar in talen
2 4 8 16 i en max-heap.
- Visa sen vad som händer när man i tur och ordning plockar ut elementen ur heapen ovan.
- Vad är komplexiteten för Heapsort?
- I labb 4 används breddenföstsökning för att hitta kortaste vägen
från fan till gud. Skulle det gå lika bra att använda bästaförstsökning
med en prioritetskö? Motivera ditt svar!
B) Automater och textsökning
Läs om
Finite-state machine,
KMP,
Boyer-Moore,
Rabin-Karp
och
reguljära uttryck.
- Hur många tillstånd kan en FSM maximalt ha?
- Rita upp en KMP-automat för att söka efter REDAREN i en text.
Ange även next-vektorn!
- Vilken komplexitet har textsökning med KMP? Definiera alla variabler du använder.
- Ge ett exempel där Boyer-Moore är snabbare än Rabin-Karp!
- Skriv upp ett reguljärt uttryck som matchar ditt efternamn stavat på olika sätt.
Du som gjort uppgiften ska skriva ditt namn
och personnummer överst till höger på alla blad.
Du som rättar ska skriva ditt namn och personnummer
längst ner till vänster på första bladet.
