« april 2008 | Main | juni 2008 »

maj 26, 2008

Några fler MiniZinc-modeller, t.ex. Smullyans Knights and Knaves-problem

Här är några MiniZinc-modeller som skapats sedan förra anteckningen om sådana modeller.

Samtliga modeller att tilnå finns via My MiniZinc page.

Digital Tomography samt några varianter
Det problem som skrevs om i Ett litet april-pyssel löste jag själv med en digital tomografi-teknik. Se modellen tomography.mzn.

En viss förklaring av digital tomografi finns på sidan Open problems in discrete tomography. Sidan innehåller några Java-applets som man själv kan leka med.

I ovanstående modell var det bara en färg ("svart") man arbetade med, men problem kan generaliseras till flera färger. En sådan generalisering görs i tomography_n_colors.mzn, och som exempel modelleras bl.a. "The two atom problem".

Solitaire Battleship (wikipedia) är en variant av "Sänka skepp" som har liknande förutsättningar som digital tomografi. MiniZinmodell: solitaire_battleships.mzn.


SONET problem
SONET-problemet är ett standardproblem inom constraint programming som jag inte hittat någon MiniZinc-modell av så därför rullade jag en egen: sonet_problem.mzn.

För mer om problemet se t.ex. Simplified SONET Problem (Postscript-fil).


A Coin Puzzle
Detta problem på en rätt stor "grid" beskrivs utförligt av Tony Hürlimann i A coin puzzle - SVOR-contest 2007 (PDF).

Min MiniZinc-implementation av problemet finns i coins_grid.mzn. Ett tips är att låta en linear programming-solver lösa problmet, dvs ECLiPSe:s eplex eller MiniZincs nya option "--solver mip". Då löses det blixsnabbt.

Några Operations Research-problem
I John Hooker:s föreläsning A framework for integrating optimization and constraint programming finns några OR-problem som imlementerats:

- freight_transfer.mzn

- product_configuration.mzn


Ett skoj fotbollspussel
I Yahoo!-gruppen lp_solve kom ett skoj problem. Tyvärr krävs inloggning till gruppen, så MiniZinc-modellen innehåller hela meddelandet.

Problemet (som är en knapsack-variant) går ut på att optimera köp av brittiska fotbollsspelare med vissa krav:
- budgeten är på 30 miljoner (pund)
- man måste köpa ett visst antal spelare (målvakt, försvarsspelare etc) för en given kostnad per spelare
- man ska maximera den totala kostnaden men inte komma över budgeten.

Problemet uttrycks i flyttal men jag har valt att arbeta med heltal av två skäl:
- för tillfället är det fler MiniZinc-solvers som klarar av helttal än flyttal

- när det gäller spelarkostnader är inte orimligt att anta hela pund.

MiniZinc-modellen finns i football.mzn och är ganska generell.


Några andra modeller
- Funktionspartitionering, dvs partionera ett gäng heltal med avseende på en funktion t.ex. modulo-funktionen: modulo_partition.mzn. Det är enkelt att ändra funktion i modellen.

- Beslutsträd. Här modelleras ett fullständigt binärt beslutsträd: decision_tree_binary.mzn.

- Markovkedjor: markov_chains.mzn: Här räknar man ut "stable state" av marknadsandelnarna för tre företagsmärken.

- Yet another recreational schackproblem: peacableArmyOfQueens.mzn.


Raymond Smullyans logiska pyssel
Så till det jag satt med i helgen.

I den underbara boken What is the name of this book? beskriver Raymond Smullyan ett stort antal logiska pyssel, de allra flesta är skapade av Smullyan själv.

Några av de mest kända pysslen från denna bok är "Knights and Knaves"-problemen från kapitel 3 (som heter just "Knights and Knaves"): Alla "knights" talar alltid sanning och alla "knaves" ljuger alltid. Senare i kapitlet kommer även "Normals" med, sådan ljuger ibland och talar sanning ibland, och så tillkommer speciella giftasregler mellan de olika typerna. Problemet är att försöka lista ut vem som är vad med ledtråd av några få ledtrådar.

De allra flesta problemen från kapitel 3 finns modellerade i respektive modell:
- smullyan_knight_knaves.mzn: bara knights och knaves
. Problem 26 till och med 35. (Problem 36, 37 och 38 har av olika skäl inte modellerats.)

- smullyan_knight_knaves_normals.mzn: här finns även normals
. Problem 39 till och med 42 (modellen för 43 är inte korrekt).

- smullyan_knight_knaves_normals_bahava.mzn, med speciella giftoregler mellan knights, knaves och normals. Problem 44, 45 och 46.

Wikipedia har mer info om Knights and Knaves.

Uppdatering något senare
Några fler problem från samma bok:

- De första problemen om Lion och Unicorn från kapitel 4 "Alice in the Forest of Forgetfulness": smullyan_lion_and_unicorn.mzn. Lejon och enhörningar ljuger vissa dagar och talar sanning andra dagar. Här gäller det att lista ut vilken dag de säger olika saker.

- De första problemen från kapitel 5 "The mystery of Portias Caskets" smullyan_portia.mzn.

Posted by hakank at 06:54 EM Posted to Constraint Programming | Pyssel

maj 05, 2008

Sammanfattning av Bloggareträff uti Malmö, söndagen 4 maj 2008

Sammanfattning av Bloggareträff uti Malmö, söndagen 4 maj (2008), klockan 13:00 på Kin Long.


Det finns två versioner av denna sammanfattning. Välj ditt val och stå sedan ditt kast:

Den korta varianten

Vi [kom, hälsade, beställde, pratade, åt, hade trevligt, betalade, gick].


Den något längre varianten

Det var inalles sju (7) stycken deltagande bloggare som träffades på Kin Long.

Trevligt och mycket god mat var det som vanligt. Maten var som vanligt gudomlig. Tips: man bör inte deltaga i animerade diskussioner just när man äter så god mat.


Denna gång var det rätt mycket blogg- eller webbrelaterat som dryftades. Det kan bero på att det var ett antal (>4) månader sedan många av oss träffades sist, och det har hänt en del relaterat.


- Strax efter att vi blivit fulltaliga tog David upp sin mobiltelefon för att Jaikua att vi börjat vår bloggträff. Det kom då en kommentar om att telefonen inte verkade vara helt optimerad till att skriva långa (eller korta för den delen) texter. Varpå en stor minoritet av deltagarna (samtliga av manligt kön) tog upp sina mobiltelefoner. Exakt vad de sade vet jag inte men det kändes på något sätt högtidligt.


- Onceability
[Stavas det verkligen så? Om det är nytt men vedertaget uttryck borde man få mer än 10 träffar på favoritsökmotorn.]

Oavsett hur det stavas så betecknar "onceability" sådana funktioner på en pryl (tänk mobiltelefon eller datorprogram) som är så komplicerade att använda så att man använder funktionen endast en gång. Sedan glömmer man bort funktionen och/eller så hittar man inte manualen. Det är därför man endast använder de avancerade telefonerna till att ringa med och till essemessen.

En mot-gambit till detta är att ge apparaten till någon i den yngre generationen som garanterat kommer att hitta funktioner som du inte har någon aning om. Troligen kommer densamma ungdomen att ändra inställningarna så att du måste leta rätt på manualen för att kunna använda apparaten igen.


- Mer telefoner, det långt efter ovanstående telefonmania inträffade: Någon i sällskapet klagade på sin nya mobiltelefon att den hade kamera som denne inte använde: "Det gör den alldeles för tung" (obs! ej ordagrant citat. Citattecknen innebär endast att någon sade något).

Flera höll med om problemet att prylar inom normalt prisområde (speciellt mobiltelefon) har funktionalitet som inte används (zerobilitet?).
En kommentar var däremot följande: "Jag tycker det är bra med lite tyngre telelfoner som man känner av den i fickan. Är de för små så är det lätt att tro att man glömt den eller inte är medveten om den.".

Varpå ett förslag kom att telefonen borde bli tyngre beroende på hur många telefonsamtal/SMS man inte besvarat.

[Sammanställarens anmärkning: Av någon anledning kommer jag att tänka på Umberto Ecos underbara analys av jeans i hans "Vad kostar ett mästerverk". En poäng med jeans är att man - till skillnad från andra byxor - känner av dem, och blir ständigt medveten om sin kropp.]


Ovanstående förslag ledde osökt till:

- USB minne som blir större ju mer data som finns lagrat.
Se Tommys inlägg Kort minne. Diskussion fördes då naturligtvis hur man skulle kunna utnyttja denna typ av återkoppling. Några förslag:
- för att radera alla filer så "punkterar" man "ballongen"
- om man skakar den hör man på rasslet hur mycket data som finns (kanske även vilken typ av data det är). Det bör dock inte låta som något är löst eftersom då förfelar det sin avsedda verkan.


- En utlovad länk: Här är en trevlig blogg som använder spelteori och andra ekonimiska metoder för att analysera föräldraskap: Game Theorist - Musings on economics and child rearing.


- Någon (jag hakank) hade läst Framtidens bloggstjärnor (*, samt min fetning) :


Nästa hajp i bloggsvängen kommer inte vara en ytlig trendblogg utan en djup, nördig sajt med otroligt sakkunskap. Här är kandidaterna.

De fem kandidaterna till framtidens bloggstjärnor finns att läsa i artikeln. De är repektive en kollektiv litteraturblogg, en kollektiv musikblogg, en gruppblogg om musik, en modeblogg (!) samt en anonym tv-blogg.

Det noterades att det inte fanns någon representant av teknikbloggarna (übernördbloggaren), vilket ansågs som synd. Det har naturligtvis att göra med storleken på målgruppen.

Diskussion fördes om vad en nördblogg egentligen är. Generellt ansågs en modeblogg inte vara en nördblogg, däremot kan en blogg om enbart Gucciprodukter vara det, liksom en blogg som endast handlar om vänsterskor, eller enbart om produkter för vänsterhänta.

(*)
Jag tror att det var Veckans affärer som skrev originalartikeln. I dagens hypermedia är det svårt att veta vem som ursprungligen publicerat en artikel. Eftersom det med stor sannolikhet var på VA jag läste artikeln (möjligen via någon annan) så är det rätt att länka till dem. Tror jag...


- Mikrobloggning/sociala nätverkssystem
Eftersom David var med oss blev det en del prat om detta. Det noterades alltså att ett antal personer som varit aktiva inom den svenska bloggosfären numera i viss mån bytt fokus och skriver nu istället på sådana ställen som Jaiku.

Poängen är mycket att det både är ett socialt nätverk och att det finns en snabbhet i publikationer som t.ex. vanliga bloggar saknar, samt är mycket mer renodlat till att texta än de stora Yet-Another-Social-Networks(YASN)-härkena såsom Facebook.

Bloggvärldsbloggen skrev om detta för ett tag sedan: Mikrobloggar är det nya svart.

Den första diskussionen kring detta spårade snabbt ur eftersom någon undrade om det verkligen var "mikrobloggning": varför inte minibloggning, eller nanobloggning. Eller Ångströmsbloggning?

Det gjorde då också en undring hur stor (dvs liten) en bloggning måste vara för att vara mikro (och därmed svart). Ursäkta att det skojades till här. Men det är så det kan gå ibland.

Det relativt okända YASN-systemet Plaxo nämndes också. Det var inte många som kände till det. Det verkar inte har fått upp något större momentum i Sverige ännu. Man kan se det som en blandning av Facebook (kan skriva t.ex. blogginlägg) och Linked In, där man lägger in sina riktiga kontakter.

Diskussionen kom naturligtvis även in på vilken egentlig nytta man har av sådana YASN. Ett skäl så gott som något var att helt enkelt studera hur det sociala nätverket evolverar över tiden, när det exploderar och sedan stelnar.

Det nämndes även ett YASN som förr heter Klassträffen eller något liknande, men numera har ett engelskspråkigt namn (David kom ihåg det svenska namnet). [...En sökmotorsökning senare...] Ah, det var ju StayFriends. Där hade någon fått kontakt med gamla skolkamrater och tyckte det var funktionellt för just detta ändamål.

Ett aktuellt mem som visar konstigheterna i slika sociala nätverkssystem: Facebook in reality.


Till detta inte helt orelaterad:

- Videobloggning, youtubning.

Det sågs inte helt odelat positivt att fler och fler bloggar har inlägg med endast en inbäddad Youtube-film. Det ses (av vissa i alla fall) vara ungefär på samma nivå som ett inlägg med endast en länk till en artikel någon annanstans.

Sedan kom vi in på "riktig" videobloggning, dvs då bloggaren skapar en egen film. Här tyckte en hel del att det är mycket bättre med text eftersom det är svårt att skumma filmer för att se om det är intressant. Någon annan höll principiellt med men ansåg att videoföreläsningar var ett mycket bra påfund.

Ett trevlig exempel på videobloggning är den i svensk folkmun relativt okände trollkarlen Johan Ståhl som videobloggat (med kompletterande text) om sin resa till USA för några mycket ansedda föreställningar samt tävling i Las Vegas. Speciellt roligt är Tävling i Las Vegas där prisutdelningen videofieras.

(Efter detta kom vi in på trolleri och trolleriets psykologi, framförallt om man som gammal trollkarl kan bli lurad. Men det tillhör sådant som det inte skrivs om här. Not: inga hemligheter avslöjades.)


- Vad gäller luras så kom vi sedan in på att utbildare är tvunga att "lura" sina elever för att kunna förklara hur saker och ting fungerar. Efter ett tag kan man tillföra mer och mer detaljer för att få en mer sann bild.

Någon kommenterade att det var på samma sätt när man förklarar saker för sina barn. (Det specifika exemplet här var differentialekvationer men jag tror inte att det måste vara så extremt).

Varpå det kommenterades att matematiken är troligen den enda disciplinen som inte gör denna omväg kring att förenkla för eleverna utan förklarar från börjar "hur det är" med att börja med grunderna i stället för att "pedagogisera" ämnet. Till förfång för mången elever. (Naturligtvis är denna beskrivning i sig en förenkling av hur det verkligen är. Det finns många bra matteböcker och mattelärare. Så var det sagt.)

Här bevingades även uttrycket "Nils Holgersson-perspektiv" som den skånska varianten av helikopterperspektiv.


- Det torrprogrammerades inte i Excel, och i övrigt var det inte speciellt mycket matematiknörderier.

- Ett kärt ämne: hur mycket följer man statistiken på sin blogg.

Det verkar som om intresset överlag har minskat under åren, naturligtvis med några undantag. Någon hade inte kontrollerat sin besöksstatistik på flera månader.

Några var överens om att den mest intressanta var att man hade kontroll av länkar till sin blogg. Andra tyckte att det var mest intressant vilka ord som besökarna använde för att komma till bloggen.

I samband med detta utbrast en av deltagarna (hakank) sin starka irritation över den spam-farm som sedan några veckor försöker anropa mt-tb.cgi (som sedan länge är helt borttagen från systemet). Naturligtvis försöker de att få bättre rankning på sökmotorerna. Idioter!


- "Blogga ett inlägg om dagen"

Eftersom de allra flesta av deltagarna numera är mindre aktiva än tidigare pratades det om orsaken.

I vissa fall är fokus på andra publikationssystem (se ovan), i andra fall att man inte anser sig har något nytt att komma med, där kraven vad som är nytt och relevant att skriva om har ökat med åren.

Någon: "en tanke är att helt enkelt radera sin gamla blogg och börja om från början, med en helt annan inriktning än den nuvarande".

Någon: "jag ska testa att skriva ett inlägg om dagen under en månad..."

Varpå det naturligtvis blev en diskussion hur stort/litet en sådant inlägg måste vara för att det ska räknas. Pendangen till föregående uttalande var iofs "... oavsett hur stort eller litet det är".

Någon annan hade löst det genom att ha ett flertal specialinriktade bloggar (mer eller mindre anonyma och/eller skilda från existerande blogg), men - och det tyckte vi var lite roligt - kom inte ihåg alla de bloggar som skrevs på.

- Att själv skriva sina kommentarer under ett annat namn ansågs vara fusk och om det kommer ut blir det stor skandal: "Länkskandal i bloggosfären" var förslag på rubrik (om det var någon mer känd blogg än våra). Inte helt catchy rubrik, dock.


- Fusk i rekommendationssystem
Länk angående fusk i sådana system utlovades:
Shilling Recommender Systems for Fun and Profit.

Se även: ("recommendation system" | "recommender systems" | "collaborative filtering") (attack | shilling).


Det diskuterades även allmän osäkerhet i vissa typer av betygssättarsystem:

- för få betygssättare ger skevt medelbetyg

- vet inte alltid vad det egentligen är som betygssätts

- vet inte alltid när betygssättningen gjordes. Är det ett gammalt betyg kan saker och ting har förändrats (till det bättre eller sämre).


- Cocktails

I vissa sammanhang kring matbordet är det oundvikligt att whisky kommer upp på dagordningen. I detta sällskap är det istället cocktails som dryftas.

En sak som vi alla nu väntar på är en djup analys vilken typ av maträtt som passar bäst till vilken cocktail, såväl före som efter maten (endera eller bådadera).


- Skulle du läsa din blogg om du inte skrev den själv?

(Här låter vi allt annat i världen vara ceteris paribus, dvs vi antar bara att det inte är du som skrev din blogg, men att ditt liv i övrigt var detsamma. En märklig förutsättning, men OK.)

Flera (an|in)såg att man nog inte skulle läsa eller bloggbevaka sin blogg. Exakt av vilka skäl anfördes inte, men man kan skönja en viss koppling till att samma personer inte läser så många bloggar.

En deltagare medgav dock att det berodde på att denne som skribent vill styra händelsens utveckling, vilket ju inte kan göras som läsare. Någon annan skulle dock läsa sin egen blogg.

- Det klagades på alldeles för långa bloggtexter.

Med viss rätt.


- Typealyzer
Naturligtvis nämndes Typealyzer där man kan skriva in en URL varpå texten analyseras enligt en personlighetstyp.

(hakank: Jag blir alltid INTP eller INTJ på alla denna typ av texter. Ett av de få undantaget är det gamla litterära försöket Till min dagbok om jag hade någon. Vilket inte är så konstigt.)

Vissa tekniska saker kring systemet diskuterades.


- "Bloggar du för dina läsare eller för sökmotorerna?"

En förstulen kommentar kring Googles PageRank orsakade ovanstående fråga. Det är alltså inte bara frågan om vem som är målgruppen utan även "när" är målgruppen. Bloggar kommer traditionellt högt på sökmotorerna eftersom det dels länkas mellan varandra men även att det nu finns ett antal aggregatorer där text + länk kommer upp.

Exempel: mitt första inlägg om MiniZinc (Constraint Programming: Minizinc, Gecode/flatzinc och ECLiPSe/minizinc) efter någon timme fanns i en eller annan form på ett 10-tal svenska sajter - inklusive sökbart på google och yahoo - efter bara några timmar. ("minizinc" är tacksamt som att ha som test eftersom det fortfarande är relativt få som skriver om det. Tyvärr.)


Utlovad länk till Firefox-extension (add on) för visning av Google PageRank:
Live PageRank. PageRanken visas nere till höger i statusfältet.
Se även LivePR, som funkar inte så bra i skrivande stund.

Sedan är det en helt annan fråga hur mycket:

1) man kan lita på att detta är det korrekta PageRank-värdet som används av google själv

2) av PageRank som används av google vid en söksortering.

Posted by hakank at 08:35 EM Posted to Bloggmiddagar | Comments (12)