GRUDAT, ÖVNING 11

  Textkomprimering och grafalgoritmer

Jag går igenom Huffman noga och övriga komprimeringar
(LZW, GIF, JPEG, MPEG, MP3,...) slarvigt. Grafalgoritmerna
är Dijkstra (bästa-först-sökning efter kortaste vägen),
Kruskal (billigaste spännande träd, ta billigaste vägstump
först, näst billigaste sen även om dom inte sitter ihop...)
och Prim (billigaste vägstumpen byggs ut så att man alltid
har ett träd). Men jag har inte några bra övningar på lager.
Här är några idéer - ni har säkert bättre!

1 KOMPRIMERADE GENER

En gen är ett cirka tusen bokstäver långt ord i
fyrbokstavsalfabetet ACGT. Som bekant består den
genetiska koden av tripletter så att AAA kodar
för aminosyran lysin och AGA för arginin osv.
Föreslå en lämplig komprimerad kodning för gener!

2 CYKELFRIA VÄGAR

Ett vägnät är givet som en symmetrisk kvadratisk 0-1-matris.
Om det står en etta i position (i,j) finns det en direkt
väg mellan ort i och ort j. Föreslå en algoritm för att
avgöra om vägnätet är sammanhängande och cykelfritt, dvs
är ett träd!

3 SOLITAIRESPELET

Ett gammalt fint spel med 36 kulor och 37 hål.       o o o
En kula får hoppa över en annan vågrätt eller        o o o
lodrätt till ett tomt hål på andra sidan. Den        o o o
överhoppade kulan tas bort. Målet är att få    o o o o o o o o o
bort alla kulor. Föreslå en algoritm som kan   o o o o   o o o o
avgöra om det går!                             o o o o o o o o o
                                                     o o o
4 SNABBAST NERFÖR PISTEN                             o o o

Det finns många sätt att ta sej ner. Om man
antar att tiden för varje vägstump är känd,
hur finner man snabbaste vägen från toppen
och ner (till någon punkt nedanför pisten)?