Tegelzetten	Fruitvliegen	Global Traffic	FreeCell	Building Brains
Inleiding Tegelzetten is een vak apart. Hoewel de meeste zettingen regelmatig zijn (denk aan de vierkantjes in keuken en badkamer) zijn er ook ambitieuzere patronen, zoals een 'versailles-pattern' waarin twee of drie verschillende tegeltjes in een veelal repeterend patroon worden gerangschikt. In een zeldzaam geval is de zetting echt onregelmatig, in schikking of tegeldiversiteit, maar het gaat dan bijna altijd om relatief kleine vlakken en vormen waaraan een kunstenaar of architect veel tijd kwijt is. In deze opdracht willen we kijken of we met een algoritme structuren in zettingen kunnen ontdekken. Er is java-sourcecode voor deel a beschikbaar, en er is java-sourcecode voor deel b beschikbaar, en zelfs een stukje matlabcode. Opdracht a) Verzin een algoritme om tegelset #1 in het bijgeleverde invoervak te zetten. Een zetting is correct als er geen tussenruimte tussen de tegels is, en tegels elkaar niet overlappen. Tegels hoeven niet gedraaid te worden. b) Verzin een algoritme om tegelset #2 in het bijgeleverde invoervak te zetten. Een zetting is correct als er geen tussenruimte tussen de tegels is, en tegels elkaar niet overlappen. Tegels hoeven niet gedraaid te worden. Advanced Pas je algoritme zo aan, dat het een zelfgemaakte set van twintig random tegels in een zo groot mogelijk rechthoekig invoervak zet. Tegelset #1 Tegelset #2	Inleiding Knolrapen en bloemkolen blijken veel overeenkomsten te hebben. Sterker nog, de genen van beide soorten zijn vrijwel identiek. Het verschil zit hem in de volgorde van de genen en ook daarin is het verschil klein; het kost maar vijf mutaties om van de één de ander te maken. Voor kleine stukken genoom, waarop weinig mutaties kunnen plaatsvinden, is een reeks van vijf mutaties, en daarmee een mogelijk historisch evolutietraject, gemakkelijk te vinden. Drosophila Melanogaster en Drosophila Miranda (fig. boven) zijn fruitvliegsoorten waarvan het genoom goed bestudeerd is. Ook hierbij geldt dat de genen van het genoom voor beide soorten (vrijwel) identiek zijn, en dat het verschil ligt in de volgorde (fig. 2). Mutaties in het genoom vinden alleen plaats doordat gedeelten ervan omkeren (fig. 3), en zo de genvolgorde veranderen. Formeler laat de opdracht zich als volgt omschrijven: een fruitvliegengenoom is een rijtje van 25 genen, die we voor het gemak van hun naam ontdaan en hebben en genummerd hebben van 1 tot 25. Een mutatie vindt plaats door een willekeurig subrijtje van een willekeurige lengte te inverteren. Vind een reeks van mutaties waardoor het genoom van fruitvlieg 1 in fruitvlieg 2 verandert. Hoe korter de reeks hoe beter. Er is wat software beschikbaar om de sequenties te visualiseren en je algoritme te evalueren. Ga naar de fruitvliegen-pagina. Fig.2: De genomen van D. miranda en D.Melanogaster zijn componentsgewijs identiek; het verschil tussen de soorten komt voort uit de volgorde van de individuele genen. Fig.3: Een mutatie vindt plaats door middel van een omkering van een set genen. Opdracht a) Schrijf een algoritme dat het genoom van D. Melanogaster in het genoom van D. Miranda verandert, met zo min mogelijk mutaties. b) Evalueer je algoritme op basis van een zelfgemaakte test-set met 10000 random-volgorde genomen van lengte 10, 25, 50, 100. Baseer je evaluatie op het benodigd aantal mutaties om de genen op volgorde te krijgen. c) Schrijf een algoritme dat het genoom van D. Melanogaster in het genoom van D. Miranda verandert, met zo min mogelijk verplaatste genen. Dat betekent dat de omkeer-mutaties gemiddeld zo klein mogelijk moeten zijn. d) Evalueer dit algoritme op basis van je zelfgemaakte test-set. Baseer je evaluatie op het aantal mutaties en het aantal verplaatste genen. Zoek uit welk mutatietraject nodig is om een Melanogaster in een Miranda te doen veranderen. Het is mogelijk dat er meerdere antwoorden zijn; bewaar ze allemaal. Advanced Op wat voor genomen gaat je algoritme een korte mutatiereeks vinden? Op welke een lange? Motiveer je antwoord.	Inleiding De nieuw opgerichte Nederlandse maatschappij Mokum Airways (MAW) heeft Amsterdam als thuisbasis en landingsrechten voor veertien verschillende bestemmingen, allen in Europa (zie afbeelding rechts). Ze heeft een herkenbaar logo en een luchtvloot, bestaande uit toestellen van het type Boeing 737-400 (zie afbeelding onder). Mokum Airlines heeft een marktonderzoek gedaan voor de veertien luchthavens waarop zij actief is waarbij gekeken is hoeveel mensen er potentieel tussen twee luchthavens vervoerd zouden kunnen worden door Mokum Airways. Het doel van deze opdracht is een daggebaseerde dienstregeling op te stellen zodat er zoveel mogelijk passagiers vervoerd worden. Er zijn gegevens beschikbaar voor potentiële passagiers en voor vliegafstanden tussen de steden. Alle vliegtuigen hebben een gemiddelde A-tot-B-snelheid van 800 km/u en moeten na een landing een uur blijven staan voor unboarding, schoonmaak en boarding alvorens weer op kunnen stijgen. Als de tank leeg is (zie:'bereik') moet het een uur extra blijven staan om te tanken. Een dag duurt van 6:00 's ochtends tot 2:00 's nachts. Daartussen mag niet geland of opgestegen worden in verband met geluidsoverlast van omwonenden. Alle toestellen moeten tenminste eenmaal daags Amsterdam aandoen voor personeelswissels. Mokum airways maakt winst door zoveel mogelijk passagiers over zoveel mogelijk afstand te vervoeren. De afstand is de afstand die de passagier wil reizen, dus als hij van Amsterdam naar München vliegt via een omweg, telt toch de afstand Amsterdam-München, en niet de omweg. Opdracht a) Maak een correcte dagroute voor één vliegtuig, zodat er zoveel mogelijk passagiers over zoveel kilometers verplaatst worden. De score voor een schema is het aantal passagiers vermenigvuldigd met het aantal kilometers tussen haar start- en eindpunt. Een correcte dagsroute voldoet aan de volgende eisen: Het begin- en eindpunt zijn gelijk. Het vliegtuig komt tenminste éénmaal in Amsterdam Het vliegtuig komt niet tijdens een vlucht zonder brandstof te zitten Het vliegtuig komt tenminste éénmaal in Amsterdam Het vliegtuig landt niet, en stijgt niet op tussen 2:00 en 6:00 b) Maak een correct dagschema voor alle zes de vliegtuigen uit de vloot, zodat er zoveel mogelijk passagiers over zoveel kilometers verplaatst worden. De score voor een schema is het aantal passagiers vermenigvuldigd met het aantal kilometers tussen haar start- en eindpunt. Advanced Mokum airlines zoekt een nieuwe thuishaven om haar passagierskilometers verder te optimaliseren. Geef een gegrond advies. Er is software en sourcecode beschikbaar op onze op onze GlobalTraffic-pagina .	Inleiding FreeCell is een spel wat gratis met Windows en Unix wordt meegeleverd. De beginconditie bestaat uit acht random stacks: vier van zeven kaarten en vier van acht kaarten. Een zet bestaat uit het verleggen van een kaart naar 1. een FreeCell (linksboven) 2. een GoalCell (rechtsboven) 3. een andere kaart op een stack (onder) In geval (2) mag een kaart alleen op de direct lagere kaart van zijn eigen 4-kleur liggen. In geval (3) mag de kaart alleen op een direct hogere kaart van een andere 2-kleur liggen. Eenmaal in een GoalCell komt een kaart er niet meer uit. GoalCells worden dus op 4-kleur en volgorde gesorteerde kaartenstapeltjes. Als alle kaarten in een GoalCell liggen is het spel gewonnen. Een prikkelende frase uit de manual luidt: "It is thought, though not proven, that every game of FreeCell can be won." De beste manier om deze opdracht aan te gaan is een aantal spelletjes FreeCell te spelen om fingerspitzengefühl te ontwikkelen. Enige voorzichtigheid is geboden: verslaving ligt op de loer. Het spel en haar sourcecode zijn beschikbaar op onze freecellpagina . Opdracht De opdracht is een FreeCell-Solver te maken, die vanuit een gegeven positie en zettensequentie vindt die tenminste tien kaarten wegspeelt. Advanced Verbeter je algoritme zodat het vanuit een beginpositie een zettensequentie vindt die het hele spel oplost. Fig.1: Geldige zetten in een freecell-situatie. Fig.2: Ongeldige zetten in een freecell-situatie.	Inleiding Small-worlds zijn netwerken met een hoge cluster coefficiënt, en een lage karakteristieke padlengte. Het internet, het menselijk brein en de Japanse taal zijn van dit soort netwerken. Zie ook de extra extra informatie over small-world networks . Er is wat java sourcecode beschikbaar om dingen wat makkelijker te maken. Hier vind je een werkende buildingbrains-applet met sourcecode. Opdracht 1. Vind de maximale cluster coefficiënt van een netwerk van 100 knopen en 300 verbindingen. 2. Vind de minimale karakteristieke padlengte van een netwerk van 100 knopen en 300 verbindingen. Vind ook de maximale padlengte.
Versailles-patroon Onregelmatige tegelzetting op een voor ons bekende plek. Geen tegels, wel onregelmatig.	Philogenie van de familie fruitvlieg. Iedere splitsing in de boom geeft de mutatie naar een nieuwe soort aan.	Structuur van een Boeing 737-400. Amsterdam, thuisbasis van Mokum Airways.	Free cell in Alcatraz.	Hersencellen (neuronen) vormen een netwerk met small-world eigenschappen. Een graaf van hersenactiviteit vertoont een small-world structuur.