Samenvatting IPRO2: Programmeren van complexe vraagstukken
8 vues 0 fois vendu
Cours
IPRO2
Établissement
Hogeschool Leiden (HSL)
Deze samenvatting is gebasseerd op de videocolleges en collegeslides van het vak IPRO2. Er zijn afbeeldingen en voorbeelden toegevoegd voor ondersteuning van het aanleren van de stof.
- 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
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur loispeter. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €7,49. Vous n'êtes lié à rien après votre achat.
