Informatique 2
Pr. Yassir MATRANE (yassermatrane@[Link])
Département génie Informatique
2025-2026
Informatique 2
1. Rappel
2. Notion de complexité des algorithmes
3. Programmation avancée et Maîtrise de la Mémoire
4. Structures de Données Essentielles pour la Performance
5. Fichiers, Sérialisation et Persistance des Données
2025-2026
Objectifs du cours
▪ Représentation en mémoire des structures de données de base:
▪ Structures linéaires (tableaux, listes, piles, files);
▪ Structures arborescentes (arbres binaires);
▪ Tables de hachage ;
▪ Graphes.
▪ Etude de la pluspart des algorithmes qui permettent de manipuler ces structures.
2025-2026
Rappels
▪ La programmation consiste à écrire un ensemble d’instructions dans un ordre bien défini, avec un
langage compréhensible par l’ordinateur, qui une fois exécuté sur un ensemble de données aboutit à la
résolution automatique d’un problème.
▪ L’élaboration d’un programme passe généralement par les étapes suivantes :
2025-2026
Introduction
▪ Un algorithme est une séquence d’opérations visant à la résolution d’un problème en un temps fini. La
conception d’un algorithme se fait par étapes de plus en plus détaillées.
▪ La traduction de l’algorithme en un langage informatique et on obtient un programme qui est défini
comme une suite d’instructions permettant de réaliser une ou plusieurs taches, de résoudre un
problème, de manipuler des données.
▪ Le langage de base compréhensible par un ordinateur, appelé langage machine est constitué d’une suite
de 0 et de 1.
▪ Plusieurs langages de programmation : structurelle (C, Pascal, …), fonctionnelle (Lisp,…), logique
(Prolog, …), scientifique (Maple, Matlab,…), objet (C++, Java, …)
2025-2026
Introduction
Caractéristiques du langage C
▪ C est universel : permet aussi bien la programmation système que la programmation de divers
applications (scientifique, …)
▪ C est prés de la machine : offre des opérateurs qui sont très proches de ceux du langage machine…
▪ C est de haut niveau : C est un langage structuré, typé, modulaire et compilé
▪ C est portable : en respectant le standard ANSI-C, il est possible d’utiliser le même programme source
sur d’autres compilateurs.
2025-2026
Introduction
Composantes du langage C
▪ Fonctions : composée d’une ligne déclarative et un bloc d’instructions
▪ Fonction main() : fonction principale et obligatoire des programmes en C ;
▪ Variables : spécifiés par des identificateurs et contenant les valeurs nécessaires pour l’exécution. Ils
doivent être déclarés avant leurs appels
▪ Identificateurs : Les noms des fonctions et des variables en C sont composés d'une suite de lettres et
de chiffres, plus le caractère souligné ( _ ). Commençant par une lettre
▪ Commentaires: programme plus compréhensible, \\ ou \* …*\
2025-2026
Types de Variables
Types de Base
Type Taille (octets) Plage de valeurs Format printf
char 1 -128 à 127 %c ou %d
unsigned char 1 0 à 255 %u
short 2 -32,768 à 32,767 %hd
-2,147,483,648 à
int 4 %d
2,147,483,647
unsigned int 4 0 à 4,294,967,295 %u
long 4 ou 8 Dépend du système %ld
float 4 ~6-7 chiffres significatifs %f
double 8 ~15-16 chiffres significatifs %lf
2025-2026
Types de Variables
Exemple
2025-2026
Conversion de Types (Cast)
▪ Les variables et les constantes sont les données principales manipulées par un programme.
2025-2026
Opérations Arithmétiques et Logiques
▪ Opérateurs Arithmétiques
2025-2026
Opérations Arithmétiques et Logiques
▪ Opérateurs Arithmétiques
int a = 5, b, c;
b = a++; // b = 5, puis a = 6 (post-incrémentation)
c = ++a; // a = 7, puis c = 7 (pré-incrémentation)
2025-2026
Opérations Arithmétiques et Logiques
▪ Opérateurs de Comparaison
2025-2026
Opérations Arithmétiques et Logiques
▪ Opérateurs Logiques
2025-2026
Opérations Arithmétiques et Logiques
▪ Opérateurs Bit à Bit
2025-2026
Portée des Variables
▪ Variables Locales
▪ Les variables locales sont déclarées à l'intérieur
d'une fonction ou d'un bloc {}.
▪ Caractéristiques :
✔ Créées à l'entrée du bloc
✔ Détruites à la sortie du bloc
✔ Stockées dans la pile (stack)
✔ Non initialisées par défaut (contiennent des
valeurs aléatoires)
2025-2026
Portée des Variables
▪ Variables Globales
▪ Les variables globales sont déclarées en dehors de
toute fonction.
▪ Caractéristiques :
✔ Accessibles partout dans le fichier (et autres
fichiers avec extern)
✔ Durée de vie = durée du programme
✔ Stockées dans le segment de données
✔ Initialisées à 0 par défaut si non initialisées
2025-2026
Portée des Variables
▪ Variables Static
▪ Static dans une fonction (variable locale
persistante)
▪ Caractéristiques :
✔ Durée de vie = durée du programme
✔ Portée limitée au bloc ou au fichier
✔ Initialisée une seule fois
✔ Garde sa valeur entre les appels
2025-2026
Portée des Variables
▪ Variables Const
const double PI = 3.141592653589793;
const int MAX_SIZE = 100;
// PI = 3.14; // ERREUR DE COMPILATION ! Modification interdite
// Pointeur constant vs donnée constante
const int *ptr1; // Pointeur vers un entier constant
int const *ptr2; // Idem (synonyme)
int *const ptr3 = NULL; // Pointeur constant vers un entier
const int *const ptr4 = NULL; // Pointeur constant vers un entier constant
2025-2026
Fonctions et Passage de Paramètres
▪ Déclaration et Prototype
▪ Une fonction est définie par un entête et un corps contenant les instructions à exécuter
2025-2026
Fonctions et Passage de Paramètres
▪ Passage par Valeur
▪ Dans le passage par valeur, la fonction reçoit une copie des arguments.
2025-2026
Fonctions et Passage de Paramètres
▪ Passage par Adresse (Pointeur)
▪ Le passage par adresse permet de modifier la variable d'origine.
2025-2026
Fonctions et Passage de Paramètres
▪ Exemple
2025-2026
Fonctions et Passage de Paramètres
▪ Exemple
2025-2026
Les tableaux
▪ Une structure de données est une structure logique destinée à stocker et à organiser un ensemble de
deux ou plusieurs données dans la mémoire de l’ordinateur pour former un type de variables que l’on
peut utiliser dans un programme et traiter à volonté.
▪ Les donnée d’une structure peuvent être de différents types: entiers, réels, caractères,…
Exemple: les tableaux
2 5 0 …
Indice: 0 Indice: 1 Indice: 2
Adresse: 2024 Adresse: 2025 Adresse: 2026
Donnée: 2 Donnée:5 Donnée: 0
2025-2026
Les tableaux
▪ Déclaration des tableaux Type Nom_tableau[Nombre_elements];
▪ type définit le type d'élément que contient le tableau, c'est-à-dire qu'il définit la taille d'une case du
tableau en mémoire.
✔ Lorsque le tableau est composé de données de type simple, on parle de tableau monodimensionnel (ou vecteur)
✔ Lorsque le tableau est composé de données qui sont eux aussi de type tableaux, on parle alors de tableaux
multidimensionnels (matrice ou table)
▪ Nom_tableau est le nom que l'on décide de donner au tableau, le nom du tableau suit les mêmes règles
qu'un nom de variable.
▪ Nombre_elements est un nombre entier qui détermine le nombre de cases que le tableau doit
comporter.
Exemple: int t[n]; /* la valeur n doit être fixée avant la déclaration de t */
Cette instruction demande au microprocesseur de réserver une zone mémoire suffisante pour2025-2026
stocker n nombres entier :
▪ Lecture et affichage des tableaux
Les tableaux
Lecture d'un tableau d'entiers Affichage d’un tableau
Void lecture(int t[],int n) Void affichage(int t[],int n)
{ {
int i; int i;
for (i=0; i<n; i++){ for (i=0; i<n; i++)
printf("t[%d]=",i); printf("%d\t",t[i]);
scanf("%d",&t[i]); printf("\n");
}
}
} Exécution de la fonction main()
Appel des procédures lecture et affichage t[0]=8
main(){ t[1]=3
int n=4, t[n]; t[2]=0
lecture(t,n); t[3]=9
affichage(t,n); 8 3 0 9
} |
2025-2026
Les tableaux
▪ Les tableaux n'ont pas de primitives officiellement décrites. Par l'accès direct aux éléments du
tableau, la plupart des primitives usuelles sont grandement simplifiées. Nous ne présenterons donc ici
que 6 fonctions utiles:
✔ echanger(): échange la position de deux élément
✔ suppression(): supprime un élément du tableau (en redimensionnant le tableau).
✔ insertion(): ajoute un élément dans le tableau (en redimensionnant le tableau).
✔ minimum(): renvoie le plus petit élément du tableau
✔ maximum(): renvoie le plus grand élément du tableau
✔ rechercher(): renvoie l'index de l'élément cherché dans le tableau
2025-2026
▪ Fonction echanger()
Les tableaux
▪ Fonction insertion()
void echanger(int t[], int i, int j) void insertion(int t[], int n, int x, int indice){
{ int i=n-1;
int tmp; do
tmp = t[i]; t[i+1]=t[i];
t[i] = t[j]; i--;
t[j] = tmp; while (i>=indice);
} t[indice]=x;}
▪ Fonction suppression() ▪ Fonction maximum()
void suppression(int t[], int n, int int maximum(int tab[], int i_min, int i_max){
indice){ /* on considère que le plus grand élément est le
int i; premier */
/* décalage des élément à droite int indice_max=i_min;
d'indice vers la gauche */ /* on compare les éléments du tableau à l'élément
for(i=indice; i<n-1; i++); d'indice_max
t[i]=t[i+1];} for(i=i_min; i<=i_max; i++)
if(t[i] > t[indice_max])
indice_max = i;
return indice_max;
} 2025-2026
Algorithmes récursifs
Un algorithme est dit récursif lorsqu'il s'appelle lui même de façon directe ou indirecte.
▪ Tout algorithme récursif doit distinguer plusieurs cas dont l’un au moins ne doit pas comporter l’appel
récursif.
✔ Ce cas est appelé cas de base ou cas de terminaison.
✔ L’oubli de ce cas peut causer un calcul infini (divergence du programme).
▪ Le cas de base doit figurer de préférence au début de l’algorithme.
▪ Il est préférable d’écrire mathématiquement l’algorithme sous forme d’une équation de
récurrence avant de le traduire en pseudo-code.
2025-2026
Paradigme «diviser pour régner»
▪ Ce sont des algorithmes qui résolvent un problème donné par appelle d’eux-mêmes récursivement une
ou plusieurs fois sur des sous-problèmes très similaires, mais de tailles moindres et se basent sur trois
étapes à chaque niveau de récursivité :
✔ Diviser: le problème en un certain nombre de sous-problèmes ;
✔ Régner: sur les sous-problèmes en les résolvant récursivement ou, si la taille d’un sous-problème
est assez réduite, le résoudre directement ;
✔ Combiner: les solutions des sous-problèmes en une solution complète du problème initial.
2025-2026
Récursivité simple ou linéaire
▪ Un algorithme est de récursivité simple s’il s’appel lui-même au plus une seul fois.
▪ Exemple: Algorithme qui calcule: n!
▪ Ecriture mathématique:
si n = 0 ou n = 1
⎧1
n! = ⎨ si n > 0
⎩n(n - 1)!
▪ Ecriture informatique:
si n == 0 ou n ==
⎧1
factoriel( n ) = ⎨ 1 si n >= 0
⎩n* factoriel(n - 1)
2025-2026
Récursivité simple
Exécution: pour n=4
unsigned long factoriel(int n) factoriel(4)=4*factoriel(3)=4*6=2
{
if (n < 0) 4
exit(EXIT_FAILURE); descente
if (n == 1 || n ==
0) return 1;
factoriel(3)=3*factoriel(2)=3*2=6
factoriel(2)=2*factoriel(1)=2*1=
else
2
return n*factoriel(n-1); montée
} factoriel(1)=
1
▪ Les appels des fonctions récursives sont en fait empilées dans une pile qui est une structure de donnée
régie selon le mode LIFO: Last In First Out, Dernier Entré Premier Sorti. Chaque appel se trouve donc
l'un à la suite de l'autre dans la pile du programme. Une fonction de ce type possède donc deux
parcours: la phase de descente et la phase de remontée.
2025-2026
Récursivité multiple
▪ Un algorithme est de récursivité multiple s’il fait plusieurs appels de lui-même.
▪ Exemple: Equation de récurrence
▪ Ecriture mathématique:
▪ Ecriture informatique:
2025-2026
Récursivité multiple
Exécution: pour n=3
unsigned long u(int n) u(3)=u(1)+2*u(2)=1+2*3=7
{
if (n == 0) descente
return 0;
if (n == 1)
u(1)=1 u(2)=u(o)+2*u(1)=1+2*1=3
return 1;
else
return u(n-2)+2*u(n-1); montée
u(1)=1
} U(0)=1
▪ Les appels des fonctions récursives sont en fait empilées dans une pile qui est une structure de donnée
régie selon le mode LIFO: Last In First Out, Dernier Entré Premier Sorti. Chaque appel se trouve donc
l'un à la suite de l'autre dans la pile du programme. Une fonction de ce type possède donc deux
parcours: la phase de descente et la phase de remontée
2025-2026
Récursivité croisée
▪ Deux algorithmes sont mutuellement croisé si l’un fait appel à l’autre et vice versa.
▪ Exemple: teste de parité d’un entier n
▪ Ecriture informatique:
2025-2026
Récursivité croisée
char paire(int n) char impaire(int n)
{ {
if (n == 0) if (n == 0)
return ‘V’; return ‘F’;
else else
return impaire(n-1); return paire(n-1);
} }
Exécution: pour n=4
Paire(4) impaire(3) paire(2) impaire(1) paire(0) V
2025-2026
Récursivité terminale
▪ L’algorithme renvoie directement la valeur obtenue par l'appel récursif courant, sans qu'il n'y ait
d'autres opérations à faire, ce qui n'est pas le cas dans le cas d’algorithme à récursivité simple, où l'on
multiplie n par le retour de la fonction.
▪ Les appels de la fonction n’ont pas besoin d'êtres empilés car l'appel suivant remplace simplement
l'appel précédent dans le contexte d'exécution.
unsigned long fac_ter(int n, int result)
{
if (n<0)
exit(EXIT_FAILURE);;
if (n ==0||n== 1)
return result;
else
return fac_ter(n-1,n*result);
}
Exécution: pour n=4
Fac_ter(4,1) → fac_ter(3,4) → fac_ter(2,12) → fac_ter(1,24) → 24
2025-2026
Dangers et précautions de la récursivité
Les fonctions récursives étant un moyen assez puissant pour résoudre certains problèmes de façon
élégante, mais il faut les utiliser avec prudence.
▪ Dépassement de capacité
C'est un phénomène qui se produit lorsque vous essayez de stocker un nombre plus grand que la
capacité de stockage de la variable d’affectation. Il faut donc utiliser un type variable pouvant contenir
la plus grande valeur possible du calcul considéré.
▪ Débordement de pile (Stack Overflow)
Les appels récursifs de fonctions sont placés dans la pile de l’ordinateur qui a une taille assez limité car
elle est fixée une fois pour toutes lors de la compilation du programme.
Dans la pile sont non seulement stockés variables des fonctions mais aussi leurs adresses. Si les appels
sont récursifs sont nombreux, un débordement de la pile peut très vite arriver ce qui provoque
sans conteste une sortie anormale ou un plantage du programme.
2025-2026