Teoriuppgifter till labb 2

Dessa teoriuppgifter hör till labb 2 och kan redovisas för en teoripoäng till tentan. Redovisningen görs skriftligt och muntligt på övningen den 17 september (ingen annan redovisningsmöjlighet finns). Det är frivilligt att redovisa teoriuppgifterna, men för att klara av att göra labben bör du ha gjort dom. Arbeta gärna i grupp med labbteoriuppgifterna, men var och en ska vid redovisningen ha med en lösning. Om det är flera som samarbetat om lösningen ska du se till att det framgår klart (se hederskodex.). Överarbeta inte lösningen - den behöver inte se snygg ut. Ta med lösningen på papper till övningen. Det går bra att lämna in en handskriven lösning.

Teoriuppgifter

Sätt dig in i hur det givna programmet fungerar och svara sedan på följande frågor.

1. Formulera rekursionen (partDist i programmet) så kompakt som möjligt med matematisk notation Download matematisk notation. Du får gärna kalla funktionen PD så blir det ännu kompaktare.

2. Beräkna partDist("labd", "blad", x, y) för alla x och y mellan 0 och 4 och för in värdena i en matris M. Vad blir M?

3. Vad är det alltså metoden partDist(w1, w2, x, y) beräknar?

4. Visa att tidskomplexiteten för Distance(w1, w2) är exponentiell i ordlängden. Du kan anta att w1 och w2 har samma längd. Det räcker att motivera med ord.

5. Visa hur man kan spåra vilka editeringsoperationer som görs i den kortaste editeringsföljden från "labd" till "blad" genom att titta på matrisen M.

6. Visa med pseudokod hur rekursionen kan beräknas med dynamisk programmering, dvs hur en dynprogmatris M kan skapas. Vilken beräkningsordning är lämplig vid beräkning av M?

7. Analysera tidskomplexiteten för att bestämma editeringsavståndet mellan ett n-bokstavsord och ett m-bokstavsord med dynamisk programmering.

8. Beräkna dynprogmatrisen för editeringsavståndet mellan "labs" och "blad".

9. Vilken del av matriserna för "labd"-"blad" och "labs"-"blad" skiljer?

10. Allmänt sett, vilken del av matriserna för Y-X och Z-X skiljer när orden Y och Z har samma första p bokstäver?