Lösningar

LÖSNINGAR

1. A B R A K A D A B R A i 1 2 3 4 5 6 7 8 9 10 11 next(i) 0 1 1 0 2 0 2 0 1 1 0 KMP-sökning tar n+m jämförelser, där m är antal tecken i söksträngen och n är antal tecken i texten. Alltså 1.8 miljoner+11. 
2. a) [A-Z][a-z]*
   eller
   [^.] [A-Z][a-z]*
   b) lösning:
   .*[.]py
   eller
   .*\.py
3. a) sandlåda, sand-låda, sondlåda men inte syndlåda b) [CK]rou?h?nskoo?g [CK]ro[uh]*nskoo?g 
4. Syntax för kanadensare Alternativ 1 och 2 kan producera alla meningarna. Alternativ 3 och fyra kan inte producera 'Kanot 1 och kanot 2 ska in!' Alternativ 1 och 4 godkänner felaktigt 'Kanot 4 och'. Alternativ 3 godkänner felaktigt 'Kanot och kanot 2'.
5. Värsta webbsyntaxen

     
   <webbfil> ::= <nothing>
                 | <text>
                 | <Q><webbfil></Q>
                 | <webbfil><BR><webbfil>
   <Q>       ::= "<Q>"
   </Q>      ::= "</Q>"
   <BR>      ::= "<BR>"

6. Använd bästaförstsökning med en prioritetskö som prioriterar på lägsta seglade totaltiden. Låt varje nod innehålla total seglingstid samt ha en faderspekare (för rekursiv utskrift av vägen då lösning hittats). Princip för genomgång av problemträdet:

   1. Lägg startpunktsnoden med totaltiden noll och tom faderspekare i prioritetskön.
   2. Upprepa punkterna 3-4 så länge kön inte är tom.
   3. Plocka ut en fadersnod ur kön. Om detta är slutpunkten, skriv ut vägen rekursivt och avsluta.
   4. Generera en son i taget genom att för varje punkt runt omkring fadersnoden skapa en sonnod med seglingstiden ökad beroende på vindstyrka, vindriktning och placering i förhållande till fadersnoden. Lägg in sonnoden i prioritetskön.

   Om dumbarnskoll ska utnyttjas måste det ta hänsyn till både punkten och totala seglingstiden till den punkten. Alla söner med sämre tider till samma punkt är då dumsöner. På det viset slipper algoritmen besöka samma punkt flera gånger - den blir effektivare.

   Eventuellt krävs någon snabb uppslagning av punkternas information, t ex med en hashtabell som hashar på punkternas nummer eller position. Noderna kan innehålla lägsta tid som uppnåtts för att tillåta dumbarnkoll utan att kräva extra minne.

   För kortaste vägen, använd istället bredden först med en vanlig kö och blanda inte in totala seglingstiden i varje nod. I detta fall måste vi göra dumbarns koll för att sökningen ska bli effektiv.

   Datastrukturer:
   Prioritetskö / kö
   Hashtabell
   Noder med seglingsdata