Övningsmästarprov 1

Det riktiga mästarprovet ska lösas individuellt och redovisas både skriftligt och muntligt. Detta övningsmästarprov får däremot mycket gärna lösas i tvåpersonsgrupp. Det är dessutom tillåtet att diskutera det i ännu större grupper. Skriv ner lösningen för hand eller med dator och ta med till övningstillfället 24 september. Ta med en egen utskriven lösning även om du gjort den tillsammans med en kamrat. Vid övningen kommer lösningarna att kamraträttas enligt samma kriterier som används vid det ordinarie mästarprovet. Den som vid övningstillfället redovisar ett gott försök till lösning (den behöver inte vara korrekt i alla delar) får en teoripoäng.

Övningsmästarprovet är frivilligt, till skillnad från det ordinarie mästarprovet som är ett obligatoriskt moment i kursen. Det ordinarie mästarprovet består av tre uppgifter som motsvarar betygskriterierna för E, C respektive A. Övningsmästarprovet har bara en uppgift, och den motsvarar betygskriterierna för E. För att se exempel på hur utförliga lösningarna bör vara kan du titta på lösningar till tidigare mästarprov på kurswebben. Där finns också tips om hur man skriver pseudokod.

Kortaste texten

Betygskriterium: utveckla algoritmer med datastrukturer för enkla problem givet en konstruktionsmetod.

En text består av n stycken ord. Ordens längd i tecken betecknas w₁, ..., w_n (i samma ordning som orden förekommer i texten). För enkelhets skull ingår skiljetecken (som punkt och komma) i det ord dom följer, så vi slipper skilja på bokstäver och skiljetecken. När vi skriver ner texten ska det som vanligt stå ett mellanslag mellan två ord som följer på varandra på samma rad. Målet är att formatera texten (utan avstavningar) så att den ryms på så få rader av längd len som möjligt. Ordens inbördes ordning ska bibehållas.

Konstruera och beskriv pseudokoden för en effektiv girig algoritm som givet n, len och w₁, ..., w_n beräknar och returnerar det minimala antalet rader av längd högst len som texten kan skrivas ner på. Du kan anta att inget enskilt ord i texten är längre än len tecken.

Som vanligt för giriga algoritmer ingår det att motivera att algoritmen returnerar det optimala värdet. Det brukar vara en större utmaning än att utveckla själva algorimen, som ibland kan vara närmast trivial. Analysera också tidskomplexiteten för algoritmen (med enhetskostnad).

Exempel på en text och motsvarande indata till problemet:

"Tidskomplexiteten O(1) betyder att komplexiteten är oberoende av indatas längd."

n=10, len=25, w₁=17, w₂=4, w₃=7, w₄=3, w₅=13, w₆=2, w₇=9, w₈=2, w₉=7, w₁₀=6.

Den optimala lösningen är 4 rader.

Bedömningskriterier

Mästarprov 1 betygsätts efter betygskriterierna för målen utveckla algoritmer med datastrukturer samt analysera algoritmer med avseende på effektivitet och korrekthet. Dessutom kommer målet jämföra alternativa algoritmer och datastrukturer med hänsyn till effektivitet och pålitlighet naturligt att övas vid algoritmkonstruktionen.

Bedömningsgrund	Kravnivå för denna uppgift
Algoritmbeskrivning
Modellerar problemet på ett rimligt sätt	nej
Beskriver algoritmen övertygande i ord och ev. i bild	måttliga
Beskriver algoritmen i pseudokod	ja
Bra urval av detaljer i pseduokoden	måttliga
Algoritmen är tillräckligt effektiv	polynomisk
Algoritmen löser rätt problem	ja
Tidskomplexitet
Anger tidskomplexitet i föreskrivna variabler	ja
Motiverar tidskomplexitet	måttliga
Korrekthetsresonemang
Förklarar vad som i allmänhet behöver visas i ett korrekthetsbevis av denna typ	endast principerna
Motiverar att algoritmen ger optimalt värde	bevisskiss/idé
Genomför ett fullständigt korrekthetsresonemang  som omfattar alla delar	nej

Ovanstående krav ska vid det ordinariet mästarprovet vara uppfyllda efter den muntliga redovisningen, där oklarheter och små ofullkomligheter och fel kan redas ut. Kraven på den skriftliga lösningen är något lägre.

Lösningsförslag och övningsbedömning

På övningsmästarprovsövningen gicks detta lösningsförslag Download detta lösningsförslag

igenom och en kamratbedömning Download kamratbedömning

av övningsmästarprovet genomfördes med detta rättningsprotokoll Download detta rättningsprotokoll

. Vid det riktiga mästarprovet kommer ett sådant rättningsprotokoll att användas vid bedömningen.