Algorithmique
Mouhamadou GAYE
UFR Sciences et Technologies
Département Mathématiques
Licence 1 en Mathématiques et Informatique
15 décembre 2016
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence15 décembre
1 en 2016
Mathématiques et 1Informat
/ 17
Contenu du module
Introduction à l’Algorithmique
Instructions de base d’un algorithme
Structures de contrôle
Tableaux et algorithmes de tri
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence15 décembre
1 en 2016
Mathématiques et 2Informat
/ 17
Déroulement
Volume horaire : 40h (20h CM et 20h TD)
CM : Jeudi 8h30-10h30
TD Groupe 1 : Samedi 8h30-10h30
TD Groupe 2 : Samedi 10h30-12h30
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence15 décembre
1 en 2016
Mathématiques et 3Informat
/ 17
Évaluation
Devoir surveillé : 40
Examen final : 60
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence15 décembre
1 en 2016
Mathématiques et 4Informat
/ 17
Introduction à l’Algorithmique
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence15 décembre
1 en 2016
Mathématiques et 5Informat
/ 17
L’informatique
Un domaine d’activité scientifique, technique et industriel concernant
le traitement automatique de l’information via l’exécution de
programmes informatiques par des machines.(Wikipédia)
Sciences et techniques du traitement automatisé de l’information,
c’est à dire des données.
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence15 décembre
1 en 2016
Mathématiques et 6Informat
/ 17
Architecture d’un ordinateur
Un ordinateur est composé de :
une unité centrale appelée CPU contenant le processeur ;
une mémoire centrale et des mémoires secondaires ;
des périphériques d’entrées et de sorties (clavier, écran, etc.) ;
un système d’exploitation
des logiciels d’applications (Office, Jeu, etc.)
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence15 décembre
1 en 2016
Mathématiques et 7Informat
/ 17
Architecture d’un ordinateur
Figure: Architecture matérielle d’un ordinateur
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence15 décembre
1 en 2016
Mathématiques et 8Informat
/ 17
Une application informatique
Un programme directement utilisé par l’utilisateur pour réaliser une
tâche, ou un ensemble de tâches élémentaires d’un même domaine.
Une séquence d’instructions qui spécifie étape par étape les opérations
à effectuer pour obtenir un résultat.
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence15 décembre
1 en 2016
Mathématiques et 9Informat
/ 17
C’est quoi un algorithme ?
Définition
Une suite d’instructions simples permettant d’obtenir un résultat espéré si
elles sont correctement utilisées.
Définition
Une suite finie, séquentielle de règles que l’on applique à un nombre fini de
données, permettant de résoudre des classes de problèmes semblables.
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence
151décembre 2016
en Mathématiques 10Informat
et / 17
Pourquoi écrire un algorithme ?
Expliquer à la "machine" comment elle doit s’y prendre pour effectuer
un travail à notre place.
Expliquer et formaliser un raisonnement.
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence
151décembre 2016
en Mathématiques 11Informat
et / 17
Exemples d’algorithme
Les recettes de cuisine.
Une recette de cuisine comporte trois étapes :
1 Réunir les ingrédients ;
2 Préparer ;
3 Servir.
La préparation consiste à exécuter une suite d’instructions : par exemple,
plonger les tomates dans une casserole d’eau bouillante pendant quelques
instants avant de les peler, etc.
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence
151décembre 2016
en Mathématiques 12Informat
et / 17
Exemples d’algorithme
La recherche d’un mot dans le dictionnaire.
On regarde d’abord la première lettre du mot, et on la compare avec
celle des mots de la page où le dictionnaire est actuellement ouvert.
Suivant la position relative des deux lettres en question dans l’ordre
alphabétique, on tourne alors les pages en avant ou en arrière, jusqu’à
ce que les premières lettres coïncident.
Puis on reproduit la même procédure avec la deuxième lettre du mot,
puis la troisième, et ainsi de suite...
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence
151décembre 2016
en Mathématiques 13Informat
et / 17
Place de l’algorithme dans le processus de programmation
Figure: Différentes étapes du processus de programmation
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence
151décembre 2016
en Mathématiques 14Informat
et / 17
Propriétés d’un algorithme
lisible : doit être compréhensible même par un non-informaticien ;
précis : il doit indiquer ;
l’ordre des différentes ;
à quel moment il faut commencer une action ;
à quel moment il faut cesser une action ;
comment choisir entre différentes possibilités ;
structuré : doit être composé de différentes parties facilement
identifiables.
déterministe : une suite d’exécutions à partir des mêmes données doit
produire des résultats identiques ;
fini dans le temps : il doit s’arrêter au bout d’un temps fini ;
de haut niveau : doit pouvoir être traduit en n’importe quel langage
de programmation ;
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence
151décembre 2016
en Mathématiques 15Informat
et / 17
Problèmes fondamentaux en algorithmique
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ésolve ?
Correction
Peut-on être sûr qu’un algorithme réponde au problème pour lequel il a
été conçu ?
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence
151décembre 2016
en Mathématiques 16Informat
et / 17
Comment écrire un algorithme
1 Bien comprendre le problème et, si le principe de l’algorithme n’est pas
donné, trouver un principe de résolution.
2 Si on ne comprend pas bien le principe, l’utiliser sur un exemple.
3 Si besoin, réaliser un organigramme pour mieux comprendre.
4 Ecrire l’algorithme.
5 Il peut être utile, voire nécessaire, de prouver l’algorithme.
6 Il peut être utile d’évaluer l’efficacité de l’algorithme.
Mouhamadou GAYE (UFR Sciences et Technologies Département
AlgorithmiqueMathématiques Licence
151décembre 2016
en Mathématiques 17Informat
et / 17