Caribbean Secondary Education Certificate - Information Technology/Testing Algorithms for correctness

From WikiEducator
Jump to: navigation, search

Correctness of Algorithms

Functional Correctness The kind of computational problem that will be considered in this course can generally be described by the following:

  • Precondition: A description of the problem’s inputs, including their types as well as any relationships or properties that they must satisfy.
  • Postcondition: A description of the problem’s outputs, including all relationships and properties — involving both inputs and inputs — that must be satisfied when the problem has been “solved.”

Proofs of Correctness of Algorithms

A proof of correctness of an algorithm is a mathematical proof of the following:

  • Whenever the algorithm is run on a set of inputs that satisfy a problem’s precondition, the algorithm halts, and its outputs (and inputs) satisfy the problem’s postcondition.

A proof that a program is correct often has two pieces (that can be developed separately):

  • Proof of partial correctness:
    • this is a proof that, whenever an algorithm is run on a set of inputs satisfying the problem’s precondition, either
      • the algorithm halts, and the outputs (and inputs) satisfy the problem’s postcondition, or
      • the algorithm does not halt at all!

So, an algorithm might be “partially correct” because it never, ever halts.

  • Proof of termination: This is a proof that the algorithm always halts, whenever it is run on a set of inputs that satisfy the precondition.

Various strategies have been found to prove the correctness of different kinds of algorithms — including single statements, sequences of simpler programs, tests, and loops. As time permits, some of these strategies will be described.

Principles of Testing and Debugging

Unfortunately, there are virtually no (nontrivial) computer programs that actually are correct immediately after they have been written: At the very least syntax and similar minor programming errors tend to get made.

The main idea of “software testing” is to show that a program is incorrect, by exhibiting one or more sets of program inputs that cause the program to behave in an unexpected way. One can then try to debug the program in order to find and remove the error (or errors) that caused the program to misbehave.

Additional information about testing and debugging will be provided in class. As time permits, this will either include information about the following, or references for further reading.

  • testing principles, objectives, and limitations
  • stages of testing
  • test design techniques
  • test implementation and evaluation
  • effective (and ineffective) debugging practices

Reference: [1]