27/10/2024

3.1 - Introduction
Matériel / Logiciel
• Domaine du logiciel (software)
Chapitre 3 : Algorithmique • instructions expliquant à l’ordinateur comment traiter un problème
• algorithmes et représentation informatique de ces instructions
• programme

1 2

3.1 - Introduction 3.2 - Algorithmes et programmes

• Notion précise d’algorithme a été découverte en 825
• Les programmeurs sont amenés à concevoir des logiciels de plus en par le mathématicien arabe Muhammmad ibn Musa
plus complexes pour répondre aux besoins des utilisateurs al-Khawarezmi
(applications en réseau, base de données réparties, …)
• Moyen d’automatisation et d’économie de la pensée
•  maîtriser le développement des logiciels est très important • Petit Larousse : suite d’opérations élémentaires
constituant un schéma de calcul ou de résolution de
problème.

3 4

1
 27/10/2024

3.2 - Algorithmes et programmes 3.2 - Algorithmes et programmes

• Pour nous : Informations
• Un algorithme est une séquence précise et non en entrée
ambiguë d’une suite d’étapes pouvant être exécutées
de façon automatique par un ordinateur pour résoudre Algorithme informatique
un problème
=
schéma de calcul
• Spécification du schéma de calcul sous forme d’une
suite finie d’opérations élémentaires obéissant à un
enchaînement déterminé. Un algorithme est une suite finie de règles à appliquer Informations
dans un ordre déterminé à un nombre fini de données, en sortie
pour arriver en un nombre fini d’étapes, à un certain
résultat, et cela indépendamment des données.

5 6

3.3 - Langages de programmation

3.2 - Algorithmes et programmes
• Programme : • RAPPEL: Langage machine
• codage d’un algorithme afin que l’ordinateur puisse • langage binaire
exécuter les actions décrites • ses opérations sont directement compréhensibles par
• doit être écrit dans un langage compréhensible par l’ordinateur
l’ordinateur • propre à chaque famille d’ordinateur
•  langage de programmation
• Un programme est donc une suite ordonnée • Ecriture des premiers programmes en langage
d’instructions élémentaires codifiées dans un machine
langage de programmation

7 8

2
 27/10/2024

Algorithme
3.4 - Importance des algorithmes
programmation
• Pour mener à bien un traitement sur un
ordinateur il faut : Programme en langage évolué
1. Concevoir un algorithme qui décrit comment le
traitement doit être fait
traduction
2. Exprimer l’algorithme sous la forme d’un programme
dans un langage de programmation adéquat
3. Faire en sorte que l’ordinateur exécute le programme : Programme en langage machine
compilation
Interprétation par l’Unité Centrale de traitement

le traitement souhaité est réalisé

9 10

3.4 - Importance des algorithmes

Efficacité
• Quels sont les aspects et propriétés des
algorithmes qu’il est nécessaire d’étudier ? • Simuler une partie d’échec:
• Trop d’états à mettre en mémoire
• On choisit des choses non-optimales mais efficaces
1. La calculabilité des algorithmes (convergence de
• Voyageur de commerce
l’algorithme et existence de l’algo) la méthode existe t elle ? • Comment minimiser le trajet du voyageur de commerce allant de villes en villes
2. La complexité des algorithmes (nombre • Enoncé simple, mais solution très difficile si nombre de villes est grand (n!
d’opérations nécessaires) possibilités)
• N=5 =>120, n=15 => 1300 G
3. L’efficacité des algorithmes (vitesse des algo:
raisonnable) TEMPS D'EXÉCUTION - MÉMOIRE
OCCUPÉE

11 12

3
 27/10/2024

3.5 – Affinement des algorithmes 3.5 – Affinement des algorithmes

• Un algorithme doit décrire précisément le • Problèmes :
traitement qu’il doit exécuter et s’assurer que tous • fuseaux horaires différents
les cas de figures possibles ont bien été prévus. • Si un point applique l’heure d’Été et pas l’autre

• Exemple : algorithme permettant de calculer la • Pour éviter de telles erreurs le concepteur doit
durée d’un voyage à partir du tableau d’affichage suivre une démarche rigoureuse et méthodique :
des aéroports • Affinement progressive de l’algorithme
• Démarche descendant, top down
1. Consulter l’heure de départ • Technique du « diviser pour mieux régner »
2. Consulter l’heure d’arrivé
3. Soustraire l’heure de départ de celle d’arrivée
13 14

3.5 – Affinement des algorithmes 3.5 – Affinement des algorithmes

• Exemple : robot domestique avec un algorithme • 1. faire bouillir l'eau
de préparation d’une tasse de café soluble peut être affinée en :
1. Faire bouillir l’eau
2. Mettre le café • 1.1. remplir la bouilloire d'eau
3. Ajouter l’eau dans les tasses • 1.2. brancher la bouilloire sur le secteur
• 1.3. attendre l'ébullition
• 1.4. débrancher la bouilloire

15 16

4
 27/10/2024

3.5 – Affinement des algorithmes

3.5 – Affinement des algorithmes
• 3. ajouter de l'eau dans la tasse pourrait être
affinée en :
• 2. mettre le café dans la tasse 3.1. verser de l'eau dans la tasse jusqu'à ce que celle-ci soit
pourrait être affiné en : pleine.

• 2.1. ouvrir le pot à café • 1.1. remplir la bouilloire d'eau peut nécessiter les
• 2.2. prendre une cuillère à café affinements suivants:
• 2.3. plonger la cuillère dans le pot • 1.1.1. mettre la bouilloire sous le robinet
• 2.4. verser le contenu de la cuillère dans la tasse • 1.1.2. ouvrir le robinet
• 2.5. fermer le pot à café • 1.1.3. attendre que la bouilloire soit pleine
• 1.1.4. fermer le robinet

17 18

3.5 – Affinement des algorithmes 3.5 – Affinement des algorithmes

• Affinement ne se fait pas dans le vide • Processeur informatique : ordinateur, capacités

• Savoir où s’arrêter d’interprétation connues
• Connaître les capacités du processeur • Le concepteur d’un algorithme doit donc affiner ce
dernier jusqu’à ce que les étapes puissent être
• Exemple : écrites à l’aide d’un langage de programmation
• Brancher la bouilloire, activité interprétable
• Remplir la bouilloire, activité non interprétable 
affinement

19 20