République Algérienne Démocratique et Populaire
Université des Sciences et de la Technologie Houari Boumediene
Faculté d’Informatique
Cours Algorithmique et Structures de Données (L2 Informatique )
Présenté par : Dr. B. BESSAA
Définition d’un Algorithme
Un algorithme est un ensemble de règles opératoires dont
l’application permet de résoudre un problème énoncé au moyen
d’un nombre fini d’opérations (Encyclopédie LAROUSSE).
Un algorithme est une procédure de calcul bien définie qui prend en
entrée une valeur, ou un ensemble de valeurs et donne en sortie
une valeur, ou un ensemble de valeurs. Un algorithme est donc une
séquence d’étapes de calcul qui transforment l’entrée en sortie
(Cormen, Leiserson, Rivert).
Un algorithme est un ensemble d'opérations de calcul élémentaires,
organisé selon des règles précises dans le but de résoudre un
problème donné. Pour chaque donnée du problème, il retourne une
réponse après un nombre fini d'opérations. (Beauquier, Berstel,
Chrétienne)
Un algorithme est une suite finie et non ambiguë d’opérations ou
d'instructions permettant de résoudre une classe de problèmes
2
Propriétés d’un Algorithme
1- Validité : la validité d’un algorithme est son aptitude à réaliser
exactement la tâche pour laquelle il a été conçu.
2- Robustesse : la robustesse d’un algorithme est son aptitude à se
protéger de conditions anormales d’utilisation (prise en compte des
différentes instances, cas particuliers…)
3- Réutilisabilité : la réutilisabilité d’un algorithme est son aptitude
à être réutilisé pour résoudre des tâches équivalentes à celle pour
laquelle il a été conçu.
4- Complexité : la complexité d'un algorithme est la quantité de
ressources nécessaires pour traiter des entrées. Les principales
ressources mesurées sont le temps (nombre d'instructions utilisées)
et l'espace (quantité d'espace mémoire nécessaire).
3
Algorithmique et Structures de Données
Algorithmique
L’algorithmique est la science des algorithmes. L’algorithmique
s’intéresse à l’art de construire des algorithmes ainsi qu’à caractériser
leur validité, leur robustesse, leur réutilisabilité, leur complexité et
leur efficacité.
L’algorithmique permet ainsi de passer d’un problème à résoudre à
un algorithme qui décrit la démarche de résolution du problème.
Démarche de résolution d’un problème
Analyse du problème : qu’est ce qu’on veut faire ?
Définir les données : leurs caractéristiques, leurs types.
Définir les résultats : leurs caractéristiques, leurs types.
Définir les relations entre résultats-données : comment passer des
données aux résultats ?
4
Structures de Données
une structure de données est une manière d'organiser
les données pour les traiter plus facilement. Une structure de
données est une mise en œuvre concrète d'un type abstrait.
Structure générale d’un algorithme
Partie Entête Algorithme <nomAlgo> ;
Const <IdObj> = <ValeurObj> ;
Partie Déclaration Type <IdObj> = <idType> ;
Var <IdObj> : <TypeObj> ;
Debut
<Action1> ;
Partie Action <Action2> ;
---
<ActionN> ;
Fin. 5
Les Actions
L’affectation :
<IdObj> ← <Expression> ;
Les Structures de Contrôle:
Les Structures Alternatives (conditionnelles):
Si <Condition> Alors <Bloc Action> Fsi;
Si <Condition> Alors <Bloc Action1> Sinon <Bloc Action2> Fsi;
Cas <Expression> Vaut
<Val1> : <Bloc Action1>;
<Val2> : <Bloc Action2>;
---
<ValN> : <Bloc ActionN>;
Sinon <Bloc ActionAutres> ;
FinCas;
6
Les Structures Itératives (boucles):
Tantque <Condition> Faire <Bloc Action> Fait;
Repeter <Bloc Action> Jusqu’a <Condition> ;
Pour <IdCompt> ← <Val1> à <Val2> Faire <Bloc Action> Fait;
Pour <IdCompt> de <Val1> à <Val2> Faire <Bloc Action> Fait;
Les Actions Paramétrées:
Les Fonctions:
Fonction <nomFonction> (<paramètres formels>) : <TypeResultat>;
Var <Déclaration de variables locales> ;
Debut
<Bloc Action> ;
<NomFonction> ← <Expression> ;
Fin;
7
Fonction <nomFonction> (<paramètres formels>) : <TypeResultat>;
Var <Déclaration de variables locales>;
Debut
<Bloc Action> ;
retourner <Expression> ;
Fin;
Les Procédures:
Procedure <nomProcedure> (<paramètres formels>) ;
Var <Déclaration de variables locales> ;
Debut
<Bloc Action> ;
Fin;
Appel :
<nomFonction> (<paramètres Effectifs>) se comporte : Variable
<nomProcedure> (<paramètres Effectifs>) se comporte : Action
8
Passage de paramètres :
Passage par valeur (Entrée): dans ce cas l’action paramétrée
manipule des copies des données passées comme paramètres. Une
fois terminée, les valeurs originales ne changent pas.
Les paramètres effectifs sont traités comme des variables locales.
Passage par adresse (Entrée/Sortie): Dans ce cas, l’action paramétrée
accède aux données originales. Toute modification apportée aux
paramètres affecte les variables originales. Ces modifications sont
appelées effets de bord.
Les paramètres effectifs sont traités comme des variables globales.
Structures de Données
Types de base (Simples): Entier, Reel, Caractère, Booleen
Tableau: regroupement de variables de même type.
Enregistrement: regroupement de variables de différents types.
Fichier: Support mémoire externe
Liste : Allocation dynamique de la mémoire
9
Programme
1- Analyse des Algorithmes (Etude de la complexité)
2- Allocation Dynamique et Listes Chainées (LLSC, LLDC, LLCC)
3- Les Pile et Les Files
4- La Récursivité
5- Les Arbres
6- Les Tables de Hachage
Algorithmique et Structures de Données
1 - 4 2 - 3 -5-6
10
Bibliographie
Brigitte Chauvin, Julien Clément, Danièle Gardy.
« Arbres pour l’algorithmique. » hal-01708981v3
([Link]
01708981/document)
Pierre Boudes. « Algorithmique et arbres »,
creative common 2011
([Link]
gorithmique_et_arbres.pdf)
Michel Divay. « Algorithmes et structures de
données génériques : Cours et exercices corrigés
en langage C » Ed. DUNOD 2eme édition 2004.
T.H. Cormen, C. Leiserson, R. Rivest, C.
Stein. « Introduction à l’algorithmique : Cours et
Exercices » Ed. DUNOD 2eme Edition 2004.
Brahim BESSAA « Algorithmique et Structures de
Données: Rappels de Cours, Exercices Corrigés et
Programmes en C » Ed. Pages Bleues 2020.
11
brbessaa@[Link]
Cours (L1 + L2)
[Link]
12