Under forelæsningen gennemgås eksempler på korrekthedsbeviser for nedenstående tre eksempler.

  1. Algoritmen "DutchFlag" fra [HS] side 67. Algoritmen i bogen er ikke korrekt. For at algoritmen skal være korrekt skal tildelingerne
         A[i] <-> A[w]; w <- w + 1;
         A[i] <-> A[b]; b <- b + 1;
    
    erstattes med
         A[i] <-> A[b]; 
         A[b] <-> A[w];
         w <- w + 1;
         b <- b + 1;
    
  2. Kvadrering af et heltal udelukkende ved hjælp af addition, subtraktion og halvering af lige tal: Eksamensopgave 1 fra august 2002 i kurset "Algoritmer og Datastrukturer".
  3. Algoritme for at finde majoritetselementet i et array:
         ALGORITHM : Majoritet
         INPUT     : Array A af længde n>=1, hvor der findes et majoritets
                     element der forekommer >n/2 gange
         OUTPUT    : x = Majoritet(A)
         METHOD    : i <- 1
                     j <- 1
                     x <- A[0]
                     { I } while i < n do
                              if j=0 then
                                 x <- A[i]
                                 j <- 1
                              else
                                 if x=A[i] then
                                    j <- j+1
                                 else
                                    j <- j-1
                              i <- i+1
         
         Invarianten I er:
         
           1)  1 <= i <= n
           2)  0 <= j
           3)  -j <= i - 2 * (antal forekomster af x i A[0]...A[i-1])
           4)  for alle y<>x: j <= i - 2 * (antal forekomster af y i A[0]...A[i-1]) 
    

Denne side vedligeholdes af Gerth Stølting Brodal <gerth@cs.au.dk>.