---
title: "Introduction aux algorithmes"
date: "2022-09-21"
---

# Qu'est-ce qu'un algorithme?

## Définition informelle (recette)

* des entrées (les ingrédients, le matériel utilisé) ;
* des instructions élémentaires simples (frire, flamber, etc.), dont les 
  exécutions dans un ordre précis amènent au résultat voulu ;
* un résultat : le plat préparé.

. . .

## Histoire et étymologie

- Existent depuis 4500 ans au moins (algorithme de division, crible 
  d'Eratosthène).
- Le mot algorithme est dérivé du nom du mathématicien perse
    *Muḥammad ibn Musā al-Khwārizmī*, qui a été "latinisé" comme 
    *Algoritmi*.

. . .

## Définition formelle

En partant d'un état initial et d'entrées (peut-être vides), une séquence finie 
d'instruction bien définies (ordonnées) implémentables sur un ordinateur, afin 
de résoudre typiquement une classe de problèmes ou effectuer un calcul.

# Notions de base d'algorithmique

## Variable

. . .

* Paire: identifiant - valeur (assignation);

## Séquence d'instructions / expressions

. . .

* Opérateurs (arthimétiques / booléens)
* Boucles;
* Structures de contrôle;
* Fonctions;


# Algorithme de vérification qu'un nombre est premier (1/3)

Nombre premier: nombre possédant deux diviseurs entiers distincts.

. . .

## Algorithme naïf (problème)

```C
booléen est_premier(nombre) 
    si 
        pour tout i, t.q. 1 < i < nombre 
            i ne divise pas nombre
    alors vrai
    sinon faux
```

. . .

## Pas vraiment un algorithme: pas une séquence ordonnée et bien définie

. . .

## Problème: Comment écrire ça sous une forme algorithmique?

# Algorithme de vérification qu'un nombre est premier (2/3)

## Algorithme naïf (une solution)

```C
booléen est_premier(nombre) // fonction
    soit i = 2;       // variable, type, assignation
    tant que i < nombre // boucle
        si nombre modulo i == 0 // expression typée
            retourne faux    // expression typée
        i = i + 1
    retourne vrai // expression typée
```

# Algorithme de vérification qu'un nombre est premier (3/3)

## Algorithme naïf (une solution en C)

```C
bool est_premier(int nombre) {
    int i; // i est un entier
    i = 2; // assignation i à 2
    while (i < nombre) { // boucle avec condition
        if (0 == nombre % i) { // is i divise nombre
            return false; // i n'est pas premier
        }
        i += 1; // sinon on incrémente i
    }
    return true;
}
```

. . .

## Exercice: Comment faire plus rapide?

# Génération d'un exécutable

- Pour pouvoir être exécuté un code C doit être d'abord compilé (avec `gcc` ou `clang`).
- Pour un code `prog.c` la compilation "minimale" est

    ```bash
    $ gcc prog.c
    $ ./a.out # exécutable par défaut
    ```

- Il existe une multitude d'options de compilation:

    ```bash
    $ gcc -O1 -std=c11 -Wall -Wextra -g porg.c -o prog 
    	-fsanitize=address 
    ```
    1. `-std=c11` utilisation de C11.
    2. `-Wall et -Wextra` activation des warnings.
    3. `-fsanitize=…`  contrôles d’erreurs à l’exécution (coût en performance).
    4. `-g` symboles de débogages sont gardés.
    5. `-o` défini le fichier exécutable à produire en sortie.
    6. `-O1`, `-O2`, `-O3`: activation de divers degrés d'optimisation



# La simplicité de C?

## 32 mots-clé et c'est tout

---------------- -------------- ---------------- ---------------
`auto`{.C}       `double`{.C}   `int`{.C}        `struct`{.C}   
`break`{.C}      `else`{.C}     `long`{.C}       `switch`{.C}   
`case`{.C}       `enum`{.C}     `register`{.C}   `typedef`{.C}  
`char`{.C}       `extern`{.C}   `return`{.C}     `union`{.C}    
`const`{.C}      `float`{.C}    `short`{.C}      `unsigned`{.C} 
`continue`{.C}   `for`{.C}      `signed`{.C}     `void`{.C}
`default`{.C}    `goto`{.C}     `sizeof`{.C}     `volatile`{.C}
`do`{.C}         `if`{.C}       `static`{.C}     `while`{.C}
---------------- -------------- ---------------- ---------------

# Déclaration et typage

En C lorsqu'on veut utiliser une variable (ou une constante), on doit déclarer son type

```C
const double two = 2.0; // déclaration et init.
int x;   // déclaration (instruction)
char c;  // déclaration (instruction)
x = 1;   // affectation (expression)
c = 'a'; // affectation (expression)
int y = x; // déclaration et initialisation en même temps
int a, b, c; // déclarations multiples
a = b = c = 1; // init. multiples
```

# Les variables (1/2)

## Variables et portée

- Une variable est un identifiant, qui peut être liée à une valeur (un expression).
- Une variable a une **portée** qui définit où elle est *visible* (où elle peut être accédée).
- La portée est **globale** ou **locale**.
- Une variable est **globale** est accessible à tout endroit d'un programme et doit être déclarée en dehors de toute fonction.
- Une variable est **locale** lorsqu'elle est déclarée dans un **bloc**, `{...}`{.C}.
- Une variable est dans la portée **après** avoir été déclarée.

# Les variables (2/2)

## Exemple 

```C
float max; // variable globale accessible partout
int foo() {
    // max est visible ici
    float a = max; // valide
    // par contre les varibles du main() ne sont pas visibles
}
int main() {
    // max est visible ici
    int x = 1; // x est locale à main
    {
        // x est visible ici, y pas encore
        // on peut par exemple pas faire x = y;
        int y = 2;
    } // y est détruite à la sortie du bloc
} // x est à la sortie de main

```

<!-- TODO: quiz, compile, compile pas -->
<!-- ```C
int main() {
    global = 1;
} // COMPILE PAS
```

```C
int main() {
    int global = 1;
    {
        printf("global = %d", global);
    }
} // COMPILE
```

```C
int local;

int main() {
    local = 1;
    {
        printf("local = %d", local);
    }
} // COMPILE
```

```C
#include <stdio.h>
int local = 0;

int main() {
    int local = -1;
    {
        int local = 1;
        printf("local = %d\n", local);
    }
} // COMPILE
``` -->

# Quiz: compile ou compile pas?

## [Quiz: compile ou compile pas](https://cyberlearn.hes-so.ch/mod/evoting/view.php?id=1033948)

# Types de base (1/4)

## Numériques

Type                               Signification (**gcc pour x86-64**)            
---------------------------------- ---------------------------------------------
`char`{.C}, `unsigned char`{.C}    Entier signé/non-signé 8-bit
`short`{.C}, `unsigned short`{.C}  Entier signé/non-signé 16-bit
`int`{.C}, `unsigned int`{.C}      Entier signé/non-signé 32-bit
`long`{.C}, `unsigned long`{.C}    Entier signé/non-signé 64-bit
`float`{.C}                        Nombre à virgule flottante, simple précision
`double`{.C}                       Nombre à virgule flottante, double précision
---------------------------------- ---------------------------------------------

**La signification de `short`{.C}, `int`{.C}, ... dépend du compilateur et de l'architecture.**

# Types de base (2/4)

Voir `<stdint.h>` pour des représentations **portables**

Type                               Signification
---------------------------------- ---------------------------------------------
`int8_t`{.C}, `uint8_t`{.C}        Entier signé/non-signé 8-bit
`int16_t`{.C}, `uint16_t`{.C}      Entier signé/non-signé 16-bit
`int32_t`{.C}, `uint32_t`{.C}      Entier signé/non-signé 32-bit
`int64_t`{.C}, `uint64_t`{.C}      Entier signé/non-signé 64-bit
---------------------------------- ---------------------------------------------

. . .

## Prenez l'habitude d'utiliser ces types-là!

# Types de base (3/4)

## Booléens

- Le ANSI C n'offre pas de booléens.
- L'entier `0`{.C} signifie *faux*, tout le reste *vrai*.
- Depuis C99, la librairie `stdbool` met à disposition un type `bool`{.C}.
- En réalité c'est un entier:
  - $1 \Rightarrow$ `true`{.C}
  - $0 \Rightarrow$ `false`{.C}
- On peut les manipuler comme des entier (les sommer, les multiplier, ...).

# Quiz: booléens

## [Quiz: booléens](https://cyberlearn.hes-so.ch/mod/evoting/view.php?id=1032492)

<!-- TODO Quiz en ligne -->
<!-- ```C
if (42) { /* vrai */ }

int x = 100;
if (x == 4) { /* faux */ }
if (x) { /* vrai */ }

int x = 100;
while (x−−) { /* répète tant que x est différent de 0 */ }

if (0) { /* faux */ }
if (i = 4) { /* vrai */ }
if (i = 0) { /* faux */ }

#include <stdbool.h>

bool x = true;
if (x) { /* vrai */ }
``` -->

# Types de base (4/4)

## Conversions

- Les conversions se font de manière:
  - Explicite:
    ```C
    int a = (int)2.8;
    double b = (double)a;
    int c = (int)(2.8+0.5);
    ```
  - Implicite:
    ```C
    int a = 2.8; // warning, si activés, avec clang
    double b = a + 0.5;
    char c = b; // pas de warning...
    int d = 'c';
    ```

# Quiz: conversions

## [Quiz: conversions](https://cyberlearn.hes-so.ch/mod/evoting/view.php?id=1033446)

<!-- TODO Quiz en ligne -->
<!-- ```C
int a = (int)2.8; // 2

double b = 2.85;
int c = b + 0.5; // 3

int d = a + 0.5; // 2

bool d = 2.78; // 1
bool e = 1.0; // 1
``` -->

# Expressions et opérateurs (1/6)

Une expression est tout bout de code qui est **évalué**.

## Expressions simples

- Pas d'opérateurs impliqués.
- Les littéraux, les variables, et les constantes.

```C
const int L = -1; // 'L' est une constante, -1 un littéral
int x = 0;        // '0' est un litéral
int y = x;        // 'x' est une variable
int z = L;        // 'L' est une constante
```

## Expressions complexes

- Obtenues en combinant des *opérandes* avec des *opérateurs*

```C
int x;     // pas une expression (une instruction)
x = 4 + 5; // 4 + 5 est une expression
           // dont le résultat est affecté à 'x'
```

# Expressions et opérateurs (2/6)

## Opérateurs relationnels

Opérateurs testant la relation entre deux *expressions*:

  - `(a opérateur b)` retourne `1`{.C} si l'expression s'évalue à `true`{.C}, `0`{.C} si l'expression s'évalue à `false`{.C}.

| Opérateur | Syntaxe      | Résultat             |
|-----------|--------------|----------------------|
| `<`{.C}   | `a < b`{.C}  | 1 si a <  b; 0 sinon |
| `>`{.C}   | `a > b`{.C}  | 1 si a >  b; 0 sinon |
| `<=`{.C}  | `a <= b`{.C} | 1 si a <= b; 0 sinon |
| `>=`{.C}  | `a >= b`{.C} | 1 si a >= b; 0 sinon |
| `==`{.C}  | `a == b`{.C} | 1 si a == b; 0 sinon |
| `!=`{.C}  | `a != b`{.C} | 1 si a != b; 0 sinon |

# Expressions et opérateurs (3/6)

## Opérateurs logiques

| Opérateur | Syntaxe      | Signification        |
|-----------|--------------|----------------------|
| `&&`{.C}  | `a && b`{.C} | ET logique           |
| `||`{.C}  | `a || b`{.C} | OU logique           |
| `!`{.C}   | `!a`{.C}     | NON logique          |

# Quiz: opérateurs logiques

## [Quiz: opérateurs logiques](https://cyberlearn.hes-so.ch/mod/evoting/view.php?id=1033629)

<!-- TODO: Quiz -->
<!-- ```C
1 && 0 == 0
7 && 3 == 1
4 || 3 == 1
!34 == 0
!0 == 1

Soit n un unsigned char initialisé à 127:
!n == 0
``` -->

# Expressions et opérateurs (4/6)

## Opérateurs arithmétiques

| Opérateur | Syntaxe      | Signification        |
|-----------|--------------|----------------------|
| `+`{.C}   | `a + b`{.C}  | Addition             |
| `-`{.C}   | `a - b`{.C}  | Soustraction         |
| `*`{.C}   | `a * b`{.C}  | Multiplication       |
| `/`{.C}   | `a / b`{.C}  | Division             |
| `%`{.C}   | `a % b`{.C}  | Modulo               |

# Expressions et opérateurs (5/6)

## Opérateurs d'assignation

| Opérateur | Syntaxe      | Signification                               |
|-----------|--------------|---------------------------------------------|
| `=`{.C}   | `a = b`{.C}  | Affecte la valeur `b` à la variable `a`     |
|           |              | et retourne la valeur de `b`                |
| `+=`{.C}  | `a += b`{.C} | Additionne la valeur de `b` à `a` et        |
|           |              | assigne le résultat à `a`.                  |
| `-=`{.C}  | `a -= b`{.C} | Soustrait la valeur de `b` à `a` et         |
|           |              | assigne le résultat à `a`.                  |
| `*=`{.C}  | `a *= b`{.C} | Multiplie la valeur de `b` à `a` et         |
|           |              | assigne le résultat à `a`.                  |
| `/=`{.C}  | `a /= b`{.C} | Divise la valeur de `b` à `a` et            |
|           |              | assigne le résultat à `a`.                  |
| `%=`{.C}  | `a %= b`{.C} | Calcule le modulo la valeur de `b` à `a` et |
|           |              | assigne le résultat à `a`.                  |

# Expressions et opérateurs (6/6)

## Opérateurs d'assignation (suite)

| Opérateur | Syntaxe      | Signification                               |
|-----------|--------------|---------------------------------------------|
| `++`{.C}  | `++a`{.C}    | Incrémente la valeur de `a` de 1 et         |
|           |              | retourne le résultat (`a += 1`).            |
| `--`{.C}  | `--a`{.C}    | Décrémente la valeur de `a` de 1 et         |
|           |              | retourne le résultat (`a -= 1`).            |
| `++`{.C}  | `a++`{.C}    | Retourne `a`{.C} et incrémente `a` de 1.    |
| `--`{.C}  | `a--`{.C}    | Retourne `a`{.C} et décrémente `a` de 1.    |


# Structures de contrôle: `if`{.C} .. `else if`{.C} .. `else`{.C} (1/2)

## Syntaxe

```C
if (expression) {
    instructions;
} else if (expression) { // optionnel
                         // il peut y en avoir plusieurs
    instructions;
} else {
    instructions; // optionnel
}
```

```C
if (x) { // si x s'évalue à `vrai`
    printf("x s'évalue à vrai.\n");
} else if (y == 8) { // si y vaut 8
    printf("y vaut 8.\n");
} else {
    printf("Ni l'un ni l'autre.\n");
}
```

# Structures de contrôle: `if`{.C} .. `else if`{.C} .. `else`{.C} (2/2)

## Pièges

```C
int x, y;
x = y = 3;
if (x = 2)
    printf("x = 2 est vrai.\n");
else if (y < 8)
    printf("y < 8.\n");
else if (y == 3)
    printf("y vaut 3 mais cela ne sera jamais affiché.\n");
else
    printf("Ni l'un ni l'autre.\n");
    x = -1; // toujours évalué
```

# Quiz: `if ... else`{.C}

## [Quiz: `if ... else`{.C}](https://cyberlearn.hes-so.ch/mod/evoting/view.php?id=1033916)


# Structures de contrôle: `while`{.C}

## La boucle `while`{.C}

```C
while (condition) {
    instructions;
}
do {
    instructions;
} while (condition);
```

## La boucle `while`{.C}, un exemple

```C
int sum = 0; // syntaxe C99
while (sum < 10) {
    sum += 1;
}
do {
    sum += 10;
} while (sum < 100)
```

# Structures de contrôle: `for`{.C}

## La boucle `for`{.C}

```C
for (expression1; expression2; expression3) {
    instructions;
}
```

## La boucle `for`{.C}

```C
int sum = 0; // syntaxe C99
for (int i = 0; i < 10; i++) {
    sum += i;
}

for (int i = 0; i != 1; i = rand() % 4) { // ésotérique
    printf("C'est plus ésotérique.\n");
}
```
