Resultat: Senior

Lösning:

Rätt svar är 3 dagar

(6,3,3,0,4)->(0,9,0,7,0)->(9,0,7,0,0)->(0,16,0,0,0)

Koppling till datavetenskap

Detta problem handlar om svärm-intelligens. Tanken med denna typ av algoritmer är att man kan lösa problem med väldigt enkla mekanismer även om antalet inblandade är stort. Exempelvis har myror utvecklat beteenden som baseras på enkla regler oberoende av alla andra myror. Om det är många myror så kan de fortfarande utföra komplicerade uppgifter såsom att bygga myrstackar, hitta bästa vägen eller dela på löv. 

I detta problem har vi ett antal ekorrar som också beter sig enligt enkla regler. Men det visar sig att dessa enkla regler är för själviska för att deras kollektiva beteende ska bli särskilt smart. Alla vill bo så rymligt som möjligt men slutar ändå i samma hål. Sensmoralen är att det oftast är bättre att samarbeta än att vara självisk, även när det handlar om algoritmer.

Lösning:

Rätt svar är 3 st tröjnummer

Förklaring

Tröjnummer 14, 19 och 23 förekommer i bägge lagen.

Koppling till datavetenskap

Sökning i en sorterad lista kan gå mycket snabbare än i en osorterad. Denna uppgift visar att det går mycket snabbare att söka efter ett specifikt tröjnummer i lag 1 jämfört med lag 2. 

Om vi antar att det tar 1 sekund att jämföra två nummer kommer det att ta ca 45 sekunder att lösa denna uppgift genom att för varje tröjnummer i lag 2 söka upp motsvarande nummer i lag 1. Om man istället för varje tröjnummer i lag 1 söker upp motsvarande tröjnummer i lag 2 kommer det att ta ca 112 sekunder.

Ju längre listor man arbetar med, desto större kommer skillnaden i söktider att bli. Om listan skulle innehålla 1000 nummer skulle det gå 50 gånger snabbare för en människa - eller för en dator - att söka i en sorterad lista jämfört med en osorterad. 

Sökning i listor är ett centralt problem i datavetenskap. Efter du har löst denna uppgift har du säkert utarbetat en egen strategi för att söka igenom listan med tröjnummer för lag 1. Sannolikt är den strategin en befintlig algoritm för sökning i sorterade listor - exempelvis binärsökning, hoppsökning eller interpolation. 

Ordnade listor är ett vanligt verktyg vid datalogiskt tänkande. Det är ofta en bra strategi att sortera en osorterad lista innan man söker i den, särskilt om man ska söka igenom den flera gånger.

Om listan över tröjnummer för lag 2 sorteras så att även den är sorterad efter tröjnummer innan vi påbörjar sökningen så kommer vi mycket snabbare att se att det finns tre gemensamma tröjnummer. 

Lag 1: 1, 4, 5, 7, 9, 14, 15, 17, 18, 19, 21, 22, 23, 25, 26

Lag 2: 2, 3, 6, 8, 11, 12, 13, 14, 16, 19, 23, 24, 27, 28, 29

Lösning:

är rätt svar. För 2 par av ögon fungerar programmet som i exemplet. Sedan dras snöret upp genom ögat, men det byter inte sida. Därefter dras snöret ned genom ögat en gång på vardera sig och sedan byts sidan. Programmet fortsätter sedan som i exemplet.

Koppling till datavetenskap

Detta enkla programmeringsspråk har flera delar som finns i vanliga programmeringsspråk. Det har kommandon för loopar och det har inbyggda variabler som pilarnas positioner.

Lösning:

Rätt svar är

Ta det vänstra pappret. Det beskriver att vänstra delen av golvet ska målas med en halvcirkel med den runda sidan åt vänster. För högra halvan av golvet är instruktionerna återigen att använda samma ark två gånger, men delen som måste målas måste vara minst 1 meter lång. Lägg märke till att orienteringen av de två 1:orna är motsatta. Detta indikerar att arken måste vändas rätt varje gång.

Tänk på att de två runda sidorna på ark 1 rör vid varandra, detta betyder att de runda sidorna av halvcirklarna alltid kommer att röra vid varandra.

Koppling till datavetenskap

Självrefererande instruktioner som den här kallas för rekursiva. Rekursion är ett viktigt begrepp i datavetenskap. Rekursiva lösningar är vanligtvis kortare och mer kompakta än andra lösningar, men ibland lite svårare att förstå. Rekursiva mönster hittas ofta i naturen. Villkoren för att sluta, som de i exemplet, är viktiga för att undvika oändliga loopar.

Lösning:

Rätt svar är franska flaggan:

Varje rad behöver lika många par som antalet gånger färgen byts på den raden. Om hela raden har samma färg så behövs bara ett par. Till exempel Tysklands flagga består bara av rader som har en färg. Tjeckiens flagga byter färg exakt en gång per rad, från blå till vit eller från blå till röd. Varje rad behöver alltså exakt två par. Frankrikes flagga byter alltid färg två gånger per rad, från blå till vit till röd. Det behövs alltså alltid exakt tre par per rad. Den svenska flaggan är lite mer komplicerad för den byter färg två gånger för de flesta rader utom raderna i mitten som är enfärgade. Alltså behövs det fler par totalt sett jämfört med den tyska flaggan men färre par jämfört med den franska flaggan.

För att jämföra de svenska och tjeckiska flaggorna behöver vi avgöra det genomsnittliga antalet färgbyten. För den tjeckiska är det alltid exakt två. Om den svenska flaggan hade haft lika många enfärgade som trefärgade rader hade den också behövt två par i genomsnitt per rad. Då den enfärgade delen av svenska flaggan är betydligt smalare än halva höjden så kommer det alltså behövas mer än två par i genomsnitt per rad. Den svenska flaggan kräver alltså mer utrymme än den tjeckiska.

Sammanfattningsvis är ordningen, från minsta till största, Tyskland, Tjeckien, Sverige och Frankrike.

Koppling till datavetenskap

Komprimering av data är en viktig utmaning inom datavetenskapen för att spara på datorns lagringsutrymme, minska nätverkstrafiken och snabba upp överföringen av information mellan datorer. Bra algoritmer för datakompression kan alltså spara mycket pengar vilket gör det viktigt att hitta bättre och mer effektiva algoritmer för att komprimera bilder, ljud och video då de vanligtvis behöver stort utrymme.

Den typen av kompression som används i den här uppgiften kallas för skurlängdskodning (Run Length Encoding) – för en introduktion på engelska se följande video: https://www.youtube.com/watch?v=ypdNscvym_E

Lösning:

Rätt svar är

 Enligt dessa regler är följande möjligt:

För att utesluta

måste vi göra några observationer. Först, om vi börjar med en triangel eller en cirkel så kan vi aldrig få några kvadrater. Alltså måste vi börja med en kvadrat. Om vi börjar med en kvadrat så får vi följande sekvens och ytterligare byten leder till en sekvens som är för lång.

För att utesluta

kan vi se att det aldrig går att få två kvadrater efter varandra då det inte finns någon regel som direkt ger flera kvadrater och ingen regel tar bort någon form så det kommer alltid finnas andra former mellan varje par av kvadrater.

För att utesluta

kan vi på ungefär samma sett se att det aldrig går att få cirklar efter varandra. Det enda sättet vore att byta ut två trianglar men då finns det alltid en kvadrat emellan cirklarna. 

Koppling till Datavetenskap

Reglerna kallas vanligtvis omskrivningsregler och används bland annat för att beskriva grammatiken hos kontextfria språk, eller andra grammatiker. Dessa grammatiker kan beskriva saker som

• naturliga fenomen, t.ex. hur plantor växer
• naturliga språk, t.ex. hur man skapar meningar
• formella språk, t.ex. programmeringsspråk.

Uppgiften handlar om att avgöra om en mening kan härledas (eller deriveras) från olika omskrivningsregler. Detta är samma sak som datorn behöver göra för att tolka (eller parsa) ett program från något vi människor kan förstå till något som datorn kan förstå.

Lösning:

En korrekt tilldelning är följande:

Max: [192.168.1.20]
Mia: [192.168.1.21]
Pia: [192.168.1.22]
Tim: [192.168.1.30]
Leo: [192.168.1.32]

Koppling till datavetenskap

Att få datorer att prata med varandra har alltid varit en utmaning. Förutom mer tekniska frågor som bandbredd och pålitlighet är det en mer diplomatisk fråga att införa adresser. I ett datornätverk måste varje nod ha en egen unik adress. Det behövs någon som kan bestämma över andra!

Den internationella adresseringssystemets historia är intressant: husnummer, radiofrekvenser, telefonnummer, postnummer, registreringsskyltar och nu Internet.

Dagens vanligaste kommunikationsprotokoll, Internet Protocol version 4 (IPv4) från september 1981, har som du sett i den här uppgiften, maximalt 256 x 256 x 256 x 256 = 4.294.967.296 IP-adresser. Är det tillräckligt? Det finns betydligt fler människor än tillgängliga IP-adresser och antalet enheter per person ökar hela tiden. Vad händer när IPv4-adresserna tar slut?

Inget! Som tur är finns det redan ett nytt protokoll IPv6 som har betydligt fler möjliga adresser. Det har ungefär 34.000.000.000.000.000.000.000.000.000.000.000.000.000 adresser, som ser ut så här 30h1:0db8:0000:08d3:0gc0:8a2e:0070:7344. Hur länge kommer de räcka? Tänk om det blir ett genombrott för nano-robotar?

Lösning:

Bea måste ta 1 tändsticka första omgången så att det blir 12 tändstickor kvar. För varje följande drag så tar Bea bort så många tändstickor så att det blir en multipel av 4 kvar (alltså först 8 och sedan 4). Om hon följer strategin så kommer hennes vän till slut att få 4 tändstickor kvar och kan därmed inte vinna spelet.

Koppling till datavetenskap

Detta är ett klassiskt strategispel för två spelare som turas om att göra drag. Efter varje drag analyserar datorn sina möjliga drag och beräknar det drag som har störst chans att leda till en vinst. Därefter utför datorn sitt drag och väntar på motståndarens drag.

För det här spelet finns det en exakt algoritm. För andra spel finns det ingen exakt algoritm, istället använder man då heuristiker som ofta leder till bra drag. 1997 vann datorn för första gången över en världsmästare i schack. Datorn gjorde det genom att använda den här typen av heuristiker.

Lösning:

Rätt svar är BC16

Förklaring

Svaret kan fås genom att se på tabellen och konvertera kix-koden till motsvarande bokstäver. Bokstäverna som används i koden är markerade i tabellen nedan:

Koppling till datavetenskap

Kix-koderna - som faktiskt används på riktigt i vissa länders postsystem - är ett exempel på streckkoder som kan avläsas av en dator. Detta är användbart för att automatisera urval och sortering av post.

I detta fall är informationen uppdelad i en övre och en nedre del, vilket är vanligt förekommande metod.

Lösning:

Rätt svar är 3 st

Förklaring

När två kort kombineras är regeln följande: för en svart ruta på det resulterande kortet krävs att motsvarande ruta på de kort som kombineras har samma färg (svart eller vit) - i annat fall blir rutan vit.

När de två korten i frågan kombineras blir det resultatet detta:

Koppling till datavetenskap

Detta handlar om boolska kretsar som är en matematisk beräkningsmodell. Om vi antar att en vit ruta tolkas som 0 och en svart ruta som 1 så kan operationen att kombinera två kort beskrivas enligt följande tabell:

1 ⇔ 1 → 1

0 ⇔ 1 → 0

1 ⇔ 0 → 0

0 ⇔ 0 → 1

Denna tabell går att komma fram till genom utifrån det givna exemplet. 

Lösning:

Rätt svar

Endast fyra instruktioner kan repeteras. Detta gör att den enda tänkbara lösningen är att låta sköldpaddan följa en sprialformad bana.

Det finns fyra alternativa sekvenser med instruktioner som kommer flytta Cassy över hela åkern i en spriralformad bana:

• framåt R rutor, sväng vänster, framåt R rutor, sväng vänster
• framåt R rutor, sväng höger, framåt R rutor, sväng höger
• sväng vänster, framåt R rutor, sväng vänster, framåt R rutor
• sväng höger, framåt R rutor, sväng höger, framåt R rutor

Detta är datavetenskap

Denna uppgift ber dig att skriva ett program. Ett program är en sekvens av instruktioner. En dator utför dessa instruktioner en i taget. Om programmet är korrekt, gör datorn exakt vad du vill. Om inte, gör datorn exakt vad du programmerat - men inte vad du vill. Datorn kan inte upptäcka dina programmeringsmisstag.

I den här uppgiften kan du komponera ett instruktionsblock bestående av fyra instruktioner. Upprepad exekvering av en instruktionsblock kallas slinga; Observera att slingan i denna uppgift ger en slingräknare . Alla användbara pogrammingsspråk erbjuder loopar (slingor) - och mer, som selektion (exekvering av instruktioner beroende på vissa villkor) eller subrutiner (instruktioner som består av andra instruktioner) etc.

Lösning:

Endast påståendet att en omgång väger exakt 100kg stämmer.

Den första omgången består av de tre första säckarna 40+20+34=94kg.

För den andra omgången så lastas den första säcken (55kg) in i hissen. Nästa säck (50kg) är för tung och flyttas till andra sidan av korridoren. Nästa säck (23kg) lastas in i hissen, eftersom den totala vikten är 55+23=78kg så väntar hissen på mer last. Nästa säck (45kg) är för tunga och flyttas till andra sidan korridoren framför den säcken som redan står där. Samma gäller för nästa säck (30kg). Nästa säck (10kg) får plats i hissen som nu går då den har en total vikt på 55+23+10=88kg.

De tre sista säckarna från den ursprungliga raden (25+30+15=70kg) ställs in i hissen. Den tredje omgången är komplett när den första säcken från andra sidan korridoren (30kg) lastas in så att den totala vikten blir exakt 100kg.

Nu finns bara två säckar kvar, 45+50=95kg, de lastas in och blir den fjärde och sista omgången.

Koppling till datavetenskap

Säckarna i uppgiften bildar vad man kallar för en stack. En stack är en vanligt förekommande datastruktur där den sak som läggs till sist tas ut först (sist in, först ut). Exempel på stackar är en stapel med tallrikar i matsalen, man tar alltid den översta tallriken i stapeln. Ett annat exempel är en glasstrut där första kulan hamnar längst ned i struten och varje ny kul läggs ovanpå. Ett tredje exempel är när du surfar på webben, varje sida du besöker läggs på en stack och när du trycker på "bakåt"-knappen kommer du till den översta sidan i stacken som sedan tas bort från den.

En stack är inte alltid rätt. Om du kommer till ett sjukhus vill du inte att de alltid tar emot den patient som kom dit senast. Då använder man istället en kö. En kö är annan vanligt förekommande datastruktur där det som läggs in först kommer ut först (först in, först ut).

Lösning:

Rätt svar är

Låt oss ta en typisk pixel, se nedan. Om vi sorterar pixlarna efter deras intensitet så kommer det vara två vita till höger, tre svarta till vänster och fyra grå i mitten. Medianen är alltså grå. Vidare, om en svart pixel är omsluten av svarta pixlar så kommer den fortsätta vara svart. Samma sak gäller för vita pixlar.

Koppling till datavetenskap

Bildbehandling är ett viktigt område för att förbättra bilder genom att till exempel minska bruset. De flesta användare vet inte hur algoritmerna som bildbehandlingsprogram använder fungerar. Det är mycket roligare att förstå vad som händer. Medianfilter är en sådan algoritm som dessutom är enkel att förklara hur den fungerar. Uppgiften introducerar även det statistiska begreppet median.

Lösning:

Rätt svar är 29

Förklaring

Antalet handskakningar är längden av ena ledet plus längden av det andra ledet minus ett.

Anta att det bara är en spelare per lag. Efter en sekund är alla handskakningar avklarade. 

Anta att det är två spelare per lag. Under den första sekunden skakar de första spelarna i varje lag hand. Under den andra sekunden skakar den första spelaren i varje lag hand med spelare två i det andra laget, och under den tredje sekunden skakar spelare två i bägge lagen hand med varandra. Alltså totalt 3 sekunder.

Med 15 spelare i varje lag blir det totalt 15 + 15 - 1 sekunder av handskakningar.

Koppling till datavetenskap

Detta kan ses som ett exempel på samtidighet i form av s.k. pipelining. Pipelining är ett väldigt effektivt sätt att få flera datorer att arbeta tillsammans för att lösa problem snabbt och effektivt. Det kan dock ta tid att uppnå den effektiviteten, på samma sätt som att den sista spelaren i varje led får vänta ett tag innan de ens får börja skaka hand med motståndarlaget. 

Analys av hur lång en algoritm tar på sig är en sofistikerad del av datavetenskap som kallas tidskomplexitetsanalys. I denna uppgift vet vi att lagens storlek alltid är 15 och kan därmed exakt fastställa den totala tiden till 29 sekunder. En tidskomplexitetsanalys kräver däremot att man anger ett svar som inte är bundet till en viss storlek på lagen. Man skulle då komma fram till att handskakningar alltid tar 2N-1 sekunder för alla lagstorlekar N där N är ett heltal som är 1 eller större.

Lösning:

Rätt svar är: A, B och C.

Förklaring

Spelet slutar aldrig om Emil börjar med tre kulor där den nedersta kulan är blå. 

Om han börjar spelet med en röd kula i botten kommer spelet däremot att sluta efter endast ett klick på KÖR-knappen.

Låt oss beskriva innehållet i röret som en sekvens av bokstäver där R står för en röd kula och B för en blå kula. Den första bokstaven indikerar den översta kulan. Om vi skissar upp de fyra olika fall som finns med en blå kula i botten ser vi att vi efter maximalt 5 klick på KÖR-knappen kommer till rörinnehållet RBRRBR:

BBB → RBRB → RBRRB → RBRRBR;

BRB → RBRB → RBRRB → RBRRBR;

RBB → RBRR → BRB → RBRB → RBRRB → RBRRBR;

RRB → RBRR → BRB → RBRB → RBRRB → RBRRBR.

Spelet hamnar därefter i en cykel som aldrig tar slut, eftersom innehållet RBRRBR kommer att återkomma efter fyra tryck på KÖR-knappen:

RBRRBR → BRBRR → BBRB → RBRBB → RBRRBR

Koppling till datavetenskap

Spelet är ett exempel på ett produktionssystem, en beräkningsmodell som bygger på omskrivning av strängar. Det är utvecklat av Emil Leon Post på 20-talet, men som inte publicerades förrän 1943. Emil Leon Post (1897-1954) var en polskfödd amerikansk matematiker och logiker som utvidgade vår kunskap om beräkningsteori.

Omskrivningsmodeller omfattar en stor mängd olika system som beskriver hur en sträng får skrivas om till en annan. Omskrivningarna är de möjliga operationerna man kan göra på objekten (strängarna).

Teoretisk datavetenskap kallar idag dessa system för kontextfria gramatiker. Till exempel kan multiplikation och addition beskrivas som en enkel kontextfri gramatik med några enkla regler. Ett annat berömt och användbart exempel är att använda kontextfria gramatiker för att beskriva programmeringsspråk på ett uttömmande och fullständigt sätt.