Computation, Programming and Computational Thinking
What is Computation
There are two types of knowledge: declarative and imperative. Declarative knowledge (or descriptive knowledge) is mainly expressed as statements of facts. For example, the following statement defines the term “maximum”: The maximum of a collection of numbers is the one which is larger than any others.
Imperative knowledge is oftentimes a procedure (recipe), describing steps of actions. For example, we can define a sequence of steps to find the maximum in a collection of numbers: Pick up each element one by one, compare it with all others, and terminate when the current element is larger than all others.
Computation is mainly about imperative knowledge, that is, solving problems by providing specific procedures; ideally, such procedures should be implementable using computers.
Let’s consider several example problems and see how to solve them using computers.
Finding the maximum. This problem is to find the maximum value given a collection of numbers. There are many solutions to this problem:
- Pick up each element one by one and compare it with all others; when the current element is larger than all others, output it and terminate.
- Consider the numbers are in a sequence. Pick up each element in sequence, and compare it with only the ones behind itself; if the current element is larger than all those behind, output it and terminate.
- Sort the number in the descending order and output the first one in the sorted result.
All these solutions involve procedures of computation. It is not hard to verify that they are all correct (they will output the correct answer). In addition, these procedures are not designed to fit any predefined collection; they work well for any collections of any size. Computation is about giving generic solutions to generic problems.
However, these three procedures are different in terms of efficiency. In fact, the second one is the most efficient one since it involves few comparisons in the whole procedure. The efficiency of a procedure depends on the number of basic computational operations, but not on the description of the procedure itself.
Each computational procedure has inputs and outputs. The input in this case is a collection of numbers, and the output is one single number, which should be the maximum value if the procedure is correct.
Finding the square root of a number. The square root of a number \(b\) is a number \(a\) such that \(a\times a = b\). The problem here is to find the square root of any given number, say 10.
Note that we wish to have a procedure which works for any input number. Although finding the square roots for some numbers (such as 4) is easy, it is not clear for arbitrary numbers like 10, 1234567, etc.
The definition of “square root” does not give us much hints on how to find it. The following is a naive “try-and-fail” procedure. It is better to describe the procedure for a specific input, say 10.
- Try each integer 1, 2,… and compare the square with 10; since 3*3 < 10 < 4*4, we know the square root of 10 is between 3 and 4.
- Then try 3.1, 3.2, … and compare the square with 10. Thus we know the square root of 10 is between 3.1 and 3.2.
- Try 3.11, 3.12, … and then we know the square root of 10 is between 3.16 and 3.17.
- Continue until we get a number with a good precision.
The general idea of this procedure is to continuously narrow down the search space and make progress step by step. We also use compositions of simple tasks (computing the square of a number) to solve the complicated final task (computing the square root).
Below is a more efficient way to find the square root. Let \(y\) be the input number.
- Start with a guess \(g\) (any number is OK).
- If \(g\times g\) is close enough to \(y\), then \(g\) is a good approximation and output it.
- Otherwise, make a new guess \(g \leftarrow (g + y/g) / 2\). Using this new guess, go back to the previous step
Primality test — checking whether a number is prime. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For example, 5 is prime, but 6 is not since 6=2*3. The problem here is to decide whether a given natural number is prime (primality testing).
Let n be the given number. A trivial way to test primality is to try each integer from 2 to n-1 and check whether or not n is divisible by it. But this approach can be improved by just trying integers from 2 to \(\sqrt{n}\), since any nontrivial factor must be at most \(\sqrt{n}\).
Here we see that, if we have a better understanding of the problem itself, we can design more efficient solutions. Note that the “efficiency” here does not depend on which computer is being used to run the solution (as a procedure); it depends only on the procedure itself together with the input.
[Primality testing is an important mathematical problem. There are much more efficient procedures for primality testing, which you may find online.]
Programming
Programming is the process of solving problems by writing computer programs. It usually include the following steps:
- Analyzing the problem.
- Designing a solution.
- Implementing the solution.
- Testing.
A programming language is a formal language designed to communicate instructions to computers. Programming languages give us a way to control the behavior of a machine and let it interact with the user. The most used programming languages include C, C++, Java, JavaScript, Perl, PHP, Python, etc.
A language is specified by its syntax and semantics.
- Syntax: Which sequences of characters and symbols are well-formed strings?
- Static semantics: Which well-formed strings have a meaning?
- Semantics: What is that meaning?
Computational Thinking
Computational thinking is the way of solving problems using computer science techniques. It is a problem-solving process that usually include: analyzing the problem from a computational perspective, formulating the problem as a computation task, identifying potential solutions and making the choice, implementing and testing solutions.
Many techniques have been developed and formulated by computer scientists and software engineers over the years. They are also widely applied to write programs underlying computer applications. For example,
- Decomposition. Breaking down a task into easily handleable components with simple connections.
- Pattern Recognition. Identifying similarities and common features that lead to predictions or reusable solutions.
- Generalization and Abstraction. Identifying critical components and filtering out unnecessary information, and reformulating the problem in a generic way.
The following video presents how Google engineers use computational thinking to solve real-world problems.