Wie met wie seks heeft gehad op de studentenvereniging, het wegennet tussen Nederlandse steden, de getallen van één tot en met duizend met minstens één gezamenlijke deler. Het zijn allemaal voorbeelden van een graaf – een verzameling knooppunten met verbindingen ertussen. Het is berucht ...
Sommige problemen kunnen door een computer efficiënt worden opgelost, andere niet. In die categorie bevindt zich ook Mario, het befaamde Nintendospel uit de jaren tachtig en negentig van de vorige eeuw. Dat hebben wetenschappers van het Massachusetts Institute of Technology bewezen.
Het vierkant hierboven lijkt op het eerste gezicht een willekeurige kleuring van 17 × 17 vakjes. Maar achter deze schijnbare willekeur gaat wiskunde schuil. Het vierkant is namelijk de oplossing van het zogeheten ‘17 × 17 probleem’.
Informatici van het Massachusetts Institute of Technology hebben een methode gevonden om willekeurig grote Rubikkubussen op te lossen. Ze vonden dat het maximale aantal stappen om een n x n x n kubus op te lossen, van de orde n kwadraat gedeeld door log n is.
“Bijen kunnen het Handelsreizigersprobleem sneller oplossen dan computers. Ze zijn in staat om telkens de kortste weg te kiezen tussen bloemen. Laat een computer hier op los en hij is jaren bezig met complexe wiskundige berekeningen om tot dezelfde ideale route te komen.” Over de d...
Een van de zeven ‘millennium problems’ – wiskundige vraagstukken waarmee een miljoen dollar verdiend kan worden – is het ‘P versus NP probleem’. NP-problemen zijn grof gezegd ‘heel moeilijke problemen’. Een bijzondere klasse van NP-problemen heet...