Читать книгу Algorithms For Dummies - John Paul Mueller, John Mueller Paul, Luca Massaron - Страница 32

The previous section introduces you to the vagaries of discovering real-world solutions, ones that consider issues that solutions found in the lab can’t take into account. However, just finding a solution — even a good one — isn’t sufficient because even good solutions fail on occasion. Playing the devil’s advocate by locating counterexamples is an important part of starting to solve a problem. The purpose of counterexamples is to

 Potentially disprove the solution

 Provide boundaries that define the solution better

 Consider situations in which the hypothesis used as a basis for the solution remains untested

 Help you understand the limits of the solution

A common scenario that illustrates a solution and counterexample is the statement that all prime numbers are odd. (Prime numbers are positive integers that can be evenly divided by themselves and 1 to produce an integer result.) Of course, the number 2 is prime, but it’s also even, which makes the original statement false. Someone making the statement could then qualify it by saying that all prime numbers are odd except 2. The partial solution to the problem of finding all the prime numbers is that you need to find odd numbers, except in the case of 2, which is even. In this second case, disproving the solution is no longer possible, but adding to the original statement provides a boundary.

By casting doubt on the original assertion, you can also consider situations in which the hypothesis, all prime numbers except 2 are odd, may not hold true. For example, 1 is an odd number but isn’t considered prime (see the discussion at https://primes.utm.edu/notes/faq/one.html for details). So now the original statement has two boundaries, and you must restate it as follows: Prime numbers are greater than 1 and usually odd, except for 2, which is even. The boundaries for prime numbers are better defined by locating and considering counterexamples.

As the complexity of a problem grows, the potential for finding counterexamples grows as well. An essential rule to consider is that, as with reliability, having more failure points means greater potential for a failure to occur. Thinking of algorithms in this way is important. Ensembles of simple algorithms can produce better results with fewer potential counterexamples than a single complex algorithm.