Kategoriarkiv: 2014

Texter från 2014

2014, Blogg

Dörrkodsproblemet

6 maj, 2014 Joar Jensén Lämna en kommentar

En skrämmande tanke

Föreställ dig följande scenario: Du är på väg till århundradets fest som förstås ordnas i Majstranden. Då du sitter på bussen märker du att du har glömt telefonen hemma, men du låter inte en sådan liten motgång sänka humöret. När du äntligen anländer till Majstranden och skall slå in dörrkoden märker du att du inte kommer ihåg den! ”Inget problem”, tänker du, för någon måste ju snart komma ut och så kan du slinka in samtidigt. Efter att ingen setts till på en kvart fattar du plötsligt att alla andra redan måste vara på festen (det är ju århundradets fest vi talar om), så det är klart att ingen är på väg ut på länge!

”Ingen orsak att panikera”, tänker du, ”detta problem går nog att lösa”. Du samlar ihop allt vad du vet om problemet: koden är fyra siffror lång (för alla koder är ju det), och från manicken du slår in den på ser du att den kan bestå av siffror från 0 till 9. Du beräknar snabbt att det finns totalt $10^4 = 10000$ möjliga koder, så ifall du prövar dem alla, måste dörren öppnas förr eller senare. För inmatandet av alla koder måste du då slå in $4 \cdot 10000 = 40000$ siffror.

Dörrkod

Hmm…1234 kanske?

Efter att du funderat på problemet en stund till, så kommer ~~någon och öppnar dörren~~ du ihåg att någon sagt åt dig att dörrkodsläsare brukar fungera lite konstigt. De kräver nämligen inte att man håller en paus efter att man slagit in de fyra siffrorna förrän den kollar ifall koden är korrekt. För att dörren skall öppnas räcker det att man i något skede slår in de fyra korrekta siffrorna i rad. Det har alltså ingen skillnad fast man matar in felaktiga siffror i början så länge den korrekta koden slås in i något skede. Ifall du slår in fem siffror har du alltså matat in två olika fyrsiffriga koder! Den första består av siffrorna 1-4, och den andra av siffrorna 2-5.

Du fattar direkt att för att alla koder skall finnas någonstans i den sekvens du slår in, måste du knappast mata in 40000 siffror, eftersom koderna överlappar varandra. Vilken strategi skulle det löna sig att använda för att få inslaget alla koder med så få siffror som möjligt? Naturligtvis lönar det sig att undvika upprepning av koder, alltså vill du i varje skede slå in en sådan siffra som skapar en fyrsiffrig kod som du inte matat in tidigare.

Simplifikation av problemet

För att simplifiera problemet rycker vi oss för en stund bort från vårat scenario och funderar i stället på en dörrkodsläsare som endast har siffrorna 0 och 1 och kräver en tvåsiffrig kod. Det finns alltså $2^2 = 4$ olika koder, nämligen koderna $00$ , $01$ , $10$ och $11$ . I vilken ordning skulle man slå in siffror i detta fall för att med så liten möda som möjligt få upp dörren? En möjlighet är att slå in sekvensen $11001$ . Den innehåller alla koder:

11001
11001
11001
11001

Är det möjligt att hitta en kortare sekvens som innehåller alla koder? Genom att analysera listan ovan ser vi fort att det inte kan gå. För att visa detta, antag att $L$ är en sekvens av siffror 0 och 1. Ifall den innehåller alla fyra olika koder av längd två, måste var och en av koderna starta vid olikt index i sekvensen. Därmed kan den sista koden starta som tidigast vid index 4, och eftersom den är av längden två, måste sekvensen $L$ vara minst fem siffror lång. Detta betyder att är sekvensen $11001$ den kortaste möjliga lösningen. Dock finns det andra lösningar av längden fem också, t.ex. $00110$ .

Binär dörrkod

Dörrkodsläsare, modell datalog (Patent pending)

Hur skapades då sekvensen $11001$ ? En möjlig strategi är följande: börja med den största koden (i detta fall $11$ ), och välj sedan den lägsta möjliga siffran som skapar en ny kod till sekvensen, dvs. en kod som inte från tidigare finns i sekvensen. Ifall detta alltid lyckas, kommer vi att få till stånd en möjligtvis kort sekvens, eftersom den inte upprepar några koder.

Ifall vi använder denna strategi i vårt ursprungliga scenario, kommer vi att få till stånd en sekvens av längden $10^4 + (4-1) = 10003$ (börjandes med siffrorna $9999$ ) som innehåller alla koder, en klar förbättring till att vara tvungen att mata in 40000 siffror!

Det allmänna problemet

Den stora frågan är följande: Kan vi för alla kodlängder $k$ och sifferantal (dvs. baser) $b$ alltid skapa en sekvens som inte upprepar någon kod två gånger? Svaret är kanske aningen överraskande ja. Beviset i sin helhet, till vilket det finns en länk i slutet av artikeln, är lite för invecklat för att tas upp i denna artikel, men det bygger på följande observation: Antag för enkelhetens skull att vi vill skapa koder av längd 4 som består av siffrorna 0, 1, 2 och 3. Ifall vi har någon kod, t.ex. $0233$ , kan efter denna kod i sekvensen följa endast en kod som börjar med siffrorna $233$ och slutar med en av siffrorna 0, 1, 2 eller 3. Detta gör att sekvensen blir mycket symmetrisk, eftersom det efter någon av koderna $0233, 1233, 2233, 3233$ endast kan följa någon av koderna $2330, 2331, 2332, 2333$ .

Tillämpning till scenariot

Smart som du är kom du på denna lösning till problemet på säg…22 minuter. Du började sedan knacka in siffrorna, och eftersom du har ett utomordentligt minne kunde du hålla reda på vilka koder du redan slagit in. Efter en dryg timme lyckades du därmed få upp dörren, och kvällen var räddad. Snäll som du är skapade du åt dina vänner en textfil med den kod som behövs för att öppna vilken som helst dörr med fyrsiffrig kod i bas 10!

Till sist

Ett stort tack till Lasse och Jeremias för hjälpen med detta problem!

Den som är intresserad att läsa mera om dörrkodsproblemet kan ta en titt på följande text (på engelska):

The door code problem

Ifall du vill veta den sekvens (av längden 10003) som du säkert kommer in till Majstranden med, kan du skriva ut följande textfil:

Bas 10, kodlängd 4

2014, Blogg

Regnbågen av kön

16 april, 2014 Spektraklet Lämna en kommentar

Det har varit intressant att följa hur de homosexuellas rättigheter har utvecklats i västvärlden under de senaste åren. Det finns ännu mycket kvar att utveckla; men i stort sett har det blivit lika självförstörande att identifiera sig som homofob som det var att identifiera sig som homosexuell för inte så länge sedan, ett klart tecken på att majoriteten har accepterat homosexuella människor. Det är mycket överväldigande att vittna om hur en förtryckt minoritet har ryckt framåt och blivit en godkänd del av samhället. Det är inte utan orsak som kampen för de homosexuellas rätter kallas vår tids medborgarrättsrörelse.

Däremot finns det en del av HBT-samhället (homosexuella, bisexuella och transpersoner) som först nu har börjat erkännas och synas, nämligen transpersoner. Deras erkännande är ett brådskande ärende, att vara osynlig har nämligen ett högt pris. I USA är det 41% sannolikare att en transperson försöker begå självmord jämfört med någon från den allmänna befolkningen. Detta trots att USA är i främsta stridslinjen då det gäller rättigheter för och erkännande av HBT-minoriteter. I andra länder är situationen troligtvis även värre.

I februari gav Facebook ett viktigt bidrag till kampen för de transpersonernas rättigheter genom att börja erbjuda 58 olika könsval och tre pronomensval (”her”, ”his”, ”their”) till sina engelskspråkiga användare i USA. Könsvalen utarbetades i samarbete med GLAAD; en icke-statlig organisation som stödjar HBT-människornas omsorgsfulla och rättvisa presentering i olika medier. Man kan dra nytta av dessa könsval även i Finland om man väljer English (US) som språk på Facebook.

Facebooks åtgärd är särskilt avsevärd med tanke på att så sent som år 2012 klassades ”könsidentitetsstörningar” som psykiska störningar enligt den amerikanska psykiatrins handbok. Som jämförelse så fanns homosexualitet med i samma bok senast år 1974. Å ena sidan visar detta hur pass stämplade transpersoner har varit ända fram till den sista tiden. Å andra sidan väcker en snabb förbättring i transpersonernas ställning hopp om att resten av deras kamp för jämlikhet inte kommer att bli lika krånglig och långsam som den var för den homosexuella minoriteten.

Förutom i den sociala median framskrider transpersoners rättigheter även på andra fronter. I november ifjol blev Tyskland den första europeiska staten som började tillåta föräldrar av barn med både hanliga och honliga könskaraktärer att beteckna X på deras födelseattester. Likaså erkänner Australien och Nepal transpersoner. Fast juridiskt igenkännande är mycket positivt kan man ändå påstå att Facebook genom sin åtgärd lyckades föra fram minoritetens ärenden till det allmänna medvetandet mycket plötsligare och effektivare än någon enstaka stat eller icke-statlig organisation har möjlighet till.

En av de möjliga orsakerna till svårigheterna som olika minoriteter ibland råkar ut för i samhället är en uppfattning om att minoriteternas rättigheter inte angår majoriteten – förutom då det gäller att få begagna sig av minoriteterna. Ändå kan man argumentera att alla tillvinner sig mer frihet då någon minoritet frigörs. Förtryckta minoriteter utpekas med nedsättande anmärkningar och falska skadliga uppfattningar. Dock är majoriteten själv också mycket heterogen och omfattar individer vilkas utseende och uppförande kan likna någon minoritet fast individen inte har någonting med den minoriteten att göra, dvs. genom att påminna om en stämplad minoritet kan man själv bli stämplad. Detta i sin tur pressar individen i fråga att ändra sig – åtminstone ytligt sett – för att passa in i den godtyckligt definierade normen vilket ofta sker på bekostnad ens egna välbefinnande. Ett annat exempel på folk utöver den egentliga minoritetsgruppen som lider av förtryck mot någon minoritet är deras anhöriga. Som ett exempel av detta så är det troligtvis avsevärt mer utmanande att sörja för ett transbarn än ett cis-barn, främst därför att man är tvungen att kämpa mot okunnighet och fördomar i varje skede av barnets liv för att tillförsäkra dess bemötande med värdighet.

Medborgarrättsförbättringar för förtryckta minoriteter medför alltså positiva följder till ett mångfaldigt större antal människor än de som direkt påverkas av dem. Som exempel kan nämnas att gayrättsrörelsens framgång har vidgat även heterosexuella människornas möjligheter att vara sig själva – att klä sig hur man vill och att vara tillgiven med kompisar av samma könet. Det värsta som kan hända om man gör så är att man betraktas som homosexuell vilket nuförtiden är likgiltigt med att vara betraktad som heterosexuell. Detta hände inte självmant utan är en påtaglig fördel av förbättringen av de homosexuellas rättigheter.

Kön är inte någon binär egenskap, men en kontinuerlig skala. Transpersonernas samhälleliga framgång kommer att fortsätta befrielsen av alla människors könsuttryck – för att inte tala om att den sannolikt kommer att förminska antalet självmordsförsök som begås transpersoner. Således finns det fortfarande mycket kvar att uppnå och sträva efter.

Kiilas

Facebooks 58 könsval syns här:

http://abcnews.go.com/blogs/headlines/2014/02/heres-a-list-of-58-gender-options-for-facebook-users/

Källor:

http://time.com/8856/facebooks-gender-labeling-revolution/

http://www.advocate.com/politics/transgender/2014/02/13/facebook-announces-expanded-gender-options-transgender-and-gender

http://www.huffingtonpost.com/2014/02/01/gabourey-sidibe-tranny_n_4708422.html

http://www.rfsl.se/?p=410

http://en.wikipedia.org/wiki/Diagnostic_and_Statistical_Manual_of_Mental_Disorders

2014, Blogg

Ballmer Peak – Kan XKCD ha rätt?

6 april, 2014 Spektraklet 2 kommentarer

Ballmer Peak är ett relativt känt begrepp bland folk som har läst några kurser data, samt vem som helst som känner sådana dataloger som inte förstår att hålla sina skämt till sig själva. Ursprunget till begreppet kan ni hitta i er sångbok på sidan 60, på samma sida som det i min sångbok finns en god jul hälsning samt ordet ”dubbelsup”.

Det handlar alltså om påståendet att det skulle finnas någon koncentration av alkohol i blodomloppet som betydligt skulle öka programeringsförmågan. XKCD påstår att koncentrationen skulle ligga någonstans mellan 1.29 och 1.38 promille, vilket motsvarar ca 7 portioner på 2 timmar för någon som väger 70 kg. Kan det alltså vara möjligt att det lönar sig dricka 7 öl innan man börjar med sina data räkneövningar? Detta låter ju som något värt att undersökas.

Då man designar ett experiment för att testa något sånt här möter man genast på en massa svårigheter. Begreppet ”programming ability” som finns på y-axeln i serien är inte speciellt formellt. Det är inte heller enkelt att få tag på bra samt billiga mätare för att mäta alkoholhalt i blodet. Vidare existerar det ett antal andra variabler som är svåra att kontrollera. Om man ger sju öl åt någon som just och just kan ”Hello World” i java så är det inte hemskt överraskande att den inte får något mer än Hello World gjort efter att ha druckit dem heller. Man kan alltså förvänta sig att resultaten varierar mycket från person till person beroende på dens tidigare programmeringsförmåga. Vi skulle alltså behöva en stor mängd människor att testa med.

Då man översätter stor mängd till Spektrum språk får man 5. En onsdagskväll for vi alltså mot Klubben med 5 ivriga kodare för att se ifall det ligger något bakom det hela. Som uppgifter hade jag valt räkneövningar från årets Tietorakenteet ja Algoritmit kurs (TiRA). TiRA brukar man gå under sin första vårtermin som datalog, dvs. efter ett halvt år av studier. En stor del av deltagarna på kursen tycker om TiRA så mycket att de går den flera år i rad.

En viktig detalj om TiRA uppgifter är att det ofta krävs lite mer än ren programmeringsförmåga för att lösa dem. Man måste tänka på detaljer som hur effektiv koden är. Ett exempel på en lite lättare uppgift som var med i vårt test var att koda en metod som kollar ifall två givna ord är anagram av varandra. För den intresserade läsaren finns det i källorna en artikel som behandlar exempel på kod effektivitet via fibonacci talens uträckning (som också var en av uppgifterna). Jag vill tacka TiRA handledarna och föreläsaren för uppgifterna och testen till uppgifterna.

Efter att alla blåst nollor satt vi igång. Jag hade förberett 6 ronder med 4 uppgifter per rond. Efter första ronden blev det klart att detta var allt för mycket. Det var nämligen endast en av testpersonerna som fick två uppgifter gjorda på tiden 20.14. För resten av ronderna mätte vi därför tid taget per uppgift med en timeout på 20 minuter per rond. Mellan varje rond dracks det uppfriskningar och hölls en paus på 15 minuter.

Nimetön Uppgifter

Resultaten hittas i graferna. Stapeldiagrammet till höger visar mängden lösta uppgifter varje runda, andra grafen visar mätta promillehalten innan varje runda. I äkta statistik anda borde jag nu hitta på metriker vilka skulle få resultaten att bli imponerande. Men först vill jag kommentera på en observation jag gjorde under ronderna. Som ni ser så steg promill nivåerna inte hur högt som helst. Dock skulle man på ljudnivån som testgruppen höll inte ha trott att de flesta var i körskick de första tre ronderna. En placebo-effekt kunde alltså definitivt märkas, inte så mycket på själva problemlösningen som allmänna beteendet.

När det kommer till de egentliga resultaten krävs det mycket fantasi för att kunna säga något. Det enda jag kommer på är att under första rundan (efter en enda öl) löste hela gruppen flest uppgifter, vilket med lite handviftande skulle kunna tyda på att en öl lugnade ner testgruppen tillräkligt för att öka totala mängden uppgifter löst. Men som sagt, mycket handviftande krävs för att dra några statistiskt signifikanta slutsatser.

Därför är det säkert bäst att spela beer pong istället.

Det blev alltså inte så mycket bevisat den kvällen. Tur i oturen så har effekten av alkohol på människokroppen och tankeverksamheten undersökts i bredare skala annanstans. De forskningar som jag hittat undersöker oftast kopplingen mellan kreativt tänkande och alkoholkonsumption. Kreativt tänkande är mycket viktigt i problemlösning och kodning, så eventuella resultat borde gå att applicera på Ballmer Peak också.

Alkohol gör en människa full, detta torde de flesta av er veta. Men en liten mängd alkohol kan i vissa fall förbättra prestandan. Ett exempel av detta är sporter som kräver lugnhet och stadig hand, så som skytte. Dock måste det ju påpekas att det finns många orsaker varför det ändå inte skulle vara en bra idé att ha deltagare dricka alkohol innan de far ut till banan och siktar skjutvapnen mot små tavlor.

När det kommer till kopplingen mellan alkohol och kreativitet så finns det en del resultat som tyder på att en promillehalt på 1.2 -1.4 förbättrar vissa aspekter av kreativt tänkande men försämrar andra. Specifikt så lär lite alkohol göra hjärnan bättre på att kombinera information som den har fått för att skapa lösningar; ni vet de där ”ahaa” upplevelserna som kommer då man minst förväntar sig. Däremot gör alkohol hjärnan sämre på att ta in ny information samt verifiera att lösningarna den hittar på är korrekta. Det har även gjorts undersökningar om effekten av alkohol på kreativ produktivitet bland 34 kända författare, kompositörer samt andra artister under 1900-talet. Resultatet var ofullständiga och delvis motsägelsefulla. I 75% av fallen hade alkohol en negativ inverkan på produktiviteten, speciellt en långvarig alkoholanvändning. En direkt positiv inverkan kunde observeras i 9% och en indirekt i 50%. I undersökningen hittades också tecken på att kreativ produktivitet även ökar alkoholintagningen, vilket gör det hela till ett ”hönan och ägget” problem. Dock rapporteras inte mängder alkohol kvantitativt, vilket gör undersökningen svårare att applicera på Ballmer Peak.

En del undersökningar stöder tanken om att alkohol egentligen fungerar som placebo när det kommer till kreativitet och problemlösning. I en undersökning drack olika testgrupper olika starka vodka tonics utan att veta exakt hur starka var och en fick. En positiv effekt av alkohol för problemlösning kunde observeras i alla testgrupper, vilket föreslår att effekten kan bero på att man förväntar sig bli bättre om man dricker lite. Liknande resultat märktes bland våra testpersoner; att man förväntar sig vara onykter bidrar också en hel del till hur onyktert man beter sig.

Avslutningsvis tänkte jag visa er en alternativ tolkning av balmers peaken. XKCD har tydligen endast valt att använda projektionen av den egentliga 3D kurvan till två dimensioner. Nästa gång röstar jag för att vi kör liknande tester i Mallbolage istället med endast ”Hello world” som uppgift. Tack till alla frivilla som hjälpte till med testandet, hoppas ni hade lika roligt som jag.