Définition 1 : Un algorithme
Un algorithme est une séquence finie d’opérations élémentaires qui permettent de résoudre un
problème.
Définition 2 : Propriétés d’un algorithme
1) Les entrées: un algorithme prend des valeurs d’entrée à partir d’ensembles définis.
2) La sortie: un algorithme renvoie une sortie qui constitue la solution du problème
considérée.
3) La finitude: l’algorithme doit produire la sortie souhaitée en un nombre fini d’étapes
quelque soit l’entrée.
4) La correction : Un algorithme doit produire un résultat correct.
5) La précision : Chaque étape d'un algorithme doit être définie précisément. Les actions à
transposer doivent être spécifiées rigoureusement et sans ambigüité pour chaque cas.
6) L’efficacité: Chaque étape de l’algorithme doit pouvoir s’exécuter dans un temps fini.
7) La généralité: L’algorithme s’applique à toutes les instances du problème considéré.
Définition 3 : Problèmes fondamentaux en algorithmique
1) Complexité :
a. En combien de temps un algorithme atteint-il le résultat ?
b. De combien d’espace mémoire a-t-il besoin ?
2) Calculabilité :
a. Existe-t-il des problèmes pour lesquelles il n'existe aucun algorithme ?
b. Étant donnée un problème, peut-on détecter s'il existe un algorithme qui le résout ?
3) Correction :
a. Peut-on être sûr qu'un algorithme réponde au problème pour lequel il a été conçu ?
Définition 4 : Un programme
Un programme est une implémentation d’un algorithme dans un langage de programmation
sur un système particulier.
Définition 5 : La théorie de la complexité
La théorie de la complexité des algorithmes étudie formellement la quantité de ressources, en
temps et en espace, nécessaire pour l'exécution d'un algorithme ainsi que la difficulté
intrinsèque des problèmes algorithmiques.
Slim BECHIKH, Juillet 2011 1/7
Définition 6 : Algorithme de tri
Un algorithme de tri est un algorithme qui permet d'organiser une collection d'objets selon un
ordre déterminé. Les objets à trier font donc partie d'un ensemble muni d'une relation d'ordre.
Les ordres les plus utilisés sont l’ordre numérique et l'ordre lexicographique.
Définition 7 : Problème de décision
Chaque problème informatique peut se réduire à un problème de décision, c’est-à-dire un
problème formulé comme une question dont la réponse est « Oui » ou « Non ». Par exemple,
la taille du plus court chemin est 42 KM. Un problème qui n'est pas formulé de cette manière
peut être très simplement transformé en un problème de décision équivalent. Le problème du
voyageur de commerce, qui cherche, dans un graphe, à trouver la taille du cycle le plus court
passant une fois par chacun des sommets, peut s'énoncer en un problème de décision comme
suit : Existe-t-il un cycle passant une et une seule fois par chaque sommet tel que la somme
des coûts des arcs utilisés soit inférieure à 42 KM. Ce problème est équivalent au problème
du voyageur de commerce au sens où si l'on sait résoudre efficacement l'un, on sait aussi
résoudre efficacement l'autre.
Définition 8 : Algorithme déterministe
Un algorithme déterministe est un algorithme qui, si on l’exécute avec les mêmes données en
entrée, à chaque étape passera toujours à l’étape suivante prévue par le concepteur de
l’algorithme. S’il y a un choix à faire, il fera toujours le même choix.
Définition 9 : Algorithme non-déterministe
Un algorithme non-déterministe est un algorithme qui, si on l’exécute avec les mêmes
données en entrée, lorsqu’il se trouve face à un choix, peut indifféremment choisir l’un des
chemins d’exécution sans pouvoir prédire à l’avance son choix.
Définition 10 : Classes de complexité
La théorie de la complexité repose sur la définition de classes de complexité qui permettent de
classer les problèmes en fonction de la complexité des algorithmes qui existent pour les
résoudre.
Définition 11 : Classe L
C’est la classe des problèmes de décision qui peuvent être résolus par un algorithme
déterministe en un temps logarithmique par rapport à la taille de l'instance.
2/7
Définition 12 : Classe NL
C’est la classe des problèmes décision qui peuvent être résolus par un algorithme non-
déterministe en un temps logarithmique par rapport à la taille de l'instance.
Définition 13 : Classe P
C’est la classe des problèmes décision qui peuvent être résolus par un algorithme déterministe
en un temps polynomial par rapport à la taille de l'instance.
Exemple : recherche d’un cycle Eulérien.
Définition 14 : Classe NP
C’est la classe des problèmes de décision qui peuvent être résolus par un algorithme non-
déterministe en un temps polynomial par rapport à la taille de l'instance. Ou encore, d’une
manière équivalente, la réponse « oui » peut être vérifiée par un algorithme déterministe en un
temps polynomial par rapport à la taille de l'instance.
Définition 14 : Classe NP-complet (Problème NP-complet) = NP-difficile + NP
En théorie de la complexité, un problème NP-complet est un problème de décision vérifiant
les propriétés suivantes :
▪ Il est possible de vérifier une solution efficacement en un temps polynomial, càd, le
problème fait partie de la classe NP, et
▪ Tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale;
cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de
la classe NP. On dit que le problème est NP-difficile.
Tous les algorithmes connus pour résoudre des problèmes NP-complets ont un temps
d'exécution exponentiel par rapport à la taille de l’instance dans le pire cas et sont donc
inexploitables en pratique même pour des instances de taille modérée.
La seconde propriété de la définition implique que s'il existe un algorithme polynomial pour
n'importe quel problème NP-complet, alors tous les problèmes de la classe NP peuvent être
résolus en temps polynomial. Trouver un algorithme polynomial pour un problème
NP-complet ou prouver qu'il n'en existe pas permettrait de savoir si P = NP ou P ≠ NP, une
question ouverte qui fait partie des problèmes non résolus en mathématiques les plus
importants à ce jour.
Exemples : Le voyageur de commerce, le cycle hamiltonien, le sac à dos, le coloriage de
graphe, etc.
Slim BECHIKH, Juillet 2011 3/7
Définition 14 : Classe NP-difficile (Problème NP-difficile)
Un problème est NP-difficile si ce problème est au moins aussi dur que tous les problèmes
dans NP. Π est alors NP-difficile si pour tout problème Π' de NP, Π' se réduit à Π par un
algorithme polynomial (on parle de réduction polynomiale). Ainsi, si l'on a un algorithme
pour résoudre Π, on sait aussi résoudre Π'.
Exemple d’un problème NP-difficile qui n’est pas NP-complet : Halting problem (Etant
donné une description d’un programme informatique et un ensemble de données en entrée, on
cherche à décider si un programme finit ou s’exécute infiniment).
Définition 15 : Réduction de problème (soit par transformation du problème, soit par réduction
polynomiale)
Pour montrer qu'un problème Π est C-difficile pour une classe C donnée, il y a deux façons
de procéder: montrer que tout problème de C se réduit à Π, ou bien il suffit de montrer qu’un
problème C-difficile se réduit à Π. C'est cette deuxième méthode, plus facile, qui est utilisée
dès que l'on dispose d'au moins un problème C-complet.
Définition 16 : Transformation de problème
La réduction la plus simple (ce n'est d'ailleurs pas vraiment une réduction) consiste
simplement à transformer le problème à classer en un problème déjà classé.
Par exemple, démontrons ici que le problème de la recherche de cycle hamiltonien dans un
graphe orienté est NP-Complet.
1) Le problème est dans NP : On peut trouver de façon évidente un algorithme non-
déterministe en un temps polynomial, par exemple, en énonçant tous les cycles puis en
sélectionnant le plus court.
2) Nous disposons du problème de la recherche du cycle hamiltonien pour les graphes non-
orientés. Un graphe non-orienté peut se transformer en un graphe orienté en "doublant"
chaque arête de manière à obtenir, pour chaque paire de nœuds adjacents, des chemins
dans les deux sens. Il est donc possible de ramener le problème connu, NP-difficile, au
problème que nous voulons classer. Le nouveau problème est donc NP-difficile.
Le problème étant dans NP et NP-difficile, il est NP-complet.
NP-difficile NP-C NP P
Difficulté
4/7
Définition 17 : Réduction polynomiale
Un problème Π se réduit à un problème Π' s’il existe un algorithme polynomial qui
transforme toute entrée u de Π en une entrée v de Π' telle que :
u ∈ OUI (π ) ⇔ v ∈ OUI (π ' )
L’objectif est de mettre en relation un problème de décision (oui/non) que l’on cherche à
résoudre avec un autre problème de décision que l’on sait résoudre. Dans le cas de la
NP-complétude, la réduction permet de montrer la difficulté de la résolution d’un problème.
Remarque : comment montrer qu’un problème est NP-complet ?
Soit Q un problème NP. Supposant qu’on connait déjà un problème NP-complet Π. Si Π se
réduit polynomialement à Q alors : Q est NP-complet.
Exemples de problèmes pour chacune des classes :
Définition 18 : Les sous-programmes
1) La procédure : c’est un sous-programme qui calcule zéro ou plusieurs résultats.
2) La fonction: c’est un sous-programme qui calcule un seul résultat.
Remarques :
▪ Les paramètres formels sont des identificateurs utilisés pour introduire des données dans
la procédure ou d’en recevoir des résultats.
▪ Les variables locales sont des variables nécessaires pour exécuter sa tâche.
Slim BECHIKH, Juillet 2011 5/7
▪ Une procédure ne sert à rien si elle ne communique pas avec l'extérieur ou le reste du
programme. Pour cela, elle doit avoir un effet de bord : c'est à dire avoir une action sur un
périphérique (clavier, écran, imprimante, disque), ou modification d’une variable.
▪ Une fonction a toujours un effet de bord qui est son résultat.
▪ La portée d’une variable est l’étendue du programme dans lequel la variable est reconnue
et peut être utilisée.
Définition 19 : Passage de paramètres
Passage par valeur : Dans ce cas, le programme principal transmet à la procédure le contenu
de l’argument. La procédure ne connaît pas où se trouve l’argument. Elle pourra utiliser la
valeur transmise mais elle ne pourra pas aller écrire une nouvelle valeur dans l’argument.
Ceci constitue une sécurité pour le programme principal qui ne veut pas dans certain cas
qu’on aille modifier le contenu de ses variables.
Passage par adresse : Dans ce cas, le programme appelant transmet à la procédure l’adresse
de l’argument. La procédure peut ainsi lire son contenu ou le modifier. On utilise ce mode de
passage lorsque le paramètre va recevoir un résultat à la fin du traitement.
Les paramètres formels transmis par adresse sont précédés du mot clé VAR, alors que ceux
transmis par valeur ne le sont pas.
Remarques :
▪ A la place d’un argument transmis par valeur, on peut indiquer une constante, une variable
ou une expression.
▪ Un argument transmis par adresse ne peut être qu’une variable.
Définition 20 : Tableau
Un tableau est une structure linéaire de données constituée d'un nombre fini d'éléments de
même type. Un tableau possède un identificateur et chaque élément du tableau est repéré par
un indice précisant sa position au sein du tableau.
Définition 21 : Plan d’un cours d’algorithmique
1) Introduction à l’algorithmique : connaître les concepts de base (analyse, algorithme,
algorithmique, programmatique, etc), données du problème, démarche de résolution
d’un problème, etc.
2) Eléments de base d’un algorithme : structure générale d’un algorithme, les objets
algorithmiques (constante, variable, les types de données, les opérateurs), les
instructions simples/élémentaires (lecture, écriture, affectation).
3) Les structures conditionnelles : simples, imbriquées, à plusieurs choix.
6/7
4) Les structures itératives : Pour, tant que, répéter ... jusqu’à.
5) Les procédures et les fonctions : sous-programme appelant/appelé, variable
locale/globale, passage de paramètres par valeur/adresse.
6) Les types structurées : Les tableaux unidimensionnels/bidimensionnels et les
enregistrements.
7) Les algorithmes de tri et de recherche (bulle, sélection, insertion, rapide, etc; et
recherche séquentielle/dichotomique).
8) La récursivité.
9) La notion de pointeur : opérateurs sur les pointeurs.
Définition 22 : Tri par bulles
On parcourt le tableau à trier du début à la fin, en comparant les éléments consécutifs deux-à-
deux tout en faisant ainsi « descendre » vers la fin du tableau les éléments qui doivent être
placés à la fin; à la manière d'une bulle. Si ceux-ci sont dans le bon ordre, on les laisse sinon
on les inverse. Lorsque l'on a fini de parcourir le tableau une première fois, on est sûr d'avoir
placé le dernier élément à la bonne place. On parcourt donc de nouveau le tableau pour placer
le reste des éléments.
Définition 23 : Tri par sélection
Le principe du tri par sélection est de chercher à chaque étape le minimum dans le reste du
tableau et de faire l’échange avec lui.
Définition 23 : Tri par insertion
Le principe du tri par insertion est d'insérer à la nième itération le nième élément à la bonne
place. Donc, à chaque itération i, les i premiers éléments sont triés. Le problème de cet
algorithme est qu'il faut parcourir le tableau trié pour savoir à quel endroit insérer le nouvel
élément, puis décaler d'une case toutes les valeurs supérieures à l'élément à insérer.
Définition 24 : Tri rapide
La méthode consiste à placer un élément du tableau appelé pivot à sa place définitive, en
permutant tous les éléments de telle sorte que tous ceux qui lui sont inférieurs soient à sa
gauche et que tous ceux qui lui sont supérieurs soient à sa droite. Cette opération s'appelle le
partitionnement. Pour chacun des sous-tableaux, on définit un nouveau pivot et on répète
l'opération de partitionnement. Ce processus est répété récursivement jusqu'à ce que
l'ensemble des éléments soit trié.
Définition 25 : Tri par fusion
L'algorithme peut être décrit récursivement : (1) On découpe en deux parties à peu près égales
les données à trier, (2) on trie les données de chaque partie, (3) on fusionne les deux parties.
La récursivité s'arrête car on finit par arriver à des listes composées d'un seul élément.
Slim BECHIKH, Juillet 2011 7/7