Algorithms For Dummies. John Paul Mueller

Чтение книги онлайн.

СКАЧАТЬ

      However, real-world problems are even more complex than simply looking at static data or iterating that data only once. For example, anything that moves, such as a car, airplane, or robot, receives constant input. Each updated input includes error information that a real-world solution will need to incorporate into the result in order to keep these machines working properly. In addition to other algorithms, the constant calculations require the proportional integral derivative (PID) algorithm (see https://www.ni.com/en-us/innovations/white-papers/06/pid-theory-explained.html for a detailed explanation of this algorithm) to control the machine using a feedback loop. Every calculation brings the solution used to control the machine into better focus, which is why machines often go through a settling stage when you first turn them on.

When modeling a real-world problem, you must also consider non-obvious issues that crop up. An obvious solution, even one based on significant mathematical input and solid theory, may not work. For example, during WWII, the allies had a serious problem with bomber losses. Therefore, the engineers analyzed every bullet hole in every plane that came back. After the analysis, the engineers used their solution to armor the allied planes more heavily to ensure that more of them would come back. It didn’t work. Enter Abraham Wald. This mathematician suggested a non-obvious solution: Put armor plating in all the places that lacked bullet holes (because the areas with bullet holes are already strong enough; otherwise the plane wouldn’t have returned). The resulting solution did work and is now used as the basis for survivor bias (the fact that the survivors of an incident often don’t show what actually caused a loss) in working with algorithms. You can read more about this fascinating bit of history at https://medium.com/@penguinpress/an-excerpt-from-how-not-to-be-wrong-by-jordan-ellenberg-664e708cfc3d.

      Real-world modeling may also include the addition of what scientists normally consider undesirable traits. For example, scientists often consider noise undesirable because it hides the underlying data. Consider a hearing aid, which removes noise to enable someone to hear better (see the discussion at https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4111515/ for details). Many methods exist for removing noise, some of which you can find in this book starting with Chapter 9 as part of other topic discussions.

      However, as counterintuitive as it might seem, adding noise to the data also requires an algorithm that provides useful output with that noise in place. For example, Ken Perlin wanted to get rid of the machine-like look of computer-generated graphics in 1983, and he created an algorithm to do so. The result is Perlin noise (see https://catlikecoding.com/unity/tutorials/pseudorandom-noise/perlin-noise/ for details). The effect is so useful that Perlin won an Academy Award for his work (see https://cs.nyu.edu/~perlin/doc/oscar.html for details). A real-world scenario often requires choices that may not be obvious when working in the lab or during the learning process.

      

The main gist of this section is that solutions often require several iterations to create, you may have to spend a lot of time refining them, and obvious solutions may not work at all. When modeling a real-world problem, you do begin with the solutions found in textbooks, but then you must move beyond theory to find the actual solution to your problem. As this book progresses, you’re exposed to a wide variety of algorithms — all of which help you find solutions. The important thing to remember is that you may need to combine these examples in various ways and discover methods for interacting with data so that it lends itself to finding patterns that match the output you require.

      Finding solutions and counterexamples

      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.

      Standing on the shoulders of giants

      A myth that defies explanation is that the techniques currently used to process huge quantities of data are somehow new. Yes, new algorithms do appear all the time, but the basis for these algorithms is all of the algorithms that have gone before. In fact, when you think about Sir Isaac Newton, you might think of someone who invented something new, yet even he stated (using correct spelling for his time), “If I have seen further it is by standing on the sholders of Giants” (see https://en.wikiquote.org/wiki/Isaac_Newton for additional quotes and insights).

The algorithms you use today weren’t even new in the days of Aristotle (see https://plato.stanford.edu/entries/aristotle-mathematics/) and Plato (see https://www.storyofmathematics.com/greek_plato.html). The origins of algorithms in use today are so hidden in history that the best anyone can say is that math relies on adaptations of knowledge from ancient times. The use of algorithms since antiquity should give you a certain feeling of comfort because the algorithms in use today СКАЧАТЬ