Algoritmen en Datastructuren (ALGODS)

© Harry Broeders.

Deze pagina is bestemd voor studenten van de Haagse Hogeschool - Faculteit voor Technologie, Innovatie & Samenleving groep ECV. Dit vak is onderdeel van de verdiepende lintminor Elektrotechniek (EVMIN). Op deze pagina vind je het bij de module ALGODS gebruikte studiemateriaal.

Let op! Deze pagina bevat mogelijk verouderde informatie, kijk op Blackboard voor de meest recente informatie!

Inhoud.

Beschikbaar materiaal:

• Studiewijzer (inclusief gedetailleerde planning).
• Het belangrijkste studiemateriaal is het dictaat: Algorithmen en Datastructuren: dictaat_ALGODS.pdf 27-04-2015. Het dictaat heeft een bindmarge en is dus gemaakt om dubbelzijdig af te drukken! Er is ook een ebook versie: dictaat_ALGODS_ebook.pdf 27-04-2015.

  Algoritmen en Datastructuren van Harry Broeders is in licentie gegeven volgens een Creative Commons Naamsvermelding-NietCommercieel-GelijkDelen 3.0 Nederland-licentie.

• Alle sheets in één Powerpoint: ALGODS.pptm 27-03-2015.
• Informatie over Boter Kaas en Eieren.
• Introductie in het gebruik van Visual Studio Express 2013 for Windows Desktop.
• Voorbeeldprogramma's uit mijn dictaat :
  • balance.cpp (paragraaf 3.1) met de benodigde header files: stacklist.h en stack.h. In stack.h wordt gebruik gemaakt van twee C++11 features default implementations en deleted functions. In stacklist.h wordt gebruik gemaakt van de C++11 features explicit overriding.
    Dit programma controleert of de haakjes in de invoer netjes gebalanceerd zijn. Dit is een eenvoudige toepassing van de stack datastructuur.
  • postfix.cpp (paragraaf 3.2.2) met de benodigde header files: stacklist.h en stack.h.
    Deze postfix (RPN) calculator maakt gebruik van een stack.
  • Infix2Postfix.cpp (paragraaf 3.2.3) met de benodigde header files: stacklist.h en stack.h.
    Deze infix naar postfix converter gebruikt een stack en het rangeerstationalgoritme, zie Shunting-yard_algorithm .
  • Infix.cpp (paragraaf 3.2.3) met de benodigde header files: stacklist.h en stack.h.
    Dit programma combineert de infix naarpostfix converter en de postfix calculator tot een infix calculator.
  • InfixCalc.cpp (paragraaf 3.2.3) met de benodigde header files: stacklist.h en stack.h.
    Deze Calculator class berekent de waarde van een infix expressie die bestaat uit integers en operatoren. De volgende operatoren worden herkend: ^ (machtsverheffen), *, / ,% (modulo), + en - . ^ heeft de hoogste prioriteit, daarna *, / en % en tot slot + en -. Je kunt haakjes, ( en ), gebruiken om de prioriteit aan te passen.
  • stackarray.cpp (paragraaf 4.1) met de benodigde header files: stackarray.h en stack.h.
    Dit programma test de stack die geïmplementeerd is met behulp van een array (in de include file stackarray.h).
  • stacklist.cpp (paragraaf 4.2) met de benodigde header files: stacklist.h en stack.h.
    Dit programma test de stack die geïmplementeerd is met behulp van een gelinkte lijst (in de include file stacklist.h).
  • stack.cpp (paragraaf 4.3) met de benodigde header files: stackarray.h, stacklist.hen stack.h.
    Dit programma laat zien hoe je dynamisch (tijdens run-time) kunt kiezen voor een bepaalde implementatie van de stack. Dit is mogelijk door het gebruik van een Abstract Base Class en is een voorbeeld van het gebruik van polymorfisme.
  • stdstring.cpp (paragraaf 6.1), stdvector.cpp (paragraaf 6.2.1.1), stdbalanced.cpp (paragraaf 6.2.2.1), set.cpp (paragraaf 6.2.3.1), multiset.cpp (paragraaf 6.2.3.2), unordered_set.cpp (paragraaf 6.2.3.3) en stdcntwords.cpp (paragraaf 6.2.3.4).
    Deze programma's laten zien hoe je de standaard datastructuren: vector, stack, set, multiset, unordered_set en map gebruikt.
  • generiekPrint-index.cpp (niet in dictaat), generiekPrint-iterator.cpp, generiekPrint-range-based-for.cpp en generiekPrint-range.cpp (alle drie uit paragraaf 6.2.1.1).
    Deze programma's laten verschillende manieren zien hoe je een generieke functie kunt maken waarmee een (deel van een) container kan worden afgedrukt. De laatste oplossing is de beste.
  • find_upper_middle_random_access.cpp, find_upper_middle_bidirectional.cpp en find_upper_middle_forward.cpp(alle drie uit paragraaf 6.3.1).
    Deze programma's laten zien dat de implementatie van een algoritme afhankelijk kan zijn van de soort iterator die beschikbaar is. Hetzelfde algoritme wordt geïmplementeerd voor 3 verschillende iterator soorten.
  • reverse_iterator.cpp (paragraaf 6.3.2).
    Dit programma maakt gebruik van reverse-iteratoren om een container van achter naar voor te doorzoeken.
  • streamitr.cpp (paragraaf 6.3.5).
    Dit programma maakt gebruik van stream-iteratoren en een back_insert_iterator om een uit een bestand te lezen en naar een bestand te schrijven.
  • iteratoren.cpp (paragraaf 6.13).
    Dit programma maakt gebruik van stream-iteratoren, een insert_iterator en reverse_iteratoren om strings uit een bestand te lezen en in een set te plaatsen (strings die meerdere malen in het bestand voorkomen worden slechts één maal in de set geplaatst) en deze vervolgens in omgekeerd alfabetische volgorde op het scherm af te drukken.
  • algorithm_vs_memberfunction.cpp (paragraaf 6.4).
    Dit programma laat 2 gevallen zien waarin je beter een specifieke memberfunctie dan een generiek algoritme kunt gebruiken.
  • find.cpp (paragraaf 6.4.1.1), find_if.cpp (paragraaf 6.4.1.2), galgje_find.cpp (paragraaf 6.4.1.2), find_first_of.cpp (paragraaf 6.4.1.3) en for_each.cpp (paragraaf 6.4.1.4).
    Deze programma's laten zien hoe je de standaard algoritmen: find, find_if, any_of, find_first_of en for_each gebruikt.
  • closure.cpp (paragraaf 6.4.2.1), res2geheel.cpp (paragraaf 6.4.2.2) en find_if_c++14.cpp (paragraaf 6.4.2.3).
    Deze programma's laten zien hoe je lambda-functies en closures gebruikt. Het laatste programma laat zien dat je in C++14 auto als parametertype van een lambda-functie kunt gebruiken.
  • accumulate.cpp (paragraaf 6.4.2.1).
    Dit programma laat zien hoe je met acculate de som van alle even getallen in een range kunt bepalen.
  • transform.cpp, galgje_strings_transform.cpp (beide uit paragraaf 6.4.3.1), remove.cpp en generate_n.cpp (beide uit paragraaf 6..4.3.2).
    Deze programma's laten zien hoe je de standaard algoritmen: transform, remove en generate_n gebruikt. Het laatste programma laat zien hoe je de vector v kan vullen met kwadraten door het algoritme generate_n, een insert-iterator en een closure te gebruiken. Al kun je jezelf in dit geval natuurlijk wel afvragen of een simpele for-lus niet eenvoudiger en duidelijker is.
  • sort_lambda.cpp en sort_deelnemers.cpp (beide uit paragraaf 6.4.4.1).
    Deze programma's laten zien hoe je de standaard algoritmen: sort en stable_sort gebruikt.
  • galgje_sets.cpp (paragraaf 6.4.4.2)
    Dit programma laat zien hoe je galgje kan implementeren met behulp van de standaard bewerkingen op verzamelingen.
  • mem_fn.cpp (paragraaf 6.4.4.2)
    De standaard functie mem_fn die de koppeling vormt tussen generiek programmeren en object georienteerd programmeren wordt in dit programma gedemonstreerd.
  • find_upper_middle.cpp (paragraaf 6.4.5).
    Dit programma laat zien hoe je de compiler zelf de meest effciënte implementatie van een algoritme kunt laten kiezen afhankelijk van het soort van de als argumenten meegegeven iteratoren.
  • sort_greater.cpp, find_if_bind.cpp en remove_bind.cpp (alle drie uit paragraaf 6.4.6).
    Deze programma's laten zien hoe je standaard functie-objecten kunt gebruiken om een bepaalde voorwaarde of een bepaalde bewerking aan een algoritme door te geven. Persoonlijk vind ik het gebruik van lambda-functies in de laatste twee gevallen eenvoudiger.
  • MinMax0.cpp, MinMax0PrintTree.cpp, MinMax1.cpp en MinMax2.cpp (alle vier uit paragraaf 7.1.1).
    Deze programma's helpen je bij het begrijpen van het minimax algoritme.
  • AlphaBeta0.cpp, AlphaBeta0Verbose.cpp, AlphaBeta1.cpp, AlphaBeta1Verbose.cpp, AlphaBeta2.cpp en AlphaBeta3Verbose.cpp (alle zes uit paragraaf 7.1.2).
    Deze programma's helpen je bij het begrijpen van alpha-beta pruning.
    
  • Zie voor de programma's die genoemd worden in paragraaf 7.1.3: Boter Kaas en Eieren.
  • Paths.cpp (paragraaf 7.2).
    Een programma om het kortste pad in een graaf te berekenen. Er zijn 4 verschilllende algoritmen geïmplementeerd: Breadth-first search, Dijkstra, Bellman-Ford en Topological searc (Acyclic). Bijbehorende invoerbestanden:

    graph_positive.txt	graph_negative.txt
    graph_acyclic.txt	graph_steden.txt

• Nog meer voorbeeldprogramma's :
  • max-range-based-for.cpp
    Voorbeeldprogramma gebruikt in de sheets van week 1.
  • galgje_sets2.cpp en galgje_strings.cpp.
    Nog twee manieren om galgje te spelen.
  • MatrixWithIteratoren.h en bijbehorend testprogramma MatrixWithIteratorenTest.cpp.
    Een matrix met 3 verschillende soorten iteratoren waarmee je respectievelijk de hele matrix, een rij of een kolom kunt doorlopen. Met behulp van deze iteratoren kun je met standaard algoritmen werken op rij en kolom niveau.
• Practicumopdrachten:
  • Opdracht 1: Een "homemade" gelinke lijst.
  • Opdracht 2: Algoritme runtime analyse.
  • Opdracht 3: Exceptions.
  • Opdracht 4: Opsporen van fraude.
  • Opdracht 5: Eindopdracht ALGODS.
• Hoe nu verder? Meer leren over C++.
• Andere interessante sites betreffende ALGODS.