Hoofdstuk 2: Algoritmen en Programmeren
2.1 Algoritmen
Een algoritme is een reeks eindige instructies die een gegeven begintoestand omzetten in
een beoogd doel.
Het beschrijft hoe een welbepaald probleem kan worden opgelost door:
1. De nodige stappen te bepalen.
2. Vanuit een welbepaalde beginsituatie te starten.
3. Een vooropgestelde uitkomst te bereiken.
Opm: instructies = welpbepaalde elementaire handelingen
Subjectief, hangt af van de gebruiker/ontvanger
Opm: eindige reeks?
Zoniet wordt beoogd doel NIET bereikt
Eindigheid in tijd impliceert eindigheid in aantal instructies (niet omgekeerd!)
Opm: natuurlijke taal leidt tot verschillende interpretaties DUS nood aan meer specifieke taal
2.2 Problemen
Probleem 1: beperkingen op instructies (Torens van Hanoi)
- Set van instructies is: (1) beperkt & (2) a-priori (= op voorhand)
bepaald
Probleem 2: klassen van problemen (Traveling Salesman Problem &
Torens van Hanoi)
- Meerdere instantiaties vb. ander netwerk, andere klanten,…
Gevolg: niet elke keer hetzelfde scenario
Klasse van problemen
Opm: instructies zijn ook beperkt en a-priori bepaald vb. aantal wegen
beschikbaar om te gebruiken
Instantiaties, correcte en incorrecte algoritmen
Een instantiatie van een probleem betreft een specifieke
begintoestand en doel
Opm: begintoestand en/of doel kunnen verschillen
(1) Een correct algoritme bereikt voor iedere instantiatie het beoogde doel
m.a.w. het algoritme lost het betreffende probleem op
(2) Een incorrect algoritme bereikt niet voor iedere instantiatie het beoogde doel; het kan
in sommige gevallen falen of helemaal geen oplossing genereren. Vb. chatGPT
Opm: wel nuttig, want lost bepaalde problemen wel op
,The illusion of thinking: long-reasoning model vs large-language model
- Klasse van problemen Andere begintoestand mogelijk vb. # schijfjes veranderd
- Beide vinden snel geen oplossing naarmate het aantal schijven toeneemt
Conclusie: beide modellen maken fouten incorrecte algoritmen
Opm: is een probleem oplosbaar? Kritisch over nadenken voor je er aan begint
2.3 computeralgoritmen
Wat is data, informatie en een computerlagoritme?
Data = alles dat kan opgeslagen worden als een bitsequentie
Informatie = alles dat kan opgeslagen worden als een bitsequentie dat utiliteit en waarde heeft
voor een gebruiker (=subjectief)
Computeralgoritme = creëert waarde door het omzetten van data naar informatie
Uitvoering van algoritme kan ook aansturing van een robot zijn
Opm: doel algoritme = verwerking van data naar informatie
Y=f(X) met:
- Y = output
- X = input
- F = algoritme
Opm: gelijkenis met productieproces: grondstoffen producten
Opm: systematische benadering
Computeralgoritme
= een duidelijk gedefinieerde computationele procedure die waarde of verzameling van waarden
als invoer neemt en een waarde of verzameling van waarden als uitvoer produceert
Begintoestand: computer kan enkel bits als invoer aannemen
Doel: computer kan enkele bits als uitvoer produceren
Instructies: eindige reeks computer-uitvoerbare instructies
Voorbeelden: (1) sorteren van een rij gehele getallen, (2)bankautomaat & (3) HRM systeem
Opm: pseudocode = nog geen concrete programmeertaal maar neigt er fel naar
, 2.4 Computationele procedure
= geordende reeks ondubbelzinnige, computer-uitvoerbare instructies die een eindig proces beschrijven
Opm : een proces = herhaalbare reeks afhankelijke activiteiten met een welbepaald eindresultaat en
startende vanaf een welbepaald beginpunt
1: Geordend
- Volgorde instructies is van belang
- ‘Afhankelijke activiteiten’ geen willekeurige volgorde
- Geen losse verzameling, maar geordende set (tenzij anders gespecifieerd)
OPM: niet alle instructies moeten in een vooraf vastgelegde volgorde zijn geplaatst om dezelfde uitkomst
bekomen
Parallel computing (multicore processors) = in parallel meerdere instructies tegelijk uitvoeren
Opm : niet van toepassing bij Torens van Hanoi , wel bij Traveling Salesperson
Parallele (multi-threated) algoritmen
= omvatten meerdere reeksen instructies, die expliciet bepaald zijn in het algoritme en die afzonderlijk kunnen
uitgevoerd worden (uitgevonden voor multi-processormachine)
Niet toepasbaar voor alle algoritmen vb. oorzaak-gevolg ketens, verkeerssimulaties,…
2: Ondubbelzinnig
- VEREIST, omdat computer NIET kan interpreteren
- Of om ervoor te zorgen dat programmeur het niet verkeerd begrijpt
Vb. interpretatie van algoritme omzetten van pseudocode naar programmeertaal
DUS computeralgoritmen moeten exact specifiëren wat er moet gebeuren (≠ een snufje zout)
Probleem: dubbelzinnigheid hangt af van notatie van het algoritme:
- Notatie in natuurlijke taal: dubbelzinnig
- Notatie in (pseudo)-programmeertaal: ondubbelzinnig
Algoritmes in ontwikkeling die wel kunnen interpreteren vb. ChatGPT
3: Computer-uitvoerbaar
- Instructie = doenbaar indien ze bestaat uit doenbare instructies
- Instructie op het laagste niveau reeks basisinstructies in machinetaal
- Algoritme is zelf een instructie en een instructie (behalve basisinstructies) een algoritme
- Computer-uitvoerbare instructie uitvoerbaar in eindige tijd (≠ lijst van alle natuurlijke getallen)
Instructies: verschillende niveaus
Laagste niveau: beperkte set basisinstructies (= bitsequenties die gevoed worden aan processor)
Uitdaging bij ontwikkeling computeralgoritmes: complexe problemen oplossen enkel gebruikmakend
van beperkte set computer-uitvoerbare instructies
MAAR bestaande algoritmes kunnen als hoger-niveau of hogere-orde instructies HERBRUIKT worden
Opm: eens algoritme gemaakt is wordt het een nieuwe instructie
4: Eindig
- Eindigheid in tijd impliceert eindigheid in aantal
MAAR ondersteunt ook ‘oneindig doorlopende processen’ (geen a-priori bepaald eindpunt)
Vb. toestel voor patiënt in ziekenhuis
DUS het zijn zichzelf herhalende algoritmen, waarbij op het eindpunt aangekomen, het algoritme zichzelf
terug initieert
Stopcriteria of stopcondities (vb. knop om uit te schakelen)
Een programma is een uitvoerbare representatie of implementatie van een algoritme
2.1 Algoritmen
Een algoritme is een reeks eindige instructies die een gegeven begintoestand omzetten in
een beoogd doel.
Het beschrijft hoe een welbepaald probleem kan worden opgelost door:
1. De nodige stappen te bepalen.
2. Vanuit een welbepaalde beginsituatie te starten.
3. Een vooropgestelde uitkomst te bereiken.
Opm: instructies = welpbepaalde elementaire handelingen
Subjectief, hangt af van de gebruiker/ontvanger
Opm: eindige reeks?
Zoniet wordt beoogd doel NIET bereikt
Eindigheid in tijd impliceert eindigheid in aantal instructies (niet omgekeerd!)
Opm: natuurlijke taal leidt tot verschillende interpretaties DUS nood aan meer specifieke taal
2.2 Problemen
Probleem 1: beperkingen op instructies (Torens van Hanoi)
- Set van instructies is: (1) beperkt & (2) a-priori (= op voorhand)
bepaald
Probleem 2: klassen van problemen (Traveling Salesman Problem &
Torens van Hanoi)
- Meerdere instantiaties vb. ander netwerk, andere klanten,…
Gevolg: niet elke keer hetzelfde scenario
Klasse van problemen
Opm: instructies zijn ook beperkt en a-priori bepaald vb. aantal wegen
beschikbaar om te gebruiken
Instantiaties, correcte en incorrecte algoritmen
Een instantiatie van een probleem betreft een specifieke
begintoestand en doel
Opm: begintoestand en/of doel kunnen verschillen
(1) Een correct algoritme bereikt voor iedere instantiatie het beoogde doel
m.a.w. het algoritme lost het betreffende probleem op
(2) Een incorrect algoritme bereikt niet voor iedere instantiatie het beoogde doel; het kan
in sommige gevallen falen of helemaal geen oplossing genereren. Vb. chatGPT
Opm: wel nuttig, want lost bepaalde problemen wel op
,The illusion of thinking: long-reasoning model vs large-language model
- Klasse van problemen Andere begintoestand mogelijk vb. # schijfjes veranderd
- Beide vinden snel geen oplossing naarmate het aantal schijven toeneemt
Conclusie: beide modellen maken fouten incorrecte algoritmen
Opm: is een probleem oplosbaar? Kritisch over nadenken voor je er aan begint
2.3 computeralgoritmen
Wat is data, informatie en een computerlagoritme?
Data = alles dat kan opgeslagen worden als een bitsequentie
Informatie = alles dat kan opgeslagen worden als een bitsequentie dat utiliteit en waarde heeft
voor een gebruiker (=subjectief)
Computeralgoritme = creëert waarde door het omzetten van data naar informatie
Uitvoering van algoritme kan ook aansturing van een robot zijn
Opm: doel algoritme = verwerking van data naar informatie
Y=f(X) met:
- Y = output
- X = input
- F = algoritme
Opm: gelijkenis met productieproces: grondstoffen producten
Opm: systematische benadering
Computeralgoritme
= een duidelijk gedefinieerde computationele procedure die waarde of verzameling van waarden
als invoer neemt en een waarde of verzameling van waarden als uitvoer produceert
Begintoestand: computer kan enkel bits als invoer aannemen
Doel: computer kan enkele bits als uitvoer produceren
Instructies: eindige reeks computer-uitvoerbare instructies
Voorbeelden: (1) sorteren van een rij gehele getallen, (2)bankautomaat & (3) HRM systeem
Opm: pseudocode = nog geen concrete programmeertaal maar neigt er fel naar
, 2.4 Computationele procedure
= geordende reeks ondubbelzinnige, computer-uitvoerbare instructies die een eindig proces beschrijven
Opm : een proces = herhaalbare reeks afhankelijke activiteiten met een welbepaald eindresultaat en
startende vanaf een welbepaald beginpunt
1: Geordend
- Volgorde instructies is van belang
- ‘Afhankelijke activiteiten’ geen willekeurige volgorde
- Geen losse verzameling, maar geordende set (tenzij anders gespecifieerd)
OPM: niet alle instructies moeten in een vooraf vastgelegde volgorde zijn geplaatst om dezelfde uitkomst
bekomen
Parallel computing (multicore processors) = in parallel meerdere instructies tegelijk uitvoeren
Opm : niet van toepassing bij Torens van Hanoi , wel bij Traveling Salesperson
Parallele (multi-threated) algoritmen
= omvatten meerdere reeksen instructies, die expliciet bepaald zijn in het algoritme en die afzonderlijk kunnen
uitgevoerd worden (uitgevonden voor multi-processormachine)
Niet toepasbaar voor alle algoritmen vb. oorzaak-gevolg ketens, verkeerssimulaties,…
2: Ondubbelzinnig
- VEREIST, omdat computer NIET kan interpreteren
- Of om ervoor te zorgen dat programmeur het niet verkeerd begrijpt
Vb. interpretatie van algoritme omzetten van pseudocode naar programmeertaal
DUS computeralgoritmen moeten exact specifiëren wat er moet gebeuren (≠ een snufje zout)
Probleem: dubbelzinnigheid hangt af van notatie van het algoritme:
- Notatie in natuurlijke taal: dubbelzinnig
- Notatie in (pseudo)-programmeertaal: ondubbelzinnig
Algoritmes in ontwikkeling die wel kunnen interpreteren vb. ChatGPT
3: Computer-uitvoerbaar
- Instructie = doenbaar indien ze bestaat uit doenbare instructies
- Instructie op het laagste niveau reeks basisinstructies in machinetaal
- Algoritme is zelf een instructie en een instructie (behalve basisinstructies) een algoritme
- Computer-uitvoerbare instructie uitvoerbaar in eindige tijd (≠ lijst van alle natuurlijke getallen)
Instructies: verschillende niveaus
Laagste niveau: beperkte set basisinstructies (= bitsequenties die gevoed worden aan processor)
Uitdaging bij ontwikkeling computeralgoritmes: complexe problemen oplossen enkel gebruikmakend
van beperkte set computer-uitvoerbare instructies
MAAR bestaande algoritmes kunnen als hoger-niveau of hogere-orde instructies HERBRUIKT worden
Opm: eens algoritme gemaakt is wordt het een nieuwe instructie
4: Eindig
- Eindigheid in tijd impliceert eindigheid in aantal
MAAR ondersteunt ook ‘oneindig doorlopende processen’ (geen a-priori bepaald eindpunt)
Vb. toestel voor patiënt in ziekenhuis
DUS het zijn zichzelf herhalende algoritmen, waarbij op het eindpunt aangekomen, het algoritme zichzelf
terug initieert
Stopcriteria of stopcondities (vb. knop om uit te schakelen)
Een programma is een uitvoerbare representatie of implementatie van een algoritme
