software constructie •de software bestaat uiteindelijk uit
recursieve datastructuren
datatypen functies
college 15
•verbindingen geven gebruik aan is de top van het bouwwerk elementaire datatypen vormen de bodem alles daartussen gebruikt wat en wordt zelf gebruikt bij recursie is er een rondgaand pad main
software engineering highlights
•hoe komen we aan dit bouwwerk? trail and error ? begin met iets dat er op lijkt en ga debuggen ? gebruik een ontwerp !
1
2
5 stappen plan
ontwerpen
1. Probleemanalyse, specificatie 2. Ontwerp van algoritmen en datastructuren •
•dit is de essentiële en spannende stap plaatjes, formules, pseudo-code
•hoeft niet tot in het laatste detail
plaatjes, tekst, formule, algemeen geval
dingen die 'zeker lukken' kun je overslaan
3. Reflectie • •
•layout van dialogen •initialisatie van een rijtje •vergeet dit uiteindelijk niet
zal het gaan werken zal het probleem opgelost worden
4. Implementeren •
hoe meer ervaring, hoe minder details in ontwerp
pas hier code schrijven
•groot gevaar voor zelfoverschatting
•reflectie moet mogelijk zijn op basis van ontwerp
5. Evaluatie • • •
testen om kwaliteit te bepalen werkt het in alle gevallen, verificatie is het probleem opgelost, validatie
voor grote projecten maak je soms een prototype hiervoor doorloop je dezelfde stappen ! 3
4
1
implementeren
software constructie
•ontwerp ligt klaar voor je begint •top-down: van boven naar onder •bottom-up •incrementeel:
•in een plaatje:
bouw stukje bij beetje begin met een programma dat weinig kan maak het langzaam krachtiger test ieder gebouwd stukje meteen maak eerst de stukken waar twijfels over bestaan •als herontwerp nodig is, is er weinig verloren •problemen kun je maar beter snel kennen
compleet ontwerp nodig om bouwwerk uiteindelijk af te kunnen maken
incrementeel 5
6
pointers •behalve een type, waarde en naam hebben objecten een object-id •iedere instantie van een type heeft een unieke id •in C++ (en andere talen) is de id z'n adres
highlights
dit idee is al ouder dan OO
•die adressen veranderen niet •adressen kun je manipuleren als normale objecten in je programma: pointers
programmeertaal aspecten recursieve datastructuren dynamic programming programma ontwerp taal implementatie graph algoritmen lineaire algebra abstractie
afspraak NULL-pointer wijst nergens heen
•nuttig en nodig in veel programma's recursieve datastructuren je kunt er ook veel fouten mee maken 7 8
2
programmeertaal aspecten
subklassen
•pointers T*, &x, NULL •functies
•van iedere klasse kun je een subklasse maken deze kan extra attributen en methoden bevatten
resultaat: void, T, T*, T& argumenten: T, T*, T&, T []
class sub : public hoofd { int extra; protected: int f ( ) { return extra+1; } };
•rijen, C-strings aanname: T* wijst altijd in rij T[] r[i] en *(r+i) zijn dan gelijk
•hiding via private, public en protected •herdefinitie voor virtual methoden •overal waar je hoofd verwacht mag je sub gebruiken
•objecten zichtbaarheid (scope) levensduur altijd het huidige compound statement objecten gemaakt met new leven voor 'eeuwig' opruimen met delete
typeconversie van sub naar hoofd voor directe types dynamic binding via pointers en ref args (C& of C*) 9
•object-id: this pointer
dynamic binding
10
recursieve datastructuren •voorbeelden:
class hoofd {public: virtual int f ( ) { return 1; } }; class sub : public hoofd {public : int f ( ) { return 2; } }; geeft dus: int main ( ) 1, 2 { hoofd h; sub s; hoofd h2 = s; hoofd *hp = &s; cout << h2 . f ( ) << ", " << hp -> f ( ) << endl; ...
lijst, gesorteerde lijst, queue, stack, .. boom, zoekboom, ..
•basis knoop is object of structuur met één element knoop bevat pointer(s) naar opvolger(s) •null pointer: er is geen opvolger •hierdoor kan dynamisch iedere grootte gemaakt worden
gebruik aparte klasse om eigenschappen te bewaken •zoekboom, queue, stack, ..
list: 11
1
2
3 12
3
lijsten
lijst in C++ typedef class Knoop *Lijst;
•knoop heeft hooguit één opvolger •voordeel boven rijen:
// Lijst is een pointer !!
class Knoop { El kop; // het lijstelement, private Lijst staart; // recursie: pointer naar de volgende public: Knoop ( El hd, Lijst tl = Leeg ) : kop ( hd ), staart ( tl ) { } ~Knoop() { delete staart; } // destructor: ruim hele lijst op friend El& head ( Lijst ); // vrienden kennen private velden friend Lijst& tail ( Lijst ); }; El& head ( Lijst l ) { assert ( l != Leeg ); // voorkom selectie uit lege lijst return l->kop; }
altijd een element toe te voegen element ertussen of eruit kan altijd goedkoop O(1)
•nadeel element opzoeken is duurder: O(n) i.p.v. O(1)
13
14
bomen
gesorteerde datastructuren
•implementatie als lijsten •verschil: bomen hebben meer dan 1 opvolger •gebruik:
•gebruikt om elementen efficiënt te vinden structuur
gesorteerde rij
gesorteerde lijst
gebalanceerde zoekboom
element zoeken
O ( log n )
O(n)
O ( log n )
element toevoegen
O(n)
O(1)
O(1)
element verwijderen
O(n)
O(1)
O(1)
actie
zoekbomen (gebalnceerde zoekbomen, AVL, Red-black) representatie van talen ...
1) dit zijn bovengrenzen, soms kan het sneller 2) we gaan er bij toevoegen en verwijderen vanuit dat we de plaats weten 3) balanceren en gebalanceerd houden van de boom vergt extra werk 15
4) ongebalanceerde bomen gedragen zich als lijst
16
4
speciale zoekbomen
lijst/boom-manipulaties
•houden zich dynamisch steeds in balans
•gebruiken altijd pointers •aflopen is nooit een probleem
alle operaties in O(log N)
•AVL-bomen
pointer zelf of kopie van pointer zijn evengoed
verschil in hoogte steeds hooguit 1 sla dit op in iedere knoop als knoop uit balans: herbalanceren (draaien)
•veranderen: zorg dat je geen kopie verandert pak pointer uit knoop tail ( l ) = tail ( tail ( l ));
gebruik een reference argument in recursieve functie
•Red-Black trees
void f ( Lijst & l ) { l = tail ( l ); }
wortel en bladeren zijn zwart alle paden hebben zelfde aantal zwarte knopen alle rode knopen hebben zwarte kinderen indien uit balans: draaien en/of kleuren
gebruik pointer naar pointer Knoop ** p = &l; p = & (( *p ) -> next ); *p = ( *p ) -> next;
•B-bomen, 2/3 bomen, ... 17
18
taal implementatie
parser
•altijd opbreken in verschillende fasen
•recursive descent:
scanner: maakt tokens van invoer
goede syntax nodig ( niet links recursief, LL(1) )
•gebruik reguliere definities voor syntax van tokens •altijd simpel, nooit een moeilijke keuze
•met LL(1) kun je direct zien welke regel past •anders grote look ahead of backtracking nodig •stop prioriteit van operatoren in de regels van de grammatica E -> E + T | T // expressie T -> T * F | F // term F -> ( E ) | num // factor
parser: maakt syntaxboom van tokens •maak een klasse hiërarchie die past bij de syntax boom
interpreter: bepaalt waarde met deze syntaxboom •syntaxboom blijft hetzelfde
simpel en direct
manipulatie: verander deze syntaxboom
•regels van parser volgen direct de grammatica
•interpretatie
•bottom-up
semantiek geeft vertelt direct wat er moet gebeuren
tabel met prioriteiten en stack nodig •(bijna) alle parser generatoren maken zo'n shift reduce parser 19
20
5
dynamic programming
lineaire algebra
•idee: dubbel recursieve functies hebben vaak een vreselijke complexiteit, b.v. O(2n ) •als het aantal mogelijke argumenten beperkt is kunnen we een tabel maken met resultaten •in plaats van opnieuw uitrekenen kunnen we nu waarden opzoeken in de tabel, O(1) •voor N waarden en m argumenten hebben we O(N m ) waarden in de tabel •maakt veel problemen doable
•lineaire afbeeldingen in Rn kunnen handig met een matrix vermenigvuldiging A(Bv)=(AB)v •schuiven is niet lineair, maar kan met vermenigvuldiging in Rn+1 ga over op homogene coördinaten (voeg extra 0 toe)
•implementatie vergt vectoren en matrices van verschillende grootte dit kan prima met templates
edit distance, ...
21
22
graph algoritmen
Minimum Spanning Tree
•veel problemen laten zich formuleren in termen van (gelabelde) graphen
•Prim: greedy algoritme begin bij een knoop voeg steeds goedkoopste link toe tussen de boom en een nieuwe knoop algoritme geeft ouders van knopen in MST: tree
verbindingen tussen knopen met een gewicht kortste pad, grootste flow, bereikbaarheid, ..
•verschillende representaties als bomen, rij van verbindingen per knoop, globale rij van verbindingen, verbindingsmatrix, ..
•Kruskal greedy algoritme iedere knoop in eigen kluster verbind steeds klusters met de goedkoopste link resultaat is verzameling links (verbindingen)
•aantal standaard algoritmen Prim, Kruskal: Minimum Spanning Tree Dijkstra: korste pad Floyd: all pair shortest path Ford-Fulkerson: grootste flow 23
24
6
kortste afstand tot startknoop
kortste afstand tussen alle knopen
•Dijkstra's kortste pad algoritme
•Floyd-Warshall (all pair shortest path)
lijkt erg op Prim in het begin is afstand van wortel tot zichzelf 0 als er geen directe verbinding is, is de afstand ∞ greedy algoritme: voeg steeds de knoop toe die het dichts bij de boom ligt alle directe buren van die knoop kunnen hierdoor dichter bij de wortel komen levert afstand tot wortel op i.p.v. ouder
gebruik completen afstandmatrix in het begin alleen direct verbindingen alle andere afstanden op ∞ edge relaxation: maak een steeds betere schatting: W(i,j)k = min ( W(i,j)k-1, W(i,k)k-1+ W(k,j)k-1) for ( int k=0; k < g.Size; k++ ) for ( int i=0; i < g.Size; i++) for ( int j=0; j < g.Size; j++ ) { int wk = g.w[i][k] + g.w[k][j]; if ( wk < g.w[i][j] ) g.w[i][j] = wk; }
25
26
maximale stroom door netwerk
representatie graph
•netwerk is graph gewicht is capaciteit
•idee is simpel (Ford-Fulkerson): initieel is de flow 0; while ( er is nog een pad waarover de flow verhoogd kan worden ) verhoog de flow over dat pad;
•je verhoogt de flow steeds zoveel als mogelijk over het gevonden pad •als flow in integers: O ( E f) met f maximale flow •variaties in het zoeken van dat pad: depth first breadth first (algoritme het dan Edmonds Karp): O ( V E2 ) onafhankelijk van f
•met boomknopen
•verbindingen per knoop A A
B
B D
E
A
E
D
E
C E D E E B D
B
C A
B E
•knopen en kanten
27
knopen = { A, B, C, D, E } edges = { (A,A), (A,B) , (B,D), (B,E) , (C,E), (D,E) , (E,B), (E,D) }
•verbindingsmatrix C
D
→naar ↓ van
A B C D E
A 1 0 0 0 0
B 1 0 0 0 1
C 0 0 0 0 0
D 0 1 0 0 1
E 1 1 1 1 0
28
7
abstractie
tentamenstof
•verberg details
• alles wat we behandeld hebben • uit het dictaat
maakt het duidelijker kunt niet per ongeluk iets fout doen realisatie:
14 tot en met 19, 21, 24 testen, parseren, interpreteren, red-black trees, en graphs staat nog niet in het dictaat
•private elementen van klasse •module
• de hoofdstukken uit Big C++ die info geven
•maak programmafragmenten algemener
8, 10, 16-18, 22 lang niet alles staat in het boek
los in een keer meer problemen op goed voor hergebruik realisatie •speciale gevallen en stopconditie in extra argumenten •klasse hiërarchie •templates 29
30
Vragen
31
8
