Výpocet maxima, SA

• Úloha: urcit m = ?max j: 0 ? j < N:: A[j]? pre dané pole A[0..N ? 1]

Sekvencná architektúra (SA):

• invariant m ? ?max j: 0 ? j < N:: A[j]?
• FP ? m ? ?max j: 0 ? j < N:: A[j]?
• FP mozno písat aj takto:
  FP ? ?? j: 0 ? j < N:: m ? A[j]?
  FP ? ?? j: 0 ? j < N:: m = max(m, A[j])?

• Program Maximum1

  initially m = ??
  
  assign ? ||j: 0 ? j < N:: m := max(m, A[j]) ?

end {Maximum1}

• kazdé z priradení sa môze napríklad vykonat viac ráz po sebe, co nevedie k nicomu; dve stratégie, ako sa takejto neefektívnosti vyhnút:

1. moznost:

initially j = 0

m, j := max(m, A[j]), j + 1 if j < N

2. moznost:

initially ? ||j: 0 ? j < N:: e[j] = true?

m, e[j] := max(m, A[j]), false if e[j]

Previous slide

Next slide

Back to first slide

View graphic version