Iskanje najkrajših poti v usmerjenem grafu

• najkrajše poti od izbrane točke do vseh drugih
• dolžina povezave (a,b) naj bo c(a,b)
• rekurzivna definicija

t(a,a) = 0

• za nenegativne cene Dijkstrin algoritem
• požrešno delovanje, uporablja prioritetno vrsto
• če algoritem spremenimo, da uporablja največje razdalje, ga lahko uporabimo za izračun kritične poti)],(),([

Simulacija algoritma Dijkstra

• izpišimozaporedje stanj prioritetne vrste, implementirane s kopico
• izpisujemo (vozlišče, parent,distance)
• vozlišča, ki jih vzamemo iz prioritetne vrste, vsebujejo rezultat

Rešitev dobimo s kopico:

dobimo drevo najkrajših poti

Prioritetna vrsta brez kopice:

vedno vzamemo najmanjšo

(a,-,0)

(b,a,4) (c,a,9)

(c,a,9) (e,b,15) (d,b,11)

(e,b,15) (d,b,11) (g,c,27)

(e,b,15) (g,c,27) (f,d,16)

(g,c,27) (f,d,16) (h,e,33)

(g,f,23) (h,e,33) (i,f,19)

(g,f,23) (h,e,33)

(h,e,33)

Dobimo rešitev:

Dokazovanje pravilnosti programov

preverjanje pravilnosti

• branje in razumevanje
• testiranje na izbrani množici testnih podatkov
• formalno dokazovanje

program f: X →Z preslika vhodne podatke <x1, x2, ... xn> ∈X v izhodne <z1, z2, ... zm> ∈Z

začetni pogoj Φ(x₁,x₂,...x_n) –kakšni so lahko podatki

izhodni pogoj Ψ(z1,z2,...zm,x1,x2,...xn) –kakšen mora biti rezultat

Pravilnost programa

parcialna pravilnost

če se za vse vhodne podatke, ki izpolnjujejoΦ ustavi, izhodni podatki pa izpolnjujejo Ψ

totalna pravilnost

če je parcialno pravilen in se za vse vhodne podatke, ki izpolnjujejo Φustavi po končnemštevilu korakov

Prireditev

// P(izraz)
y = izraz;
// P(y)

//2x + 5 % 2 = 0
y = 2x + 5
//y % 2 = 0

Izbira

// P(y)
if(Pogoj(y))
// P(y) Pogoj(y)}
St ;
else
// P(y) ¬Pogoj(y)
Se ;

//2x + 5 % 2 = 0
if (x + 3 > 10)
  // 2x+5 % 2  x + 3 > 10
  St;
else
  // 2x+5 % 2  x + 3 > 10
  Se;

Zanka

// P1(y)
while(Pogoj(y)) {
  // zai-to izvajanjePi(y) ∧Pogoj(y)}
  S ;
  // Pi + 1(y)
}
// Pk(y) Pogoj(y)

pogoj Pi + 1(y) izpeljemoiz Pi(y)   Pogoj(y)
Pk(y) je odvisen od števila izvajanj zanke

Zaporedje

// P0(y) S1;S2; ... Sk; // Pk(y) pri čemer P_i+1(y) izpeljemo iz P_i(y)

Združitev več poti izvajanja

if... St// P_t(y)}
  else Se // P_e(y)}
//Pt(y) Pe(y)

if (x>3)
  St //x>10;
else
  Se; // x%2 = 0;
 x > 10  X % 2 = 0