IPRO2 samenvatting: Programmeren van complexe vraagstukken
9 views 0 purchase
Course
IPRO2
Institution
Hogeschool Leiden (HSL)
Deze samenvatting is gebaseerd op de videocolleges en collegeslides voor het vak IPRO2. Er zijn afbeeldingen en voorbeelden toegevoegd ter ondersteuning.
- Een manier om over de performance van een algoritme te praten.
- Het is de worst-case complexiteit, dus in het slechtste geval.
o Kan over tijd of ruimte gaan.
- Er zijn andere notaties voor best-case en average-case complexiteit.
Definitie O (n)-notatie:
- Een algoritme heeft een worst-case tijdscomplexiteit O(f(n)), als de looptijd van het algoritme voor
grote n kleiner is dan c*f(n).
- Voorbeeld: code die 3*n tijd nodig heeft is O(n).
Hoe bepaal je de O(n) complexiteit?
- Analyseer je code en tel hoeveel stappen je maakt, bijvoorbeeld het aantal loops.
- Voorbeeld:
o 5n² + 7n + 8 stappen -> O(n²)
o 42 stappen -> O(1)
o 6 + 2n³ - n² + 8n stappen -> O(n³)
- In het voorbeeld wordt luie wiskunde gebruik, dus je zoekt naar het grootste gedeelte: n² of n³
Big O in je code:
,Week 1 – Problem Solving Theorie
Waarom problem solving:
- Moeilijk om uit ‘warrige’ probleemomschrijving de essenties te halen.
- Probleem niet begrepen, dat kan resulteren in verkeerde code.
- Het probleem begrijpen voordat je begint.
- Oplossingen bedenken voordat je begint met coderen.
- Dus: niet direct de code in duiken.
Problem Solving stappen:
1. Lees het probleem minsten tweemaal door.
2. Los het probleem handmatig op met drie sets van voorbeeld data:
a. Input
b. Proces
c. Output
3. Optimaliseer de handmatige oplossing.
4. Schrijf de handmatige oplossing uit in pseudo-code.
5. Zet de pseudo-code om in echte code.
6. Optimaliseer de code.
7. Test de code.
Als je vast loopt kan je de stappen herhalen, denk ik oplossingen en niet in problemen. Begin NIET met
programmeren, maar denk na over wat je moet doen. Onthoud dat het niet altijd in 1x goed gaat.
Week 1 – Binair zoeken
Binair zoeken:
- Zoeken in een gesorteerde lijst, als je weet hoe de data in elkaar ziet wordt binair zoeken
makkelijker, zoek de letter F.
1. Zoek het midden, als dat niet kan ga je voor de linker kant. Dit is plaats 4, dus de letter H.
2. Omdat je weet dat de F kleiner is dan H weet je dat hij aan de linkerkant moet zitten. Nummer 5
(K) t/m 9 (Z) kan je weggooien, het probleem is gehalveerd.
3. Je houdt 0 (A), 1 (D), 2 (F), 3 (G) over, ook hier kies je weer het midden (tussen 1 en 2) en vervolgens
de linkerkant. Dit is de 1 (D) en dat is kleiner dan F.
4. Nu zoek je tussen de 4 (H) en 1 (D) in, dus 2 (F) en 3 (G). Ook dit halveer je en kies de linkerkant.
Dit is 2, de F.
- In totaal zijn het maar drie stappen: kijken naar de H, kijken naar de D en vervolgens de F.
- Binair zoeken is relatief snel omdat je al vrij snel een groot deel van je data weg kan doen.
- Er zitten 10 waardes in bovenstaande array en we hebben maar 3 stappen nodig gehad om de F
te vinden.
, In pseudo-code ziet dat er als volgt uit:
Functie zoekBinair(lijst, doel):
Zolang getal niet gevonden:
Check midden van de lijst
Te groot? Zoek verder in linkerdeel
Te klein? Zoek verder in rechterdeel
Gelijk? Gevonden!
De code kan er als volgt uit zien (dit werkt niet helemaal):
zoekBinair(lijst, doel):
min = 0
max = lijst.size -1
while min <= max:
midden = (max + min)/ 2
if lijst[midden] > doel:
max = midden -1
else if lijst[midden] < doel:
min = mid +1
else
return midden
Best case binair zoeken: 1 stap
Worst case: O(log n)
Waarom: je halveert telkens je probleem, dat is log₂ (n) stappen
Andersom: rij verdubbelen is 1 stap extra.
Week 2 – debuggen
Debuggen kan met:
- Het toevoegen van printstatements.
- Het gebruiken van de IDE debugger.
- Unit testing. Met kleine stukjes code verschillende situaties testen.
Week 3 – Bubble Sort
Er is een lijst met getallen:
65318724
Bubble Sort pakt de eerste twee getallen en vergelijkt dit met elkaar, het kleinste getal wordt als eerste
neergezet:
65318724>56318724
Dit gaat zo door:
56318724>53618724
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller loispeter. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.94. You're not tied to anything after your purchase.
