Algoritmen - paardensprong

• Informatica
• Middelbare school
• vwo
• Leerjaar 5

Introduction

lgg

Algoritmen - paardensprong

Dit gifje heeft niks met de les te maken

Agenda

• PLUGGED - Herhalingsquizje ~ 10 min
• UNPLUGGED - stadgids raadsel ~ 10 min
• UNPLUGGED - paardensprong raadles ~ 10 mon
• afmaken: fundament B1

Er is een reiziger die naar een aantal steden moet reizen. Hij wil alle steden maar één keer bezoeken. Hij wil daarnaast zo weinig mogelijk hoeven te reizen. Dit is één van de bekendste moeilijk op te lossen problemen. Je kunt het algoritme van Dijkstra hiervoor niet gebruiken. Waarom niet?

Geef twee voorbeelden waar je een brute-force algoritme voor kan gebruiken.

1. rugzakprobleem (zie fundament)
2. wachtwoorden breken
3. bitcoins minen

Wat is dit voor graaf?

Een gewogen graaf

Alle straten één keer doorlopen

1. Ja, dat kan
2. Nou dat kan dus gewoon helemaal NIET

Alle straten maar één keer doorlopen. Kan dat?

Tip

Als er meer dan twee kruispunten met een oneven aantal aangesloten straten zijn, moeten sommige straten meerdere keren worden doorlopen

Dit is Henk. Henk is een beetje vaag. Maar hij weet wel de weg

Dit zijn Tina en haar moeder en tante. Die willen van Henk de beste route weten. Maar omdat ze lui zijn willen ze niet teveel lopen.

Aan de slag

Fundament B1 - 3. Onoplosbare problemen t/m 3.4

Dit heb ik vandaag geleerd

Volgende les

• Start website project