[AlgEnComp] Vragen bij Hfst 4 van Algo

[Beatle]

Vraag 1:
Bij de stelling op p73 zegge dat de tijdscomplexiteit evident is. Kan er me iemand verduidelijk waarom deze evident is.

Vraag 2:
Hoe ziet de matrix Ag eruit? Wat is dit concreet?
p74

Vraag 3:
Singele source: wilt dit zeggen dat het maar op een knoop begint? (Een intiele knoop dus).
Bovnaan p76

Vraag 4:
Stelling p78 waarom is het hier evident dat de tijdscomplexiteit O(n²) is?

Vraag 5:
Laatste witte ruitje op p 78 en eerste witte ruitje p79. Is een beetje chinees wilt er iemand het een beetje verduidelijken?

Grtz

[Quintus Maximus]

Vraag1:
for k := 1 to n do
for i := 1 to n do
for j := 1 to n do

--> tijdscomplexiteit n^3 (is evident)

Vraag2: Ag is de adjacency matrix!!!
dus het ij'de element van Ag is l(vi,vj)
Vb: beschouw volgende Adjacency matrix
2 8 5
3 0 0
0 2 0

dan zien we dat er 3 nodes zijn v1, v2 en v3
en 5 edges.
er is een lus van v1 naar v1 met kost 2
er is een edge van v1 naar v2 met kost 8
er is een edge van v1 naar v3 met kost 5
er is een edge van v2 naar v1 met kost 3
en er is een edge van v3 naar v2 met kost 2.


Vraag3: Tjien nu da ge het zegt zou da wel is kunne ja. Vroeg mij da feitelijk ook af

Vraag4: Minder evident dan vraag1, maar toch nog forlus binne whilelus
moet wel nog is nazien aantal keer dat while lus herhaald wordt en hoogste aantal elementen in V\S...

Vraag5: pffff... straks mss. (eerst is zien wa ge hier over de volgende hoofdstukke nog hebt gevraagd)

[Karen]

Vraag2: Ag is de adjacency matrix!!!
dus het ij'de element van Ag is l(vi,vj)
Vb: beschouw volgende Adjacency matrix
2 8 5
3 0 0
0 2 0

Die 0-en moeten oneindig zijn

Succes!

[Beatle]

Als die Ag-matrix dan met oneindig wordt opgevult geeft dit dan geen problemen met de matrixvermenigvuldiging?

Of is die matrixvermenigvuldiging in de cursus hergedefineerd?

[Quintus Maximus]

Da hangt af denk ik van welke semi-ring ge gebruikt eh.