Introduction

What is algorithmics?

Algorithmics is a method for finding a reliable and efficient solution to a problem.

• Analyse the problem. Analyse it again if needed.

• Decide on a method to solve it.

• Write down the final algorithm.

• Translate the algorithm into a suitable programming language.

• Start over if needed.

French is lucky here: computer science is called « informatique », the science of information, and not “the science of computers”.

[Computer science] is not really about computers – and it's not about computers in the same sense that physics is not really about particle accelerators, and biology is not about microscopes and Petri dishes...and geometry isn't really about using surveying instruments. — Hal Abelson

Caml

We still need a programming language to write and try out our algorithms: we will use Caml.

Families of languages

Functional? Imperative?

Languages can be sorted into several “families”.

1. Imperative programming: write a list of instructions which, starting from a state of the machine defined by the initial data, sets out the successive changes to the memory that deliver the requested result.

2. Declarative programming: describe the relationship (the relations) between the data and the results.

1. Functional languages: relations are seen as functions, and computation combines intermediate functions. (Lisp, Caml)

2. Logic languages: relations are described by logical formulas, and computation is done by an inference engine. (Prolog)

Compilation or interpretation

Binary code is the only code the machine can understand directly, and therefore actually run. Any program written in a high-level language must first be translated into machine code before it can run.

So there are two ways to produce executable code:

• Compilation: the whole program is translated at once by another program, called a compiler, and the machine code it produces is optimised. This machine code can then be run as many times as you like.

• Interpretation: a program (the interpreter) decodes the instructions (or expressions) of the source program one by one, and runs (evaluates) them as it goes.

Caml can do both. In this course we mostly use it as an interpreter: you type an expression and it is evaluated straight away. It is the simplest way to try out what you write. The same programs can also be compiled, with ocamlc or ocamlopt.