Les cours d'informatique en MP2I et MPI

Qui dit nouvelle filière, dit nouveaux professeurs et nouveaux cours. Vous vous demandez sûrement en quoi consiste le cours d’informatique en MP2I et MPI, et bien cette page est là pour vous éclairer !

Répartition horaire

• Cours : cours théorique en classe entière, comme pour les mathématiques par exemple.
• Travaux Dirigés (TD) : exercices en demi-groupe, où l’objectif est de pratiquer pour maîtriser les concepts et progresser.
• Travaux Pratiques (TP) : travaux sur machine pour implémenter ce que vous avez vu en cours : c’est là qu’on code !

Remarquez que ce nombre d’heures peut varier : il n’est pas rare qu’un professeur d’informatique rajoute des heures de TP pour vous faire pratiquer un peu plus en début d’année par exemple !

La théorie

La première chose à comprendre est que ce cours d’informatique est principalement théorique.

Beaucoup des notions abordées font d’ailleurs plus précisément partie de l’algorithmique, c’est-à-dire l’étude des algorithmes.

Un premier critère pour savoir si cette filière est faite pour vous est donc : Est-ce que j’aime les mathématiques ?

Programme en MP2I

Programme en MPI

La pratique

Le but principal des TP est de faire fonctionner un algorithme étudié en cours (avant ou après) sur un ordinateur, et de créer de nouveaux algorithmes pour des tâches connexes.

Langages de programmation

Pendant les TP, la programmation se fait en C et en OCaml.

Retrouvez la documentation en ligne du C ainsi que le site OCaml.

On utilise quelquefois Python lors de TP de physique, mais c’est davantage une compétence de traitement de données que des algorithmes complexes.

Exemples

Voici un exemple classique de tâche pour lequel on va construire un algorithme : calculer les termes de la suite de Fibonacci. Pour rappel, les premiers termes de cette suite valent 0 et 1, puis on construit le terme suivant en additionnant les deux précédents.

En Python

Dans le chapitre récursivité, vous avez vraisemblablement déjà rencontré la suite de Fibonacci.

def fibo(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibo(n - 1) + fibo(n - 2)
    
# On pourrait omettre les "else" mais ils peuvent aider à la compréhension.

En OCaml

En “traduisant” simplement la syntaxe :

let rec fibo n = 
    if n = 0 then 0
    else if n = 1 then 1
    else fibo (n-1) + fibo (n-2) 
    
(* Les parenthèses ne sont pas systématiques en OCaml. 
   On doit les utiliser lorsque notre expression n'est pas associative, 
   pour dissocier les différents cas. 
   Ici, nous voulons bien passer n-1 en paramètre, 
   et non faire fibo n puis décrémenter le résultat. *)

Cependant, le pattern matching permet d’obtenir une écriture plus élégante pour ce genre de codes ; il est également possible de préciser le type des paramètres utilisés ainsi que celui de l’expression renvoyée.

(Il existe quelque chose de ressemblant en python, mais ça n’est que du sucre syntaxique)

Ces optimisations syntaxiques permettent de déceler plus vite une incohérence, et donc de produire un code plus sécurisé en s’assurant qu’il réalise exactement ce que l’on veut. On dit qu’OCaml est fortement typé.

(* La fonction fibo prend en paramètre un entier n, et renverra aussi un entier. *)
let rec fibo (n:int) : int = 
    match n with 
    (* On filtre la variable n. 
       Si la valeur ne correspond pas au filtre, on passe au filtre suivant. *)
    | 0 -> 0 (* Première valeur de la suite de fibonnaci *)
    | 1 -> 1 (* Deuxième valeur *)
    | n -> fibo (n-1) + fibo (n-2) 
    (* Ce filtre prend toute valeur de n, il permet d'effectuer un filtrage exhaustif.
       En conséquent, aucun autre filtre suivant ne sera pris en compte. *)

Cependant, comme vous le verrez en cours, les algorithmes précédents sont peu efficaces, car ils calculent de nombreuses fois les mêmes termes (donc ils deviennent très vite lents lorsque la taille de l’entrée augmente) et peuvent finir par faire “exploser la pile d’appel”.

Afin de réduire la quantité de mémoire utilisée par le programme, il est possible d’appliquer le principe de récursivité terminale, comme le fait l’exemple ci-dessous :

let fibo (n:int) : int =
    (* On crée une fonction auxiliaire pour stocker les valeurs de la suite *)
    let rec aux i f1 f2 = 
        match i with
            | 0 -> f1
            | 1 -> f2
            | _ -> aux (i - 1) f2 (f1 + f2)
    in aux n 0 1 (* Et on renvoie sa valeur ici *)

Dans le programme ci-dessus, chaque valeur de la suite est calculée une seule fois, et est stockée dans les arguments de la fonction auxiliaire. Cela nous permet d’atteindre une complexité linéaire en réduisant le nombre d’opérations effectuées par la fonction.

En C

Dans la même idée, il est possible d’écrire cette même fonction dans le langage C :

int fibo(int n)
{
    /* En C, un double égal permet de comparer deux valeurs. 
     * Un simple égal est considéré comme une assignation.
     * Des parenthèses sont nécessaires autour de chaque expression logique. 
     */
    if (n == 0)      // On peut omettre les accolades si il y a qu'une seule expression dans le bloc
        return 0;
    else if (n == 1) // Pareil qu'en Python, on peut aussi omettre les else ici
        return 1; 
    else
        return fibo(n - 1) + fibo(n - 2);
}

Ici, chaque appel à la fonction fibo recalcule chaque valeur de la suite, ce qui augmente l’usage en mémoire et la complexité du programme. Il est possible d’appliquer le même principe de récursivité terminale en C, avec le coût ajouté des arguments supplémentaires dans la signature de la fonction (il est impossible de définir des fonctions dans les fonctions en C).

Si on cherche à l’optimiser un peu en appliquant la récursivité terminale, ça donnerait :

int fibo(int n, int n0, int n1)
{
    if (n == 0)
        return n0;
    if (n == 1)
        return n1;
    return fibo(n-1, n1, n0+n1);
}

/* Ne vous souciez pas de ce que contient cette fonction, 
 * vous verrez tous les détails du fonctionnement du langage en cours :) 
 */
int main()
{
    int fibo10 = fibo(10, 0, 1); /* Correspond au premier appel récursif en OCaml */
    return 0;
}

Bien sûr, il est toujours possible d’aller un peu plus loin et de s’amuser avec le côté obscur de l’informatique :

long int fibo(int n)
{ 
    int a = 0, b = 1;
    for (int i=0; i<n; i++){
        a+=b;
        a^=b;
        b^=a;
        a^=b;
    }   
    return a;
}

Ce code est en fait basé sur un XOR swap. Comme quoi, on peut s’amuser en MP2I/MPI, même avec une tâche aussi simple !

Ne prenez pas peur si vous ne savez écrire dans aucun de ces langages, leurs compilateurs respectifs vous accompagneront tout du long en vous indiquant les erreurs et comment les corriger 😉