More about Trakhtenbrot here: Derpetology: Trakhtenbrot, an Unsung Hero of Computer Science
***
Boris (Boaz) Abramovich Trakhtenbrot was a Russian-Israeli mathematician in logic, algorithms, theory of computation, and cybernetics.
***
A flowchart is like an algorithm. The German animal name flowchart is my favorite.
Here is how I would define one: an algorithm is a finite set of computations with at least one loop. A simple example of this is long division. As an algorithm, it looks like this:
1. Multiply the divisor by a number so that it is close to but does not exceed the dividend. Start with 1 and increment to 9.
2. Subtract the result of step 1 from the dividend and use the remaining number as the new dividend.
3. Repeat steps 1 and 2 until the remaining number is smaller than the divisor.
4. Make a fraction of the remaining number and the divisor, convert it to a decimal, and add it to the rest of the quotient.
The details of the YouTube algorithm for suggesting videos are proprietary, but it works something like this: If people who watch video A also watch video B, video B is suggested after video A is watched. As a user watches more videos, the algorithm gets better at making suggestions because it has more information about what the user likes to watch. The goal of the algorithm is to maximize the amount of time the user spends watching videos.
Algorithms are subject to the halting problem. That is, there is no way of knowing in advance whether an algorithm will get stuck in a loop or not for every possible input.
Simple algorithms tend to be slower than more complex ones. Below are some visual aids.
There are problems that can't be solved with algorithms, but that doesn't mean the problem is unsolvable. Sometimes proving there is no general solution to a problem opens up a new field of math. Group Theory came into being because Galois used it to prove there is no general solution to a 5th order polynomial equation.
No comments:
Post a Comment