Skyfall. Mobile Apps. Cubics Graphs. A Beautiful Mind. containing: Gala : shaken not stirred. the future of. counting matchings in

MACHAZINE Volume 19 - Issue 1 November 2014

Gala : shaken not stirred

Skyfall the future of

Mobile Apps counting matchings in

Cubics Graphs movie Review

A Beautiful Mind

containing: Current Affairs | Association | Computer Science | Mathematics | Miscellaneous

The future belongs to those who challenge the present.

Start your career at Cognizant Technology Solutions We have diverse jobs in which you can start: Developer, Business analyst, Project coordinator, Quality Engineering & Assurance Analyst, Data scientist We offer: • An introduction training program abroad • The opportunity to work for our large multinational clients soon after your start • An open, international and multicultural environment, open to entrepreneurship • Access Cognizant Academy to ensure your professional development • A mentor who will support you Who are we? Cognizant is a leading provider of information technology, consulting, and business process outsourcing services, dedicated to helping the world’s leading companies build stronger businesses. With over 75 development and delivery centers worldwide and approximately 187,400 employees as of June 30, 2014, Cognizant is a member of the NASDAQ-100, the S&P 500, the Forbes Global 2000, and the Fortune 500 and is ranked among the top performing and fastest growing companies in the world. Visit us online at www.cognizant.com Interested in finding out more? Contact Leonie Westerman, graduate recruitment manager: [email protected] or 06-46256397 or apply directly through www.cognizant.com/careers

KEEP CHALLENGINGTM

content & colophon Machazine is a publication of

W.I.S.V. ‘Christiaan Huygens’

Current Affairs

Chief Editors Patrick van Hesteren

Editorial 2

Editorial staff Rebecca Jacobs, Pieter Hameete, Anouk Ren-

Activity Calendar

2

tier, Cindy Caljouw, Rebecca Glans

Column - Fantoom redenaties

3

Column - Van het Bestuur

4

Herman Banken, Floris Verburg, Saskia Vert-

Column - You have new mail

5

regt, Bastiaan Grisèl

Facultaire Studentenraad

6

Column - International Student

7

Art Directors

Contact address Mekelweg 4, 2628 CD Delft

TU Delft Nieuws

E: [email protected] T: 015-2782532

Association

Concept and design G2O Kesteren

Publisher

Eerstejaarsweekend 10

Gildeprint Drukkerijen

Eerstejaarsweekend Reünie

Cover

12

LedenLunCH 13 IFF 13

Cooperating on this issue: Arie Troebel, Patrick van Hesteren, Fred

Gala 14

Vermolen, Steffie van Loenhout, Eftychia

Delfts Kampioenschap Programmeren

15

Thomaidou, Tom Brouws, Tom Harting, Joep

FlitCie fotopagina

16

Bom, Daniël Swaab, Stefanie Vonk, Danique

Eerstejaarsblog Informatica

18

Lummen, Maaike Mol, Lars Tijhuis, Martijn

Eerstejaarsblog Dubbele Bachelor

19

Rentmeester, Hylke Visser, Martin van Gijzen, Wolter Groenevelt, Pim Otte, Casper Markensteijn, Mark Veraar, Pieter van den Berg, Rik Versendaal, Thijs Jacobs.

Computer Science Context-Based Spelling Correction for the Dutch Language

20

Towards a Social Web based solution to bootstrap new domains in

Terms and Conditions The MaCHazine-committee and the Board

cross-domain recommendations

are responsible for the content within this

The Future of Mobile Apps

22 24

MaCHazine, in such terms that the opinion

Java Puzzlers

26

of a writer is not (necessarily) a reflection of the opinion of the committee or association. All rights reserved. No part of this publication may be reproduced, stored in a (retrieval) system or transmitted in any form or any

Mathematics

means, electronic, mechanical, photocopying,

Wiskundepuzzel 27

recording, scanning or otherwise, without the

Global tide model with DFlow-FM

28

prior written permission of the committee or

IDR as a Fixed-Point Method for Solving Linear Systems of Equations

30

association.

Harige Bollen

32

Time-dependant Ambulance Locations Model with Start-up and Relocation Cost 34

Advertiser index Cognizant Inside Front Cover Copernica Inside Back Cover

Counting matchings in cubic graphs

36

Arithmetische progressies in random kleuringen van de natuurlijke getallen

38

ASML 9 Prime Vision

41

Miscellaneous Historisch Persoon: Nicomachus

40

Studeren in het buitenland

42

Film review: A Beautiful Mind

44

Volume 19 • Issue 1 • November 2014

Activity Calendar November 11 Lunch Lecture Cryptography 13 WiFi Neon Party

Editorial Cindy Caljouw

13 Teacher of the year awards 18 Lunch lecture cryptography 19 ADSL 25 Lunch lecture cryptography 26 Maphya Double Degree Dinner 28 Skyfall: gala

December 2 Members lunch 4 Oliebollen Drink

Current Affaris

5

2

YES!Delft excursion

15 General assembly 16 Lunch lecture 18 Christmas Dinner

Fantoom redenaties Arie Troebel

Current Affairs 3


gemakkelijk herkenbaar maakt zodat iedere eerstejaars weet wie je bent. Tot op dit moment blijf ik me verbazen over de hoeveelheid mensen die je kunt leren kennen in een weekend dat zo voorbij is.

Van het bestuur Patrick van Hesteren

Op het moment van schrijven is het bijna eind september en de eerste maand van mijn bestuursleven zit er al weer bijna op. Het lijkt al weer

Terwijl de meesten van jullie in de week erna tijdens de OWee vele feestjes en activiteiten mee hebben gepakt, om zo samen met je mentorgroepje heel Delft en alle verenigingen te leren kennen, waren wij vooral ontzettend druk bezig op de vereniging om de laatste hand te leggen aan ons beleidsdocument en het voorbereiden van de Algemene Vergadering, waarin we als bestuur officieel verkozen en geïnstalleerd zijn. Na deze vergadering zijn we direct doorgegaan naar de fietsenkelder van onze faculteit om onze verkiezing te vieren tijdens onze constitutieborrel. Het is ontzettend gaaf om te zien hoe veel mensen er naar deze borrel komen om je te feliciteren onder het genot van een lekker drankje en een traditioneel slap verhaal. Na deze borrel ben ik traditiegetrouw kaalgeschoren door een aantal oud-voorzitters van onze vereniging, waardoor ik er tijdens het diner na afloop van de constitutieborrel uit heb gezien als een kaal geplukte kip. Nu het nieuwe collegejaar al enkele weken in gang is en mijn haar weer aan begint te groeien, zijn de eerste activiteiten van onze studievereniging ook alweer achter de rug. De lunchlezingen over “Flexible gate scheduling” en “HTML5 en Code Generation in cloudsystemen” werden bijzonder goed bezocht en ook de /Pub zat tijdens de ledenlunch bomvol met allemaal nieuwe gezichten. Het is ontzettend gaaf om te zien dat er zo veel mensen enthousiast zijn voor de activiteiten en voor CH, maar het leukste vind ik toch wel dat er op iedere activiteit andere mensen zijn en dat er op iedere activiteit weer nieuwe gezichten voor mij tussen zitten.

eeuwen geleden dat het allemaal begonnen is. Het begon allemaal de avond dat ik gevraagd was om plaats te nemen in bestuur 58. Vanaf dat moment begonnen er allemaal gekke vragen in je hoofd te dagen: “Met wie ga ik dit jaar samen beleven?” en “Wat gaat het aankomende jaar ons

Dat enthousiasme van jullie was ook duidelijk te merken tijdens de EJW Reünie. De /Pub stond weer stampvol eerstejaars en (oud-)commissieleden om daar met zijn allen onder het genot van het drankje te genieten van de EJW-film. Velen van jullie hebben tijdens deze borrel aangegeven interesse te hebben om plaats te nemen in een van de mooie commissies die onze vereniging kent. Een aantal van deze commissies zijn inmiddels gestart en de meesten zullen vlak hierna ook van start gaan!

brengen?”.

Current Affairs

Nadat ik dan toch eindelijk kennis had gemaakt met mijn aankomende bestuursgenoten, was het tijd om te beginnen. Terwijl jullie als eerstejaars studenten van jullie welverdiende vakantie hebben kunnen genieten na jullie eindexamens, zijn wij als bestuur vooral bezig geweest met het vormen van het beleid voor de studievereniging voor dit collegejaar. Naast het nadenken over de toekomst van de vereniging, zijn we in de weken voorafgaand aan het collegejaar ook vooral bezig geweest met onze inwerk- en overdrachtssessies. Nu enkele maanden verder is het dan allemaal zo ver, het nieuwe collegejaar, en daarmee mijn bestuursjaar, is begonnen. Ik kan me nog goed herinneren dat ik me vorige jaren heb verbaasd over de enorme hoeveelheid fietsen voor de faculteit. Ik hield me vorig jaar niet zo bezig met alle eerstejaars, maar dit jaar des te meer. De fietsenrekken staan weer bomvol, de collegezalen puilen uit met alle enthousiaste eerstejaars (die trouwens weer met vele malen meer zijn dan vorige jaren), de koffie en het fris in de pauzes is niet aan te slepen, om over de hoeveelheid studieboeken die dagelijks over de toonbank gaat nog maar niet te spreken. Tijdens het eerstejaarsweekend heb ik velen van jullie leren kennen tijdens de leuke activiteiten en mooie feestjes. Hoewel ik er moeite mee had om al jullie namen uit mijn hoofd te leren, hadden jullie daar overduidelijk minder moeite mee. Wellicht dat dat iets te maken had met mijn gemakkelijk herkenbare koningsblauwe mantel met bijbehorende kroon, een outfit die je als bestuur

4

Met al het aanwezige enthousiasme en alle gave activiteiten die er aan zitten te komen, hoeven we de komende weken in ieder geval zeker niet stil te zitten! Ik hoop jullie dan ook nog vaak te mogen begroeten op onze activiteiten, bij CH of in de /Pub!


You have new mail Fred Vermolen

Current Affairs 5


Facultaire Studentenraad Steffie van Loenhout

Het nieuwe studiejaar is inmiddels begonnen, en daarmee is ook de nieuwe FSR van start gegaan. Een deel van de oude FSR heeft plaatsgemaakt voor nieuwe leden. Bij deze willen we Jan-Willem, Laura, Herman, Max, Pieter, Bas, Vincent en Wietse bedanken voor hun inzet in het afgelopen jaar. Er kan worden teruggekeken op een jaar waarin we in

Verbouwing – Als FSR zijn wij betrokken bij de verbouwplannen van de faculteit. Wij zijn betrokken geweest bij het opstellen van het plan van eisen voor de verbouwing van de Veemhal. Studieruimten – Zoals jullie misschien wel merken is het aantal studieplekken binnen EWI minimaal. Als FSR proberen wij meer studieplekken en ook meer projectruimtes te creëren. Echter zit heel de faculteit vol met werkkamers en afdelingen en is dit een lastig punt. Wel kunnen de meetingrooms op de eerste verdieping van laagbouw gereserveerd worden en is dit onder de aandacht gebracht bij studenten.

prettige samenwerking met de faculteit mooie dingen hebben bereikt. Mocht dit het eerste MaCHazine zijn dat je leest dan is een toelichting van wat de FSR doet waarschijnlijk niet overbodig. De FSR is een medezeggenschapsorgaan binnen onze faculteit EWI. Bij beslissingen die in de faculteit worden genomen vertegenwoordigt de FSR het belang van de studenten. De FSR werkt intensief en proactief samen met het faculteitsbestuur en de onderwijsdirectie om de kwaliteit van het onderwijs en de faciliteiten op de faculteit te verbeteren. De FSR van het studiejaar 2014-2015 bestaat uit de volgende studenten: Kamer Technische Wiskunde: Pim Otte Inoni van Dorp Steffie van Loenhout

Current Affairs

Kamer Technische Informatica: Ginger Geneste Bart Heemskerk Wietse Heida Xander Zonneveld

Kamer Electrical Engineering: Moritz Fieback Rob Bootsman Dorus Leliveld Ralph van Schelven

Afgelopen jaar hebben wij ons weer enthousiast ingezet voor het verbeteren van het onderwijs en de faciliteiten binnen EWI. Om jullie een idee te geven waar wij allemaal mee bezig zijn geweest, zullen wij hiervan een aantal punten toelichten: Drebbelweg – Door het verdwijnen van de PC’s op Drebbelweg die plaats hebben gemaakt voor werkplekken hebben we ons ingezet om de werkplekken iets te verbeteren: zo zijn er o.a. extra stroomaansluitingen bijgeplaatst. Na enkele klachten over het netwerk bleek dit een TU - breed probleem te zijn waar nog hard aan gewerkt word.

6

Fietsenstallingen – Door de toename aan studenten op EWI bleek er een tekort te zijn aan fietsenstallingen. Daarom hebben we ons afgelopen jaar ingezet voor het bijplaatsen van fietsenrekken aan de voorkant van EWI zodat de fietsen nu allemaal in de rekken geplaatst kunnen worden. Reglementen – De FSR heeft de veranderingen in de Onderwijs- en Examenreglement en de Uitvoeringsreglementen goed doorgenomen, en aan het einde van het jaar goedgekeurd. Er zijn een aantal veranderingen doorgevoerd, en ze zorgen ervoor dat jij als student je rechten behoudt! Heb je ze nog nooit ingekeken? Kijk dan op http://studenten.tudelft.nl/ewi/reglementen/ . Studentenassistenten – Omdat het soms veel tijd kan vergen om voldoende studentassitenten te werven, hebben wij een aantal voorstellen gedaan bij de faculteit zodat dit proces verbeterd kan worden. Zo is er gekeken naar mogelijkheden om het studenten assistentschap aantrekkelijker te maken, en een algemene studentenpool te ontwikkelen zodat student assistenten voor meerdere vakken gevraagd kunnen worden. Ook hebben we ons gericht op de kwaliteit van de studentassistenten. Er is een enquête ontwikkeld die eenmalig is uitgevoerd tijdens een eerstejaars TI project. Momenteel worden de mogelijkheden onderzocht om de enquête te verwerken voor andere projecten. Studieadviseurs – De FSR heeft haar zorg uitgesproken over de hoge werkdruk van de studieadviseurs, waardoor we de faculteit hebben aanbevolen om een derde studieadviseur aan te stellen. Feedback onderwijs terugkoppelen naar studenten – Vaak is het bij studenten niet duidelijk wat er met de feedback op onderwijs wordt gedaan. Afgelopen jaar heeft de FSR samen met andere faculteitsmedewerkers in een werkgroep deelgenomen waarin er gewerkt is aan een plan dat de feedback van student en terugkoppeling van een docent openbaar zal maken. Komend jaar gaat de FSR daarmee verder zodat studenten de verbeteringen van het vak gemakkelijk kunnen inzien. Op dit moment is de FSR 2014-2015 druk bezig met het ontwikkelen van een beleid voor komend jaar. Hier zullen we in het volgende MaCHazine meer over vertellen. Mochten jullie nog vragen, klachten of suggesties hebben dan horen we deze graag. Dit kan o.a. via de mail [email protected].

Column International Student Eftychia Thomaidou

A new academic year has started and I’m back to my study room on the 12th floor. Back to studying and the creative work. My studies? MSc Bioinformatics. The track of Bioinformatics is a joined program among TU

all these data we have (DNA, RNA, proteins). This way we can try to understand the human body better as well as other organisms and benefit from it. Among others, applications of Bioinformatics can be found in medical centers, lifescience companies, cancer research institutes or plant research groups. If you are interested in learning more about Bioinformatics in the Netherlands, you may visit this link: biosb.nl/.

Delft and Leiden University. The average number of students, per year, is around 10. If you compare that number to other tracks in TU Delft, then you know that is a pretty small group. Though not a non-significant group! Bioinformatics is a growing field of expertise and especially in the Netherlands. The aggregation of the people working on this field

(bioinformatics.tudelft.nl) has a good reputation. It is actually quite funny, when one attends a conference, or an RSG meeting, that one meets the same people. New academic year and I’m curious to meet the freshmen. The Master Kick off is successfully over and the courses are fully started. Soon the Quarter will be over! If you are a student at TU Delft, then you probably know that the academic year is divided in quarters. That was in the beginning very confusing to me. As an international student, it was hard for me to adapt to this system, because I was used to semesters. The academic year in Leiden University is divided in semesters as well. So, if you are a Bioinformatics International student the confusion is double. One ends up in having exams in Delft and a class to follow in Leiden, even in the same day! But the quarter/semester has just started. I remember myself the first days, as a student here, trying to understand and collect the pieces of this big puzzle, called Bioinformatics. In case you are not familiar with the term, let me introduce you. This field focuses on the development of algorithms and models to interpret genomic data, in other words, get useful information from

Current Affairs

is still small enough, that everybody knows each other and our lab

Wondering what brought me in the Netherlands? My willingness to combine Computer Science with my love for Biology, and TU Delft was a good choice. I never had been to the Netherlands before; a constantly rainy place, occupied by tall people with an incomprehensible language. I managed to learn the language, at least an adequate part of it, which helped me understand the people and their culture. Netherlands is a small country with not very long history, not an easy and peaceful history though. What I managed to learn till now, led by the curiosity about ‘living under the water level’, is that the Netherlands has suffered from 7 big floods. The big rivers, that have their delta in the Netherlands, have flooded, as well as the sea, costing the life to the population of the country and the loss of their properties. However, the Dutch didn’t abandon the area, they built many windmills and with the use of it they managed to allocate the water, drying the ground and creating canals scattered in the whole country, in order to counterbalance between water and terrain. That’s why one can see everywhere in the Netherlands those beautiful windmills. That is also the reason that makes the Dutch the first in Water Management. Something more what a foreigner notices in the Dutch culture, is that the Dutch are very straightforward people, saying exactly what they think without hesitation. At the beginning, I was very often offended by the way the Dutch were speaking to me. Now, I am used to it and, as I am a spontaneous person myself, I adapted fast. This way of expression, I learned to appreciate while working in the Netherlands too. People will tell you what you do wrong, and what needs to be fixed, but also praise your good work. Still lots to learn about the Dutch and their culture as well as about my studies! If you want to learn more about my integration in the Netherlands, you may visit my blog: http://eftychia.weblog.tudelft.nl/. I will leave you for now to get back to work. Have a great and creative academic year!

7

TU Delft Nieuws

Current Affairs

Cindy Caljouw

8

Discover your opportunities At the ASML Inhouse Day If you are a technology graduate with high ambition, we would like to introduce ourselves to you. Our special Inhouse Day includes an opening by our SVP Technology Jos Benschop, one-on-one meeting, information market and of course we give you a unique view on our technology. We aim to give you a real feel of what it’s like to work here. Sound interesting? Sign up before 1 November, there are limited seats available.

Thursday 13 November 15.00h - 20.00h Transport to Veldhoven will be arranged!

www.asml.com/inhouseday

Eerstejaarsweekend Tom Brouws

Afgelopen augustus was het weer zover, bijna 200 enthousiaste nieuwe studenten kwamen ’s ochtends vroeg bepakt en bezakt aan op onze faculteit EWI, om daar aan een nieuw hoofdstuk van hun leven te

Ook wij kwamen die ochtend met onze tassen aan op EWI, zelf ook een beetje zenuwachtig, maar vol waardevolle kennis over het studeren, het studentenleven, de mooie stad Delft, onze studievereniging ‘Christiaan Huygens’ en het belangrijkste op dat moment: het eerstejaarsweekend! Aan ons de taak om de nieuwe studenten te helpen om de eerste stappen te zetten in hun nieuwe leven.

beginnen. Zenuwachtig schuifelden ze naar binnen, leverden hun tassen en telefoons in en trokken het mooie witte eerstejaarsweekendshirt aan, met daarop het thema van dit jaar: ‘Angry Nerds!’.

Association

Het is nog niet heel lang geleden dat ik zelf begon aan het avontuur dat studeren heet. Een jaar geleden stond ik op dezelfde plek, niet goed wetend wat zo’n eerstejaarsweekend eigenlijk allemaal inhoudt. Het zou één van de mooiste en leukste weekenden van mijn leven worden, vol activiteiten, gezelligheid, feestjes en vooral nieuwe vrienden. Juist om die reden was ik laaiend enthousiast toen afgelopen jaar de oproep werd gedaan om je in te schrijven als mentor voor het eerstejaarsweekend.

10

De eerste dag stond in het teken van de kennismaking. Uit eigen ervaring wisten we dat het erg lastig is om in die massa van vreemde dingen en mensen meteen aansluiting te vinden. Daarom volgden de mentoren hetzelfde programma als de eerstejaars, om ze een steuntje in de rug te geven bij het leggen van eerste contact met hun medestudenten, maar ook met de ouderejaars die aanwezig waren. Onder andere een rondleiding door de faculteit en een aantal groepsspellen stonden op het programma, waarbij uiteraard de befaamde OWEE-liedjes goed zijn geoefend. Aan het einde van de middag stroomde iedereen naar de bussen om af te reizen naar een prachtige locatie in Brabant, waar de rest van het weekend plaats zou vinden. Aan ons de taak om de nieuwe studenten te helpen om de eerste stappen te zetten in hun nieuwe leven. Het vermaak in de twee uur durende busreis werd verzorgd door de nieuwe bestuursleden van ‘Christiaan Huygens’, die allemaal iets origineels hadden bedacht om de eerstejaars goed kennis te laten maken met elkaar en het nieuwe bestuur. Zij zijn immers het komende jaar hét aanspreekpunt van de studievereniging en moeten een vertrouwde plek creëren voor alle nieuwe studenten. In de bus waarin ik zat werd een heuse bingo georganiseerd door Sander, de commissaris Public Relations. Alle eerstejaars én alle mentoren mochten om de beurt naar voren om een nummertje te trekken en iets over zichzelf te vertellen. Toen we uiteindelijk op de locatie aankwamen kende iedereen elkaar weer een stukje beter en zat de sfeer er goed in. Nadat iedereen zijn spullen had gevonden en een kamer had uitgezocht, konden we buiten genieten van een overheerlijke maaltijd bereid door de Wocky!.


‘s Avonds stonden leuke spelletjes op het programma, met onder andere het bier-bananenspel, levend Mario Kart en het smokkelspel. Ondertussen werd door de WIEWIE en de Wocky! in de kelder de voorbereidingen getroffen voor het feest van die avond. Met genoeg bier en fris en een gigantische geluidsinstallatie waren alle ingrediënten aanwezig voor een fantastisch studentenfeest! Menig eerstejaars én ouderejaars waagde een dansje op de dansvloer onder het genot van de muziek en een drankje. Het feestje duurde tot in de vroege ochtenduren, waarna de laatste feestbeesten volledig uitgeput hun bed opzochten. De nachtrust waar iedereen zo naar verlangd had duurde echter niet lang, in de vroege ochtend maakte de WIEWIE met luid kabaal de groep wakker voor ochtendgymnastiek. Zo konden we, sommigen nog een beetje beneveld, fris aan de nieuwe dag beginnen. De ochtend stond in het teken van sport en spel. Over het gehele terrein waren activiteiten opgezet, variërend van volleybal en trefbal tot een zeepglijbaan en watervoetbal. Het zonnetje scheen en het was een aardige temperatuur, dus iedereen kon wel van de buitenspelen genieten. Door de vossenjacht kon iedereen kennismaken met de verschillende aspecten van CH en de manieren waarop je jezelf kan ontplooien binnen de vereniging. Helaas sloeg het weer ’s middags om en moesten de poncho’s tevoorschijn worden gehaald voor de vossenjacht. De eerstejaars werden op pad gestuurd het platteland op, waar ze verschillende posten bezochten. Zo kwam elke groep langs een bouwplaats waar de FaCie bivakkeerde, om een vragenlijst in te vullen en foto’s te laten nemen voor het smoelenboekje. Zelf zat ik samen met andere leden van de eerstejaarscommissies op een plek in het bos, waar we elk passerend groepje wat vertelden over de ins en outs van de commissies. Dit sloot mooi aan op de bestuurspost, waar het nieuwe bestuur zat met interesselijsten voor de commissies en de collegeresponsiegroepen. Door de vossenjacht kon iedereen kennismaken met de verschillende aspecten van CH en de manieren waarop je jezelf kan ontplooien binnen de vereniging. De laatste avond was al weer aangebroken, met wederom een spetterend feest op het programma, maar niet voordat iedereen zich tegoed had gedaan aan een zelf gebraden stuk vlees op de barbecue. Die avond werd er (zover mogelijk)

nog harder gefeest dan de avond ervoor en het was goed te zien dat de eerstejaars zich steeds meer op hun gemak begonnen te voelen. Voor ons mentoren was het in ieder geval ‘missie geslaagd’! Helaas komt er een eind aan alle mooie dingen, zo ook aan dit eerstejaarsweekend. De wekker stond zondag iets later dan zaterdag, maar toen iedereen eenmaal wakker was moest er flink opgeruimd worden. Een laatste spel werd gespeeld, de tassen werden ingeladen en de terugreis naar Delft was al weer aangebroken. In tegenstelling tot de heenreis was er dit keer geen drukte in de bus, de meesten probeerden wat uurtjes slaap in te halen. Voordat we er erg in hadden waren we weer op EWI, wat toch echt het einde van dit prachtige weekend betekende. Maar wat het einde van een weekend was, was ook het begin van een fantastische week, de OWEE! Ook die week was een avontuur, maar dat is een verhaal voor een andere keer. Terugkijkend op het weekend heb ik misschien wel meer plezier gehad dan op ‘mijn’ eerstejaarsweekend. Het was fantastisch om nieuwe studenten wegwijs te maken en ze te laten zien hoe mooi en leuk het studentenleven is. Nu het academisch jaar weer begonnen is, zie ik ze hun eerste stappen zetten als echte student en besef ik me hoe hard de tijd gaat als je plezier hebt. Wellicht lees ik volgend jaar in de MaCHazine wel over hun ervaringen als mentor.

Association 11


Eerstejaarsweekend Reünie

Association

Tom Harting

12


LedenlunCH

IFF

Joep Bom

Daniël Swaab

Het was alweer zover, de eerste LedenlunCH van het studiejaar.

Salsa Tequila! Een geweldige zomerhit waar onder andere het woord

Onbeperkt genieten van vers brood, heerlijk beleg en meer voor het

tequila in bevat. Muziek en drank, oftewel een feestje! Naast de vele

symbolische bedrag van een euro. Vele CH-ers hapten dan ook toe op dit

serieuze activiteiten die onze studievereniging natuurlijk organiseert,

heerlijke aanbod. Om de drukte voor te zijn, lagen er zelfs twee enthousi-

is het af en toe ook goed om te kunnen ontspannen door een feestje te

aste twaars te campen voor de ingang van de /Pub. Het leek wel alsof de

organiseren.

nieuwe iPhone 6 verkocht werd.

Om een goed feest te kunnen neerzetten, heb je natuurlijk mensen nodig. Nu is W.I.S.V. ‘Christiaan Huygens’ van oorsprong niet één van de grootste studieverenigingen (maar natuurlijk wel de mooiste studievereniging). Om deze reden is er een aantal jaar geleden het IFF opgericht. IFF is een afkorting voor ‘InterFacultair Feest’. Dit houdt in dat we samen met andere Delftse studieverenigingen die relatief weinig leden hebben een feest organiseren. Dit zijn de studieverenigingen die meedoen aan het IFF: LIFE, ETV, MV en Froude. Vanuit elk bestuur helpt 1 persoon mee met het organiseren van het feest.

Toen de pauze begon, daalden de studenten met bosjes de trap af. En wat was het druk! Voor degene die zijn kaartje niet voor de lunCH gekocht had, moest dan ook waCHten totdat het bestuur wist of er uberhaupt nog plek was. Nadat iedereen zijn plekje gevonden had, kon het smulfestijn beginnen. Het thema van de lunCH was: ‘Tijd voor een beloning, kom eten als een Koning!’, en dat is precies wat er gebeurde. Er werd genoten van het koninklijke buffet als nooit

Op woensdag 24 september was het dan zo ver, het IFF ging beginnen! Het grandioze thema luidde als volgt: “Met je sombrero op je kont, schiet de maffia tequila in je mond, berijd je kameel als een beest de oase rond, snuif het zout van de grond en beleef een zure avond!”

Naast de trouwe ouderejaars en ereleden waren er ook opvallend veel sjaars aanwezig. Deze konden hun ogen en smaakpapillen niet geloven. Naast het gebruikelijke lekkers stonden er namelijk ook sCHalen vol met koekjes op de bar, die goed in de smaak vielen. Menigeen rende, misselijk van de koekjes, in de riCHting van de wc, om vervolgens weer terug te keren voor meer koekjes. Er werd ook zeer vrij geëxpirimenteerd met koekjes. Boterhammen met CHocoladekoekjes en kaas, kartoffelsalat met lange vingers, ieder zijn eigen ding. Ook werd er melk geadt, appelsap gezopen en sinaasappelsap getankt. Na het bunkeren droop iedereen verzadigd af riCHting de collegezalen. Velen hadden nog een flinke verzameling koekjes bij zich om na te genieten. Ook dagen later had CH nog genoeg koekjes voor bij de thee en koffie. Al met al, was het een zeer geslaagde lunCH.

Association

tevoren. Broodjes werden rijkelijk belegd en er werd hard gesocialized.

Alles en iedereen: van Maffia tot Mexicaans, en van palmboom tot beest kon komen en de sombrero’s dansten door de lucht. De voorbereidingen waren soepel verlopen en om 10 uur ‘s avonds werden de deuren bij de Lorre geopend. De organisatie van het IFF was mooi verkleed en had al een voorproefje van de tequila in de loop van hun pistool, want wat is nu een feest zonder welkomstdrankjes? Door de avond heen liepen er dames rond met dienbladen vol zout, citroen en tequila. Er werd door hen ook goed uitgelegd hoe het drinken van deze drank behoort te gaan. Doordat deze welkomstdrankjes met open armen ontvangen werd raakte de zaal al lekker vroeg in de avond los. Er waren verschillende DJ’s die heerlijk hebben gedraaid, maar de voornaamste en bekendste was natuurlijk DJPJ! Met hem achter de draaitafel stond de hele vloer te springen en was het feestje niet meer te houden. Het was dan ook niet voor niets dat het feest halverwege de avond uitverkocht was. Tijdens het feest werden er nieuwe contacten gelegd, ontstonden er waterpistool gevechten, maar jammer genoeg kon het feest niet voor altijd doorgaan. Om 4 uur ’s nachts was het IFF afgelopen en moest iedereen naar huis. Gelukkig hebben een groot deel van de mensen het feest tot het einde bijgewoond. Het was een geslaagd feest en tot volgend jaar!

13


Gala Stefanie Vonk

Je komt om 2 uur s middags uit je bed rollen, kijkt in de spiegel en ziet nog restjes make up op je gezicht zitten, je haar nog half in de krullen. Je herkent nog een vage schim van hoe geweldig je er gisteren uitzag. Voor de mannen onder ons... Je kijkt in de spiegel en je kunt eigenlijk alleen nog maar dromen over die knappe date van gisteravond. Dit is waarschijnlijk hoe jij je de dag van 29 november gaat voelen, want vrijdag 28 november staat er iets heel gaafs te gebeuren, maar let op, het is ... For your eyes only! Op deze dag zal er op een unieke locatie in Rotterdam de skyfall worden bewonderd. Voor wie nog steeds niet door heeft waar het over gaat: op 28 november zal er in club Eclipse een gala plaatsvinden met als thema ‘Skyfall. For your eyes only!’. Tijdens dit gala zal er een Big Band aanwezig zijn om iedereen te voorzien van de juiste muziek en afsluitend een dj om helemaal los te gaan. Een advies aan de dames, is om een paar ballerinas mee te nemen, want om het allemaal nog wat specialer te maken, stijgen we tot grote hoogte in Club Eclipse naar de koepel. Kijkend naar de sterren, ga je de mooiste avond van het jaar beleven. Voorafgaand aan het gala is er de mogelijkheid om te genieten van een hapje en een drankje tijdens het galadiner en is er na afloop de mogelijkheid om met de bus terug te gaan naar station Delft. Dit alles tegen zeer scherpe prijzen, zoal jullie van CH gewend zijn.

Galakaarten

Association

Ben jij eerstejaars (of niet) en wordt dit jouw eerstestudentengala, dan ben je waarschijnlijk nog in de veronderstelling dat je jouw eindexamenpak nog aan kan. Hoewel wij dit als James Bond fans natuurlijk zeer kunnen waarderen, is het gebruikelijk voor studentengala’s dat de heren in rokkostuum verschijnen. Wij bieden jou de mogelijkheid om voor maar 135 euro zo’n rokkostuum te bemachtigen, dit kan op vrijdag 31 oktober van 12:30 tot 13:45. Voor de dames is een lange galajurk gewenst. Benieuwd naar nog meer etiquette, zoals het vragen van een date, taart eten en horloges dragen, wel of niet, kijk dan op wisv.ch/gala!

Dansworkshop Na het aanschaffen van een rokkostuum, kun je gelijk door naar de dansworkshop. Leer hier alvast wat goede dansskills zodat je tijdens het gala je date kunt verbluffen. Van 14:00 tot 15:00 kun je bij Dansschool Wesseling je dansskills opvijzelen en misschien zelfs al een leuke dansende date scoren, dubbel prijs dus! De dansskills komen daarnaast goed van pas als de Big Band hun nummers speelt. De workshop is zowel toegankelijk voor mannen als vrouwen.

Cocktailworkshop Als echte James Bond, weet je vast al hoe je een heerlijke cocktail kunt maken. Stirred, not shaken. Of was het nou juist Shaken, not stirred? Ik ben er nog niet helemaal over uit, jij wel of heb jij ook nog een workshop nodig, kom dan naar de cocktailworkshop op 22 oktober vanaf 18:00. De kosten voor het deelnemen aan de workshop bedraagt €5, inclusief 3 zelf bereidde cocktails. Aansluitend aan de workshop is er de mogelijkheid om te eten. Dit zal een verzorgd tapasmenu zijn en zal slechts 10 euro per persoon kosten. De cocktailworkshop is alleen toegankelijk voor 18+. Kort samengevat:

Voor het gala alleen, en dat is dus onbeperkt drank, hapjes, foto’s en een kleine verrassing, betaal je slechts 60 euro per paar. Wil je ook nog wat eten vooraf en daar bedoel ik mee: een heerlijk driegangendiner met een drankje, koop dan ook gelijk kaarten voor het diner. Deze kosten slechts 30 euro extra per paar. Er is maar een beperkt aantal plaatsen voor he diner beschikbaar, dus wees hier snel bij. “Now put your clothes back on and I’ll buy you an ice cream.”

Cocktailworkshop Woensdag 22 oktober vanaf 18:00 uur €5 (+ €10 voor tapas achteraf) Pasdag Vrijdag 31 oktober van 12:30 tot 13:45 uur

(For your eyes only)

Wil je er zeker van zijn dat je terug in Delft komt na het gala, koop dan ook gelijk een busticket. Deze zijn 10 euro per paar. Ben je er nog niet zeker van dat je samen met je date naar huis gaat, dan kun je ook een los busticket kopen. Al deze kaarten zijn verkrijgbaar via wisv.ch/gala, het bestuur of natuurlijk de galacommissie zelf.

14

Pasdag

Dansworkshop Vrijdag 31 oktober van 14:00 tot 15:00 uur €1 Gala Vrijdag 28 november vanaf 22:00 uur vanaf €60


Delfts Kampioenschap Programmeren Rebecca Jacobs

Zaterdag 27 september was het weer tijd voor het Delfts Kampioenschap Programmeren, oftewel het DKP! Om 10 uur ’s ochtends stonden de deelnemers al enthousiast voor de deur van de Drebbelweg te wachten tot ze naar binnen mochten. Om 11 uur stipt klonk het startsein en werd het direct even stil. De deelnemers moesten onder het genot van een

Toen iedereen de spullen bij elkaar had geraapt en alles had afgesloten, verhuisde men van de Drebbelweg naar de /Pub, voor de prijsuitreiking. Tijdens de prijsuitreiking bleek dat Fox IT dit jaar het beste bedrijventeam was, en dat de eerste prijs voor de studententeams ging naar team Zodiac. Dit was een extra speciale overwinning, omdat team Zodiac alleen bestond uit Jorn Hoofwijk, eerstejaars TW&TN, de in zijn eentje maarliefst 5 opgaven had opgelost! Van harte gefeliciteerd Jorn! We gaan vast en zeker nog meer van jou horen op het aankomend BAPC. Na de prijsuitreiking was er nog een gezellige borrel, waar even rustig kon worden nagepraat over de precieze interpretatie van de verschillende opgaves.

handje pepernoten de opgaven bekijken en analyseren. De stilte duurde niet lang, binnen 5 minuten werd er al druk overlegd. Er werd besproken wie precies welke opgave ging oplossen en binnen een kwartier kwam de stroom aan oplossingen langzaam maar zeker op gang. Als een opgave correct was opgelost, dan zorgde de organisatie er voor dat het betreffende team een prachtige gekleurde ballon kreeg, zodat de rest van de zaal ook kon zien hoe ver de concurrentie was. Als je even niet uit een opgave kwam, kon je naar de lunchtafel lopen, waar onder andere heerlijke broodjes Leo waren, alsmede een gigantisch grote slagroomtaart, verzorgd door Technolution. Naast alle studententeams die streden om de eer, waren er ook twee bedrijventeams die vochten om de titel “Beste Bedrijventeam”, een team van Fox IT en een team van Alten. Om 3 uur werd het scorebord bevroren, want hoewel de deelnemers nog een uur hadden om opgaven in te leveren, kon men nu de concurrentie niet meer bijhouden. Vlug werd er nog geprobeerd om dat ene probleem nog even op te lossen, om die ene oplossing nog te tweaken zodat je onder de time-limit error uitkwam en om net nog wat puntjes binnen te sprokkelen voor het eindsignaal. Toen om 4 uur het eindsignaal klonk, waren alle teams toch een beetje teleurgesteld, het was dit jaar een pittige opgaveset. Desondanks heeft elk team het toch weten te presteren om minstens één opgave op te lossen, waarvoor chapeau!

Al met al was het wederom een geslaagd DKP, en we willen graag alle sponsoren, jury en de rest van de organisatie bedanken voor de hulp, en natuurlijk de deelnemers bedanken voor alle inzet. Wij hopen alle deelnemers van het DKP 2014 volgend jaar terug te zien op het DKP 2015. Verder gaan we ervan uit dat er volgend jaar ook weer een flink aantal nieuwe deelnemers zal zijn, die de strijd aan zullen gaan om de titel “beste programmeur van Delft”. Ook wensen we alle Delftste teams die mee zullen doen aan het BAPC, wat dit jaar plaats zal vinden in Eindhoven, veel succes. Hieronder staan de uiteindelijke scores van de deelnemende studententeams. Aan de linkerkant staat de plaats en de teamnaam en aan de rechterkant de naam van de opgeloste opgaven. 1. Zodiac A, B, D, F, G 2. Team Integer A, F, J 3. Glashard A, F 4. Phoenix A, F 5. Frontpage F 6. Anders gaat ons verwerkingssysteem over de zeik F 7. 57 – The odd boys F 8. RolfNotFoundException F 9. Pils Cobra’s F 10. Bioshock F 11. Mooiboy81 F

15



Section 17


Eerstejaarsblog Informatica Danique Lummen

Daar sta je dan als kersverse sjaars. Je tas is nog net niet zo zwaar als toen je een brugklasser was, maar ergens in je achterhoofd voel je je toch wel weer een klein beetje de ‘brugsmurf’. Gelukkig valt dit in werkelijkheid wel mee en na een dag vol informatie en presentaties van onder andere de decaan kan het ‘echte’ studeren dan eindelijk beginnen.En dan

Naast alle struggles van een nieuwe stad, op kamers gaan en al het feesten moet er ook nog gestudeerd worden. Hé wat jammer nou, want studeren is een feestje, calculus is geweldig en computerorganisatie is ontzettend makkelijk te begrijpen (voel je het sarcasme?). Maar er zijn ook leuke dingen, zoals de lichaamsbeweging die we krijgen bij computerorganisatie. Wil je die bonuspunten dan zal je toch echt wel wat meer moeten doen dan alleen het goede antwoord geven. Dit antwoord moet namelijk op het bord, en laat je nou alleen via een aantal acrobatische bewegingen lopend over stoelen en tafeltjes bij het bord kunnen komen.

begint het studeren ook direct, want rustig aan beginnen staat blijkbaar niet in het Delftse woordenboek. Dinsdagochtend kwart voor 9: in een sneltreinvaart door heel je 6vwo wiskunde heen bij het geweldige vak calculus, om vervolgens door te gaan bij OOP met een spoedcursus Java voor dummies. Gelukkig bestaat het studentenleven voor een nieuwe sjaars niet alleen uit studeren, maar vooral ook uit feestjes! Want hoe leuk is het om op maandagavond door je mentoren meegesleurd te worden naar de constitutieborrel van het nieuwe bestuur, om dan maar meteen haarfijn uitgelegd te krijgen wat brassen is en hoe het werkt (wat was ik blij dat ik die ochtend geen jasje had aangetrokken). Twee dagen daarna zaten voor de allereerste keer in de /Pub en leerden we adten op de echte Delftse manier.

Association

Maar voor deze allereerste collegeweek begon hadden we nog de geweldige OWee en het EJW. Aan het EJW heb ik geweldige herinneringen, want wie vindt ochtendgymnastiek om 9 uur in de ochtend na een avond met te veel bier niet geweldig? Of proberen schoon te blijven terwijl je door een modderig weiland rent (hint: dit lukt niet)? En na het EJW gingen we meteen door naar de OWee, waar je op maandagochtend je hele stem kapot schreeuwt en de rest van de week meer dan 4 doosjes keelpastilles erdoorheen werkt om nog maar een beetje normaal te kunnen praten. Dan pas leer je het echte studentenleven in Delft kennen. Voor een meisje uit Tukkerland is het hier in Delft echt een cultuurschok. Ineens moet je opletten of er geen tram aankomt en krijgt de zin “Ik moet een fiets regelen” een compleet andere betekenis dan dat die eerst had. Daarnaast moet je ook nog eens op kamers, want 4 uur heen en terug iedere dag is niet te doen. Je moet ook zelf maar je eigen eten proberen te koken, met de nadruk op proberen, want het brandalarm laten afgaan en de brandweer moeten bellen omdat je niet weet hoe het brandalarm weer uit moet valt niet onder de categorie ‘geslaagde poging tot koken’. Naast het grote probleem genaamd koken moet je óók nog eens je eigen was gaan doen. Dat is ook geen groot succes, want dan krijg je van die leuke telefoontjes naar je moeder: “Ja eh.. Mam… SOS. Hoe werkt een wasmachine?”.

18

En de feestjes blijven maar komen en komen. Losgaan in je dieren onesie bij het IFF om dan vervolgens de volgende ochtend wakker te worden met de meest rare dingen op je voorhoofd geschreven in watervaste stift. Geloof me: watervaste stift krijg je niet zomaar van je gezicht af, dus de volgende ochtend zat ik met tekeningetjes op mijn gezicht doodleuk weer bij calculus. Als mijn eerste weken een voorbode zijn voor hoe de rest van mijn jaar eruit moet gaan zien heb ik straks een haat-liefde verhouding met calculus, breek ik mijn been bij computerorganisatie, moet ik misschien maar brandblussers gaan kopen en krijg ik een fobie voor mensen met watervaste stiften. Kortom, ik wil het voor geen goud missen!


Eerstejaarsblog Dubbele Bachelor Maaike Mol

De eerste weken van mijn leven als sjaars, tja, wat zeg je daarop. Terugkijkend op het eerste octaal, denk ik toch wel: druk druk en nog eens druk. Inleveropgave hier, toetsje daar, huiswerk maken tot laat op de universiteit of in de UB. Tja het leven van een dubbele bachelor student is nu eenmaal niet heel rustig, maar wel héél erg leuk. Ik ben Maaike Mol en ik studeer dus Technische Wiskunde en Technische Natuurkunde hier in delft, net begonnen aan mijn eerste jaar als student. Na het eerstejaarsweekend en de OWee, die allebei echt te gek waren, was ik erg blij dat ons mentorgroepje bij elkaar kon blijven. Ik had het niet beter kunnen treffen. Heel erg bedankt Dieuwke en Nelleke en de rest voor alle gezelligheid! Dan heb je toch een beetje houvast aan elkaar, zo na de langste vakantie van je leven moet je opeens weer naar school (de uni dan nu). Je moet weer opnieuw wennen aan het ritme en aan het studeren zelf, maar ook aan de nieuwe mensen om je heen. Ook aan de nieuwe stad Delft en het treinen moet je gewend raken. Naarmate de tijd verstrijkt, leer je steeds meer mensen kennen, raak je vertrouwd met ze en voel je je zo ook steeds meer thuis op EWI en op TNW en in heel Delft. Na een week of twee gaat het eigenlijk al vanzelf.

De natuurkunde vakken zijn een stuk moeilijker en vergen ook wat tijd van je. Zeker om met een heel nieuw programma zoals Matlab te gaan werken (op een laptop die je pas 5 weken nadat je hem hebt besteld krijgt van de TU, duurt lang), vergt wat energie van je. Elke week een bonustoets is vermoeiend, gelukkig is de stof wel interessant. Dat houdt het een beetje in evenwicht. De lunchpauzes waren wel een grote vraag, hoe vul je die in. Eén heel uur niks doen is niets voor mij. Lunchen met vrienden is ook heel gezellig, maar je probeert je tijdens de lunches ook nog een beetje nuttig te maken. Toen kwam CRW om de hoek kijken, gratis lunch om te praten over de kwaliteit van het onderwijs, waarom niet. Achteraf ben ik blij dat ik ervoor gekozen heb om het te doen, want het is ook nog eens erg gezellig. Ook af en toe naar een ledenlunch is erg fijn. Bij beide hoef je je eigen brood niet te smeren, wat natuurlijk ideaal is. En zo probeer ik elke dag met mijn lunches wel iets te doen.

Ik voetbal daarnaast thuis nog drie keer in de week en heb een seizoenskaart voor Feyenoord. In de eerste week van september heb ik ook nog eens mijn rijexamen gehaald, dus daar wordt nu ook optimaal van geprofiteerd, voor zover dat kan, want als 17 jarige mag je alleen onder begeleiding van bijvoorbeeld je ouders rijden. Ik probeer ook af en toe een concert mee te pakken. Je oude vrienden van de middelbare school worden ook niet vergeten. Als het even kan spreek je dan nog af omdat je elkaar natuurlijk veel minder ziet dan de voorgaande jaren. Tijd voor leuke dingen moet je vrijmaken, dat gebeurt ook zeker. Als het combineren maar goed gaat, heb je de tijd van je leven.

Association

Vol goede moed begon ik aan m’n dubbele studie, benieuwd wat ik allemaal voor colleges zou krijgen. De eerste colleges gingen me dan ook prima af. De wiskundevakken Caleidoscoop en Wiskundige Structuren vind ik heel erg leuk en zijn (tot nu toe) nog prima te volgen. Voor Caleidoscoop sta ik zelfs een 9,6 op de helft van het vak (yes!). Het is wel heel bizar dat je bijvoorbeeld opeens moet bewijzen dat 1 > 0, tja, dat ziet toch iedereen.

De studie is tot nu toe nog goed te doen, maar genieten doen we ook. Natuurlijk was ik ook aanwezig bij de commissieïnteresseborrel en de EJW-reünie. De EJW-film was echt geweldig, heel leuk om het eerstejaarsweekend weer te beleven door de ogen van de camera. Van veel dingen in de film wist ik niet eens dat die gebeurd waren. En natuurlijk was het handig om naar de borrel te gaan om je op te geven voor commissies. Het IFF had ik helaas gemist doordat ik nog geen 18 ben. Uiteindelijk was het ook maar goed dat ik er niet bij was, want de volgende dag hadden de meeste van mijn medestudenten goede hoofdpijn en lagen er een paar zelfs te slapen in de collegezaal, ehe oeps.

Zo weer denkend aan dit allemaal ben ik ervan overtuigd dat ik de juiste keuze heb gemaakt. Ik verveel me geen minuut en ben heel blij dat ik hier mag zijn. Ik ben helemaal thuis in Delft en geniet met volle teugen van het leven als student!

19


Context-Based Spelling Correction for Context-Based Spelling Correction for the Dutch Language: Applied on the Dutch spelling errorsLanguage extracted from the Dutch Wikipedia revision history Lars Tijhuis

Lars Tijhuis

When using a spellchecker on a piece of text, the spellchecker is given

Spelling error?

Preprocess and tokenize

Text

the task of finding misspellings and to supply the correctly spelled word

Per token No, skip

Yes

given a misspelling. In this article we will give a brief introduction on

Candidate Suggester(s)

Candidate Ranker

Annotated text

how this task is performed using the context in which words appear. Figure 1: The process of spellchecking a piece of text.

Why context-based?

Computer Science

A straightforward approach to finding misspellings is to check for each word if they are present in a dictionary; if a word is not in the dictionary, the word is erroneous. Given this erroneous word, it is the objective of the spellchecker to determine what word is most likely meant to be typed. Different approaches are used in order to find candidate replacement words and to find which of these candidates is the correctly spelled one. Unfortunately, language is an always evolving concept and a dictionary containing all words and their different word forms becomes larger and larger. With each addition, it becomes more likely that a misspelling of a word results in a different word that is also in the dictionary. How could we possibly detect such a misspelling? Take for example the word “loopt” (walks). A simple misspelling would be to replace the letter l by the letter k, resulting in the word “koopt” (buys). One can imagine this typo could occur, because on the most commonly used QWERTY -keyboard the letters l and k are right next to each other. To people, the word “koopt” looks like it is properly spelled and since it is also in the dictionary, a spellchecker would not be able to tell that in fact “loopt” was meant to be typed. Now, when we add context to the word, we get for example the sentence “De jongen koopt naar zijn huis.” (The boy buys towards his house.). A person would immediately be able to tell that “koopt” in fact should be “loopt” as she is taking the context into account. A spellchecker should thus do the same; it should check the correctness of words in their context.

w

s

Noisy channel

Text

… s ...

s → w?

Spellchecker

Figure 2: The objective of the spellchecker in the noisy channel model.

The noisy channel model Introduced by Kernighan et al., the noisy channel model is a model that assumes a user knows what word w to type, but because of noise between the user and the input mechanism, it results into the word s being added to the text [1]. With the text as input, the misspelled word s is thus observed by the spellchecker. As illustrated in figure 2, the objective now is to find the corrected word w ˆ given s such that: w ˆ = argmax P (w|s)

(1)

w∈V

P (s|w)P (w) P (s)

(2)

= argmax P (s|w)P (w)

(3)

= argmax w∈V w∈V

General approach spellchecking First, let us take one step back and take a look at what steps are taken in the process of correcting spelling errors. We identify the following tasks: 1. Error detection, 2. For each error found: (a) Candidate generation,

(b) Candidate ranking.

Those steps can be seen as a pipeline, where the output of one task is the input for the next one, as illustrated in figure 1. Let us first introduce a model with which we approach the task of correcting an error, before we explain how to detect them.

20

User

Here, V is the set of candidate words that might replace s. This set is often referred to as the confusion set of s and consists of words that are very similar to s or for example have the same phonetic sound. We thus want to find the word in this set that is most likely to be the correct word, given word s. Equation (2) follows from Bayes’ theorem. In equation (3) the P (s) term is removed, as this is the same for every w. The different terms in the resulting equation can be interpreted as follows: • P (s|w) is the error model; It is a formal notation of the question “How likely is it that s was typed by mistake, when w was intended?”, • P (w) is the language model (LM); It is a formal notation of the question “How likely is word w to appear in a piece of text?”. Both probabilities can be found using different methods. We will explain the approach we have used.


The error model To find a measure for how likely a word w was meant to be typed instead of the observed word s, we want to know what kind of spelling errors occur more often. We found this distribution using the revision history of Wikipedia. In the numerous revisions of the different articles, we identified spelling errors made, that were later corrected. We did so by looking at small changes between two article revisions. By extracting these erroneous-corrected word pairs, we found a large set to build a model from. Using these pairs, we would find a measure for the error model using the following approach: • For every error-correction pair, we would find the edit operations O needed to go from the erroneous word to the corrected word. These edit operations can be insertions, deletions, substitutions, and translations of characters. • For every operation o ∈ O, we stored both the original character, and replacement character. For translations, these are two characters. • Furthermore, we stored the N surrounding characters in the original word as the character context in which the edit occurred. After gathering all edit operations with their context, we find the probabilities of these edits to occur. For this, we define the edit operation α → β. The probability of this operation is found by counting the occurrences of the original string, and the number of times it was replaced by the resulting string: P (o) = P (α → β) =

C(α → β) C(α)

(4)

For the count of α, we used the full sentences in which we found the spelling errors. To find the probability P (w|s), we now determine what edit operations O are needed to turn s into w and multiply the probabilities for these operations: ∏

P (o)

(5)

o∈O

The language model A simple measurement of how likely words are to appear in a piece of text, can for example be calculated by taking large amounts of text and simply counting the number of times w occurred compared to the total number of words N : P (w) =

C(w) N

However, we would like to take the context in which the word appeared into account. We thus have to find a measure for how likely the word w is to be found given the surrounding words. The model used by Mays et al. stores n-grams and the probability of these n-grams occurring in text [2]. An n-gram is a sequence of n words. If such a sequence is often found in texts, the probability of the corresponding n-gram is high. The probabilities are trained by taking large amounts of texts and then count how often every n-gram occurs. Using this model, we can find the probability of some word wn occurring after words w1n−1 = w1 , w2 , . . . , wn−1 occurred, notated as: P (wn |w1n−1 ) If we would be using all of the words in the sentence that occurred before wn to find this probability, the whole sentence would have to be part of our language model. Because language is unlimited in the amount of sentences that can be created, such a language model cannot be created. In practice, we therefore only look at n-grams with a limited n. To explain the concept of

P (wn |w1n−1 ) ≈ P (wn |wn−1 ) This probability can easily be computed given the counts of the bigrams in our model, by taking the times wn−1 was found, and how many times it was followed by wn : C(wn−1 wn ) P (wn |wn−1 ) = C(wn−1 ) For a given sentence w1n , we can now compute the probability in the following way: P (w1n ) = P (w1 ) · P (w2 |w1 ) · . . . · P (wn |wn−1 )

(6)

By calculating this probability for every w ∈ V , we can rank the candidate words on their likeliness in the given context.

Error detection Now that we have introduced our language model, we can explain how we use it to detect errors like the one from the example in the introduction. To do so, we find the confusion set V for the word under inspection. Using the language model just described, the probability for the sentence using each word in V can be determined. If it turns out that a word in V is more probable in the given context than the current word, we can say that the word appears to be erroneous in their context. However, this could lead to a high number of false positives. Therefore, we favor the original word over its alternatives using a parameter α, which is the a priori belief that this word is correct. We multiply the probability of the original word with this α and divide the remaining weight over the candidates. In this way we can control the balance between finding more errors and the number of false positives.

References

Computer Science

P (w|s) =

using an n-gram model to compute the probability of a sentence, we now look at 2-grams, or bigrams. Because we cannot take the whole previous history into account when looking at the context, we make the Markov assumption. This assumption means that we only take the previous state into account; we assume that the next state only depends on this state. In an n-gram, the previous state is the combination of n − 1 words that precede the n-th word, being the next state. With this assumption, we get the following approximation for bigrams:

[1] Mark D. Kernighan, Kenneth W. Church, and William A. Gale. A spelling correction program based on a noisy channel model. Proceedings of the 13th conference on Computational linguistics, 2: 205–210, 1990. [2] Eric Mays, Fred J. Damerau, and Robert L. Mercer. Context based spelling correction. Information Processing & Management, 27(5):517–522, 1991.

Lars Tijhuis is a recently graduated computer science student. During his thesis project he has found his enthusiasm for working with data and statistics. After his travel to South America he hopes to start working in the field of Enterprise Architecture or some other field where he can do cool analyses!

21


Towards a Social Web based solution to bootstrap Towards a Social Web based solution to bootstrap new domains in new domains incross-domain cross-domain recommendations recommendations Martijn Rentmeester

Martijn Rentmeester

When a new domain of items is added to a cross-domain recommender system, knowledge about users’ preference towards the newly added items lacks and therefore recommending these items is not so straight

As one can already see, one of the problems related to the content-based method is its limitation in recommending serendipitous items. It recommends items very similar to the one that is already preferred by the user. Is that useful? Would the user not be able to find that item herself? Therefore most often the collaborative filtering method is preferred.

forward. For my master thesis I researched this problem and proposed a

Cross-domain recommender systems

new solution.

In the examples given above, items are recommended from a single domain. Currently, most recommender systems only recommend items from a single domain, e.g. Netflix only recommends videos and Last.fm only recommends music. However, humans preferences may span across multiple domains. Cross-domain recommender systems are a class of recommender systems that specializes in recommending items across multiple domains. An example of a cross-domain recommender system is the e-commerce website Amazon.com, where users are recommended e.g. DVDs, music, books and video games. Also in cross-domain recommender systems, recommendations can be computed using the content-based method or using collaborative filtering. However, using these methods in a cross-domain recommender systems adds extra complexity. First, when one wants to use the content-based method, one faces the problem that items across domains do not have a lot of overlap. For example, items in the domain books are described quit different from items in the domain toys. Therefore it makes it much harder to use this method in the cross-domain setting. The collaborative filtering method still works the same, except that when one wants to compute cross-domain recommendations one needs to have at least one user that has expressed its preference for items in multiple domains. Lets consider as an example a recommender system that can recommend both movies and books. One of the users in this recommender system is Alice that prefers the book ”Harry Potter”. Another user is Bob, that prefers the book ”Harry Potter”, but also prefers the movie ”The Lord of the Rings”. Using collaborative filtering, we can recommend Alice the movie ”The Lord of the Rings”. See also figure 1.

Computer Science

Recommender systems are systems that produce personalized recommendations as output or have the effect of guiding the user in a personalized way to interesting or useful items in a large space of possible options. These recommender systems were introduced a couple of decades ago to help humans in information seeking tasks cope with the information overload that arose because of the enormously growing amount of digital information. The basic building blocks of a recommender system are items and users. Items are the objects in the recommender system that can be recommended such as a certain video on YouTube. Users are the humans that make use of the recommender system and recommended items. Using these building blocks, recommendations can be computed in two different ways, using the so-called content-based method or using collaborative filtering.

Content-based vs. Collaborative filtering In the content-based method the user is recommended items that are similar to the items for which is known that the user prefers them. Lets consider the following example. In a book recommender system, one of the users expressed its preference for the book ”Harry Potter and the Prisoner of Azkaban”. To compute recommendations for this user, the recommender system is looking for the most similar items to the book ”Harry Potter and the Prisoner of Azkaban”. Lets consider that the recommender system also contains the item (read: book) ”Harry Potter and the Chamber of Secrets”. This item is very similar to the item ”Harry Potter and the Prisoner of Azkaban”, therefore it is recommended to the user. So, for this method, we need to know the preferences of one user and information of all the items in the recommender system. In the collaborative filtering method the user is recommended items that are preferred by a similar user. Lets consider as an example a book recommender system. In this system, one of the users, called Alice, expressed its preference for the book ”Harry Potter and the Prisoner of Azkaban”. Another user, called Bob, expressed its preference for the book ”Harry Potter and the Prisoner of Azkaban” and for the book ”The Hunger Games”. Now, when Alice wants to get recommendations, the system computes the most similar user instead of the most similar items. In this case, the most similar user is Bob, because both like the same book. Now the recommender systems looks which items are preferred by Bob that are not seen yet by Alice. In this case it is the book ”The Hunger Games”, and therefore this item is recommended to Alice. So, for this method, we need to know the preferences of multiple users, while information about the items is less relevant.

22

Figure 1: Collaborative filtering in a cross-domain setting

The problem of bootstrapping a new domain The problem researched in this thesis arises when a new domain is added to a cross-domain recommender system. In that situation, we do not know


the preferences of users in that new domain and as such can not use the collaborative filtering method anymore to recommend items from that new added domain. The content-based method is also useless as we saw earlier and therefore I proposed a new solution, being the first to tackle this problem.

Proposing a new Social Web based solution The proposed solution uses the Social Web. The Social Web is a set of social relations that link people through the World Wide Web [1]. In this Social Web, users express their preferences for items. For example on Facebook one can express its preference for books and videos. Users that express their preference for items from both domains create a relation between items from both domains. These relations can be used to bootstrap newly added domains in another cross-domain recommender system. Therefore the information needs to be transferred from an auxiliary Social Web system to the cross-domain recommender system in which a newly added domain needs to be bootstrapped. How this information can be transferred is the real underlying problem that I researched during my thesis.

Case study

Figure 2: The proposed model applied in a case study on the Open Images dataset using YouTube as auxiliary Social Web system To measure the performance of this new proposed model, we set up a user study in which we compared our model to random recommendations and to recommendations that are computed using tags. Tags are more often used to compute cross-domain recommendations and are a good way to create relations between items from multiple domains. However, we did not use them to solve

In the user study we did a pairwise comparison. We showed one video at a time to the user and showed them two top-5 lists of recommendations, computed using different methods. Then we asked the user which recommendations she prefers, given the showed video. Doing this for multiple videos and multiple combinations of methods, we got a lot of datapoints. Analyzing the gathered data, we found that the recommendations computed using the tag-based method where preferred most often, followed by the recommendations computed using my model. The recommendations that were preferred the least were the random recommendations.

Conclusion The problem we encountered during this thesis was that the related videos on YouTube were computed content-based for the videos that we had. This took away the advantage of relations between items based on user preferences. Therefore for a news item about the Vondelpark we got a documentary about the Vondelpark as recommendation. We could have got this recommendation also using the content-based method instead of my model. So in order to apply the new proposed model successfully, one has to have a dataset with popular videos to increase the chance that the same video on YouTube is watched in the last 24 hours. This is the hypothesis that needs to be tested in future work to see if in that case the related videos are still content-based or not. Another thing that we found is that the item sets in the different systems needs to be very similar. An example of one thing we encountered is that the YouTube video ”Koning opent koningsspelen in Ede” is coupled to the Open Images video ”Keizer bolling met de krulbol”. The reason is that the latter is the most similar video in the Open Images dataset. One possibility is to solve this using a threshold, however, in the case study this would have let to no recommendations for most Open Images videos. So, we were the first to come up with a possible solution for the described problem. This has let to some first insights1 , but more research is needed to give some definite conclusions.

References [1] Appelquist, D., et al. A Standards-based, Open and Privacy-aware Social Web 2010 [2] Davidson, J., et al. The YouTube video recommendation system 2010

Martijn Rentmeester started his Computer Science study in 2006 at Delft University of Technology. He got his MSc. diploma in August 2014, after graduating at the Web Information Systems department. In the many years in between he spent a year as chairman on board 55 of study association ’Christiaan Huygens’. After graduating, Martijn started working at Deloitte as a business analyst in the service line Business Intelligence & Analytics. Figure 3

Computer Science

The proposed solution was researched in a case study on the Open Images dataset. This dataset contains videos about the Dutch Cultural Heritage. Instead of using domains as books and movies, we used different types of videos as domains, such as news items, documentaries and video blogs. Therefore we made a taxonomy containing video types and used that taxonomy to classify our dataset into domains. As we did not have enough data about the videos to automatically annotate each video with a domain, we set up this task to be performed by users. I used the platform BruteForce for this purpose. This platform was developed by another graduate student, so I helped him with his research as well. After the dataset was divided into domains, we selected YouTube as the auxiliary system from the Social Web. Next, we computed cross-domain recommendations for each Open Images video in the following way. First, we searched the most similar video on YouTube using the YouTube search API. For the found YouTube video, we could retrieve 50 related videos. Because of the closed nature of the YouTube system, it is hard to justify the way it computes this related videos. According to [2], videos are related if they cooccurred in one session in the last 24 hours and otherwise related videos are calculated content-based. Since this paper dates from 2010, this information might be outdated. The last step that we performed was mapping back the related YouTube videos to the most similar Open Images video. We used Lucene for this purpose. In figure 2 this whole process is illustrated.

our problem as it will cost time before all items from a newly added domain are tagged.

1 This thesis, ”Towards a Social Web based solution to bootstrap new domains in cross-domain recommendations”, can be found on http://repository.tudelft.nl/

23


The Future ofThe Mobile Apps Future of Mobile Apps Hylke Visser

Hylke Visser

Nowadays, practically every company and organisation has a set of mobile Apps to keep in touch with their customers, members or whoever else is interested. Developing such Apps for the numerous mobile platforms is time consuming and costs tons of money. As a result, we now have an overwhelming amount of low-quality Apps that crash your phone and kill your battery. If a company wants Apps for iOS, Android and Windows Phone you will be building the exact same functionality at least three times, in three different programming languages. Unless you are an experienced developer for all of these platforms, you will spend a huge amount of time reading documentation and searching for solutions to problems you encounter during the development of each of these three Apps.

Computer Science

Let’s assume that after a few months of work you finally finished your three apps and published them in the different stores. We all know that after some time your client will have come up with this small piece of functionality he wants to add to his Apps. And the entire process starts over again. Three different Apps, three different programming languages, tons of money and an unsatisfied client because it takes so much time.

Web-Apps Luckily these different OSs have one thing in common: they are all equipped with web browsers. Many developers are very enthusiastic about the new features in HTML5 and CSS3, and they should be. These features enable them to build web pages that feel like you are using a real application and run in virtually every web browser on any smartphone, smartwatch, computer and in a few years probably even on your fridge and your washing machine. One of the most interesting efforts in the category of web-Apps is Polymer (https://www.polymer-project.org/). Polymer is a platform that leverages the upcoming web components (https://www.w3.org/wiki/WebComponents/) technologies to make development of applications on the web easier and faster.

24

Figure 1: A calculator web-App built with Polymer

Unfortunately web-Apps have their limitations. Obviously, web browsers should be secure and therefore not allow access to other parts of your phone than your web browser. But this also means it is nearly impossible to use special functionality such as motion sensors or notifications. As you would expect, there is a solution for that. Apache Cordova (https://cordova.apache.org/) is one of the most popular frameworks for creating web-Apps that are a little bit more integrated with your smartphone. It supports many platforms, including iOS, Android and Windows as well as some popular desktop Operating Systems. It has several plugins that allow the developer to use native functionality in their web-Apps, making this framework a big step in the right direction. Cordova and similar technologies seem very promising, but for now these kind of Apps are not really efficient, still not well enough integrated with your phone’s Operating System and they just don’t look and feel the same as native Apps.

Cross-Compiling The idea behind cross-compiling is that every line of code you write will eventually be converted to machine code that can be understood by the processor of your smartphone. This means that using a smart compilation process, it could now be possible to reuse a large amount of your code on multiple platforms. Xamarin (https://xamarin.com/) is one of the biggest players in crosscompiling. The roots of Xamarin are in a framework called Mono (http://www.mono-project.com/). In 2000 Microsoft first announced the .NET framework and the open standard for the underlying infrastructure. You could compare this to something like Java, where your code is compiled to platformindependent code, which is in turn compiled to platform-specific machine code. Well, simply said, Mono is the open source implementation of this standard. While Mono was built to run .NET applications on Linux, specific versions were created to support iOS and Android. These and other platforms are now included in the Xamarin Platform. Developers are now able to write large parts of their App Logic once and reuse it on the different platforms. Even a large part of the User Interface code can be shared between the different platforms. And best of all, you are still able to interact with native API’s and build a native User Interface that is completely integrated with your shared code.

Figure 2: Code sharing between native Apps


Vantage Practice Last spring we actually built an iOS App using these technologies. Together with Herman Banken and Patrick van Hesteren we did the final project of our bachelor at the company Emando B.V. which is currently making custom software systems for the Dutch iceskating association. Our task was to build an App that allows people to keep track of their training sessions and monitor their performance and progress in real-time. To accomplish this we had access to the existing infrastructure of the rinks that detects the position of a skater using transponders and detection points beneath the ice. Each time a skater passes a detection point, our servers would receive a message with the skater’s transponder ID (who), the time (when), and the detection point (where). With these three pieces of information, we were able to build a system that analyses the performance and progress of the skaters.

Backend Deciding what kind of architecture we were going to use for our backend was quite easy. We wanted a solution that is able scale up to process the data of hundreds of skaters in real-time and scale down when there is no activity. This requirement left us with no other option than a cloud-based, distributed backend. Many other applications Emando B.V. had already built were deployed in Microsoft’s Windows Azure cloud. This convinced us to use Azure as well, because then we could use the existing knowledge within the company and wouldn’t have to reinvent the wheel by ourselves.

Async and Await One of the most amazing things I’ve only seen in C# so far are the async and await keywords. These keywords make it extremely simple to do asynchronous and parallel programming. In the example code below you can see how work that is not dependent on the retrieval of a website is done while the website is fetched from the Internet. Only when all other work is done, the program waits for the website retrieval to complete. a s y n c Task < i n t > G e t T h e W e b s i t e ( ) { H t t p C l i e n t c l i e n t = new H t t p C l i e n t ( ) ; Task < s t r i n g > g e t t i n g T h e S i t e = c l i e n t . G e t S t r i n g A s y n c ( ” h t t p : / / ch . t u d e l f t . n l ” ) ; DoWorkThatDoesNotDependOnTheSite ( ) ; string contents = await gettingTheSite ; return contents . Length ; }

Unity Dependency Injection and Inversion of Control are two terms you probably never heard of during your studies. And I have no idea why not, because these concepts make your life as a programmer so much better. Unity

SignalR

SignalR (https://www.asp.net/signalr) is a library that enables developers to include real-time communication between the servers and the clients. You may have already played with WebSockets in Node.js, and well, this is almost the same, only a little bit better. Let’s say you define a public function TriggerMe in the so-called Hub Proxy on your client. You can now extremely easily call this function from your server by just calling Clients.Client(id).TriggerMe(). Simple as that.

iOS App Let’s go back to the App. As said before, we used Xamarin cross-compiling to build an iOS App. This meant that we could use all of the benefits of C#, .NET and libraries like SignalR just as easily in our iOS App. A large part of the code we wrote for this iOS App could just as easily be used in an Android or Windows Phone App. The only tricky part is attaching everything to the User Interface. And that’s because iOS and Objective-C do not know how to work with all this asynchronous stuff. And fortunately there is a library for that!

Reactive UI Reactive UI (http://www.reactiveui.net/) is an extension among others of TU Delft professor Erik Meijer’s Reactive Extensions library (https://rx.codeplex.com/) that helps developers write User Interfaces that react to asynchronous changes in data. In the code fragment below, we bind the Time property of our ViewModel to the Text attribute of our UILabel. t h i s . OneWayBind ( V i e w M o d e l , vm => vm . Time , v => v . t x t T i m e V a l u e . T e x t , t => S t r i n g . F o r m a t ( ” { 0 : # # . 0 0 } ” , t . T o t a l S e c o n d s ) )

Computer Science

As a long time Apple fan and thus a Windows hater without any experience in C# programming, I was quite sceptic about all these Microsoft tools. But I was positively surprised about the power of the C# programming language, the .NET framework and the great amount of available packages and extensions.

(https://unity.codeplex.com/) does exactly that. Say for example you have a UserAuthenticator class that requires a database to authenticate the user. In that case Unity could instantiate this database connection and inject it into your UserAuthenticator class without you having to worry about that.

With this small piece of code we instructed the library to watch the Time property and when it changes, automatically switch to the main thread and update the User Interface.

Conclusion

Making smartphone Apps is a time-consuming and expensive process. The numerous platforms all work in a different way and require you to write in different programming languages. Web-based applications are becoming more and more popular. Cross-compiling helps developers write large parts of their Apps just once, while still maintaining the performance and the feeling of a native App. Both approaches work quite good, but still a lot of work has to be done to fully integrate these technologies with the native Operating Systems of the smartphones. Also, some performance issues arise when dealing with mediumlarge amounts of data. But I’m sure that in the future these and other issues will have been solved and that mobile App development will be many times easier, faster and cheaper.

25


Java Puzzlers Oplossing ’The Name Game (62)’ De Puzzler

More of the Sa

De Puzzle

De Puzzler Last MaCHazine you had the puzzle ’The Name Game’. Several solutions

Each MaCHazine there will be a puzzle with a script of a program, here is

have been submitted. The best and most complete answer is submitted

the new one. It is up to you to find out what the program does. You may

by Jasper Oosterman. Now we present the solution of this puzzle.

use Java, but it‘s more fun just to use your mind.

A naive analysis of this program suggests that is should print 1. The program puts two mappings into the map, but both have the same key (Mickey). It’s a map, not a multimap, so the baseball legend (Mickey Mantle) should overwrite the animated rodent (Mickey Mouse), leaving a single mapping in the map.

This program is similar to the previous one, except this one is object-oriented. Learning from our previous mistake, this version uses a general-purpose Map implementation, a HashMap, in place of the previous program’s IdentityHashMap. What does this program print?

A more thorough analysis casts doubt on this prediction. The documentation for IdentityHashMaps says, ”this class implements the Map interface with a hash table, using reference-equality in place of [value]-equality when comparing keys” [Java-API]. In other words, the program will print 2 rather than 1 if the second occurrence of the string literal ”Mickey” evaluates to a different String instance from the first. So does the program print 1, does it print 2, or might its behavior vary from implementation to implementation?

import java . u t i l . * ; p u b l i c c l a s s MoreNames { p r i v a t e Map < S t r i n g , S t r i n g > m = new HashMap < S t r i n g , S t r i n g > ( ) ; p u b l i c v o i d MoreNames ( ) { m. p u t ( ” M i c k e y ” , ” Mouse ” ) ; m. p u t ( ” M i c k e y ” , ” M a n t l e ” ) ; }

Computer Science

If you tried running the program, you found that it prints 1, as suggested by our naive analysis, even though the analysis is flawed. Why? The language specification guarantees that string constants are interned. In other words, string constants that are equal will also be identical [JLS 15.28]. This ensures that the second occurrence of the string literal ”Mickey” in our program refers to the same String instance as the first, so our use of an IdentityHashMap in place of a general-purpose Map implementation, such as HashMap, does not affect the program’s behavior. Our naive analysis neglects two details, but these details effectively cancel each other out. The important lesson of this puzzle is: Don’t use IdentityHashMap unless you need its identity-based semantics; it is not a general-purpose Map implementation. These semantics are useful for implementing topology-preserving object graph transformations, such as serialization or deep-copying. A secondary lesson is that string constants are interned. Programs should rarely, if ever, depend on this behavior for their correct operation.

26

public int size () { r e t u r n m. s i z e ( ) ; } p u b l i c s t a t i c v o i d main ( S t r i n g a r g s [ ] ) { MoreNames moreNames = new MoreNames ( ) ; S y s t e m . o u t . p r i n t l n ( moreNames . s i z e ( ) ) ; } }

References [1]

Java puzzlers, traps Pitfalls and corner cases, Joshua Bloch & Neal Gafter

[2]

The Java® Language Specification, James Gosling, Bill Joy, Guy Steele, Gilad Bracha & Alex Buckley

Stuur je oplossing naar [email protected] en maak kans op een prijs t.w.v. 45 euro! Stuur niet alleen je antwoord op, maar ook een uitleg hoe je tot dit antwoord gekomen bent.


Wiskundepuzzel Problems and solutions ame (63)

er

Mark Veraar

Een meetkundepuzzel

(a): E(M N ) = =

∞ ∑ ∞ ∑

n=0 k=0 ∞ ∑ ∞ ∑

P({M = k, N = n})kn P({M = k})P({N = n})kn

k=0 n=0

= e−α−β = e−α−β

∞ ∞ ∑ αk ∑ β n n k k! n=0 n! k=0

∞ ∑ αk βk e k! k=0 β

β

= e−α−β eαe = eα(e

In de figuur is een zandloper te zien. Hierbij zijn AB, T S en CD alle evenwijdig en loodrecht op AC. Uit Pythagoras volgt |AD|2 = |CD|2 + |AC|2 en |BC|2 = |AB|2 + |AC|2 . (a) Geef de ontbrekende vergelijking die |ST | beschrijft in termen van |AB|, |AC|, |AD|, |CD|, |BC| (b) Neem aan dat |AB| = |CD|. Vind een oplossing waarbij |ST | minimaal is en geheel en |AB|, |AC|, |AD|, |CD|, |BC| ook alle gehele getallen zijn. (c) Vind een oplossing waarbij |ST | minimaal is en geheel en |AB|, |AC|, |AD|, |CD|, |BC| ook alle gehele getallen zijn met |AB| > |CD|.

De Poissonverdeling van een variabele M met parameter α > 0 wordt gegeven door: αk , k! ∑∞

P(M = k) = e−α Het is eenvoudig na te gaan dat verwachting geldt E(M ) = α.

k=0

k = 0, 1, 2, . . . P(M = k) = 1 en dat voor de

Laat nu M en N Poisson verdeeld zijn met parameters α > 0 en β > 0. (a) Vind de verwachtingswaarde E(M N ). (b) Is E(M N ) stijgend als functie van α ? (c) Is E(M N ) stijgend als functie van β ? Antwoorden. Correcte inzendingen zijn ontvangen van Marjon Ruijter en Wim van Geloven.

(b),(c) Aangezien de e-macht een strikt stijgend functie is voldoet het te kijken naar α(eβ − 1) − β als functie van α of β. Als functie van α is dit stijgend wegens eβ − 1 > 0. Als functie van β is dit stijgend dan en slechts dan als αeβ − 1 ≥ 0. Dus de functie is stijgend dan en slechts dan als α ≥ 1. In het geval α < 1 is de functie dalend op het interval β ∈ (0, − ln α] en stijgend op het interval [− ln α, ∞).

Wiskundeladder 1. Wim van Geloven 2. Jeroen Wille 3. Marieke van der Tuin Erik Ammerlaan Robbie Elbertse 4. Micke Vrolijk Leon Planken Jonatan Bijl 5. Jarno Hartog Jeff Smits Michiel de Reus M. Looijen Romke Rozendaal Jolien de Haas Sander Gribbling Marjon Ruijter 6. Dirk Hazenoot 7. John Simons

10 9 8 8 8 6 6 6 5 5 5 5 5 5 5 5 4 3

Mathematics

Een kansrekeningpuzzel.

−1)−β

27


Global tideGlobal model with DFlow-FM tide model with DFlow-FM Casper Markensteijn

Casper Markensteijn

My bachelor thesis was performed at Deltares, a research institute in Delft. Deltares makes use of many hydrodynamic models, but these are all over a small part of the world. Now they also want a global tide model, which is a model that predicts the waterlevel and waterspeed in the oceans and near the coast. My main focus was on finding the best grid that should be used. Therefore I will focus this piece on the grid, although I also started the implementation of the internal tides, if you would like to know about that you should read [1].

Furthermore there are some conditions. First of all the calculations are done in the spherical domain. Secondly, there will be no flow through the land-sea boundary and at last the initial water level is the mean sea level.

Grid The most important question I had to answer was what the best grid is to use for the model. Firstly, the grid has to meet some requirements: • The grid has to be orthogonal. • The cells should not have small angles. • A node can’t have to many links connected to it. • The sides of the cells may not defer to much. • It is preferred to have 4 sides on each cell. • More resolution on the shelf is wanted because there is a lot of dissipation.

Model description Deltares is working with it’s own application for hydrodynamic models, called DFlow-FM. Therefore the model was also made within this application. Within DFlow-FM the swallow-water equations [2] are solved, using the finite volume method, which are given by: ∂h + ∇(hu) = 0 ∂t 1 ∂u + (∇(huu) − u∇(hu)) = ∂t h τ −g∇ζ + ∇(ν(∇u + ∇uT )) + − 2Ωusin(ϕ)) h

I tried two possibilities first of all a rotated lat-lon grid. The standard lat-lon grid isn’t possible, as that would result in a grid with to many links connected to the North pole. So the grid will be rotated at way that the poles of the grid will be both be on land and will therefore be removed from the model. The second possibility is a grid that is more refined on points with low depths.

Rotated grid (1)

In order to rotate the grid without losing the orthogonality we used a method called stereo-graphic projection (see [3]). In figure 1 you can see a visualization of how the projection works and in figure 2 an example on the globe. If you would like to know more about how it works you should read [1].

Mathematics

Where: h : the water height u : the velocity vector g : the gravitational acceleration ζ : the water level ν : the viscosity Ω : earth’s rotating frequency ϕ : the latitude τ = Cg2 ∥u∥u : the bottom friction C : the Chezy coefficient For a global model you need more than just these equations. As without boundary conditions the initial water level will be the eventual solution. Therefore the model should also satisfy the tide generating potential: ∂ζ 1 + ∂t Rcos(ϕ)

(

∂u1 h ∂u2 hcos(ϕ) + ∂λ ∂ϕ

)

=0

Where: λ: the longitude u1 and u2 : respectively the velocity in the ϕ and λ direction R: the radius of the earth

28

(2)

Figure 1: Points of the small sphere are stereographically projected onto the plane and then reprojected onto the original sphere (dotted line). Now I had to find the best place for North and South Pole of the grid. Those two should about 180◦ apart, as we otherwise have very small cells on one side and big cells on the other side of the grid, as can be seen in figure 2. Therefore I have chosen to put the North pole on Canada and the South pole on the Antarctica, but shifted to the North-East.

Local refined grid One of the problems of the rotated grid is that we can’t easily improve the resolution as it will result in to many points. Therefore a method was created


Conclusion In order to compare the grids I run the model with the same settings except for the grid. First of all the land was removed of both grids, this results in less points and therefore in a lower calculation time. Some of the other model parameters are listed in table 1. Starting time End time Time step Friction coefficient Friction kind Gravity Initial water level Observation interval Mean water density

Figure 2: an example of a rotated grid with a resolution of 15◦ .

within DFlow-FM which refines the cells on certain points. In order to use this method we need an initial grid which is as squarely as possible. The grid that has been used is a grid with a cellwidth of about 50km, although a bit apart because of the bending of the earth (figure 3).

22-12-1991 0:00:00 03-01-1992 0:00:00 5min 62.651 Chezy 8.829m/s2 0m 30min 1024.0164kg/m3

Table 1: Some of the important parameters needed for the model.

(a)

(b)

Figure 3: The initial grid for the refinement method with in (a) a flat display and in (b) it is displayed on a sphere. The refinement is based on the cell depth. A cell is refined by a factor of two in all directions when the cell satisfies the following conditions:

I used the waterlevels of the first and second of January 1992 to compare the two grids. In order to compare them I calculated the RMS values of the grids in comparison to SR95 data (see [4]), in figure 5 you can see a plot of the waterlevels of both the model data and the SR95 data. I found that the RMS value of the rotated grid was about 3 cm higher than the local refined grid for all 24 times that it was calculated. Therefore the Local refined grid is clearly better than the rotated grid and this one will be chosen to be used in the model. I also think that the grid won’t become much better than this as we already have a cell width minimum of 5km which is very small for oceans. Therefore future work should, in my opinion, be focused upon other things, like the internal tides and some other important features that you can read about in [1].

• Courant < 1 − hmin | < |h − hmin | • |h 2

After this has been run till no more cells fit both conditions some cells are refined in order to have proper nesting, which means that two neighboring cells have no more than two refinement levels between them. At last the hanging nodes will be connected to the neighboring cells which results in triangle cells between two refinement levels. This results in the refined grid, in figure 4 you can see the grid for some part of Europe. You can clearly see that in shallow water there is a higher resolution than in deep water.

(a)

(b)

Mathematics

Where: Courant = C∆tmax /h : the wave speed ∆tmax : maximum time step h : the minimum cell width h : the new cell width 2 hmin : the minimum cell width, chosen by the user

Figure 5: The waterlevels (in cm) of a) the model and b) the SR95 dataset.

References

[1] G.C. Markensteijn Global tide model with DFlow-FM 2014. [2] Technical reference manual DFlow-FM.

[3] Ross J. Murray Explicit generation of orthogonal grids for ocean models 1996: Journal of computational physics 126. [4] E.J.O. Schrama and R.D. Ray A preliminary tidal analysis of TOPEX/POSEIDON altimetry 1994: Journal of geophysical research 99.12

Figure 4: A part of the local refined grid.

29


IDR as a Fixed-Point Method for Solving Linear Systems of Equations IDR as a Fixed-Point Method for Solving Linear Systems of Equations Martin van Gijzen

Martin van Gijzen To be able to check the convergence we can compute the residual vector r that is defined by rn = Bxn + ~ b − xn .

This article describes two fixed-point methods for solving linear systems: the Gauss-Seidel method, and the IDR method by Sonneveld.

Some straightforward manipulations yield the relation between rn and rn−1 :

IDR has recently made a comeback.

rn

=

Introduction

=

One of the main topics of research in numerical linear algebra is the study of efficient algorithms for the solution of the linear system

=

Ax = b

= =

(1)

where the matrix A is large (millions of equations) and sparse (has just a few non-zeroes per row). Such systems may for example result from the discretisation of a system of partial differential equations. A direct solution methods based on Gaussian elimination turns many zero-entries in A into non-zeroes during the elimination process. As a result, direct solution algorithms may require too many computations and too much memory. Iterative solution methods are an alternative to the direct methods. In this article I will discuss two iterative methods: the method by Gauss-Seidel and an old version of the Induced Dimension Reduction (IDR) method.

Gauss-Seidel’s method Gauss-Seidel’s method is, as the name suggests, quite old. It was very popular in the early days of the computers, since the algorithm uses very little memory. It is possible to implement it using storage only for the solution and for the matrix.

The algorithm

B(xn − xn−1 )

Brn−1 .

x0 initial guess, r0 = Bx0 + ~ b − x0

1

For n = 0, 1, 2, . . . do:

2

xn+1 = xn + rn rn+1 = Brn

Example To illustrate the convergence we consider the Finite Difference discretisation of −y ′′ (x) = f (x) , y(0) = y(1) = 0

The right-hand-side function f (x) is such that y(x) = x sin(x). We take 20 internal grid points, hence A is a matrix of size 20 × 20. The initial guess is x0 = 0. Figure 1 shows the norm of the residual divided by the norm of ~ b as function of the iteration number. The rate of convergence of the Gauss-Seidel Convergence Gauss−Seidel

0

10

−1

10

−2

10

−3

We do not need to compute the matrix B explicitly. A multiplication z = Bx is performed by first computing y = Nx and then a forward substitution z = M−1 y. These operation require exactly the same amount of computations as a multiplication with A, and can be performed using the original matrix A, without additional storage. Let x0 be an initial guess for the solution of (2). Then the following fixed-point iteration can be used to solve this equation: xn+1

= Bxn + ~ b,

n = 0, 1, 2, . . . .

The above recursion together with the definition of B define the method of Gauss-Seidel.

30

Bxn + ~ b − (Bxn−1 + ~ b)

Residual norm

Mathematics

Other splittings are also possible and give rise to different methods. We assume that A only has positive diagonal elements, and consequently that M is b = M−1 b, the system (1) can be an invertible matrix. With B = M−1 N, and ~ written as x = Bx + ~ b . (2)

xn+1 − xn

For convergence, the norms of the residuals should decrease, which is (asymptotically) the case if the moduli of the eigenvalues of B are smaller than 1. We can implement the iteration procedure as follows

In order to derive an iterative method we first transform (1) into a fixed-point problem. To this end we split A into its strictly upper triangular part −N and its lower triangular part M such that A=M−N .

Bxn + ~ b − xn

10

0

50

100

Iteration

150

200

250

Figure 1: Convergence of the Gauss-Seidel method. method is linear, which means that in every iteration the residual norm is reduced by approximately a constant factor.

The Induced Dimension Reduction method Linear convergence is too slow for most applications. In Gauss-Seidel, only information from the last iteration is used to compute a new approximation. To speed-up convergence, one can try to make use also of information of previous iterations. This is what is done in IDR.


The algorithm The IDR-method was developed by Peter Sonneveld, who was my teacher in numerical linear algebra. He developed the method in an attempt to make an assignment for the students: derive a Secant method for solving linear systems. Although his attempt to make such an assignment was a failure (it was too difficult for us...), it did give rise to an algorithm that turned out to be revolutionary. In order to make use of the last two iterations one can make a convex combination of the previous two residuals as follows:

beautiful CGS paper [1] caused a true revolution in the numerical linear algebra world, and it is still the most cited paper of our department. In the meantime, however, IDR had been forgotten. I started to work at the university in 2004, and soon after that Peter retired. Around that time, Peter had become interested in the old IDR method again and he suggested to work on it together. This has resulted in IDR(s) [2], a method that has received considerable attention, and finally gave the old IDR method the place in the history of numerical linear algebra that it earns.

References

sn = rn + γn (rn − rn−1 )

[1] P. Sonneveld. CGS: a fast Lanczos-type solver for nonsymmetric linear systems. SIAM J. Sci. and Statist. Comput., 10:36–52, 1989.

Note that taking γn = 0 yields the Gauss-Seidel method. Inspired by the Secant method, the parameter γn is chosen such that sn ⊥ p, in which p is a constant vector. Using these formulas, the updates for the solution and the residual become

[2] P. Sonneveld and M.B. van Gijzen. IDR(s): a family of simple and fast algorithms for solving large nonsymmetric linear systems. SIAM J. Sci. Comp., 31(2):1035–1062, 2008.

xn+1 = xn + γn (xn − xn−1 ) + sn and rn+1 = Bsn . Putting these equations together yields the fixed-point variant of the IDR algorithm. Fixed-point IDR-algorithm: 1

b0 , x1 = x0 + r0 , r1 = Br0 x0 initial guess, r0 = ~

2

For n = 1, 2, . . . do: γn = −

pT rn , − rn−1 )

pT (rn

sn = rn + γn (rn − rn−1 )

xn+1 = xn + γn (xn − xn−1 ) + sn

rn+1 = Bsn

Example We apply IDR to the test problem of the previous section. The relative residual norm as function of the iteration number is given in Figure 2. The convergence

Martin van Gijzen received his PhD degree from the TU Delft in 1994. His PhD research was on the iterative solution of Finite Element systems and was carried out at TNO. After his graduation he worked at Utrecht University as a PostDoc, at TNO as a project leader, and at CERFACS in France as a Senior Scientist. He returned to the TU Delft in 2004 where he is an Associate Professor in the Numerical Analysis group. His research area is numerical linear algebra.

Convergence IDR

2

10

0

10

−2

−4

10

−6

10

−8

10

−10

10

−12

10

−14

10

0

5

10

15

20

Iteration

25

30

35

40

Figure 2: Convergence of IDR. of the method is striking! The residual norm becomes of the order of machine precision after 40 iterations. This is no coincidence. It can be shown that (in exact arithmetic) IDR finds the exact solution in at most 2N iterations, with N the number of unknowns.

What happened with IDR? The search for an explanation to this surprising discovery led Peter Sonneveld to a connection between IDR and the Conjugate Gradient method, a method for solving systems with A symmetric and positive definite. Based on this relationship, he developed the CGS method for nonsymmetric matrices. The

Mathematics

Residual norm

10

31


Harige Bollen Wolter Groenevelt

Harige bollen Wolter Groenevelt

De Poincaré-Brouwer stelling zegt dat als je de haren op een behaarde

De sfeer van dimensie n − 1 in Rn met straal r is de verzameling

bol plat wilt kammen, je altijd ergens een kruin krijgt. In het Engels wordt dit de ‘hairy ball theorem’ genoemd en in het Duits ‘Satz vom gekämmten Igel’. Door gewoon te proberen een bal te kammen, ben je er waarschijnlijk vrij snel van overtuigd dat de stelling moet kloppen; je zou het ook met een egel kunnen proberen.

Sr = {x ∈ Rn | ∥x∥ = r}. In het geval r = 1 laten we het subscript weg: S1 = S. Voordat we naar het bewijs gaan, bekijken we nog even het geval met even n. Definieer het vectorveld τ : Rn → Rn door τ (x) = (−x2 , x1 , −x3 , x4 , . . . , −xn , xn−1 ). Dan ⟨τ (x), x⟩ = 0 en ∥τ (x)∥ = 1 als x ∈ S, dus τ is een continu differentieerbaar eenheidsraakvectorveld aan S.

Wiskundig gezien kunnen we de stelling als volgt formuleren: Er bestaat geen continu differenteerbaar eenheidsraakvectorveld op de eenheidssfeer in R3 . In twee dimensies klopt deze stelling niet; het is geen enkel probleem om een eenheidsraakvectorveld aan de eenheidscirkel te maken:

Voor het bewijs van Stelling 1 nemen we aan dat τ een continu differentieerbaar eenheidsraakvectorveld is van S. We gaan nu een tegenspraak afleiden. Definieer het gebied K ⊂ Rn als het gebied ingesloten door de sferen S 1 en

S 3 , d.w.z. K = {x ∈ Rn | 2

1 2

≤ ∥x∥ ≤

2

3 }. 2

K S1 2

S3 2

Mathematics

Een punt x ∈ K kunnen we schrijven als x = rx0 met x0 ∈ S en 12 ≤ r = ∥x∥ ≤ 32 . Met behulp van τ definiëren we een continu differentieerbaar vectorveld v : K → Rn door De Nederlandse wiskundige Brouwer bewees in 1912 een algemenere versie van bovenstaande stelling. (Poincaré had al eerder een equivalent resultaat bewezen, vandaar de naam Poincaré-Brouwer stelling).

Stelling 1. Zij n ∈ N oneven. Er bestaat geen continu differenteerbaar eenheidsraakvectorveld op de eenheidssfeer in Rn . Brouwer gebruikte deze stelling om zijn beroemde dekpuntstelling te bewijzen. Het bewijs van Brouwer maakt gebruik van algebraïsche topologie. In 1978 gaf Milnor [1] een bewijs van de Behaarde Bol Stelling dat alleen gebruik maakt van 1e-jaars wiskunde kennis. We zullen hier Milnor’s bewijs bekijken. We voeren eerst wat notatie in. Het (standaard) inwendig product tussen vectoren x = (x1 , x2 , . . . , xn ) ∈ Rn en y = (y1 , y2 , . . . , yn ) ∈ Rn is ⟨x, y⟩ = x1 y1 + x2 y2 + . . . xn yn ,

en de lengte van een vector x is

32

∥x∥ =

√

⟨x, x⟩ =

√ x21 + x22 + . . . x2n .

v(x) = rτ (x0 ),

x ∈ K.

Merk op dat v(x) = τ (x) als x ∈ S. We definiëren nu voor t ∈ R de functie ft : K → Rn door ft (x) = x + tv(x), x ∈ K. Lemma 1. Als |t| klein genoeg is, is ft injectief, en het volume van het beeld ft (K) kan worden uitgedrukt als een polynoom in t. Bewijs. Eerst de injectiviteit van ft . Uit het compact zijn van K en continu differentieerbaar zijn van τ , volgt dat er een constante c bestaat, zo dat ∥v(x) − v(y)∥ ≤ c∥x − y∥. (Dit kun je laten zien met de middelwaardestelling.) Kies nu |t| < 1c en stel ( ) dat ft (x) = ft (y). Dan volgt uit de definitie van ft dat x − y = t v(y) − v(x) , en dus ∥x − y∥ = ∥tv(y) − tv(x)∥ ≤ c|t|∥x − y∥. We zien dat x = y, en dus is ft injectief.


Het volume van het gebied ft (K) is ( ) Vol ft (K) =

∫

ft (K)

Uit deze twee eigenschappen volgt dat gt een uniek dekpunt heeft, d.w.z. er bestaat een unieke xd ∈ K zo dat gt (xd ) = xd . (Dit kun je laten zien met behulp van de rij gedefinieerd door xn = gt (xn−1 ), x0 ∈ K). Volgens de definitie van gt voldoet xd dan aan

du.

We passen de transformatiestelling voor meervoudige integralen toe met u = ft (x). De Jacobiaan is de determinant van de afgeleide van ft . Uit de definitie van ft volgt dat  ∂ft,1

 ∂x1   f′t (x) =  ∂ft,2  ∂x1  . ..

∂ft,1 ∂x2

···



 ∂v

1

  ∂x1     = I + t  ∂v2 · · ·   ∂x1   . .. . . .

∂ft,2 ∂x2

. ..

∂v1 ∂x2 ∂v2 ∂x2

.. .

···



   , · · ·   .. .

xd + tv(xd ) = y0 .

Schrijf xd = ∥xd ∥x met x ∈ S, dan geldt er v(xd ) = ∥xd ∥τ (x). Aangezien ⟨xd , τ (x)⟩ = 0, volgt uit (1) 1 = ∥xd ∥2 + t2 ∥xd ∥2

waarbij de functies ai , i = 1, . . . , n, continue functies van x zijn. Als t klein genoeg is, is ∂u positief. Nu volgt ∂x ( ) Vol ft (K) = k0 + k1 t + k2 t2 + . . . + kn tn ,

K

De lengte van een vector x + tτ (x), x ∈ S, is ∥x + tτ (x)∥ =

∥v(x) − v(y)∥ ≤ c∥x − y∥,

x, y ∈ K.

∥gt (x) − gt (y)∥ = |t|∥v(x) − v(y)∥ ≤ c′ ∥x − y∥,

√ ∥x∥2 + ∥tτ (x)∥2 = 1 + t2 ,

x, y ∈ K,

met c′ = c|t| < 1.

omdat x en τ (x) loodrecht op elkaar staan. De functie ft beeld dus ieder punt √ in S af in de sfeer met straal 1 + t2 . S√

Dit is het gewenste resultaat. We zullen de bewering nog bewijzen. Er bestaat een constante c (zie het bewijs van Lemma 1) zo dat

Kies nu |t| < min{ 1c , 13 }, dan geldt er ∥tv(x)∥ = |t|∥x∥ < 13 · 32 = 21 . We zien nu dat ∥gt (x)∥ ≤ ∥y0 ∥ + ∥tv(x)∥ ≤ 32 en ∥gt (x)∥ ≥ ∥y0 ∥ − ∥tv(x)∥ ≥ 12 , ofwel gt (K) ⊂ K. Bovendien,

ai (x) dx (we gebruiken a0 (x) ≡ 1).

√

1 ∥xd ∥ = √ . 1 + t2

x + tτ (x) = y.

) ( ∂u = det f′t (x) = 1 + ta1 (x) + t2 a2 (x) + . . . + tn an (x), ∂x

met ki =

⇒

√ √ Vermenigvuldig (1) met 1 + t2 , dan zien we dat het punt x = 1 + t2 xd ∈ S een oplossing is van de vergelijking

en dus is de Jacobiaan van de vorm

∫

(1)

1+t2

We kunnen nu de Poincaré-Brouwer stelling, Stelling 1, bewijzen. Kies een punt x = rx0 ∈ K. Met de definitie van ft zien we dat ft (x) = rft (x0 ) (met x = rx0 , x0 ∈ S). Volgens Lemma 2 is het beeld ft (K) dan het gebied in Rn √ √ ingesloten door de sferen met stralen 12 1 + t2 en 32 1 + t2 ; het gebied K √ wordt dus met een factor 1 + t2 opgeblazen. Er geldt dus )n ( ) (√ Vol (ft (K) = 1 + t2 Vol(K).

S ft (x) x

Mathematics

Als n oneven is, is dit géén polynoom in t, maar dit is in tegenspraak met Lemma 1. Dit bewijst de stelling.

Een verrassend gevolg van de stelling is bijvoorbeeld dat er altijd een punt op aarde is waar het windstil is, een meteorologische kruin dus. Het volgende lemma zegt dat deze afbeelding surjectief is. Lemma 2. Als |t| klein genoeg is, is het beeld van S onder x �→ x + tτ (x) de √ (n − 1)-dimensionale sfeer in Rn met straal 1 + t2 , ofwel ft (S) = S√ 2. 1+t

Bewijs. We laten zien dat voor iedere y ∈ S√

1+t2

de vergelijking ft (x) = y

een oplossing x ∈ S heeft. n door Kies een y ∈ S√ 2 en definieer de afbeelding gt : K → R 1+t

gt (x) = y0 − tv(x),

y0 = √

y 1+

t2

∈ S.

We beweren dat gt de volgende twee eigenschappen heeft: 1. gt (K) ⊂ K 2. Er bestaat een c′ < 1 zo dat ∥gt (x) − gt (y)∥ ≤ c′ ∥x − y∥, x, y ∈ K.

Verder is de stelling ook nog goed voor een behoorlijk aantal wiskundegrappen (google maar eens op ‘hairy balls’).

Referenties

[1] J. Milnor, Analytic proofs of the “hairy ball theorem” and the Brouwer fixed point theorem, Amer. Math. Monthly 85 (1978), no. 7, 521–524.

33


Time-dependent Ambulance Locations Time-dependent Ambulance Locations Model with Start-up and Model with Start-up andCost Relocation Cost Relocation Pieter van den Berg

Pieter van den Berg

Ambulance providers in the Netherlands are responsible for providing care in case of emergencies. In my research project, we develop new models to improve their performance. In this article, we will introduce a model to determine good base locations and we will present some results for the region of Amsterdam.

Introduction

Mathematcis

Emergency Medical Services (EMS) are concerned with providing adequate care to emergency patients. When a call arrives at the dispatch center, an ambulance is assigned to the call. The probability of survival of a patient that is involved in an accident is highly dependent on the time it takes before an ambulance arrives at the scene. Consequently, it is of great importance that EMS vehicles respond as quickly as possible to the calls. In most countries, there is a certain target response time in which a minimum fraction of the calls must be reached. In the Netherlands, for example, 95% of all high priority calls must be reached within 15 minutes response time. In order to meet this requirement, it is important to determine good locations for the ambulances. The objective of this research is to maximize the expected number of calls that is reached within the target response time. To do so, it is important to take the availability of ambulances into account. If an ambulance is dispatched to a call, it is not available for other calls. This can result in lower coverage, in particular in the region that was covered by the dispatched ambulance. One way of taking this into account is by requiring back-up coverage. Another way is to use the expected coverage, which is calculated using the average fraction of time an ambulance is available. In this paper we will maximize the expected coverage. When we study the data collected from the EMS systems in the Netherlands we see that the characteristics of the system vary significantly over the day. Travel speeds, available ambulances, and demand vary over the day. By ignoring these variations, we miss certain aspects of reality, which can result in sub-optimal solutions. Therefore, we consider a time-dependent location model.

Literature The first ambulance location models appeared already in the seventies. Toregas et al. [3] and Church and Revelle [1] proposed models to determine good base locations. Both models ignore the fact that ambulances are not available when dispatched to a call. Daskin [2], as well as others, later introduced a model that incorporates this unavailability. This model, the Maximum Expected Coverage Location Problem (MEXCLP), assumes that ambulances are independently unavailable a fraction q of the time. This fraction is called the busy fraction. Given that a point is covered by k ambulances, the expected coverage is then Ek = 1−q k , which is the probability of at least one success in k independent Bernoulli experiments.

34

Model We consider a time-dependent version of MEXCLP in which we define a set T = {1, 2, ..., T } of T time periods. The time periods differ in travel times, demand and ambulance availability. As a consequence, also the busy fraction fluctuate over different time periods. The busy fraction in time period t is denoted by qt . Furthermore, we define a set V that contains all demand points and a set W that contains all potential locations for a base station. Each demand point has a certain intensity with which calls arise, we call this demand dit . For each demand point, we further have a set of base locations that can cover that point within the given response time threshold. This set depends on the time period and is denoted by Wit . The number of available ambulances per time period is pt . In the model we take the relation between different time periods into account, by adding penalties for opening base locations and for ambulance relocations. For each used base location, we introduce a penalty β, which represents the cost of opening a facility. Additionally, we introduce a penalty for each time an ambulance is relocated between two time periods. This penalty is denoted by γ. The decision variables in the model are xjt , yikt , zj , r1jt , and r2jt , where xjt is the number of ambulances located at station j during time period t. The binary variable yikt indicates whether demand point i is covered by at least k vehicles in time period t and zj is one if and only if base location j is used. r1jt and r2jt are the number of ambulances relocated from and to base location j after time period t, respectively. Given these variables, we can formulate the model as an ILP. The objective is to maximize the expected coverage over the day minus the penalties for locations and relocations. max

pt ∑∑∑

t∈T i∈V k=1

dit (1 − qt )qt k−1 yikt − β

∑

j∈W

zj − γ

∑ ∑

r1jt (1)

j∈W t∈T

Here, (1 − qt )qt k−1 is the marginal coverage of the k-th ambulance, which equals Ek − Ek−1 . We add a constraint to ensure that no more than the available ambulances are used. ∑

j∈W

xjt ≤ pt

(2)

t∈T

The relation between the different decision variables is enforced by the following set of constraints. Note that the objective function ensures that yikt ≤ yi(k−1)t . ∑

j∈Wit

∑

t∈T

xjt ≥

pt ∑

yikt

k=1

xjt ≤ M zj

xjt − r1jt + r2jt = xj(t+1) xjT − r1jT + r2jT = xj1

i ∈ V, t ∈ T

(3)

j∈W

(4)

t ∈ T \T, j ∈ W

(5) (6)


(a) Current locations

(b) Optimal locations

(a) Maximum coverage

Figure 1: Maps of current and optimal locations

Case Study Data For our case study we considered the region of Amsterdam, the Netherlands. The total population of the region Amsterdam is about 1.2 million. We derive 161 demand points based on 4-digit postal codes. We assume that each demand point is also available as a possible base location. For the traveltimes between the different nodes we use a travel-time model developed by the RIVM1 . This model is based on historical travel times of ambulances. We also have historical data regarding the number of calls per part of the day. For each 2-hour block we have the number of calls per demand point over the years 2008-2011. The busy fraction is based on data about the average call duration, the available number of ambulances and the number of calls. We do not have a time-dependent travel time model yet and therefore we use the average drive time as an indication of the travel speed during a time period. By doing so, the travel time between two points varies between 97% and 108% of the average travel time.

Figure 2: Maps of optimal locations with and without single coverage requirement

is uncovered because no ambulance is located within the time threshold of 15 minutes. From a fairness perspective, this is undesired. For that reason, we add an additional constraint that ensures that every demand point is covered by at least one ambulance during each time period. ∑

j∈Wit

Optimal

390347 0.9477 9 6

411319 0.9762 5 3

Table 1: Current versus optimal When looking at the demand that is uncovered, we obtain that 1.76% of the demand is uncovered because of ambulance unavailability. The other 0.62% 1 RIVM:

Dutch National Institute for Public Health and the Environment

(7)

i ∈ V, t ∈ T

Objective value Expected coverage # Locations # Relocations

Optimal

Cover at least once

411319 0.9762 5 3

400393 0.9710 9 12

Table 2: Optimal versus cover at least once

Conclusion

Mathematics

Objective value Expected coverage # Locations # Relocations

Current

xjt ≥ 1

In Table 2 we see that in order to satisfy these constraints, the overall coverage decreases by about 0.5 percentage point. Furthermore, we see that we need 9 bases, which corresponds to the number currently in use, and 12 relocations. Figure 2 shows the location of the bases. From a practical point of view, this seems to be a better solution than the one without the additional constraint.

Results To get insight in the possible improvement we can achieve, we evaluated the model twice. First we solved the model to find the optimal set of base locations and the assignment of ambulances to the base locations. After that, we fixed the base locations to be the locations that are currently in use in the region of Amsterdam. Currently, nine different base locations are used in Amsterdam. We search for the optimal allocation of the ambulances over the existing base locations. Table 1 shows the results for the two experiments. We see that the current set of base locations is not optimal. We can obtain a higher expected coverage with even less base locations. Figure 1 shows the set of selected base locations according to both solutions.

(b) Every point covered

In this paper, we introduced a model to determine good base locations for emergency medical services. The model incorporates the changes in the characteristics of the system during the day. By introducing penalties on locations and relocations, we avoid getting different solutions in all time periods. We obtain that some improvement might be possible in the region of Amsterdam by changing the base locations. In order to get fair solutions, we propose to add a constraint that each demand point should be covered by at least one ambulance. The decrease in overall coverage as a result of this additional constraint is limited.

References [1]

Church, R., and ReVelle, C. (1974), The maximal coverage location problem. Papers in Regional Science.

[2]

Daskin, M. (1983), A maximum expected covering location model: formulation, properties and heuristic solutions. Transportation Science.

[3]

Toregas, C. et al. (1971), The location of emergency service facilities. Operations Research.

35


Counting matchings in cubic graphs Counting matchings in cubic graphs Pim Otte

Pim Otte

What I like about graph theory is that there are deceptively simple theorems and conjectures with a complex proof, or no known proof yet. For my bachelor thesis, I dissected a proof of one of these theorems. The theorem under consideration is the one proven by Esperet et al. [1] Because this theorem arose naturally from a problem in physics, this allows for a simple introduction.

C

C

C

C C

C

In Figure 1 a piece of carbon nanotube is depicted. To chemists, it will be apparent immediately why it is incomplete: each carbon atom has only three bonds, where four are required. However, like in benzene, these bonds are not fixed. The fourth bond of each carbon atom is flexible and moves around the molecule. This means that additional bonds are needed. Two of the possible scenarios are depicted in Figure 2.

C

Mathematics

C

C C

C

C

C

C

C C

C

Figure 2: Two possible arrangements for the fourth bonds.

One can imagine that the number of ways in which these final bonds can be arranged conveys something about the chemical properties of these substances. In particular, there exists a relation between the stability of these chemicals and the number of ways the fourth bonds can be added.

An exponential bound To translate this problem to a mathematical context, we observe that we can view these structures as graphs. Each carbon atom represents a node and the three fixed bonds are the edges in this graph. Note that this graph is 3regular, as each node has three edges. Such graphs are also known as cubic. A possible arrangement of final bonds corresponds to a selection of edges, such that each node is incident with exactly one of these edges. In graph theory this is known as a perfect matching. If we denote the number of perfect

36

Theorem 1 (Esperet et al. / Lovász-Plummer). There exists an ϵ > 0 such that for any cubic bridgeless graph G the following holds: 2ϵ|V (G)| ≤ |M(G)|. The particular significance of this result is that it proves that there is an exponential lower bound to the number of matchings. Earlier work only showed linear bounds, or proved that a superlinear bound existed. Esperet et al. 1 proved that this theorem holds with ϵ = 3656 . In [2] we improve this proof 1 to show that a better lower bound with ϵ = 1686 also holds.

Proof tactic

Figure 1: An incomplete piece of carbon nanotube.

C

matchings by M(G), then the following theorem, which was first conjectured by Lovász and Plummer.

As mentioned, the proof of this theorem is more complex than the simplicity of the theorem suggests. We will now provide a general overview of the proof by Esperet et al. The proof starts by defining balanced probability distributions. These distributions are on the set of matchings on (a part of) a graph and have the property that any edge has equal probability of being in a matching.

Burls and foliages Following this, burls are defined. A subset of vertices is called a burl, if the graph restricted to this subset is likely to contain an alternating cycle in a random matching, drawn from a balanced probability distributions. Alternating cycles are very relevant, because they can be used to obtain a new matching from another. Consider the left part of Figure 2. In this part an alternating cycle can be found, namely the only cycle of length six in this part. A second matching can be derived by changing double and single bonds along this cycle. Compare this to the right part of Figure 2. In this part, no alternating cycle can be found, hence there is no second matching that keeps the outgoing, dotted lines the same. A set of pairwise disjoint burls is called a foliage. Because an alternating cycle is expected in each burl, and these burls are independent from each other, we expect n disjoint alternating cycles if a graph has a foliage with size n. Because we can create a new matching by adding and removing the edges along each alternating cycle independently, this means that we can find 2n matchings starting with a single matching.

Finding foliages The only question remaining is: how do we find a foliage with enough burls? Enter the small-cut-decomposition. This decomposition maps a graph to a tree, such that every edge in the tree induces a cut of size 2 or 3 in the original graph. This fact can be used to reason about the original graph using just the structure of the tree. It turns out that certain long paths in the tree of a small-cut-decomposition correspond with burls in the original graph. This is the part in the original proof that has been replaced with a stronger lemma to yield the higher epsilon mentioned above. Finding the foliages causes a lot more issues then sketched above and the details are beyond the scope of this article. Instead we will investigate the mathematics of balanced probability distributions and burls.


Balanced probability distributions

v2

To be able to define balanced probability distributions, we first need to know what they are defined on. Given a graph G and X ⊆ V (G), we define EX to be the set of all edges with at least one endpoint in X. We can then define M(G, X) as the family of subsets of EX which are incident with every node in X exactly once. We observe that M(G, V (G)) is exactly the set of all perfect matchings of G.

v1

b

v4

e

v3

Definition 1 (Balanced probability distribution). A probability distribution M on M(G, X) is called balanced, if Pr[e ∈ M] = 13 for every e ∈ EX .

Figure 4: Small example of a burl

Example If we consider K4 , the full graph on 4 points, then M(G, V (G)) consists of three matchings and each of the six edges is contained in exactly one of these matchings. Hence, in a balanced probability distribution, each of these matchings should have probability 13 . v1

e13

v3

e12

e14 e23

e34

Namely, the union of the two is this cycle. This means that M contains an M -alternating cycle with probability at least 23 , which yields E[a(G, X, M)] ≥ 23 ≥ 13 . Therefore X is a burl.

Using matrices to determine burls

v2 1

1

2

2



1 0   0 1

e24

v4

Figure 3: K4

0 1 0 0

 1 0   0 0

Figure 5: Matrix representation for a small subgraph In Figure 5 we present a matrix representation of a potential burl. We split this by possibilities for inclusion on the dashed edges. The first 1 in this matrix signifies that there exists one element of M(G, X) which does not use any dashed edges. Similarly, there are elements of M(G, X) that use no edges on one side and both edges on the other side, as well as elements that just use dashed edge 1 on one side and dashed edge two on the other side. This is relevant, because we can chain these kinds of elements and obtain a matrix representation by multiplication, as depicted in Figure 6. 1

1

2

2



2 0   0 1

0 1 0 0

0 0 1 0

 1 0   0 1

Figure 6: Matrix representation for a small subgraph by multiplication.

Mathematics

If we look at balanced distributions on M(G, {v1 , v2 }) instead, already more options for balanced distributions exist. Note that M(G, {v1 , v2 }) = {{e12 }, {e13 , e23 }, {e14 , e24 }, {e13 , e24 }, {e14 , e23 }}. Three of these are restrictions of elements of M(K4 ) and two of those are not. To obtain a balanced probability distribution, Pr[M = {e12 }] = 13 is necessary, because that is the only element containing e12 . If we define x = Pr[M = {e13 , e23 }], then we can compute that for a balanced probability distribution we need to have Pr[M = {e13 , e24 }] = Pr[M = {e23 , e14 }] = 13 − x and Pr[M = {e23 , e24 }] = x. This yields a valid balanced probability distribution for 0 ≤ x ≤ 13 , and for x = 0 this distribution is the restriction of the only balanced probability distribution on M(K4 , V (K4 )). This example demonstrates the notion of restriction: A balanced distribution on M(G, X) can be restricted to M(G, Y ) if Y ⊆ X. In addition, it shows that balanced distributions can be unique, but in general they are not.

0 0 1 0

Burls

Want to know more?

We will now define the notion of “probably has an alternating cycle” more precisely. By a(G, X, M ) we denote the maximum number of disjoint M alternating cycles in G|X, the graph G restricted to the vertices in X.

If you would like to know how these matrices can be used to prove the above vertex set is a burl, or you want to know about this proof in more detail, I recommend reading the ArXiv version of [1] along side my thesis [2]. If you are interested in these kinds of proofs or this field in general, you can talk to Dion Gijswijt, or take one of his courses: Combinatorische Optimalisering (BSc) or Discrete Optimization (MSc).

Definition 2. A burl is a vertex set X ⊆ V (G) such that for any balanced probability distribution M on M(G, X) it holds that E[a(G, X, M)] ≥ 13 . The property that makes this definition tick, is the fact that it is local. You can determine if X is a burl, by only considering the nodes in X and the edges in EX . We will now consider one of the smaller burls possible, depicted in Figure 4 For any balanced probability distribution M on M(G, X), where X = {v1 , v2 , v3 , v4 }, it must hold that Pr[eb1 ∈ M] = 13 . This implies that Pr[eb1 ∈ / M] = 23 . From Figure 4 it becomes apparent that the only elements of M(G, X) that do not contain eb1 are {e12 , e34 } and {e13 , e24 }. However, each of these matchings induces an M -alternating cycle within X.

References

[1] Louis Esperet, Frantisek Kardos, Andrew King, Daniel Kral, and Serguei Norine. Exponentially many perfect matchings in cubic graphs. Advances in Mathematics, 227(4):1646–1664, 2011. [2] Pim Otte. Counting matchings in cubic graphs. BSc thesis, 2014.

37


Arithmetische progressies in random Arithmetische progressies in random kleuringen van de natuurlijke kleuringen van de natuurlijke getallen getallen Rik Versendaal

Rik Versendaal

’Hoe groot moet een verzameling zijn, zodanig dat er willekeurig lange patronen in voor komen?’ Deze vraagstelling is typisch voor Ramseytheorie, die we nu verder zullen bestuderen. Natuurlijk is niet elk patroon even moeilijk om te vinden. De patronen waar wij naar op zoek gaan, zijn zogeheten arithmetische progressies. Een arithmetische progressie is eigenlijk niets anders dan een rijtje natuurlijke getallen van de vorm

Echter, de priemgetalstelling geeft ons dat |P ∩ [1, n]| = lognn (1 + o(1)). Als we dat nu invullen in de definitie van de dichtheid, dan vinden we dat d(P) = lim sup n→∞

|P ∩ [1, n]| 1 = lim (1 + o(1)) = 0 n→∞ log n n

De vraag is nu, of er een andere voldoende voorwaarde bestaat die ook verzamelingen met dichtheid 0 toelaat. In 1737 heeft Euler laten zien dat ∑1 =∞ p p∈P

a, a + b, a + 2b, · · · , a + kb Het moge duidelijk zijn dat we deze patronen zo lang kunnen maken als we zelf willen. Maar wanneer bevat een verzameling nu arithmetische progressies van iedere lengte? Gelukkig is daar al het een en ander over bekend.

De vraag is nu, of we deze eis ook als ’groot genoeg’ kunnen nemen. Dat brengt ons bij het vermoeden van Erdös en Turan.

De stelling van Van der Waerden geeft ons het volgende

Vermoeden 1 (Erdös-Turan). Laat A ⊂ N. Neem aan dat

Stelling 1 (Van der Waerden). Stel dat we N kleuren met k verschillende kleuren. Dan bevat ten minste één van de zo verkregen k deelverzamelingen willkeurig lange arithmetische progressies. Door N te kleuren met k kleuren, delen we de natuurlijke getallen in feite op in k deelverzamelingen. De stelling van Van der Waerden vertelt ons dan, dat ten minste één van deze deelverzamelingen ’groot genoeg’ is om willekeurig lange arithmetische progressies te bevatten. Hij geeft ons alleen niet welke deelverzameling dat dan moet zijn. Om daar wat over te kunnen zeggen, moeten we ’groot genoeg’ wat preciezer maken.

Mathematics

Voordat we ’groot genoeg’ op een geschikte manier kunnen definiëren, moeten we eerst kijken naar de zogeheten dichtheid van een verzameling A ⊂ N in de natuurlijke getallen. De dichtheid d(A) is eigenlijk niets anders dan welke fractie de verzameling A van N is. Iets preciezer is het volgende d(A) = lim sup n→∞

|A ∩ [1, n]| n

Het blijkt nu dat een verzameling A ⊂ N in ieder geval groot genoeg is als d(A) > 0. Dat is wat de stelling van Szemerédi ons geeft.

Stelling 2 (Szemerédi). Laat A ⊂ N zodanig dat d(A) > 0. Dan bevat A willekeurig lange arithmetische progressies.

∑ 1 =∞ n n∈A Dan bevat A willekeurig lange arithmetische progressies.

Random kleuringen Als we nu eens terugkijken naar de stelling van Van der Waerden, dan zien we dat we de natuurlijke getallen in feite opdelen in stukken door de getallen kleuren te geven. Maar dat kunnen we natuurlijk ook op een willekeurige manier doen. Dan komen we aan bij het idee van een random kleuring. Een random kleuring is eigenlijk niets anders dan een rij stochasten (Xn )n die waarden aannemen in een verzameling kleuren {0, 1, 2, . . . , k − 1}. Hier betekent Xn = c natuurlijk dat getal n kleur c heeft. Wij zullen ons beperken tot een kleuring met maar twee kleuren, namelijk een 0 (wit) en 1 (zwart). Ons doel is nu om uitspraken te doen over het bestaan van willekeurig lange arithmetische progressies in de zwart gemaakte getallen. In het bijzonder zullen wij ons beperken tot arithmetische progressies van de vorm n, 2n, 3n, . . . , kn Maar hoe gaan we die terugvinden in een random kleuring?

Het is echter niet noodzakelijk dat de dichtheid groter dan 0 is. Daarvoor gaan we kijken naar de verzameling P van priemgetallen.

We willen dus weten wanneer de getallen n, 2n, . . . , kn allemaal zwart zijn. Dat is hetzelfde als afvragen of

Over de verzameling priemgetallen hebben Ben Green en Terence Tao in 2004 het volgende bewezen.

Xn = X2n = · · · = Xkn = 1

Stelling 3 (Green-Tao). De verzameling P van priemgetallen bevat willekeurig lange arithmetische progressies.

38

Maar dat is in onze situatie precies hetzelfde als nagaan of Xn X2n · · · Xkn = 1


Verder is dit product 0 zodra één van de getallen wit is. Daarom is Sk =

∞ ∑

n=1

Xn X2n · · · Xkn

dus het stochastisch aantal arithmetische progressies in een random kleuring.

bn = log1 n en verder b1 = 0 en b2 = 1. De zwarte getallen in deze random kleuring vormen nu de stochastische priemgetallen. Merk nu allereerst op dat inderdaad geldt dat bn → 0. Merk verder op dat voor iedere k ∈ N geldt dat ∞ ∑

We zullen ons nu beperken tot wat we kunnen zeggen als we de getallen onafhankelijk kleuren. Dan zijn de Xn als volgt verdeeld

Maar dan voldoen we dus aan de zwakke aanname, en dan geeft stelling 4 ons dat de stochastische priemgetallen in kans oneindig veel arithmetische progressies bevatten van iedere lengte.

P (Xn = 1) = bn P (Xn = 0) = 1 − bn We gaan nu iets beter kijken naar de bn , de kans dat het getal zwart wordt gemaakt. Als de bn niet naar 0 gaat, dan heeft de verzameling zwarte getallen naar verwachting een positieve dichtheid. Maar dan weten we al vanuit de stelling van Szemerédi dat de verzameling zwarte getallen dan willekeurig lange arithmetische progressies bevat. Wat we dus aannemen, is dat bn → 0. We kunnen ons wel voorstellen, dat als bn heel snel naar 0 gaat, dat we dan geen willekeurig lange arithmetische progressies kunnen verwachten. Daarom moeten we dus iets verzinnen om ervoor te zorgen dat we de snelheid waarmee bn naar 0 gaat kunnen controleren. We doen de volgende aanname. Aanname 1 (Zwakke aanname). Voor iedere k ∈ N geldt er dat ∞ ∑

n=1

Bk (n) = E

i=1

Sterke wet van de grote aantallen We sluiten af met een korte bespreking van hoe we bovenstaand resultaat nog kunnen verbeteren. We willen namelijk dat de convergentie bijna zeker wordt, en niet alleen in kans. Helaas gaat dit ten koste van een extra aanname. We moeten de zwakke aanname namelijk uitbreiden met een gladheidseis. Aanname 2 (Sterke aanname). Voor iedere k ∈ N geldt er dat ∞ ∑

n=1

Voordat we naar een rijtje gaan kijken die wel aan de aanname voldoet, kijken we eerst naar wat er nu eigenlijk precies volgt uit de aanname. Voor de duidelijkheid definiëren we eerst het volgende n ∑

Herinner nu, dat de stelling van Green en Tao ons geeft dat de priemgetallen willekeurig lange arithmetische progressies bevatten. Bovenstaande is dus eigenlijk een zwak stochastisch analogon van deze stelling.

bn b2n · · · bkn = ∞

Dit geeft ons inderdaad controle op de snelheid waarmee bn naar 0 gaat. Als 1 we bijvoorbeeld bn = n nemen, dan gaat dit al te snel naar 0, want er geldt met k = 2 dat ∞ ∑ 1 1 <∞ n 2n n=1

[

n=3

]

Xi X2n · · · Xkn =

1 1 1 ··· =∞ log n log(2n) log(kn)

n ∑ i=1

bi b2i · · · bki

Stelling 4. Onder de zwakke aanname geldt er voor iedere k ∈ N dat n 1 ∑ Xi X2i · · · Xki → 1 in kans Bk (n) i=1

Omdat uit de aanname volgt dat limn→∞ Bk (n) = ∞, zegt deze stelling eigenlijk dat het aantal arithmetische progressies van lengte k in een random kleuring die aan de zwakke aanname voldoet in kans, oneindig is. We zullen nu gaan kijken naar een toepassing hiervan.

Stochastische priemgetallen Nu zullen we gaan kijken naar een toepassing van dit resultaat. Daarvoor zullen we gaan kijken naar de zogeheten stochastische priemgetallen, zoals Cramèr die heeft gedefinieerd. Eerder hebben we al gezien, dat het aantal priemgetallen kleiner dan n ongeveer gelijk is aan lognn . Met dat in gedachte kunnen we de ’kans’ dat n een priemgetal is definiëren door log1 n . Om ervoor te zorgen dat het model goed gedefinieerd is, definiëren we voor n > 2 dus

én limn→∞ nδ bn bestaat voor iedere δ ∈ (0, 1). Het zal blijken dat uit het eerste deel van de aanname zelfs volgt dat limn→∞ nδ bn = ∞ voor iedere δ ∈ (0, 1). Met deze aanname krijgen we het volgende resultaat. Stelling 5. Onder de sterke aanname geldt er voor iedere k ∈ N dat n 1 ∑ Xi X2i · · · Xki → 1 met kans 1 Bk (n) i=1

Het is eenvoudig om te laten zien dat voor iedere δ ∈ (0, 1) geldt dat δ

n limn→∞ log = ∞. Maar dan geeft stelling 5 ons nu ook het sterke ston chastische analogon van de stelling van Green en Tao!

Conclusie

Mathematics

In dat geval is Bk (n) het verwachte aantal arithmetische progressies van lengte k in het interval [1, kn]. We krijgen nu het volgende resultaat:

bn b2n · · · bkn = ∞

Al met al, zijn we er dus in geslaagd om voorwaarden te vinden op hoe groot onze verzameling zwarte getallen naar verwachting moet zijn, zodanig dat deze in kans, of zelfs bijna zeker, willekeurig lange arithmetische progressies bevat. Alhoewel, we hier alleen naar onafhankelijke kleuringen hebben gekeken, zijn er ook gelijksoortige resultaten haalbaar voor bepaalde afhankelijke kleuringen, zoals kleuringen volgens een Markovketen.

39


Historical Person: Nicomachus Nicomachus (c. 60 – c. 120 AD) Cathaline Meloen

Catheline Meloen

Nicomachus (c. 60 – c. 120 AD) was a mathematician in the ancient

numbers he stated that:

world. Very little is known about his private life other than that he was

the nth perfect number has n digits; all perfect numbers end in either 6 or 8 in alternating order.

born in Gerasa, a Roman province of Syria. Nicomachus knew a lot of the works of great philosophers such as Plato (424/428 BC – 348/347 BC), Aristotle (384–322 BC), Euclid (flourished 300 BC) and Pythagoras (c. 570 – c. 495 BC). Nicomachus is considered a Neopythagorean. One of the characteristics of Neopythagorean philosofy is a tendency to assign mystical properties to numbers. One might feel alarmed by this rare congregation of mysticism and science, and it turns out these concerns are very much justified.

Famous works In music theory Nicomachus has contributed with his writing Manual of Harmonics. This is the first important music theory dissertation since the time of Aristoxenus of Tarentum (335 BC), who was a pupil of Aristotle and of Euclid of Alexandria, who was a Greek mathematician (323–283 BC), famous for his work Elements. Manual of Harmonics describes the story of Pythagoras’s epiphany that pitch is determined by numeric ratios. It also gives the first profound account of the relationship between music and the ordering of the universe via the music of the spheres. Music of the spheres is also a theory by Pythagoras that states that mathematical relationships express tones of energy which reveal itself in numbers, angles, shapes and sounds by a pattern of proportion. While explaining musical theories he describes the instruments of his time.

These assumptions are wrong, and he didn’t prove them, but merely assumed they were correct relying on these four examples.

Criticism Most mathematicians later in history very much disliked the work. On the other hand, several other mathematicians such as A. M. S. Boethius (480 – 524) translated Introduction to Arithmetic into Latin and it became a standard school book. Mathematician Thomas Little Heath (1861 – 1940) tries to explain the popularity of such a poorly written book suggesting that: ”... it was at first read by philosophers rather than mathematicians, and afterwards became generally popular at a time when there were no mathematicians left, but only philosophers who incidentally took an interest in mathematics.”

Something positive Despite the criticism his major work received centuries after his death, Nicomachus was considered to be good at something scientific after all, as proven by the words of an Athenian rhetorician, pamphleteer and satirist (120 AD ?) who made one of his characters say: ”You calculate like Nicomachus.”

Introduction to Arithmetic

Miscellaneous

Nicomachus’ unscientific fascination for mysticism is apparent in this book. The book contains both philosophical and basic mathematical ideas. This is the first work written that treats arithmetic as a separate topic from geometry.

Lack of proof A large weakness and source for errors is the lack of abstract proofs throughout his theorems; they are merely illustrated with numerical examples. Results used in this book often appeared in the works of Euclid in geometrical formulation, which is why Nicomachus knew they were correct. Unfortunately there are also many real errors in the book, as he bases his theories on examples that have the demanded properties for the theorem to be correct. Sometimes he even uses one example to proof a theory, which makes one question his scientific integrity.

Divine numbers Nicomachus distinguished numbers in divine numbers and scientific numbers. He considered prime numbers and perfect numbers (a positive integer that is equal to the sum of its proper positive divisors) of great interest and believed that arithmetic is the cause of all the other mathematical sciences (music, geometry, and astronomy). A well-known example of false assumptions are two of his quotes on perfect numbers: Four perfect numbers where known during Nicomachus’ lifetime: 6, 28, 496 and 8128. Based on these four

40

References

[1] http://www-history.mcs.st-and.ac.uk/Biographies/Nicomachus.html [2] http://en.wikipedia.org/wiki/Plato [3] http://en.wikipedia.org/wiki/Introduction_to_Arithmetic [4] http://en.wikipedia.org/wiki/Nicomachus [5] http://en.wikipedia.org/wiki/Musica_universalis [6] https://ia600709.us.archive.org/27/items/NicomachusIntroToArithmetic/nicomachus-intro-toarithmetic_no-ocr.pdf [7] http://mathworld.wolfram.com/NicomachussTheorem.html [8] http://en.wikipedia.org/wiki/Hellenistic_philosophy

Big Data start-up hunting for talent! Are you almost finishing your study and looking for a challenge? Are you an ambitious and enthusiastic young professional? Than Prime Data is looking for you! Prime Data is in a constant search for enthousiastic and entrepreneurial young professionals. We have positions ranging from R&D experts to system engineers, from data scientists to developers. Prime Data is a fast growing company that provides solutions to customers that have a need for decision support information based on large amounts of fastly changing data. We solve complex problems with robust, efficient and reusable software and platform solutions. At Prime Data you are part of a young team. You determine the further professionalisation and expansion of our solutions. Your assignments are varied, from web-based management information systems to flexibly setting up business logic of sophisticated logical decision making systems and ranging from sensor data in process industry to smartphone data for the traffic industry. If this sounds like you: • (Almost) Completed Bachelor / Master’s degree or background in information science, computer science, or otherwise technical related study; • Looking for an internship, traineeship or job; • Interested in the development of big-data based products and services; • Passionate and fascinated about the possibilities of data, Internet and mobile; • Out-of-the-box thinking and entrepreneurial; ...then we are very interested in meeting you! Send us your application (C.V. and short motivational letter) to: [email protected] and we will meet soon!

Prime Data BV • Olof Palmestraat 16-18 • 2616 LR Delft, The Netherlands • www.primedata.nl

IDR as a Fixed-Point Method for Solving Linear Systems of Equations Martin van Gijzen

Studeren in het buitenland Thijs Jacobs

Voor mijn minor van Technische Wiskunde ben ik op exchange naar Zwitserland gegaan. Ik heb in de eerste vijf weken in Zürich al ontzettend veel beleefd en wil jullie in dit stuk graag meenemen naar het land van bergen, chocola en zakmessen.

Het land

Miscellaneous

Wat waren de allereerste weken op de TU in 2012 toch mooi. Ik had nooit verwacht dat wiskunde zo super gaaf en bijzonder kon zijn. Maar dan, twee jaar later, als de meeste studenten van mijn jaar een minor gaan doen, verlaat bijna iedereen de wondere wereld van de wiskunde om een half jaar civiele techniek, geneeskunde of zelfs Latijn te studeren. Dat leek mij verschrikkelijk, dus dat zou ik anders aan gaan pakken. En als het dan toch een vrije minor wordt, waarom niet in het buiteland. Na wat stress voor de application deadlines die in de tentamenweek vielen, wist ik ergens rond maart dat ik naar de Eidgenössische Technische Hochschule (ETH) in Zürich mocht. Wat een feest, en half jaar lang, eigen gekozen vakken op een hoog aangeschreven universiteit doen! Maar de prioriteiten van dat moment lagen bij het vinden van een kamer in een overvolle stad als Zürich. Dat bleek echter niet een groot probleem, want Guus Geluk hier kreeg een relatief goedkope kamer aangeboden door de universiteit. En toen begon het allemaal op 1 september 2014. Maar de wiskunde moest eerst nog even plaats maken voor een Duits talencursus van twee weken. Een prima manier om mensen te leren kenen, heb ik mij laten vertellen. En dat bleek, want met mensen vanuit heel de wereld die ook nog niemand kenden, was het snel vrienden maken. En zoals iedereen weet van vakanties, Nederlanders zijn overal. Zo bleek ook een goede delegatie vanuit Delft aanwezig te zijn op deze cursus. De Duitse ’intensiv Kurs’ bleek niet zo heel intensief te zijn en er was genoeg tijd om Zürich en andere mensen te leren kennen. Het was zeker een goede start, waarbij je na de lange vakantie kon wennen aan het doordeweekse leven. Want vanaf 14 september was de shit aan! De vookeur voor pure wiskunde, die ik de afgelopen twee jaar heb ontwikkeld, zorgde voor de keuze van wat lekkere hardcore vakken. Het is een stapje hoger dan

42

ik gewend ben in Delft, mede doordat mijn derdejaars vakken hier ook master vakken zijn. Maar daarover later meer. Jij als CH lid bent vast nieuwsgierig hoe het met de studenten- en studieverenigingen hier in Zürich zit. Ten eerste, studentenvereningen bestaan hier helemaal niet, wat bovendien past in het plaatje van de toch wat serieuze student aan de ETH. Studieverenigingen bestaan daarentegen wel. Tot mijn grote schrik bleek dat de wiskundevereniging hier niet samen met informatica zat, maar met natuurkunde. En tot overmaat van ramp hebben ze het vernoemd [ ] naar een voor een wiskundige nietszeggende natuurkundige formule: VPM . Belangrijker voor Exchange Students zoals ik, is Erasmus Student Network (ESN). Zij organiseren activiteiten voor internationale studenten zoals feestjes, bbq’s en tripjes binnen Zwitserland. Iets als een OWee kennen ze in Zürich niet, wat denk ik alweer te maken heeft met de iets serieuzer aangelegde studenten hier. En dat is niet perse een negatief punt, ik voel me hier zeker thuis in de studie gerichte houding van de studenten. Sport is hier centraal door een vereniging geregeld. Als student krijg je gratis toegang tot alle openbare trainingen van bijna elke sport, dat zouden we ook in Delft moeten hebben! Graag zou ik ook wat woorden willen wijden aan de Zwitserse cultuur. Ook al is het niet ver weg en lijkt deze misschien best op die van Nederland, blijft het mij nog steeds verbazen. Alles is hier zo ontzettend goed geregeld. Er is heel veel openbaar vervoer in de stad, en dat rijdt uiteraard altijd op tijd. Alles wordt hier gescheiden en recycled, tot de kleur van het glas aan toe. Maar het zit ook in de kleine dingen. Zo heb ik gisteren een nieuw huisgenootje gekregen, en zijn nu al de namen op de brievenbus veranderd! In Zürich zelf zie je heel veel mensen in pak rondlopen en ontzettend veel dure auto’s langskomen. Misschien komt het omdat maar liefst 27 procent van de inwoners van Zürich US-dollar milljonair is. Verder is het bijvoorbeel heel bijzonder dat hier elke Zwitser rond zijn 20e een half jaar in het leger moet, om hier een basisopleiding te krijgen. Ondanks de neutrale houding van het land heeft bijna elk huis een bunker voor als de oorlog uitbreekt. Naast het leven in de stad, bezit het land echt super bijzondere natuur. Waar in Delft het passeren van de Sebastiaansbrug de grootste hoogtestijging van de hele omgeving vergt, zijn hier echte heuvels en bergen. En dat is gaaf! Verderop in het land, in de buurt van Luzern beginnen de Alpen wat zich goed leent


voor mooie wandeltochten. Genoeg over Zwisterland, anders is het niet meer interessant om een keer een bezoekje aan het land te komen brengen.

De wiskunde Onder het motto: ”meer echte wiskunde in het Machazine” wil ik graag met jullie, een stukje wiskunde wat ik afgelopen weken hebt geleerd, delen. En ja, hiermee wil ik zeggen dat vervelende PDV’s en realistische modelletjes geen echte wiskunde is. Graag zou ik willen beginnen met quote van Einstein: ”Als je het niet simpel kan uitleggen, dan begrijp je het niet goed genoeg. ”Dus ik ga mijn best doen voor jullie! Het komende stuk komt uit het vak Algebraïsche topologie. Men spreekt veel over Topologische ruimtes, als je niet (meer) weet wat het is, denk dan aan Rn .Een definitie: Een pad van x naar y in een Topologische ruimte X is een continue functie γ : [0, 1] −→ X zodat γ(0) = x en γ(1) = y. Nu zijn er natuurlijk in het algemeen ontzettend veel paden van x naar y. Denk bijvoorbeeld aan het pad dat in een rechte lijn van x naar y gaat, of één met drie loopings en een S-curve. Wat we nu graag willen is iets kunnen zeggen over wanneer twee paden bijna hetzelfde zijn. Hoe we dat bedoelen wordt duidelijk in de volgende definitie: Een homotopie tussen paden γ en β van x naar y is een continue functie F : [0, 1] × [0, 1] −→ X zó dat F (0, s) = γ, F (1, s) = β, F (t, 0) = x en F (t, 1) = y. In woorden: twee paden zijn bijna hetzelfde als je ze continu in elkaar kunt vervormen. Eigenlijk zijn we een beetje aan het duwen en trekken aan een elastiek tussen punt x en y. Voor een mooie animatie raad ik de Wikipedia pagina hiervan aan. We zeggen dat twee paden in relatie zijn als er een homotopie tussen de paden bestaat. Deze relatie blijkt een equivalentierelatie te zijn, en dus kunnen we equivalentieklassen definiëren.

Laten we maar iets intressanters opzoeken dan. De cirkel in R2 . En laten we in deze ruimte eens de paden van x naar hetzelfde punt x bekijken, keuze van x is willekeurig. Het simpelste pad is het pad γ : [0, 1] −→ X gegeven door γ : t −→ x, een pad wat lekker helemaal nergens heen gaat. Dit pad is natuurlijk het homotopische equivalent, lees: bijna helemaal hetzelfde,

Miscellaneous

Om even de definities wat te laten bezinken geef ik een voorbeeld. Neem nou eens een bol in R3 en twee willekeurige punten in deze bol. Bedenk nu voor jezelf twee paden van het ene punt naar de ander. Met wat voor ingewikkelde paden je ook komt, door op de goede manier het elastiek te duwen en te trekken, kan je continu het ene pad in het andere vervormen. Elk pad van x naar y in de bol is dus bijna hetzelfde! Niet echt een interessante ruimte dus.

als het pad wat eerst een rondje linksom maakt, daar x aantikt, en dan een rondje rechtsom maakt om weer in x te eindigen. Dit gekke pad zit dus in de equivalentieklasse van γ. Een pad van x naar x wat wel echt anders is, is die alleen een rondje linksom maakt. Herriner dat de ruimte waar we op leven alleen de cirkel is. Hoe we dit nieuwe pad ook gaan duwen of trekken, hij zal altijd een rondje linksom blijven maken. Maar dit pad is op zijn beurt weer hetzelfde als het pad wat bijvoorbeeld eerste en halve cirkel linksom loopt, dan een kwartcirkel terug rechtsom, om vervolgens driekwart cirkel linksom te gaan om weer in x terecht te komen. Bedenk eens voor jezelf wat voor paden er zijn die homotopie equivalent zijn aan dit pad dat een rondje linksom maakt. Er zijn er oneindig veel, dus de pret raakt nooit op. Het pad dat een rondje linksom maakt is verschillend van het pad dat twee rondjes linksom maakt, of dat een rondje rechtsom maakt. Met dit in gedachte kunnen we bedenken dat deze equivalentieklasse van paden isomorf is met Z. Denk hier op de volgende manier over na: elk pad van x naar x is homotopie-equivalent met een pad wat netjes een aantal keren een rondje linksom of rechtsom gaat. Maar paden die niet even vaak linksom of rechtsom gaat zijn niet hetzelfde. Tel nu simpelweg het aantal keer, noem n, dat het pad linksom gaat. Dan kan je dit pad associëren met het getal n ∈ Z. Het pad dat n keer rechtsom draait kunnen we associëren met −n ∈ (Z). En gek genoeg kan met dit resultaat en met hulp van andere theorie’�en al veel stellingen bewezen worden. Zo bewijzen we hiermee dat er altijd een plek op de aarde is waar het windstil is. Ach, wat maken die toepassingen nou eigenlijk uit, de theorie zelf geeft toch veel meer voldoening.

43


Film review: A Beautiful Mind FILMREVIEW: A Beautiful Mind Rebecca Glans

Rebecca Glans

Ones mind is often seen as extraordinary, when the person can accomplish above average things. Certain artists we admire or doctors we

occur once again, he believes them and it all comes to a point where he is a threat to his environment.

look up to. These are people who see beyond our eyes and open ours even more. We would almost say they posses a beautiful mind. Such a mind has the protagonist John Nash. We come to know John in his freshman year at Princeton university where he makes the impression of your typical genius with a lack of social skills. And, to top it off, some nervous ticks. When you come to find he has a roommate who, despite John’s awful ways of communication, eagerly befriends him, you can only feel happy for him. Our protagonist, unlike his classmates, has not published one paper in his freshman year. He is still looking for his ”original idea” in governing dynamics. He wishes to find a theory which predicts the outcome of decisions made by different participants at the same time, who’s decisions also influence one another. After making little to no progress and almost losing it, his friend and roommate Charles Herman, makes him come to his senses and convinces him to try a different strategy. To not work inside, where this governing dynamics problem would never occur, but to go out and experience the problem and its solution.

”That’s the only way we win”

Miscellaneous

And it worked! In a slightly unexpected but interesting way, John found his solution while studying at a bar. When he and some fellow male students were discussing who would get the gorgeous blond who just walked in with her friends, one brought up Adam Smith ”the father of modern economics”. He once said ”In competition individual ambition serves the greater good” which the boys translated to ”every man for himself”. John, however, saw some incompleteness in this statement as it would now evolve in a not so greater good. Everyone’s so called ambition was the blonde, but all targeting her at once would result in neither of them getting her. The boys would then start going for the blonde’s friends, resulting in failure again as the girls would see themselves as second choices. He then explains they should all initially go for the friends, that way every man will get a girl. Nobody will get the blonde, but everyone wins something. And that is when John finally completed his original idea.

John Forbes Nash, Jr.

It was only afterwards I realised that John making a friend – Charles – and his some sort of protective role in John’s life was the starting point of this movie’s message. This movie is based on the eponymous mathematician John Forbes Nash, Jr. and is not made only to praise his influential works. It shows that his mind, though powerful in solving problems, had unsolvable problems of its own: schizophrenia. John faces a rough period when diagnosed with the mental illness schizophrenia, as important characters in his life seem to be nonexistent. When put under medication he finds that he is unable to continue his work or maintain relationships – his family – and therefore stops taking them. The delusions

44

What is true beauty? Charles was one of the delusions and also John’s closest and dearest friend. Although pointing out many times he does not like people, mainly because they do not like him, he still managed to get a very close friend. Another person who liked him and he liked back. It seems his mind found a solution for his unaware need for a friend. Obviously, it was hard to let such a friend go, but to lose his family was not something John was willing to endure either. Then again, taking medication would require him to sacrifice his ability to work, his passion, and to be there for his family. He then chose to take matter in his own hands, handle the delusions and ignore them for the sake of himself and others. He used the love of his wife and his love of solving problems to keep himself strong. And with his Nobel Price speech it became all clear to me. This movie’s name does not refer to the great intelligence of our John, not in the way we would expect. Yes, John has the ability to influence the world in a way we still experience today. But, how? His mind was ill, deceiving him and giving him a gift at the same time. And where others would have surrendered, he kept on going because of one reason: love. He who lost control of his mind, gained it again by using it in the way it wanted, but benefiting himself as well. He used what he had to its full potential, not because it was possible, but because he finally had a beautiful reason. And for that, this movie wonderfully portrayed a beautiful mind.

Wintersport Ga mee naar Saint Sorlin D’Arves!

30

th

Jan -

8

th

Feb

Skyfall. Mobile Apps. Cubics Graphs. A Beautiful Mind. containing: Gala : shaken not stirred. the future of. counting matchings in

Recommend Documents