Wat is informatica#
Voordat we beginnen moeten we iets zeggen over informatica. Wat denk je dat informatica is?
Veel mensen denken dat het programmeren of gewoon leren coderen is of dat het iets met computers is.
Informatica is het verwerken van informatie. Gegeven een input, hoe verwerken we dat tot een gewenste uitput? Met andere woorden, het gaat om problemen oplossen. Programmeren is een belangrijk hulpmiddel om de computer de informatie te laten verwerken en tot de oplossing te komen. De truuk is om als programmeur de computer uit te gaan leggen hoe hij de data moet verwerken.
Oplossen van problemen#
Hoe kan een probleem worden opgelost
Hoe goed kan een probleem worden opgelost
Kan elk probleem worden opgelost
Als het gaat over het oplossen van problemen wil informatica deze drie belangrijke vragen proberen te beantwoorden.
Hoe kan een probleem worden opgelost?#
Kan je het probleem oplossen?
Kan je een proces ontwerpen om dit soort problemen op te lossen?
Het niet is verstandig dat als er een probleem opgelost moet worden om meteen te gaan programmeren. Probeer eerst het probleem op papier op te lossen met een klein voorbeeld. Welke stappen/instructies zijn er gebruikt om het probleem op te lossen? Dit wordt computational thinking genoemd. De vaardigheid om een set van instructies te ontwikkelen dat een gegeven probleem kan oplossen. Deze set van instucties om van A naar B te komen wordt een algoritme genoemd.
Bijvoorbeeld: het Longest Common Subsequence (LCS) probleem voor het zoeken naar de langste opeenvolging van karakters die twee woorden met elkaar gemeen hebben.
Longest Common Subsequence (LCS)#
Het string-matching probleem in DND:
‘CGCTGAGCTAGGCC…’
‘ATCCTAGGTAACTG…’ (en \(10^9\) meer!)
Wat is de langst gemeenschappelijke opeenvolging van karakters? In biologie is dit een werkelijk probleem waar het gaat om het vergelijken van DNA-sequenties.
Het is gekkenwerk om dit op een grote dataset met de hand te doen. Dan kan de vraag gesteld worden; kan een computer dit oplossen? Met andere woorden: kan dit probleem vertaald worden naar een set van instructies?
Inplaats van het probleem op te lossen op een grote dataset is het vaak makkelijker om eerst een dataset te proberen op te lossen, Bijvoorbeeld twee woorden.
‘HUMAN’
‘CHIMPANZEE’
Je zult redelijk snel zien dat ‘AN’ de langst gemeenschappelijke opeenvolging van karakters is. Dit is de eerste stap van het oplossen van een probleem; De probeer fase.
Welke stappen heb je gebruikt om tot een oplossing te komen? Zijn deze stappen ook toe te passen op een opeenvolging van 3 miljard karakters? Dit is de plan fase waarin het algoritme wordt ontworpen.
Zodra er een algoritme is ontworpen kan het geprogrammeerd worden. Dat is dan de programmeer fase.
Hoe goed kan een probleem worden opgelost#
Hoe snel kan het ontworpen algoritme de oplossing?
Is deze oplossing de best mogelijke oplossing?
Soms kunnen we een manier vinden om een probleem op te lossen, maar is het te traag. Het zal je misschien verbazen dat we ons zorgen moeten maken over snelheid, zeker nu computers zo snel zijn, maar er zijn problemen die zo groot dat we ons zorgen moeten maken over hoe snel het programma is.
Natuurlijk kan het ook zo zijn dat we een oplossing vinden dat snel genoeg is, maar is het dan echt de best oplossing?
Het sorteer probleem#
Gegeven een \(N\) aantal getallen dat gesoorteerd moet worden van groot naar klein. Denk bijvoorbeeld aan prijzen in een webwbinkel.
Oplossing 1:
Stap 1: Zet de de getallen random achter elkaar
Stap 2: Controleer of de getallen in de juiste volgorde staan. Zo niet, ga terug naar stap 1
Deze oplossing staat bekend als bogosort
Dit algoritme is niet erg efficient want als er veel data gesorteerd moet worden, kan dit heel lang duren. Sterker nog, het zou wel eens oneindig lang kunnen duren.
Oplossing 2:
Stap 1: Vergelijk de element met de buurman in de lijst. Als ze in de verkeerde volgorde staan worden ze gewisseld. Ga dan naar de volgende element in de lijst.
Stap 2: Als we aan het einde van de lijst zijn aangekomen, check of de lijst op volgorde staat, so niet, begin weer aan het begin van de lijst.
Deze oplossing staat bekend als de bubblesort
Dit is al een stuk efficienter dan de bogosort, maar het is niet de best mogelijke oplossing. Het blijft dus altijd belangrijk om je af te vragen of het de beste oplossing is.
Om verschillende algortimes te kunnen vergelijken wordt er gegeken naar hun complextieit. Hoeveel stappen hebben ze nodig om tot een oplossing te komen (tijdcomplextieit)? En hoeveel geheugen heeft het nodig (ruimtecomplexiteit)? Deze vragen liggen buiten de scope van deze cursus, het doel voor nu is om eerst tot een mogelijke beste oplossing te komen.
Kan elk probleeem worden opgelost#
Is elk probleem op te lossen?
Hoe weet je of het kan worden opgelost?
Tot slot, als het probleem bijzonder lastig is zullen we ons moeten afvragen of het kan worden opgelost. Bestaat er wel een algoritme? Is er genoeg data om het probleem op te lossen?
Bijvoorbeeld: Camera beeld Inzoomen en de dief scherp in beeld krijgen.
Let’s enhance#
Bekend van film en TV!
Hoe vaak heb je dit niet gezien, op magische wijze een afbeelding opblazen en verscherpen tot de dader scherp in beeld komt! Dit is niet realistisch omdat de data pixels zijn (beeldpunten) waar hooguit het contrast van kan worden vergroot, maar niet de resolutie (het aantal beeldpunten).
Pogingen worden wel gedaan om ontbrekende informatie aan te vullen, bijvoorbeeld op basis van andere (vergelijkbare) afbeeldingen. Dit kan soms tot bijzondere resultaten leiden als de afbeeldingen waarmee vergeleken wordt weinig divers zijn (en een bias introduceren). Je herkent hier misschien Barack Obama in het origineel…
Wat de bovenstaande vragen met elkaar gemeen hebben is dat ze alle drie te maken hebben met complexiteit, of hoe moeilijk het is om een bepaald probleem op te lossen. Je hebt technieken en gereedschappen nodig om te helpen denken over complexiteit en je gaat met een aantal hiervan kennismaken.
De drie p’s van het programmeren:
Probeer: Probeer het probleem op te lossen in gedachten of op papier.
Plan: Noteer de stappen die zijn gebruikt om het probleem op te lossen.
Programmeer: Vertaal de stappen naar een programmeertaal.