DD2350HT201
    Teoriuppgifter till labb 2
    Hoppa över till innehåll
    Översikt
    • Logga in
    • Översikt
    • Kalender
    • Inkorg
    • Hjälp
    Stäng
    • Min översikt
    • DD2350HT201
    • Uppgifter
    • Teoriuppgifter till labb 2
    • Startsida
    • Kursöversikt
    • Uppgifter

    Teoriuppgifter till labb 2

    • Inlämningsdatum 17 sep 2020 av 10.15
    • Poäng 1

    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 ladda upp lösningen som PDF-dokument. Om det är flera som samarbetat om lösningen ska det framgå klart (se hederskodex).  Det går bra att lämna in en inskannad handskriven lösning.

    Läsanvisningar för teoriuppgifterna:

    • labblydelsen och den givna programkoden
    • videorna och förberedelseuppgifterna till föreläsning 9 (dynamisk programmering del 1)
    • sida 251-260 i KT (Kleinberg-Tardos)

    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.

    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.

    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?

    1600330500 09/17/2020 10:15am
    Ytterligare kommentarer:
    Maxresultat för gradering till > poäng

    Matris

     
     
     
     
     
     
     
         
    Det går inte att ändra en matris efter att du börjat använda den.  
    Hitta en matris
    Hitta matris
    Titel
    Du har redan bedömt studenter med den här matrisen. Större ändringar kan påverka resultaten för deras uppgifter.
    Titel
    Kriterier Bedömningar Poäng
    Redigera beskrivning av kriterium Ta bort kriterium rad
    Det här kriteriet är länkat till ett lärandemål Beskrivning av kriterium
    tröskel: 5 poäng
    Redigera ranking Radera ranking
    5 till >0 poäng
    Full poäng
    blank
    Redigera ranking Radera ranking
    0 till >0 poäng
    Inga poäng
    blank_2
    Det här området kommer användas av utvärderaren för kommentarer relaterade till det här kriteriet.
    poäng
      / 5 poäng
    --
    Ytterligare kommentarer
    Poängsumma: 5 av 5