Algoritme Les 8

1 / 17
next
Slide 1: Slide
InformaticaMiddelbare schoolhavo, vwoLeerjaar 4

This lesson contains 17 slides, with interactive quiz and text slides.

time-iconLesson duration is: 50 min

Items in this lesson

Slide 1 - Slide

Deze les
  • Toestandsdiagram
  • antwoorden
  • onoplosbare problemen

Slide 2 - Slide

Slide 3 - Slide

  1. 7 paden
  2. 27 mogelijkheden
  3. 3 mogelijkheden
  4. ...........

Slide 4 - Slide

onoplosbare problemen
Er zijn heel veel problemen waar geen snelle oplossing voor bestaat. Van sommige problemen is het zelfs maar de vraag of er wel een oplossing voor is.
Het bijzondere is dat veel van die problemen heel eenvoudig te begrijpen zijn. Ook komen ze in de dagelijkse praktijk voor.

Slide 5 - Slide

Stel je de volgende situatie voor.
Je bent op een plek waar een verzameling dozen staat. Die dozen bevatten waardevolle spullen. Deze dozen hebben niet allemaal hetzelfde gewicht en dezelfde waarde.
Je hebt een rugzak bij je waarmee je maximaal 12 kg kunt vervoeren.

Slide 6 - Slide

Slide 7 - Slide

Je kunt je afvragen welke dozen je in je rugzak moet stoppen zodat er zo veel mogelijk waarde (in euro's) in zit. Dit probleem is beroemd en wordt het rugzakprobleem genoemd. Het is een heel eenvoudig probleem, maar er bestaat geen snel algoritme om het op te lossen. In dit voorbeeld is dat niet zo erg. Want er zijn maar vijf dozen en er mag maar 12 kg mee.

Slide 8 - Slide

Vraag
Probeer een oplossing te vinden voor deze situatie.
Kies de dozen die je in je rugzak stopt om zo veel mogelijk waarde mee te nemen.

Slide 9 - Slide

Oplossing
Na even puzzelen kon je in dit geval de oplossing vinden. Maar dat lukt niet meer als je een hele vrachtwagen mag vullen en je kunt kiezen uit honderden dozen.

Slide 10 - Slide

Er is geen snel algoritme dat het rugzakprobleem oplost. Daarom kunnen we twee dingen doen:

  1. Een algoritme maken dat alle mogelijkheden langsgaat.
  2. Een algoritme maken dat zo dicht mogelijk in de buurt van de oplossing probeert te komen.

Slide 11 - Slide

Alle mogelijkheden langsgaan
We maken dan een algoritme dat correct is. Natuurlijk is zo'n algoritme niet efficiënt, want het kan heel lang duren voordat de oplossing gevonden is. Soms zo lang dat we de oplossing in de praktijk misschien niet vinden.
Een algoritme dat alle mogelijkheden langsgaat, heet een bruteforce-algoritme.

Slide 12 - Slide

bruteforce-algoritme
Iemand neemt een getal tussen 1 en 100 in gedachten. Jij moet raden welk getal dat is.
Een bruteforce-oplossing is dan dat je de getallen één voor één langsgaat. Je raadt 1, dan 2, enzovoort.
Bij het rugzakprobleem is bruteforce nauwelijks een oplossing. Voor kleine problemen is bruteforce soms wel een goede oplossing.

Slide 13 - Slide

Je kent drie sorteeralgoritmen: Bubble, Merge en Quick. Welke van de drie lijkt erg veel op een bruteforce-algoritme?

Slide 14 - Open question

Vraag
Een vrachtwagen moet spullen bezorgen in Amsterdam, Zwolle en Assen. De vrachtwagen vertrekt vanuit Utrecht en gaat eerst naar Amsterdam. De chauffeur kan voor die rit kiezen uit vier routes. Van Amsterdam naar Zwolle zijn er vijf routes mogelijk. En van Zwolle naar Assen ook vijf routes. Voor de terugreis van Assen naar Utrecht zijn er zes mogelijke routes. Om de beste route te bepalen voor de gehele reis gebruiken we een bruteforce-algoritme.
Hoeveel mogelijke routes moet het algoritme onderzoeken?

Slide 15 - Slide

4 * 5 * 5 * 6 = 600 mogelijke routes

Slide 16 - Slide

Volgende les
  • het benaderen van de oplossing van een onoplosbaar probleem
  • het Chinese postbodeprobleem

Slide 17 - Slide