[Math] How to describe an algorithm with mathematical notation

algorithmsnotationterminology

I often have to create new computer science algorithm. The problem come when I have to describe them in a scientific way. I don't know where I should look for to learn how to describe my algorithms with a mathematical notation. I can do some basic stuff such as describing the different set I use and their relations… but that's all.

So I want to know if there are good book about mathematical description of algorithms. Also, what part of math should a study for that (first order logic, propositionnal logic,?)

Thank you.

Best Answer

If it's truly important to describe the algorithm in mathematical notation, look to Haskell for inspiration. Many Haskell statements can be translated directly into mathematical notation. For example, the definition

fac 0 = 1
fac n = n * fac (n - 1)

is equivalent to the mathematical statements

$$\begin{align*}fac(0) &= 1\\fac(n) &= n\ fac(n - 1)\ (\operatorname{if} n \ne 0).\end{align*}$$

In practice, however, what you really want is usually to write algorithms precisely, with mathematical terminology. In order to accomplish this, it is essential to practice doing so, and to ask other people for feedback. You can't learn to play the piano by reading books about it, nor can you learn piano while wearing earmuffs. Look at examples, too; every time you look at an example and think "oh, what a good idea!", you've learned something.

Really, I don't know of any better ways to learn this. Think of an algorithm, and try to write it down in a way that a mathematician would understand. Ask a mathematician if they understand. If not, figure out why. Repeat.

Related Question