Gäller som tentamen för:
DT2020 Datateknik B, Programmeringsmetodik, provkod 0100
DT2022 Datateknik B, Tillämpad datavetenskap, provkod 0110
DT2011 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.
Eftersom rymdvarelserna bor så långt bort, är de signaler som når fram till jorden mycket svaga. De drunknar i störningar av olika slag. För att filtrera bort störningarna lyssnar vi med många radioteleskop, och vi är bara intresserade av de signaler som tas emot av flera olika teleskop samtidigt.
Vi gör många miljarder observationer. De samlas på en fil, med en observation per rad. På raden står vilket observatorium som tog emot signalen, en tidpunkt, och två koordinater som anger vilken riktning signalen kom från. Exempel:
17 18:22:03 149 268 17 18:22:05 149 268 13 18:22:03 149 268 |
Här har observatorium 17 tagit emot en signal klockan 18:22:03 från riktning 149 268. Två sekunder senare tog samma observatorium emot en annan signal från samma riktning. Den första av dessa signaler togs dessutom emot av observatorium 13. I det här exemplet är det alltså den signalen som vi vill filtrera fram: klockan 18:22:03 från riktning 149 268.
Alla tal är heltal. En och samma signal kan observeras från ett eller flera observatorier. Om tiden och riktningskoordinaterna stämmer överens, räknas det som samma signal.
Vi behöver ett program som läser filen med observationsdata, och som talar om vilka signaler som observerats av flera observatorier samtidigt. Som utdata från programmet vill vi ha en lista på dessa signaler, med en notering om vid vilka observatorier var och en togs emot. Exempel på hur utmatningen kan se ut med exempelfilen ovan:
Tid: 18:22:03 Riktning: 149 268 Observatorier: 17 13 |
Ordningen spelar ingen roll, vare sig på signalerna eller på observatorierna.
| 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. |
Skriv ett program som först tar emot namnet på en textfil, antingen som ett kommandoradsargument eller genom att läsa in det. Textfilen ska innehålla observationer enligt scenariot ovan. Därefter ska programmet läsa den angivna textfilen, och lista de signaler som observerats mer än en gång. Numren på de observatorier som observerade signalen ska listas.
Använd länkade listor eller arrayer. Det ska vara datastrukturer gjorda specifikt för detta ändamål, så använd inte någon generell datatyp som till exempel std::list. Man får, men behöver inte, dela upp programmet i flera filer.
Övriga krav på lösningen:
Programmet måste kunna hantera minst en miljon signaler,
som var och en kan ha observerats upp till tio gånger.
Det finns inga krav på felhantering.
| 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. |
Med stora filer (som testfil-1M.txt) blir en lösning med länkade listor eller osorterade arrayer mycket långsam.
Gör en ny version av programmet i uppgift 1, men med snabbare datastrukturer. Vi vill ha en enorm förbättring av prestanda.
Datastrukturerna som används ska vara skapade specifikt för detta ändamål, så använd inte någon generell datatyp. Man får, men behöver inte, dela upp programmet i flera filer.
Övriga krav på lösningen:
Programmet måste kunna hantera godtyckligt många signaler och observationer,
bara med de begränsningar som följer av minnesstorleken.
Det finns inga krav på felhantering.
| 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 trädtypen GenericTree). 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.
| 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. |