Onhandelbaarheid

Bestaan er problemen die zelfs voor computers te moeilijk zijn? Ja, die bestaan zeker. Zoals we zullen zien in activiteit 20 is een simpel gesprek, chatten bijvoorbeeld, iets wat computers vrijwel niet kunnen. Niet omdat ze niet kunnen praten, maar omdat ze geen gevoelige dingen kunnen begrijpen of vertellen. En het is zo moeilijk om computers die kennis te leren omdat we zelf maar moeilijk begrijpen hoe we dat zelf doen. Maar dit is niet het onmogelijke probleem waar we het nu over hebben, we gaan in dit gedeelte kijken naar problemen die makkelijk aan de computer te leren zijn door een programma te schrijven, maar de computer kan in dit geval de problemen niet oplossen omdat het te lang duurt om te voltooien: miljoenen eeuwen misschien. Een snelle computer aanschaffen of ontwikkelen heeft ook geen zin. Al is deze nieuwe computer een miljoen keer zo snel, het zal nog honderden jaren kosten om deze problemen op te lossen. We hebben het hier over echt onmogelijke problemen – zo onmogelijk dat het oplossen langer duurt dan de snelste computer kan blijven bestaan!

De activiteiten in Deel II over algoritmes hebben je geleerd om manieren te vinden waardoor computerprogramma’s efficiënter kunnen werken. In dit deel kijken we naar problemen waar geen efficiënter programma’s voor bekend zijn, problemen die computers miljoenen jaren zouden kosten om op te lossen. En we zien dat dit tot vandaag de dag het grootste mysterie in de computerwetenschap is: niemand weet of er een efficiënte manier bestaat om deze problemen op te lossen! Het kan zijn dat nog niemand een goede manier heeft gevonden of dat er gewoon geen goede manier is. We weten het niet. En dat is nog niet alles. Er zijn duizenden problemen die, al lijken ze heel verschillend, in wezen hetzelfde probleem zijn. Wordt één zo’n probleem opgelost, dan kan deze oplossing makkelijk omgezet worden om alle andere problemen op te lossen. In deze activiteiten leer je over deze problemen.

Voor leraren

Er zijn drie activiteiten in dit deel.

De eerste gaat over het inkleuren van kaarten en het tellen van het aantal verschillende kleuren dat nodig is om alle buurlanden een andere kleur te geven.

Bij de tweede opdracht moeten de leerlingen een simpele kaart gebruiken en daarop de meest efficiënte plekken vinden voor een ijskar, zodat niemand heel ver hoeft te lopen voor een ijsje.

De derde is een buitenactiviteit waar je touw en haringen voor nodig hebt om te ontdekken hoe je netwerken maakt door punten te verbinden.

De activiteiten laten op een praktische manier de studenten het idee van complexiteit ervaren – hoe problemen die makkelijk te verklaren zijn soms juist heel moeilijk opgelost kunnen worden. Dit hoeven echt geen ingewikkelde problemen te zijn. Het zijn alledaagse vragen die voorkomen bij het in kaart brengen van dingen, roosters maken op school en bij het plannen van wegen. Het computerterm dat hierbij hoort heet “NP-volledigheid” wat verder wordt uitgelegd in de Waar gaat dit eigenlijk over? secties aan het eind van iedere activiteit. Hoewel de activiteiten in het eerste deel los van elkaar en in iedere volgorde gedaan zouden kunnen worden, is het in dit deel wel de bedoeling dat ze op volgorde worden gedaan. Als je bij de laatste opdracht bent zal de meest belangrijke open vraag in de hedendaagse computerwetenschap je geheel duidelijk zijn.

De technische Engelse term die computerdeskundigen voor deze moeilijke problemen gebruiken is “intractability” ofwel onpraktische groot. Onpraktische grote problemen zijn moeilijk op te lossen omdat het te lang zou duren om tot een antwoord te komen. Het klinkt misschien als grootspraak, maar als bij de oplossing van dit soort problemen een doorbraak komt zal dit een zeer grote impact hebben voor heel veel soorten onderzoek. De meeste versleutelde codes zijn erg afhankelijk van deze onhandelbaarheid en als iemand met kwade bedoelingen tot een oplossing komt voor deze problemen kan hij allemaal versleutelde wachtwoorden en bestanden achterhalen en verkopen of de bank geld naar hem over laten maken. We zullen in Deel 5 – Cryptologie, hier nog verder op in gaan.