Cours 1 - rappel

name: inverse
layout: true
class: center, middle, inverse
---

# INFORMATIQUE 3 - CM 1
## Inès de Courchelle
## 2024-2025

![image](../img/CY-tech.png)

---
layout: false
# Lets go
## Objectifs

- Faire un point sur toutes les notions vues l'année dernière
- Réaliser des rappel autour de la récursivité
- Partir sur de bonnes bases

---
# L'année dernière au S1
## Qu'est ce que l'on a vu ?
1. ADO
2. Représentation des données
3. Éléments de base
4. Fonctions et Procédures
5. Récursivité
6. Introduction UNIX
7. Le langage C
8. Les tableaux statiques
9. Types structurés

---
# L'année dernière au S2
## Qu'est ce que l'on a vu ?
1. Les pointeurs
2. Les tableaux dynamiques
3. La compilation séparée
4. La complexité
5. Tris lents
6. Tris rapides
7. Tableaux de structures
8. Les fichiers
9. Les tests
10. Le versionning

---
# TODAY
## Plan
1. Écrire un algo
2. Fonctions et procédures
3. La complexité
4. La récursivité
5. Le langage c
6. Les structures de données

---
# TODAY
## Plan
1. .under[Écrire un algo]
2. Fonctions et procédures
3. La complexité
4. La récursivité
5. Le langage c
6. Les structures de données

---
# Écrire un algo
## C'est quoi ?
- Une recette de cuisine
- Une suite d'instructions pour aller quelque part
- Des consignes de sécurité

## Comment ?
<img src="https://c.tenor.com/dsoNmYoIDUkAAAAC/gif-cerebro.gif" width=200>

---
# Écrire un algo
## Instructions
- Un programme impératif est une suite finie d'instructions comprise en le début et la fin
- L'instruction de base est l'écriture (sortie, affichage ...) d'informations dans le terminal
- Exemple de programme complet : HELLO WORLD

```
PROGRAMME Bonjour
DEBUT
    ECRIRE("bonjour tout le monde")
FIN
```

---
# Écrire un algo
## Variable
- C'est un élément du programme qui sert à stocker une valeur
- Est définie par un nom et un type
- Syntaxe :
```
nomVariable : type
```

## Type
- Un type définit un ensemble de valeurs sur lesquelles on peut appliquer des opérateurs
- Exemple : entier, réel, booléen, chaîne, caractère ...

---
# Écrire un algo
## Déclaration
```
VARIABLES :
 i,j : entiers
 x,y : réels
 estTrouvé : booleen
 reponse : chaine de caractères
```

## Affectation
- Une affectation est le fait de mettre une valeur dans une variable en cohérence avec son type
- La première affectation de valeur à une variable est appelée initialisation
- On la représente par une flèche

#### Exemple
```
i ← 4
reponse ← "Bonjour"
```
.underR[Attention] : Avant d'affecter une valeur il ne faut pas oublier de déclarer la variable

---
# Écrire un algo
## Les conditions
.pull-left[
#### SI ...ALORS
```
SI [CONDITION] ALORS
...
FIN SI
```

#### Si ... SINON SI...
```
SI [CONDITION] ALORS
...
SINON SI [CONDITION] ALORS
...
SINON
...
FIN SI
```
]
.pull-right[
#### SI ... SINON
```
SI [CONDITION] ALORS
...
SINON
...
FIN SI
```
#### SELON
```
SELON [VARIABLE]
    CAS [VALEUR]:
    CAS [VALEUR]:
    CAS [VALEUR]:
    DEFAUT:
FIN SELON
```
]
---
# Écrire un algo
## Une boucle
#### Pour
.pull-left[
Quand on sait combien de fois on veut réaliser une opération
]

.pull-right[
```
POUR i ALLANT de 0 à 10 FAIRE
...
FIN POUR
```
]

---
# Écrire un algo
## Une boucle
#### Tant que Faire ...
.pull-left[
Quand on doit répéter une opération en fonction tant qu'une condition est vérifiée
]

.pull-right[
```
TANT QUE [CONDITION EST VRAI] FAIRE
...
FIN TANT QUE
```

]

#### Faire ... Tant que
.pull-left[

Quand on doit répéter une opération en fonction tant qu'une condition est vérifiée
]

.pull-right[
```
FAIRE
...
TANT QUE [CONDITION EST VRAI]
```
]
---
# Écrire un algo
## La blagounette
<img src="img/lol.jpg" width=400>

---
# TODAY
## Plan
1. Écrire un algo
2. .under[Fonctions et procédures]
3. La complexité
4. La récursivité
5. Le langage c
6. Les structures de données

---
# Une fonction
## Définition
Une fonction est une série d'instructions regroupés sous un nom, qui permet d'effectuer des actions. Elle peut prendre entre 0 et N paramètres. Elle renvoie forcement une variable.

## En algo
```
FONCTION nomFonction(param1 : type, param2 : type) : type
VARIABLES
    ...
DEBUT
    ...
    retourner maVar;
FIN
```

.underR[Attention] : une fonction ne peut avoir qu'un seul "retourner" (à part en récursif où il peut il y en avoir plus de 2 !

---
# Une fonction
## Représentation

## Exemple
.pull-left[
<img src="img/templateAddition.png" width=400>
]
.pull-right[
<img src="img/addition.png" width=400>
]

---
# Une fonction
## L'algorithme de la fonction addition
<img src="img/algoAddition.png" width=400>

**Attention** Si le type de retour est un entier la variable retournée doit être un entier

---
# Une procédure
## Définition
Une procédure est une série d'instructions regroupés sous un nom, qui permet d'effectuer des actions. Elle peut prendre entre 0 et N paramètres.

## En algo
```
PROCEDURE nomProcedure(param1 : type, param2 : type)
VARIABLES
    ...
DEBUT
    ...
FIN
```

---
# Une procédure
## Représentation

## Exemple
.pull-left[
<img src="img/templateBonjour.png" width=300>
]
.pull-right[
<img src="img/bonjour.png" width=300>
]

---
# Une procédure
## L'algorithme de la procèdure bonjour
<img src="img/algoBonjour.png" width=600>

**Attention** Pas de valeur de retour !
---
# Procédure - Fonction
## OBLIGATOIRE
Pour chaque fonction et procédure, nous définirons :

- **Un résumé** : décrit en une phrase ce que fait la fonction
- **les préconditions** : décrit la nature de l'ensemble des contraintes sur tous les paramètres d'entrée, afin que la fonction puisse s'exécuter correctement
- **la post-condition** : décrit le résultat produit par la fonction/procédures et ses contraintes éventuelles

#### Où ?
En haut du programme

---
# Procédure - Fonction
## OBLIGATOIRE
#### addition

#### bonjour

---
# TODAY
## Plan
1. Écrire un algo
2. Fonctions et procédures
3. .under[La complexité]
4. La récursivité
5. Le langage c
6. Les structures de données

---
# La complexité
## Définition
.otro-blockquote[Étudier la quantité de ressource nécessaire à l'exécution d'un algorithme]
<center>
 <img src="img/lol.gif" width=250/>
</center>
.pull-left[
#### Mais pourquoi on fait ça ?
Pour trouver un bon algorithme
]
.pull-right[
#### Mais Comment ?
Avec du bon sens
]

---
# La complexité
## Objectifs
- Comparer et mesurer les performances d'algorithmes répondant à un même problème
- Réduire le temps d'exécution d'algorithme
- Utiliser au minimun la mémoire

.pull-left[
.under[Un bon algorithme doit : ]
- répondre à un problème posé
- être rapide
- consommer peu de ressource
]
.pull-right[
 
<center>
 <img src="img/lol2.jpg" width=200/>
</center>

]

.otro-blockquote[Vous savez, moi je ne crois pas qu'il y ait de bonne ou de mauvaise situation.]

---
# La complexité
## Problématique
- .under[complexité temporelle]
  - Réduire le temps d'exécution
  - Augmenter l'utilisation de la mémoire
- .under[complexité spatiale]
  - Réduire l'utilisation de la mémoire
  - Augmenter le temps d'exécution

.pull-left[
<center>
 <img src="img/complexite.svg" width=250/>
</center>
]

.pull-right[
<center>
 <img src="https://media.giphy.com/media/gF5xLnIVPTs62OfVTJ/giphy.gif" width=250/>
</center>
]

---
# La complexité
## Illustration
.pull-left[
#### Algo 1
```c
PROGRAMME ALGO1
VARIABLE
 a,b :reel
DEBUT
 a <- 40
 b <- puissance(a,2) * puissance(a,2)
FIN
```
]
.pull-right[
#### Algo 2
```c
PROGRAMME ALGO1
VARIABLE
 a,b,c :reel
DEBUT
 a <- 40
 c <- puissance(a,2)
 b <- c * c
FIN
```
]

#### Quel est le meilleur algorithme ?

---
# La réponse
## C'est le temps vs l'espace
.pull-left[
#### Algo 1
```c
PROGRAMME ALGO1
VARIABLE
 a,b :reel
DEBUT
 a <- 40
 b <- puissance(a,2) * puissance(a,2)
FIN
```
]
.pull-right[
#### Algo 2
```c
PROGRAMME ALGO1
VARIABLE
 a,b,c :reel
DEBUT
 a <- 40
 c <- puissance(a,2)
 b <- c * c
FIN
```
]

**Réponse**
**Algo 1**
- Il n'y a pas de variable intermédiaire, et le carré de a est calculé 2 fois
- Nous avons économisé de la mémoire mais pas du temps de calcul

##### Algo 2
- Il y a une variable intermédiaire, et le carré de a est calculé qu'une seule fois
- Nous avons économisé du temps de calcul mais pas de mémoire

---
# La complexité
## Les différents types de complexité
1. La complexité en nombre de comparaisons
2. La complexité en nombre d'opérations
3. La complexité en nombre d'affectations

---
# De manière générale
## Appel de fonctions
Si on regarde la complexité en terme d'appel de fonctions
.pull-left[
#### Exemple 1

\\[ 2N + 5 \\]
]
.pull-right[
 
La complexité est Ο(n);
]

.pull-left[
#### Exemple 2
\\[ N \over 2 \\]
]
.pull-right[
 
La complexité est Ο(n);
]

.pull-left[
#### Exemple 3
\\[ 2N^2 + 3N + 5 \\]
]
.pull-right[
 
La complexité est Ο(N²);
]
---
# Les classes
## Appelation
- Ο(1) : complexité constante
- Ο(n) : complexité linéaire
- Ο(n log n) : complexité quasi-linéaire
- Ο(n^a) complexité polynomiale
- Ο(e^n) : complexité exponentielle
- Ο(log n) : complexité logarithmique

- ...

## En pratique
- Les algorithmes à complexité quasi-linéaire et en dessous sont très efficaces
- Sur les données réduites, les algorithmes polynomiaux sont encore applicables
- Un algorithme à complexité exponentielle est inutilisable

---
# Les classes
## Représentation
<img src="img/classe_comp.png" width=450/>

---
# TODAY
## Plan
1. Écrire un algo
2. Fonctions et procédures
3. La complexité
4. .under[La récursivité]
5. Le langage c
6. Les structures de données

---
# La récursivité
## Définition
Algorithme permettant de résoudre un problème en calculant des solutions d'instances plus petites du même problème
## Principes
- Une fonction qui s'appelle elle même jusqu'à atteindre une condition d'arrêt
- Le résultat de chaque fonction enfant est retourné dans les fonctions parents, jusqu’à retourner à la fonction originale

## Pourquoi ?
- Pour gagner en temps d'execution
- Pour gagner en mémoire

---
# La récursivité
## Étapes
1. La condition d'arrêt
2. La résolution du problème
3. L'appel récursif

## Illustration
Afin d'illustrer la récursivité nous allons prendre l'exemple du compte à rebours.

---
# La récursivité
## Le compte à rebours
#### 1. La condition d'arrêt
Lorsque le compteur arrive à zéro
#### 2. La résolution du problème
compteur = compteur -1
#### 3. L'appel récursif
retourner le compteur

---
# La recursivité
## L'algo
```
FONCTION compteARebours (cpt : entier) : entier
DEBUT
 SI cpt=0 FAIRE
 retourner 0
 SINON
 ECRIRE(cpt)
 RETOURNER compteARebours(cpt-1)
 FIN
FIN
```
## Le code
```
int compteARebours (int cpt) {
 if (cpt==0)
 return 0;
 else {
 printf("%d \n",cpt);
 return compteARebours(cpt-1);
 }
}
```
---
# La recursivité
## La var
<center>
<video src="videos/car.mp4" width="400" height="300" controls poster="vignette.jpg">
Cette vidéo ne peut être affichée sur votre navigateur Internet. Une version est disponible en téléchargement sous <a href="URL">adresse du lien </a> .
</video>
</center>

---
# La récursivité
## Terminale
.otro-blockquote[Une fonction avec une récursivité terminale est une fonction où l'appel récursif est la dernière instruction à être évaluée. ]
## Non terminale
C'est l'inverse !

---
# La récursivité
## Terminale
```
FONCTION exempleT(n : entier) : entier
DEBUT
    SI condition d'arret FAIRE
        RETOURNER ...
    SINON
        RETOURNER exempleT(n-1)
FIN
```

## Non terminale
```
FONCTION exempleNonT(n : entier) : entier
DEBUT
    SI condition d'arret FAIRE
        RETOURNER ...
    SINON
        RETOURNER n+ exempleT(n-1)
FIN
```

---
# La récursivité
## Exemple : la factorielle
```
0! = 1
1! = 1
2! = 1 × 2 = 2
3! = 1 × 2 × 3 = 6
4! = 1 × 2 × 3 × 4 = 24
```

## Identifier
#### 1. La condition d'arrêt
#### 2. La résolution du problème
#### 3. L'appel récursif

---
# La récursivité
## La factorielle
#### En math
n!=n*(n-1)!
#### En gros !
 4! = 4 x 3! = 4 x (3 x 2!) = 4 x (3 x (2 x 1!)) = 4 x (3 x (2 x (1 x 0!)))
<img src="https://c.tenor.com/Cdl0FgZUZ6kAAAAd/doug-maclean-mac.gif" width="250">

---
# La récursivité
<img src="img/facto1.png" width="250">

---
# La récursivité
<img src="img/facto2.png" width="300">

---
# La récursivité
<img src="img/facto3.png" width="375">

---
# La récursivité
## La factorielle
```
FONCTION factorielle(n : entier) : entier
DEBUT
    SI n=0 ALORS
        RETOURNER 1
    SINON
        RETOURNER n * factorielle(n-1)
FIN
```
---
# La récursivité
## La factorielle

```
FONCTION factorielle(n : entier) : entier
DEBUT
 SI n=0 ALORS
 RETOURNER 1
 SINON
 RETOURNER n * factorielle(n-1)
FIN
```
<img src="img/factoEx1.png" width="450">

---
# La récursivité
## La factorielle

```
FONCTION factorielle(n : entier) : entier
DEBUT
 SI n=0 ALORS
 RETOURNER 1
 SINON
 RETOURNER n * factorielle(n-1)
FIN
```
<img src="img/factoEx2.png" width="400">

---
# La récursivité
## La factorielle

```
FONCTION factorielle(n : entier) : entier
DEBUT
 SI n=0 ALORS
 RETOURNER 1
 SINON
 RETOURNER n * factorielle(n-1)
FIN
```
<img src="img/factoEx3.png" width="330">

---
# La récursivité
## La factorielle

```
FONCTION factorielle(n : entier) : entier
DEBUT
 SI n=0 ALORS
 RETOURNER 1
 SINON
 RETOURNER n * factorielle(n-1)
FIN
```
<img src="img/factoEx4.png" width="300">

---
# La récursivité
## La factorielle

```
FONCTION factorielle(n : entier) : entier
DEBUT
 SI n=0 ALORS
 RETOURNER 1
 SINON
 RETOURNER n * factorielle(n-1)
FIN
```
<img src="img/factoEx5.png" width="300">

---
# La récursivité
## La factorielle

```
FONCTION factorielle(n : entier) : entier
DEBUT
 SI n=0 ALORS
 RETOURNER 1
 SINON
 RETOURNER n * factorielle(n-1)
FIN
```
<img src="img/factoEx6.png" width="300">

---
# La récursivité
## La factorielle en terminal
Est ce possible ?

## Comment ?
- Avec un accumulateur
- Stocker les résultats intermédiaires

---
# La récursivité
## La factorielle en terminal
```
FONCTION factorielleTerminale(n : entier, acc : entier) : entier
DEBUT
    SI n=0 ALORS
        RETOURNER acc
    SINON
        RETOURNER factorielleTerminale(n-1,acc*n)
FIN
```

## La factorielle en non terminal
```
FONCTION factorielle(n : entier) : entier
DEBUT
    SI n=0 ALORS
        RETOURNER 1
    SINON
        RETOURNER n * factorielle(n-1)
FIN
```

NONNNNNNNNNNNNNNNN

## POURQUOI ?
Lorsqu'on appel la fonction la première fois
```
factorielleTerminale(4,1)
factorielleTerminale(5,1)
```
.underR[Ce n'est pas beau !!!]

---
# La récursivité
## MOCHE
Lorsqu'on appel la fonction la première fois
```
factorielleTerminale(4,1)
factorielleTerminale(5,1)
```
## JOLI
Lorsqu'on appel la fonction la première fois
```
factorielleTerminale(4)
factorielleTerminale(5)
```

---
# La récursivité
## JOLI
Lorsqu'on appel la fonction la première fois
```
factorielleTerminale(4)
factorielleTerminale(5)
```
## COMMENT ?
- Avec une fonction intermédiaire
- Il en faudra deux !

---
# La récursivité
## La même d'avant
```c
FONCTION factorielleTerminaleCache(n : entier, acc : entier) : entier
DEBUT
    SI n=0 ALORS
        RETOURNER acc
    SINON
        RETOURNER factorielleTerminaleCache(n-1,acc*n)
FIN
```

## C'est que l'utilisateur appelera
```c
FONCTION factorielleTerminale(n : entier) : entier
DEBUT
    RETOURNER factorielleTerminaleCache(n,1)
FIN
```

## L'appel
```
factorielleTerminale(4)
factorielleTerminale(5)
```
---
# La récursivité
## Les problèmes de performance
Parfois, on se retrouve avec des appels récursifs exponentiels

## Le classique
FIBONACCI

---
# La récursivité
## Fibonacci non terminal
<img src="img/lapin.png" width=400>

## Fibonacci

\\[ F(n) = F(n-1) + F(n-2) \\]

---
# La récursivité
## Fibonacci
.pull-left[
| F  | res |
| -- | --- |
| 0  | 0   |
| 1  | 1   |
| 2  | 1   |
| 3  | 2   |
| 4  | 3   |
| 5  | 5   |
| 6  | 8   |
| 7  | 13  |
| 8  | 21  |
| 9  | 34  |
| 10 | 55  |
| 11 | 89  |
]

.pull-right[
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/3/35/Fibonacci2.jpg/220px-Fibonacci2.jpg" width=200>
]

---
# La récursivité
## Fibonacci non terminal
```c
FONCTION FiboNonT(n : entier ) : entier
DEBUT
 SI (n < 2) ALORS
 RETOURNER 1
 SINON
 RETOURNER FiboNonT(n - 1) + FiboNonT(n - 2)
 FIN SI
FIN
```

## Le problème !
- Un arbre récursif trop important !
- On recalcule des choses qui ont déjà été calculées

---
# La récursivité
## Fibonacci non terminal
<img src="img/lapin.png" width=400>

---
# La récursivité
## VAR
<center>
<video src="videos/fibont.mp4" width="400" height="300" controls poster="vignette.jpg">
Cette vidéo ne peut être affichée sur votre navigateur Internet. Une version est disponible en téléchargement sous <a href="URL">adresse du lien </a> .
</video>
</center>

#### Mais comment faire ?
- Récursivité terminal
- Calculer la suite petit à petit !

---
# La récursivité
## Fibonacci en terminal
```
FONCTION FiboT(n : entier, acc1 : entier, acc2 : entier) : entier
DEBUT
    SI (n = 0) ALORS
        RETOURNER acc2
    SINON
        RETOURNER FiboT(n - 1, acc1, acc1+acc2)
    FIN SI
FIN
```