Det här är inte en hemtenta, utan man måste göra den i tentasalen, ungefär som en vanlig salstenta.
Gäller som tentamen för:
DT2010 Datateknik B, Programmeringsmetodik, provkod 0100
DT2006 Datateknik B, Tillämpad datavetenskap B, provkod 0110
Ansvarig lärare är Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), telefon 070-73 47 013.
Som i alla moderna teleskop sitter man inte och tittar i det, utan man använder en sensor ungefär som i en digitalkamera. (Och nu börjar jag hitta på, så ni inte tror att det är så här teleskop fungerar på riktigt.)
Sensorn är fyrkantig, och kan ha ett mycket stort antal bildpunkter ("pixels"). Mätdata samlas på en fil:
Varje rad innehåller tre tal: två heltal som anger bildpunktens x- och y-koordinat, och ett reellt tal som anger mätvärde, dvs hur mycket ljus som mättes upp i just den bildpunkten. Samma bildpunkt kan förekomma flera gånger, och då ska mätvärdena summeras.
Vi ska leta efter stjärnor på bilderna från teleskopet. Därför behöver vi ett program som läser filen med mätdata, och som sen anger koordinaterna för den ljusstarkaste punkten, dvs den bildpunkt som har det högsta sammanlagda värdet. Med exempelfilen ovan blir det punkten (x=8, y=47), som har värdet 0.75.
På riktigt kommer filen att innehålla flera miljarder rader, med data om flera miljoner olika bildpunkter. Bilden från teleskopet är alltså ganska "gles": det är mest svart, och så finns det stjärnor här och där. Här är en liten del av en sådan bild, uppförstorad så man ser pixlarna tydligt:
Astronomerna har faktiskt redan löst problemet, säger de, med programmet matrix-brightest. Programmet använder en matris (dvs en "tvådimensionell array") för att lagra punkterna, och fungerar både snabbt och korrekt när de provkör det med simulerade data. Astronomerna är mycket stolta över sin prestation, så studera gärna det programmet.
Här är ett enkelt hjälpprogram som man kan använda om man vill slumpa fram testdata: make-some-data. (Programmet ger inte helt realistiska data, eftersom det sprider värdena jämt över bilden, och inte samlat i punkter som det kommer att bli på riktigt.)
| Lös denna uppgift först, och skicka in den. Spara också själv en kopia, ifall det blir något fel med posten! Börja inte med de andra uppgifterna innan du är klar med denna, och har skickat in den. |
Astronomernas program matrix-brightest fungerade som sagt bra. Men den riktiga sensorn har en storlek på en miljon gånger en miljon (dvs totalt en biljon, 1012) bildpunkter. När astronomerna ändrar konstanten SENSOR_SIDE från 1024 till 1000000, får matrisen inte längre plats i minnet, och deras fina program går inte att köra.
Hjälp astronomerna, genom att göra en lösning med en länkad lista i stället! Söknyckeln ska vara koordinaterna (x och y) för en punkt.
Det ska vara en länkad lista specifikt för detta ändamål, så använd inte någon generell datatyp (som std::list).
De här kan kanske vara en ledtråd:
| Lös först uppgift 1, och skicka in den. Därefter kan du lösa, och skicka in, den här uppgiften. Spara också själv en kopia, ifall det blir något fel med posten! Börja inte med uppgift 3 innan du är klar med denna, och har skickat in den. |
Astronomerna är missnöjda med ditt program från uppgift 2 ovan. Det går visserligen att köra, vilket är bättre än deras eget program, men tyvärr går det inte så snabbt. Det fungerar bra på små exempeldata. Men med astronomernas riktiga datafil, som ju innehöll flera miljarder rader med data om flera miljoner olika bildpunkter, tar programmet flera veckor att köra.
Gör en ny version av programmet som använder en bättre datastruktur, förslagsvis en hashtabell eller ett binärt träd. Vi vill ha en enorm förbättring av körtiden.
Datastrukturerna som används ska vara skapade specifikt för detta ändamål, så använd inte någon generell datatyp.
| Lös först uppgift 1 och 2, och skicka in dem. Därefter kan du lösa, och skicka in, den här uppgiften. Spara också själv en kopia, ifall det blir något fel med posten! |
Gör om uppgift 2 med hjälp av en generell datatyp.
Skapa först den generella datatypen (till exempel hashtabellen GenericHashTable). Välj själv metod för att skapa en generell datatyp. Dela upp på lämpliga filer. Det är inte förbjudet att inspireras av existerande lösningar, men du ska lämna in en som du gjort själv.
Använd den därefter i programmet för att lagra punkterna.
| Den här sista-uppgiften för betyget 5 kanske kan ta lite längre tid att lösa. Om den inte är helt klar när tentatiden tar slut, är det därför tillåtet att skicka in en preliminär lösning, som man sedan kan komplettera. Ange tydligt att det är en preliminär lösning. Kompletteringen ska skickas in senast en vecka efter tentan. |