Les 7 - Onoplosbare problemen - over tijdcomplexiteit

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4-6

Bubble sort

Over tijdcomplexiteit

Onoplosbare problemen

Leerdoel

Aan het eind van deze les kun je uitleggen waarom verschillende problemen een andere tijdcomplexiteit hebben. Ook ken je een voorbeeld van een onoplosbaar probleem en kun je rijk worden door het P- vs NP-probleem op te lossen.

Onoplosbare problemen?

• Niet voor alle problemen is er een perfect algoritme
  
• Hoe zit dat en wat voor problemen zijn dat?

Het rugzakprobleem

Stel...

• In je rugzak past maximaal 12 kg.
• Je wilt zoveel mogelijk waarde
  (in euro’s) meenemen
  

Welke dozen moet je in je rugzak
stoppen?

Sleep de dozen die samen zoveel mogelijk waarde (in euro's) vormen in de rugzak

Oplossing van het rugzakprobleem

De doos van €12 heeft weliswaar de hoogste waarde, maar als je deze doos kiest, mag er nog maar 1 kilogram in de rugzak. Je kunt dan maximaal €2 aan waarde toevoegen,
voor een totaal van €14. De combinatie
van de lichtere dozen
(€2 + €2 + €3 + €8 = €15) is meer waard.

Het rugzakprobleem in de praktijk

• Het rugzakprobleem komt in de praktijk vaak voor, bijvoorbeeld bij het laden van een vrachtwagen
• Of wanneer jij bepaalt waaraan je je zuur verdiende geld uitgeeft.
• Bij veel voorwerpen bestaat er geen snel
  algoritme dat dit probleem kan oplossen

Wat is er dan wel mogelijk?

Correctheid en efficiëntie

Een algoritme maken dat alle mogelijkheden langsgaat

• Dit heet een brute-forcealgoritme
  
• Het levert altijd een correcte oplossing
  
• Maar het is niet efficiënt
  
  

Een algoritme maken dat zo dicht mogelijk in de buurt van de oplossing probeert te komen

• Zo’n algoritme is wel efficiënt, maar niet (helemaal) correct

Je kent drie sorteeralgoritmen: bubble sort, merge sort en quicksort.

Welke van de drie lijkt erg veel op een bruteforce-algoritme?

1. Bubble sort
2. Merge sort
3. Quicksort

Bruteforce sorteeralgoritme

Bubble sort doorloopt steeds de hele lijst en verwisselt eventuele verkeerde combinaties van twee getallen, tot die er niet meer zijn. Dat lijkt erg op het langslopen van alle mogelijkheden, wat een bruteforce-algoritme doet.

Vraag: de beste route

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?

Hoeveel mogelijke routes moet het algoritme onderzoeken om de beste route te vinden?

Antwoord: de beste route

4 * 5 * 5 * 6 = 600 mogelijke routes

Correctheid en efficiëntie

Als het probleem te groot is, werkt bruteforcing niet meer omdat het teveel tijd kost:

• Rugzakprobleem met 30 verschillende dozen -> meer dan 2 ^ 30 = 1 miljard mogelijkheden!

Mogelijke benaderingsalgoritmen zijn:

• Het probleem vereenvoudigen
• Een willekeurige oplossing kiezen, die stapsgewijs verbeteren tot een acceptabele oplossing is gevonden
• Een bepaalde tijd allerlei verschillende oplossingen uitrekenen, daarna stoppen en de beste uitkiezen

Benaderingsalgoritme van Dantzig (1957)

Gemaakt door de Amerikaanse wiskundige
George Dantzig (1914 – 2005).

Zijn benaderingsalgoritme voor het rugzakprobleem:

• Bereken voor elke doos de waarde per kilogram.
  
• Sorteer de dozen vervolgens op die waarde van
   groot naar klein.
  
• Vul de rugzak in diezelfde volgorde tot het niet meer past.
  

Het rugzakprobleem - deel 2

• In je rugzak past maximaal 12 kg.
• Je wilt zoveel mogelijk waarde
  (in euro’s) meenemen
  

Voer het rugzakalgoritme van Dantzig
uit voor deze rugzak en dozen.

Vindt het algoritme de beste oplossing?

Het rugzakprobleem - deel 2

• In je rugzak past maximaal 12 kg.
• Je wilt zoveel mogelijk waarde
  (in euro’s) meenemen
  

1. Bereken voor elke doos de waarde
   per kilogram.
   
2. Sorteer de dozen vervolgens op die waarde
   van groot naar klein.
3. Vul de rugzak in diezelfde volgorde tot het
   niet meer past.

Vindt het algoritme de beste oplossing?

1. Ja
2. Nee

Het rugzakprobleem - deel 2

1.  Reken waarde per kilogram uit:

2.  Sorteer op waarde per kilogram:

Het rugzakprobleem - deel 2

Stop je deze lijst op volgorde in de rugtas, dan moet je bij doos 2 stoppen, omdat je dan al 0,5 + 3 + 1 + 2 = 6,5 kg in de rugtas hebt gestopt, en doos 5 van 11 kg past er niet meer bij.

Deze oplossing is hetzelfde als de beste oplossing die je in de vorige paragraaf vond, dus in dit geval heeft het algoritme inderdaad de beste oplossing gevonden.

Complexiteitsdiagram

• Big O, ook wel Big O-notatie genoemd, vertegenwoordigt de worstcase-complexiteit van een algoritme.
  
• Big O-notatie meet de efficiëntie en prestaties van een algoritme met behulp van tijd- en ruimtecomplexiteit.

Soorten tijdcomplexiteit

Van sneller naar langzamer:

• Constant: O(1)
  
• Logarithmic Time: O(log n)
  
• Linear time: O(n)
  
• Linear Logarithmic time: O(n log n)
  
• Quadratic time: O(n^2)
  
• Exponential time: O(2^n)
  
• Factorial time: O(n!)
  

Performance

n = input size.

• O(1) - Excellent/Best
  
• O(log n) - Good
  
• O(n) - Fair
  
• O(n log n) - Bad
  
• O(n^2), O(2^n) and O(n!) - Horrible/Worst
  

Behandelde algoritmes

Het gaat dus om worst case.

• O(log n) - Slim tellen, binair zoeken
• O(n) - Lineair zoeken
  
• O(n log n) - Merge sort, quick sort, korstepad
  
• O(n^2) - Bubble sort
• O(2^n) - Rugzakprobleem
• O(n!) - Handelsreizigersprobleem
  

Onoplosbare problemen?

Zijn er problemen die ook voor een computer moeilijk

zijn om op te lossen?

Welk probleem bevindt zich in de NP-klasse?

1. Het oplossen van een doolhof
2. Het sorteren van een lijst elementen
3. Het oplossen van een sodoku
4. Het uitvoeren van een vermenigvuldiging

Welk probleem bevindt zich in de NP-klasse?

• De P-klasse omvat beslissingsproblemen waarvoor er een algoritme bestaat dat het probleem kan oplossen in polynomiale tijd.
• NP omvat beslissingsproblemen waarvoor een oplossing kan worden geverifieerd in polynomiale tijd. Dit betekent dat als je een mogelijke oplossing voor het probleem hebt, je snel kunt controleren of deze oplossing correct is.

Dus het oplossen van een sudoku is een NP-probleem.

Leerdoel gehaald?

Aan het eind van deze les kun je uitleggen waarom verschillende problemen een andere tijdcomplexiteit hebben. Ook ken je een voorbeeld van een onoplosbaar probleem en kun je rijk worden door het P- vs NP-probleem op te lossen.

Doornemen

LessonUp

Les 7 - Onoplosbare problemen - over tijdcomplexiteit

Fundament 

B: Grondslagen -> Algoritmen (B1) -> 3. Onoplosbare probl.? 3.1 t/m 3.3