Algorithmique
et structure de données
Abir MHENNI
Dr. Ing. en Informatique
[email protected]
Filière : 1ère année Licence IOT
2023-2024 1
2
Objectifs
• Analyser un problème donné
• Définir l’algorithme traduisant la solution du problème d’une manière rigoureuse
• Optimiser l’algorithme et le traduire en utilisant un langage de programmation
quelconque
3
Contenu
1. Introduction à l'algorithmique
2. Environnement algorithmique
3. Structures conditionnelles
4. Structures itératives
5. Sous programmes
6. Tableaux
7. Algorithmes de recherche (recherche par dichotomie)
8. Algorithmes de tri : par sélection, par insertion, à bulle, quick sort, etc.
9. Récursivité
10. Notion de pointeur
11. Enregistrements
12. Listes chainées
Chapitre 1
Introduction à l’algorithmique
4
5
POURQUOI UN COURS D’ "ALGO" ?
• Pour obtenir une «machine» qui effectue un travail à notre place
• Problème: expliquer à la «machine» comment elle doit s'y prendre
• Besoins :
• savoir expliciter son raisonnement
• savoir formaliser son raisonnement
• concevoir (et écrire) des algorithmes:
• séquence d’instructions qui décrit comment résoudre un problème
particulier
6
CONCEPTS IMPORTANTS
• Algorithme : mot dérivé du nom du mathématicien al_Khwarizmi qui a
vécu au 9ème siécle, était membre d’une académie des sciences à Bagdad .
• Un algorithme prend des données en entrée, exprime un traitement
particulier et fournit des données en sortie.
• Programme : série d’instructions pouvant s’exécuter en séquence, ou en
parallèle (parallélisme matériel) qui réalise (implémente) un algorithme
7
ALGORITHME
• Savoir expliquer comment faire un travail sans la moindre ambiguïté
• Langage simple : composé des instructions
Suite finie d'actions à entreprendre en respectant une chronologie imposée
• L’écriture algorithmique : un travail de programmation à visée universelle :
• un algorithme ne dépend pas du langage dans lequel il est implanté,
• ni de la machine qui exécutera le programme correspondant.
8
EXEMPLES D’ALGORITHMES
• Recette de cuisine
• Notice de montage de meuble en kit
• Mathématiques : problème :
• si n est pair, on le divise par 2 ;
• si n est impair, on le multiplie par 3 et on ajoute 1.
EXEMPLES
D’ALGORITHMES
9
10
LES PROBLÈMES FONDAMENTAUX
• Complexité
• En combien de temps un algorithme va -t-il atteindre le résultat escompté?
• De quel espace a-t-il besoin?
• Calculabilité
• Existe-t-il des tâches pour lesquelles il n'existe aucun algorithme ?
• Etant donnée une tâche, peut-on dire s'il existe un algorithme qui la résoudre ?
• Correction
• Peut-on être sûr qu'un algorithme réponde au problème pour lequel il a été
conçu ?
11
Etapes de résolution d’un problème
• Pour résoudre un problème en informatique, il faut passer par 5 étapes :
▪ Définition et analyse du problème
▪ Ecriture de l’algorithme
▪ Programmation
‐
▪ Compilation du programme
▪ Exécution et test du programme
12
Etapes de résolution d’un problème
• Définition et analyse du problème
• Il s’agit de :
• Définir les données qu’on dispose et les objectifs qu’on souhaite atteindre
• Prévoir des réponses à tous les cas envisageables
• Exemple : Si le problème est la résolution d’une équation de second degré
ax2+bx+c =0
→ Les données sont : a, b et c
→ Les sorties sont : x1 et x2
→ Les cas sont : a=0 et b≠0, a =0 et b =0, a ≠0 ……
13
Etapes de résolution d’un problème
• Ecriture de l’algorithme
• C’est la phase la plus difficile et importante, elle fournit la méthode et la
démarche que l’ordinateur va suivre pour résoudre le problème posé.
• Définition d’un algorithme :
• Un algorithme est une séquence d’étapes de calcul qui utilise des données en
entrée pour arriver à des résultats en sortie.
• Programmation de l’algorithme
• Il s’agit d’exprimer l’algorithme dans un langage connu par l’ordinateur. Il faut
donc choisir un langage de programmation et ensuite traduire l’algorithme sous
forme d’un programme exprimé dans ce langage.
14
Etapes de résolution d’un problème
• Compilation
• Il s’agit de traduire le programme écrit dans un langage de haut niveau en un
programme exécutable écrit dans un langage binaire de bas niveau tout en
détectant les éventuelles erreurs. Cette tâche est réalisée par le compilateur.
• Exécution et test du programme
• Il s’agit de s’assurer que le programme donne un résultat correct dans tous les cas
et pour toutes les éventualités.
→ Effectuer plusieurs jeux de tests correspondant aux différents cas et vérifier la
validité des résultats.
15
Structure générale d’un algorithme
Schéma général d’un algorithme
• Un algorithme comporte généralement deux parties :
‐ Partie déclarative : elle contient l’entête, la déclaration des constantes et celle des
variables.
‐ Partie corps de l’algorithme : elle consiste en une séquence d’actions faisant appel
à des opérations de base de l’ordinateur.
16
Structure générale d’un algorithme
• Syntaxe :
17
Structure générale d’un algorithme
• Une action peut être :
→ Action d’affectation,
→ Action d’entrée- sortie,
→ Action de contrôle conditionnelle simple ou à choix multiple,
→ Action de répétition.
18
Structure générale d’un algorithme
• Il faut avoir une écriture rigoureuse
• Il faut avoir une écriture soignée : respecter l’indentation
• Il est nécessaire de commenter les algorithmes
• Il existe plusieurs solutions algorithmiques à un problème posé
• Il faut rechercher l’efficacité de ce que l’on écrit
19
EXEMPLE DE LANGAGE ALGORITHMIQUE
20
EXEMPLE D’ÉNONCÉ D’UN PROBLÈME
• On souhaite calculer et afficher , à partir d’un prix hors taxe saisi, le montant de la
TVA ainsi que le prix TTC
TTC = HT * (1 + TVA/100)
• Le montant TTC dépend de :
• Du prix HT
• Du taux de TVA de 20,6
To be Continued …
21
