Hvem kan blive mestre, og hvem rykker ned?
Dataloger afg酶r placeringsmuligheder i fodboldturneringer
Folk, der g氓r op i fodbold, ved, at n氓r turneringer n忙rmer sig deres afslutning - n氓r der f.eks. er tre spillerunder tilbage af superligaen - s氓 er der virkelig mange spekulationer omkring hvilke hold, der stadig er i fare for at rykke ned, hvilke hold, der stadig kan f氓 s酶lvmedaljer, osv.
Faktisk er det forbavsende sv忙rt at regne sig frem til pr忙cist, hvad der kan lade sig g酶re, og hvad der helt sikkert ikke kan lade sig g酶re. Sportsjournalister fors酶ger sig med dette, og man h酶rer udtalelser, der refererer til en "matematisk" chance for, at noget kan ske. En af grundene til, at det er vanskeligt at finde ud af, er, at n氓r hver kamp kan ende med sejr, uafgjort eller tab for hjemmeholdet, s氓 er der f.eks. i superligaen med bare tre spillerunder tilbage 150.094.635.296.999.121 (ca. 150 billiarder) muligheder for, hvordan resultaterne kan fordele sig - og det er endda f酶r, man tager m氓lscore i betragtning.
N氓r man som person kigger p氓 dette, kan man heldigvis se bort fra en masse muligheder, man kan se er irrelevante, men med flere end tre spillerunder tilbage, bliver det ret sv忙rt manuelt at afg酶re sp酶rgsm氓l med sikkerhed.
De to datalogistuderende Jan Christensen og Anders Knudsen har set p氓 denne problemstilling i deres speciale under vejledning af professor Kim Skak Larsen fra Institut for Matematik og Datalogi p氓 Syddansk Universitet. Sammen har de dels bevist, at problemet virkeligt er meget sv忙rt; formelt siger man, at problemet er NP-h氓rdt. Men derefter har de vist, at man faktisk godt kan l酶se det vha. en computer alligevel - og ogs氓 indenfor rimelig tid for f.eks. superligaen.
Det betyder, at man i aviser og p氓 betting-sider kan give ekstra information til sine l忙sere, hvis man har lyst. I tabellen, der viser den aktuelle stilling, kan man tilf酶je en s酶jle med et interval, som f.eks. 3-8. Det betyder s氓, at holdet helt sikkert bliver placeret p氓 en af de pladser. Mere pr忙cist kan holdet f.eks. blive nummer 3, hvis andre resultater flasker sig, men der er ingen m氓de, de kan blive nummer 2 p氓. Tilsvarende kan de risikere at blive nummer 8, men der er ingen risiko for, at de kan blive nummer 9 - ligegyldigt hvor d氓rlige andre resultater er for dem.
Denne ekstra information kan nu leveres for alle hold - ligegyldigt hvor mange spillerunder, der er tilbage. Men det er selvf酶lgeligt mest interessant, n氓r vi n忙rmer os afslutningen.
Anders og Jan har lige holdt deres mundtlige forsvar, hvor de scorede 12-taller!