---
title: "Introduction aux algorithmes"
date: "2022-10-05"
patat:
  eval:
    tai:
      command: fish
      fragment: false
      replace: true
    ccc:
      command: fish
      fragment: false
      replace: true
  images:
    backend: auto
---

# Rappel (1/2)

## Quels algos avons-nous vu la semaine passée?

. . .

* L'algorithme de la factorielle.
* L'algorithme du PPCM.
* Le début de l'algorithme du PGCD.

# Rappel (2/2)

## Algorithme du PPCM?

. . .

```C
int main() { 
    int m = 15, n = 12;
    int mult_m = m, mult_n = n;
    while (mult_m != mult_n) {
        if (mult_m > mult_n) {
            mult_n += n;
        } else {
            mult_m += m;
        }
    }
    printf("Le ppcm de %d et %d est %d\n", n, m, mult_m);
}
```

# Le calcul du PGCD (1/5)

## Définition

Le plus grand commun diviseur (PGCD) de deux nombres entiers non nuls est le
plus grand entier qui les divise en même temps. 

## Exemples:

```C
PGCD(3, 4) = 1,
PGCD(4, 6) = 2,
PGCD(5, 15) = 5.
```

. . .

## Mathématiquement

Décomposition en nombres premiers:

$$
36 = 2^2\cdot 3^2,\quad 90=2\cdot 5\cdot 3^2,
$$
On garde tous les premiers à la puissance la plus basse
$$
PGCD(36, 90)=2^{\min{1,2}}\cdot 3^{\min{2,2}}\cdot 5^{\min{0,1}}=18.
$$

# Le calcul du PGCD (2/5)

## Algorithme

Par groupe de 3 (5-10min):

* réfléchissez à un algorithme alternatif donnant le PGCD de deux nombres;
* écrivez l'algorithme en pseudo-code.

. . .

## Exemple d'algorithme

```C
PGCD(36, 90):
90 % 36 != 0 // otherwise 36 would be PGCD
90 % 35 != 0 // otherwise 35 would be PGCD
90 % 34 != 0 // otherwise 34 would be PGCD
...
90 % 19 != 0 // otherwise 19 would be PGCD
90 % 18 == 0 // The end!
```

* 18 modulos, 18 assignations, et 18 comparaisons.

# Le calcul du PGCD (3/5)

## Transcrivez cet exemple en algorithme (groupe de 3) et codez-le (5-10min)!

. . .

## Optimisation

* Combien d'additions / comparaisons au pire?
* Un moyen de le rendre plus efficace?

. . .

## Tentative de correction

```C
void main() {
   int n = 90, m = 78;
   int gcd = 1;
   for (int div = n; div >= 2; div--) { // div = m, sqrt(n)
      if (n % div == 0 && m % div == 0) {
         gcd = div;
         break;
      }
   }
   printf("Le pgcd de %d et %d est %d\n", n, m, gcd);
}
```

# Le calcul du PGCD (4/5)

## Réusinage: l'algorithme d'Euclide

`Dividende = Diviseur * Quotient + Reste`

```C
PGCD(35, 60):
35 = 60 * 0 + 35 // 60 -> 35, 35 -> 60
60 = 35 * 1 + 25 // 35 -> 60, 25 -> 35
35 = 25 * 1 + 10 // 25 -> 35, 20 -> 25
25 = 10 * 2 +  5 // 10 -> 25, 5  -> 10
10 =  5 * 2 +  0 // PGCD = 5!
```

. . .

## Algorithme

Par groupe de 3 (5-10min):

* analysez l'exemple ci-dessus;
* transcrivez le en pseudo-code.

# Le calcul du PGCD (5/5)

## Pseudo-code

```C
entier pgcd(m, n) {
    tmp_n = n
    tmp_m = m
    tant que (tmp_m ne divise pas tmp_n) {
        tmp   = tmp_n
        tmp_n = tmp_m
        tmp_m = tmp modulo tmp_m
    }
    retourne tmp_m
}
```

# Le code du PGCD de 2 nombres

## Implémentez le pseudo-code et postez le code sur matrix (5min).

. . .

## Un corrigé possible

```C
#include <stdio.h>
void main() {
   int n = 90;
   int m = 78;
   printf("n = %d et m = %d\n", n, m);
   int tmp_n = n;
   int tmp_m = m;
   while (tmp_n%tmp_m > 0) {
      int tmp = tmp_n;
      tmp_n = tmp_m;
      tmp_m = tmp % tmp_m;
   }
   printf("Le pgcd de %d et %d est %d\n", n, m, tmp_m);
}
```

# Quelques algorithmes simples

* Remplissage d'un tableau et recherche de la valeur minimal
* Anagrammes
* Palindromes
* Crible d'ératosthène

. . .

* Ces algorithme nécessitent d'utiliser des **tableaux**.

# Collections: tableaux statiques

* Objets de même type: leur nombre est **connu à la compilation**;
* Stockés contigüement en mémoire (très efficace);

    ```C
    #define SIZE 10
    int entiers[] = {2, 1, 4, 5, 7}; // taille 5, initialisé
    int tab[3]; // taille 3, non initialisé
    float many_floats[SIZE]; // taille 10, non initialisé
    ```
* Les indices sont numérotés de `0` à `taille-1`;

    ```C
    int premier = entier[0]; // premier = 2
    int dernier = entier[4]; // dernier = 7
    ```
* Les tableaux sont **non-initialisés** par défaut;
* Les bornes ne sont **jamais** vérifiées.

    ```C
    int indetermine_1 = tab[1];     // undefined behavior
    int indetermine_2 = entiers[5]; // UB
    ```

# Remarques

* Depuis  `C99` possibilité d'avoir des tableaux dont la taille est *inconnue à
  la compilation*;

    ```C
    int size;
    scanf("%d", &size);
    char string[size];
    ```

 . . .

* Considéré comme une mauvaise pratique: que se passe-t-il si `size == 1e9`?
* On préfère utiliser l'allocation **dynamique** de mémoire pour ce genre de
  cas-là (spoiler du futur du cours).

# Initialisation

* Les variables ne sont **jamais** initialisées en `C` par défaut.
* Question: Que contient le tableau suivant?

    ```C
    double tab[4];
    ```

. . .

* Réponse: On en sait absolument rien!
* Comment initialiser un tableau?

. . .

```C
#define SIZE 10
double tab[SIZE];
for (int i = 0; i < SIZE; ++i) {
    tab[i] = rand() / (double)RAND_MAX * 10.0 - 5.0; 
    // tab[i] contient un double dans [-5;5]
}
```

# Recherche du minimum dans un tableau (1/2)

## Problématique

Trouver la valeur minimale contenue dans un tableau et l'indice de l'élément le plus petit.

## Écrire un pseudo-code résolvant ce problème (groupe de 3), 2min

. . .

```C
index = 0
min   = tab[0]
for i in [1; SIZE] {
    if min > tab[i] {
        min = tab[i]
        index = i
    }
}
```

# Recherche du minimum dans un tableau (2/2)

## Implémenter ce bout de code en C (groupe de 3), 4min

. . .

```C
int index = 0;
float min = tab[0];
for (int i = 1; i < SIZE; ++i) {
    if min > tab[i] {
        min = tab[i];
        index = i;
    }
}
```

# Tri par sélection (1/2)

## Problématique

Trier un tableau par ordre croissant.

## Idée d'algorithme

```C
ind = 0
tant que (ind < SIZE-1)
    Trouver le minimum du tableau, tab_min[ind:SIZE].
    Échanger tab_min avec tab[ind]
    ind += 1
```

# Tri par sélection (2/2)

## Implémentation par groupe de 3

* Initialiser aléatoirement un tableau de `double` de taille 10;
* Afficher le tableau;
* Trier par sélection le tableau;
* Afficher le résultat trié;
* Vérifier algorithmiquement que le résultat est bien trié.

# Un type de tableau particulier

## Les chaînes de caractères

```C
string = tableau + char + magie noire
```

# Le type `char`{.C}

- Le type `char`{.C} est utilisé pour représenter un caractère.
- C'est un entier 8 bits signé.
- En particulier:
    - Écrire
        
        ```C
        char c = 'A';
        ```
    - Est équivalent à:

        ```C
        char c = 65;
        ```
- Les fonctions d'affichage interprètent le nombre comme sa valeur ASCII.

# Chaînes de caractères (strings)

- Chaîne de caractère `==` tableau de caractères **terminé par la valeur** `'\0'`{.C} ou `0`{.C}.

## Exemple

```C
char *str  = "HELLO !";
char str[] = "HELLO !";
```

Est représenté par

| `char`  | `H`  | `E`  | `L`  | `L`  | `O`  |      | `!`  | `\0`|
|---------|------|------|------|------|------|------|------|-----|
| `ASCII` | `72` | `69` | `76` | `76` | `79` | `32` | `33` | `0` |

. . .

## A quoi sert le `\0`?

. . .

Permet de connaître la fin de la chaîne de caractères (pas le cas des autres
sortes de tableaux).

# Syntaxe

```C
char name[5];
name[0] = 'P';  // = 70;
name[1] = 'a';  // = 97;
name[2] = 'u';  // = 117;
name[3] = 'l';  // = 108;
name[4] = '\0'; // = 0;
char name[] = {'P', 'a', 'u', 'l', '\0'};
char name[5] = "Paul";
char name[] = "Paul";
char name[100] = "Paul is not 100 characters long.";
```

# Fonctions

- Il existe une grande quantités de fonction pour la manipulation de chaînes de caractères dans `string.h`.
- Fonctions principales:

    ```C
    // longueur de la chaîne (sans le \0)
    size_t strlen(char *str);
    // copie jusqu'à un \0
    char *strcpy(char *dest, const char *src);
     // copie len char
    char *strncpy(char *dest, const char *src, size_t len);
    // compare len chars
    int strncmp(char *str1, char *str2, size_t len);
    // compare jusqu'à un \0
    int strcmp(char *str1, char *str2);
    ```

- Pour avoir la liste complète: `man string`.

. . .

## Quels problèmes peuvent se produire avec `strlen`, `strcpy`, `strcmp`?

# Les anagrammes

## Définition

Deux mots sont des anagrammes l'un de l'autre quand ils contiennent les mêmes 
lettres mais dans un ordre différent.

## Exemple

| `t`  | `u`  | `t`  | `u`  | `t`  | `\0` | ` `  | ` ` |
|------|------|------|------|------|------|------|-----|
| `t`  | `u`  | `t`  | `t`  | `u`  | `\0` | ` `  | ` ` |


## Problème: Trouvez un algorithme pour déterminer si deux mots sont des anagrammes.

# Les anagrammes

## Il suffit de:

1. Trier les deux mots.
2. Vérifier s'ils contiennent les mêmes lettres.

## Implémentation en live (offerte par HepiaVPN)

```C
int main() { // pseudo C
    tri(mot1);
    tri(mot2);
    if egalite(mot1, mot2) {
        // anagrammes
    } else {
        // pas anagrammes
    }
}
```

<!-- TODO: Live implémentation hors des cours? -->

# Les palindromes

Mot qui se lit pareil de droite à gauche que de gauche à droite:

. . .

* rotor, kayak, ressasser, ...

## Problème: proposer un algorithme pour détecter un palindrome

. . .

## Solution 1

```C
while (first_index < last_index {
    if (mot[first_index] != mot [last_index]) {
        return false;
    }
    first_index += 1;
    last_index -= 1;
}
return true;
```

. . .

## Solution 2

```C
mot_tmp = revert(mot);
return mot == mot_tmp;
```

# Crible d'Ératosthène

Algorithme de génération de nombres premiers.

## Exercice

* À l'aide d'un tableau de booléens,
* Générer les nombres premiers plus petits qu'un nombre $N$

## Pseudo-code

* Par groupe de trois, réfléchir à un algorithme.

## Programme en C

* Implémenter l'algorithme et le poster sur le salon `Element`.