Datortentamen i TDP007 torsdag 11 juni 2015 08:00-12:00 ------------------------------------------------------- Tentan startar kl. 08:00 och pågår till 12:00. Ni kommer att få köra på begränsade datortentakonton. Instruktioner för att logga in på dessa lämnas i salen. Alla filer som ni behöver för att lösa uppgifterna finns i hemkatalogen när ni har loggat in. Där finns också en PDF-version av en tidig utgåva av kursboken som ni gärna får använda er av. Öppna den med kommandot okular eller xpdf. Svar på frågor skrivs i vanliga textfiler och programkod skrivs i rb-filer. En fil per huvuduppgift ska produceras, totalt alltså sex filer. Ingen särskild inlämning behöver göras. När man är färdig loggar man ut och lämnar salen. Tentan består av sex uppgifter, några indelade i deluppgifter, som totalt kan ge 32 poäng. För godkänt krävs 50%, dvs minst 16 poäng. För betyg 4 krävs minst 21 poäng och för 5 minst 26 poäng. Inga poäng från duggor kan räknas tillgodo, utan tentan bedöms helt på egen hand. Om man redan har fått ett betyg genom duggan eller tidigare tentor kan det aldrig sänkas, bara höjas. Uppgift 1: Teorifrågor (5p) --------------------------- a) Om man läser in ett XML-dokument med hjälp av strömparsning (SAX), vad gör då lyssnarklassen? Beskriv kortfattat vad lyssnarklassen gör och vilken roll dess standardmetoder har. (2p) b) Vad är ett domänspecifikt språk? Vad kan man hoppas uppnå genom att skapa ett sådant? (2p) c) Skriv ett reguljärt uttryck som matchar alla strängar i den vänstra kolumnen, men inga strängar i den högra kolumnen. (1p) Positiva Negativa -------- -------- 'aa' 'aax' 'baaa' 'ba' 'abaa' 'abaada' 'xyz aaa' Uppgift 2: Behandling av data i textfiler (5p) ---------------------------------------------- I filerna kor.txt och befolkning.txt finns tabeller som visar hur många mjölkkor respektive personer som bodde i kommunerna i Östergötland under tre olika år. Din uppgift är att läsa in dessa tabeller på valfritt sätt och därefter beräkna hur många kor det fanns per 100 invånare i alla kommuner under dessa tre år. Resultatet ska skrivas ut i en tabell där sifferkolumnerna är snyggt högerjusterade som i exemplet nedan: >> cow_quota("kor.txt", "befolkning.txt") Kommun 1985 1995 2005 0509 Ödeshög 23.02 13.78 9.83 0512 Ydre 61.76 45.95 65.78 0513 Kinda 44.74 31.09 30.58 ... Som en bonus kommer vi äntligen få svar på vilken som är den kotätaste kommunen i Östergötland. Uppgift 3: XML (6p) ------------------- I filen tudor.xml finns ett släktträd för några av personerna i släkten Tudor, som under främst 1500-talet satt på den engelska tronen. Den information som finns lagrad utgörs av personernas namn, när de levde, under vilka år de regerade vilket land, samt vilka barn de hade. Alla personer i släkten finns inte med, utan enbart de viktigaste. Formatet framgår av en inkluderad DTD. Din uppgift är att skriva olika funktioner för att kunna läsa in och hantera informationen i filen. Om du vill göra en SAX-lösning hittar du ett exempel att utgå från i filen sax_example.rb och om du vill göra en DOM-lösning hittar du lite information om metoderna i klassen REXML::Element samt några exempel på XPath-uttryck i filen rexml.txt. a) (3p) Skriv en funktion find_regents som läser in släktträdet och i kronologisk ordning skriver regenterna för ett viss land. Så här ska det se ut: >> find_regents("tudor.xml", "England") Henry VII of England (1485-1509) Henry VII of England (1509-1547) Edward IV of England (1547-1553) Mary I of England (1553-1558) Elizabeth I of England (1558-1603) James I of England (1603-1625) b) (3p) Skriv en funktion regency som läser in släktträdet och skriver ut alla kungar och drottningar, sorterade efter hur länge de satt på tronen. Personen med längst regeringstid ska skrivas ut först. För personer som har haft flera uppdrag på tronen räknas dessa som olika, så man behöver inte summera ihop dem. Födelseåret för respektive person ska också skrivas ut. Så här ska det se ut: >> regency("tudor.xml") Elizabeth I of England (b. 1533) 45 years Henry VIII of England (b. 1491) 38 years James VI of Scotland (b. 1566) 36 years James V of Scotland (b. 1512) 29 years Mary, Queen of Scots (b. 1542) 25 years ... Uppgift 4: DSL (5p) ------------------- Många system lagrar information i relationsdatabaser som man typiskt ställer frågor till med språket SQL. Ett alternativt sätt att lagra enklare typer av information är så kallade 'triple stores' eller 'RDF stores' (efter standarden Resource Description Framework). Grundtanken med 'triple stores' är ganska enkel. Man lagrar information i form av egenskaper som knyter samman två olika objekt. Om jag vill uttrycka att Stockholm är en stad i Sverige och att Stockholm dessutom är huvudstad kan jag uttrycka det så här: city 'Stockholm', 'Sweden' capital 'Stockholm', 'Sweden' På den första raden finns egenskapen 'city' som knyter samman en stad och ett land. På den andra raden finns egenskapen 'capital' som knyter samman en huvudstad med ett land. Det är bara information som kan tredelas på detta sätt som kan lagras i ett triple store, men begränsningen gör att man kan optimera dem ganska kraftigt. I denna uppgift ska du skapa ett mycket enkelt 'triple store' som kan läsa in information på formatet ovan från en textfil. I filen triples.rb finns ovanstående exempel med några ytterligare egenskaper. Du ska betrakta innehållet i textfilen som ett litet domänspecifikt språk och behandla det därefter. Tanken är att din inläsningsrutin ska köra filen, och att den ska kunna hantera vilka egenskapsnamn som helst, inte bara de som finns i just denna fil. Ditt 'triple store' ska även kunna svara på frågor från användaren. Det ska fungera så här: >> ts = TripleStore.load('triples.rb') # >> ts.find('capital','Stockholm','Sweden') [["Stockholm", "Sweden"]] >> ts.find('population','*','Sweden') [[9600000, "Sweden"]] >> ts.find('city','*','France') [["Nice", "France"], ["Paris", "France"], ["Lyon", "France"]] Första anropet till find kollar om Stockholm verkligen är huvudstad i Sverige. Eftersom det är sant får vi tillbaka en array med ett par i. (Om svaret hade varit falskt hade vi fått en tom array.) Nästa anrop har '*' som argument. Det innebär att find ska matcha alla möjliga värden som andra argument, även om det i just detta fall bara fanns ett svar. Tredje anropet visar dock ett exempel där det finns fler svar. Specialargumentet '*' ska kunna skickas in som andra eller tredje argument till find. Uppgift 5: Constraint-nätverk (5p) ---------------------------------- I filen constraint_networks.rb finns kod för att bygga restriktionsnät som vi diskuterade i samband med seminarie 4. Vi tänker oss att du har löst seminarieuppgifterna och kan skapa ett nät för att omvandla mellan Celsius och Fahrenheit. Användningen av denna omvandlare kunde se ut ungefär så här: irb(main):176:0> c,f=create_temperature_network [#, #] irb(main):177:0> c.user_assign 0 "ok" irb(main):178:0> f.value 32 Antag att vi vill använda intervall istället för heltal. Vad blir 18-20 grader Celsius i Fahrenheit? Då vill vi kunna göra så här: irb(main):179:0> c.user_assign 18..20 "ok" irb(main):180:0> f.value 64..68 irb(main):181:0> Vad behöver göras för att uppnå detta? Du behöver inte implementera temperaturomvandlingen igen, utan skriv bara kod som gör att de constraints som finns i filen kan hantera även intervall. När vi skriver 18..20 avses alltså en instans av klassen Range. Uppgift 6: Parsning (6p) ------------------------ I den här uppgiften ska vi konstruera ett litet språk för att rita mycket enkel ASCII-grafik. Varje "program" i språket måste börja med att man anger hur stor yta man ska rita på, t.ex.: init 10 10 Detta gör att vi skapar ett rutnät med 10 x 10 tecken (första talet är bredden och andra talet är höjden). Vi tänker oss att vi har en "penna" som kan rita ett tecken i varje ruta. När vi precis har skapat rutnätet svävar pennan ovanför position (0, 0) vilket motsvarar övre vänstra hörnet av rutnätet. Vi kan "sänka" pennan med kommandot: down W Detta ritar ett "W" på den position som är under pennan. Om vi därefter gör en förflyttning kommer pennan att fortsätta rita i de rutor vi kommer till. Vi kan förflytta oss i fyra olika riktningar, motsvarande väderstrecken. Exempel: e 5 s 2 w 2 n 1 Ovanstående kommandon flyttar pennan österut (höger) fem steg, därefter söderut (nedåt) två steg, o.s.v. Om pennan är nedsänkt ritas det tecken vi har angivit, annars händer inget annat än att vi förflyttar oss. Vi kan lyfta pennan med kommandot: up Uppgiften går ut på att implementera en parser för detta lilla språk med utgångspunkt i parsern i filen rdparse.rb. Tanken är att parsern bygger upp en datastruktur som motsvarar ritningen, och när parsningen är klar ska denna ritas ut. Exempel: >> dp = DrawParser.new >> dp.draw("init 10 10 down # e3s3w3n3 up s4 down * e3s3w3n3") ------------ |#### | |# # | |# # | |#### | |**** | |* * | |* * | |**** | | | | | ------------ Ett fullständigt program börjar alltid med init-kommandot och hela programmet är på endast en rad. Som framgår av exemplet behöver man inte använda mellanslag mellan kommandon och argument om det inte är nödvändigt för tolkningen. De yttre strecken i exemplet hör inte till själva "ritningen" utan är bara en ram för att vi lättare ska se vad vi ritat. Definiera klassen DrawParser som, med hjälp av rdparse.rb, kan tolka vårt enkla rit-språk och producera ASCII-grafik enligt ovanstående exempel.