Actualité

[[{"text":"

Le pouvoir de l'algorithmique n'est pas infini. On sait que certains problèmes ne peuvent pas être résolus parfaitement de manière automatique.

L'étude des possibilités et limites des algorithmes définit le champ de la calculabilité, qui est l'un des piliers de la science informatique.

","title":"Calculabilité"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Supposons que l'on souhaite réaliser, en Python, un détecteur d'erreurs pour les programmes Python.

Pour fixer les idées, concentrons-nous sur une seule erreur à détecter:

la division par zéro.

On veut donc définir une fonction detecteur prenant en entrée un programme p et renvoyant True si l'exécution de p s'interrompt avec ZeroDivisionError et False sinon.

","title":"Problème : détecteur d'erreurs en Python"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Erreurs

En mathématiques, la division par zéro n'est pas définie. Tenter d'en réaliser une dans un programme Python lève une exception qui interrompt l'exécution du programme.

Tester le code suivant et noter l'erreur:

x = 1/0

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Le programme en tant que donnée

L'idée qu'un programme puisse n'être qu'une donnée manipulée par un autre programme peut paraître vertigineuse.

Nous l'avons cependant déjà croisée plusieurs fois, et sous différentes formes.

Considérons un programme Python défini dans un fichier don_jose.py :

Programme — don_jose.py

i = 3

while i > 0:

print(\"Prends garde à toi !\")

i = i - 1

print(1 / i)

print(\"Carmen épouse-moi !\")

Ce programme se présente sous la forme d'un fichier de texte contenant une suite de caractères.

Ce fichier est présent dans la mémoire de l'ordinateur et peut être manipulé, déplacé, copié par les autres programmes comme tout autre fichier.

Mieux, on peut même donner ce fichier comme paramètre à l'interprète Python avec la ligne de commande suivante dans le terminal:

$ python don_jose.py

Copier le programme dans le fichier don_jose.py et tester le dans le terminale avec la ligne de commande ci-dessus.

","title":""},{"edit":"

Mettre le résultat ici de l'exécution de la ligne de commande.

"},{"text":"

Ainsi, l'interprète Python lui-même est un exemple de programme prenant

en paramètre un autre programme.

On peut alors imaginer un détecteur fonctionnant de même, avec une fonction prenant en paramètre un nom de fichier à analyser et récupérant le texte qu'il contient.

def detecteur(nom_de_fichier):

fichier = open(nom_de_fichier)

programme = fichier.read()

La variable programme contient alors l'ensemble du programme à analyser, donné sous la forme d'une chaîne de caractères.

Même s'il reste assurément de la distance à parcourir, on peut imaginer qu'une analyse fine du contenu de cette chaîne nous donnera toutes les informations dont nous pourrions avoir besoin à propos du programme.

"}],[{"text":"

Détecteur naïf

Une approche très simple de la détection consisterait alors à faire comme l'interprète Python lui-même:

exécuter le programme donné

en paramètre.

La fonction exec fait exactement ceci si on lui donne en paramètre la chaîne de caractères représentant un programme.

Il suffit alors de l'encadrer avec les mécanismes de gestion des exceptions de Python pour détecter d'éventuelles erreurs.

def detecteur_naif(nom_de_fichier):

fichier = open(nom_de_fichier)

programme = fichier.read()

try:

exec(programme) # exécution du programme à analyser

return False

except ZeroDivisionError:

return True

except:

return False

Dans le cas où le programme à analyser complète son exécution sans avoir déclenché d'erreur, on exécute ensuite la ligne return False.

Toute erreur lors de cette exécution déclenche en revanche l'exécution d'un bloc except, et renvoie True en cas de division par zéro et False dans les autres cas.

Exécuter ce détecteur avec la commande suivante et noter le résultat.

erreur = detecteur_naif('don_jose.py')

print(\"Erreur dans don_jose.py?\",erreur)

Le programme intercepte l'erreur et renvoie True (après avoir affiché trois fois «Prends garde à toi!».

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Ça va durer encore longtemps?

Notre détecteur naïf ne répond hélas pas

complètement au problème posé.

Observons le programme escamiilo.py :

while True:

print(\"Veillez sur vous !\")

print(1 / 0)

Enregistrer ce programme sous escamiilo.py et tester le avec le détecteur d'erreurs. Conclure.

erreur = detecteur_naif('escamiilo.py')

print(\"Erreur dans escamiilo.py?\",erreur)

Ce programme exécute indéfiniment sa boucle sans jamais générer d'erreur.

On attendrait donc du détecteur qu'il renvoie False.

Cependant, l'exécution infinie du programme escamillo empêcherait notre

détecteur d'atteindre ses instructions return:

la détection n'aboutirait pas.

On cherche donc encore un détecteur qui répondrait à tous les coups, quel que soit le comportement fini ou infini du programme à analyser.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Ce que cache exec

L''exécution ou l'analyse d'un programme donné par son code source sous la forme d'une chaîne de caractères n'est pas

immédiate.

'i = 3\\nwhile i > 0:\\n print(\"Prends garde à toi !\")\\n i = i - 1\\nprint(1 / i)\\nprint(\"Carmen épouse-moi !\")'

Nous n'avons sous la main qu'une suite de caractères, et toute la structure du programme est à reconstruire en comparant cette suite de caractères et les règles de syntaxe du langage Python.

Le résultat de cette reconstruction est un arbre de syntaxe:

uue structure de données en forme d'arbre reproduisant la structure du programme.

Les fonctions chargées de cette analyse syntaxique en Python sont définies dans le module parse.

Un interprète, dans sa forme la plus simple, utiliserait alors cet arbre de

syntaxe pour simuler l'exécution du programme sur une entrée donnée.

Cet arbre de syntaxe peut également être compilé, c'est-à-dire traduit, en une séquence d'instructions élémentaires de type assembleur.

C'est ce qui se passe dans la version de référence de Python, avec une traduction en bytecode :

un langage assembleur qui n'est pas celui de notre ordinateur physique, mais celui d'un ordinateur idéal qui serait dédié à l'exécution des programmes Python (et qui est simulé par le programme python lui-même).

1 0 SETUP_LOOP 12 (to 14)

2 >> 2 LOAD_NAME 0 (print)

4 LOAD_CONST 0 ('Veillez sur vous !')

6 CALL_FUNCTION 1

8 POP_TOP

10 JUMP_ABSOLUTE 2

12 POP_BLOCK

3 >> 14 LOAD_NAME 0 (print)

16 LOAD_CONST 1 (1)

18 LOAD_CONST 2 (0)

20 BINARY_TRUE_DIVIDE

22 CALL_FUNCTION 1

24 POP_TOP

26 LOAD_CONST 3 (None)

28 RETURN_VALUE

En Python, on produit le bytecode avec la fonction compile.

On peut alors soit l'exécuter directement, notamment avec la fonction exec, soit manipuler ses instructions avec les fonctions du module dis.

Tester et analyser les différentes fonctions ci-dessous:

import dis

fichier = open('don_jose.py')

programme = fichier.read()

c = compile(programme, '<string>', 'exec')

print(dir(c))

print(c.co_code)

print(c.co_names)

print(c.co_consts)

dis.dis(c)

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Impossibilité de la détection

Supposons que quelqu'un ait réussi à écrire en Python une fonction detecteur_parfait, qui réalise un détecteur de divisions par zéro fonctionnant à tous les coups.

Observons alors le programme carmen.py et réfléchissons à son comportement.

Programme - carmen.py

if detecteur_parfait('carmen.py'):

print(\"Tu crois le tenir, il t'évite\")

else:

print(\"Tu crois l'éviter, il te tient\")

print(1 / 0)

Notez qu'il s'agit d'un programme qui s'applique à lui-même notre détecteur parfait de division par zéro, et se comporte ensuite à l'inverse du diagnostic obtenu.

Supposons d'abord que l'exécution du programme carmen résulte en une erreur ZeroDivisionError.

Le détecteur parfait, par définition, renverrait True.

L'exécution passerait dans ce cas par la première branche et ne déclencherait aucune erreur, en contradiction avec notre supposition.

L'exécution du programme carmen ne peut donc pas produire d'erreur ZeroDivisionError. Or, si effectivement cela n'était pas le cas, le détecteur parfait renverrait False, aiguillant l'exécution dans la branche else qui, elle, produirait l'erreur.

Nous avons ici une contradiction qui conclut notre raisonnement par l'absurde:

la fonction detecteur parfait utilisée par notre programme (par ailleurs légitime) carmen.py ne peut pas exister en Python.

Autrement dit le problème de la détection des erreurs ZeroDivisionError dans les programmes Python ne peut pas être résolu par un programme Python.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Est-ce dû à une limitation de Python?

Existe-t-il un algorithme exprimable dans un autre langage qui répondrait à notre problème?

Ou avons-nous touché quelque limite plus fondamentale?

Répondre à ces questions implique soit d'élaborer un algorithme comprenant des aspects impossibles à réaliser en Python, ce qui serait une première, soit de justifier qu'aucun algorithme ne saurait résoudre notre problème de détection.

","title":""},{"edit":"

"}],[{"text":"

La notion d'algorithme a longtemps existé en mathématiques, désignant an sens large des méthodes de calcul.

Le mot à l'origine faisait référence notamment aux techniques que nous avons apprises à l'école primaire pour réaliser les quatre opérations arithmétiques de base.

De manière générale, un algorithme attend des entrées et calcule un résultat en fonction de ces entrées.

Ainsi, un algorithme réalise une fonction mathématique et on appelle fonction calculable une fonction pour le calcul de laquelle ii existe un algorithme.

Par exemple, la fonction qui a une équation du second degré associe l'ensemble de ses solutions est calculable :

la méthode du discriminant est justement un algorithme réalisant cet objectif.

Cette notion informelle et intuitive a été suffisante jusqu'à la fin du dix-neuvième siècle.

Mais pour répondre à nos questions sur la détection d'erreurs, nous avons besoin d'une vision plus précise de ce qu'est un algorithme et de ce qui est, ou non, calculable par un algorithme.

La caractérisation des fonctions calculables acceptée aujourd'hui a été établie dans les années 1930 et elle constitue l'un des événements fondateurs de l'informatique en tant que science.

","title":"Calculabilité, des mathématiques à l'informatique","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Programme de Hilbert et Entscheidungsproblem

David Hilbert

1862-1943

Source : https://fr.wikipedia.org/wiki/David_Hilbert

Cet événement que nous allons relater est intimement lié à l'essor de l'un des courants majeurs des mathématiques du vingtième siècle :

l'école formaliste.

Le chef de file de ce courant de pensée, David Hilbert, appelle à fonder les mathématiques sur la logique et clame dès 1900 sa conviction que tout énoncé mathématique bien formulé peut être soit démontré, soit réfuté à l'aide de règles de déduction formelles en se ramenant à une base finie de postulats de départ (les axiomes).

Dans ce contexte, Hilbert développe un vaste projet de formulation des mathématiques appelé aujourd'hui programme de Hilbert et y énonce quelques objectifs de référence, dont notamment les démonstrations de la complétude :

tout énoncé vrai peut être démontré

et de la cohérence

aucune contradiction ne peut être obtenue

de cette formulation des mathématiques.

Un dernier objectif, ajouté en 1928 sous le nom d'Entscheidungsproblem (en français, problème de la décision), demande de créer un algorithme déterminant, pour tout énoncé mathématique bien formulé donné en entrée, si ce dernier est vrai ou faux.

On entend ici par algorithme un procédé mécanique, assimilable à une méthode de

calcul.

Ainsi, dans les années 1930 deux mathématiciens, Alonzo Church et Alan

Turing, ont proposé quasi simultanément deux approches radicalement différentes pour caractériser ce qui peut être, ou non, calculé par un algorithme.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Les fonctions λ-calculables de Church

Alonzo Church

1903 - 1995

Spirce : https://fr.wikipedia.org/wiki/Alonzo_Church

Par définition, les fonctions calculables couvrent tout ce qui peut être calculé.

Dit autrement tout calcul, petit ou grand, se ramène à l'application d'une fonction calculable à des arguments, et cela vaut encore pour chaque calcul intermédiaire d'une fonction que l'on chercherait à définir.

Ainsi, Church propose de définir une fonction calculable comme une fonction dont le résultat est obtenu par une combinaison d'applications de fonctions calculables.

Il propose pour les décrire un langage à la syntaxe minimale appelé λ-calcul (prononcer «lambda-calcul»).

Dans ce langage, on ne manipule rien d'autre que des fonctions calculables:

on définit des fonctions calculables dont les paramètres sont des fonctions calculables et dont le résultat n'est de même rien d'autre qu'une fonction calculable.

On peut rapprocher cela d'un programme Python qui ne manipulerait rien d'autre que la construction lambda:

f = lambda x: 2*x**2 + 3*x + 4

print(\"f(3)\",f(3))

Tester le code.

Comme on le voit cette description donnera quelques décennies plus tard les bases théoriques de la programmation fonctionnelle.

Autre fait moins intuitif :

bien que ce système extrême n'admette rien d'autre comme élément de base que la fonction, il permet tout à fait de représenter, indirectement et à l'aide de fonctions particulières, nos objets habituels, à commencer par les nombres entiers et certaines structures de données (voir page ci-après pour quelques exemples).

Grâce à cela, le λ-calcul permet effectivement de représenter des algorithmes traditionnels.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Le λ-calcul

Ce langage manipule des expressions dont la structure est définie récursivement.

Une expression est soit :

l'application d'une expression e1 à une expression e2, notée e1(e2);
une fonction attendant un paramètre x et dont le résultat est calculé par une expression e, notée λ.x.e, à rapprocher d'une fonction anonyme Python lambda x: e;
une référence à un paramètre x.

Voici trois exemples d'expressions du λ-calcul:

λx.x
λx.λy.x
λf.λg.λx.g(f(x))

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Le λ-calcul (suite)

La première est la fonction identité, qui attend un paramètre x et le renvoie tel quel comme résultat.

La deuxième est une fonction qui attend un paramètre x et renvoie comme résultat la fonction constante attendant un paramètre y mais renvoyant simplement x.

Notez que l'on peut également la voir comme une fonction attendant deux paramètres x et y et renvoyant le premier (x).

La dernière peut être vue comme une fonction qui, si on lui passe deux paramètres f et g, renvoie la fonction composée g o f.

On «calcule» avec les expressions du λ-calcul à l'aide d'une unique règle résolvant l'application

(λx.e)(a)

d'une fonction λx.e à un argument a.

Pour cela, il suffit de remplacer, dans l'expression e donnant le résultat de la fonction, chaque occurrence du paramètre x par l'argument a.

(λf.λx.f(f(x))) (λy.y) = λx(λy.y)((λy.y)(x))

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Données

Étant données deux expressions a et b, l'expression λz.z(a)(b} est une manière de représenter le couple (a,b).

Pour obtenir l'un des éléments composant un tel couple, on peut alors appliquer à ce couple l'une des deux fonctions λc.c(λx.λy.x) où λc.c(λx.λy.y).

On peut en effet développer l'application de la première ainsi:

(λc.c(λx.λy.x))(λz.z(a)(b))

= (λz.z(a)(b))(λx.λy.x)

= (λx.λy.x)(a)(b)

= (λy.a)(b)

= a

Les deux expressions λx.λy.x et λx.λy.y aperçues dans les deux fonctions de projection précédentes sont également couramment utilisées pour représenter respectivement True et False.

Avec cette double possibilité de représenter une information binaire (True/False) et de concaténer deux éléments, nous avons le pouvoir de représenter toute séquence de bits.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Itération

Prenons comme dernier exemple sur le λ-calcul l'expression suivante, usuellement notée θ (theta) et appelée combinateur de point fixe de Turing :

(λx.λy.y(x(x)(y)))(λx.λy.y(x(x)(y)))

l'application de cette expression θ à une expression f quelconque on obtient l'enchaînement suivant:

θ(f) = f(θ(f) = f(f(θ(f))) = ...

Autrement dit, on obtient la possibilité d'itérer une fonction. et le risque de rencontrer un jour un calcul qui ne s'arrêterait jamais.

Ce double tranchant peut rappeler les fonctions récursives ou la boucle while.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Les machines de Turing

Alan Turing

1912 - 1964

Source ; https://fr.wikipedia.org/wiki/Alan_Turing

L'approche de Turing retient quant à elle l'aspect mécanique du calcul, avec un système comportant deux composantes:

un ruban de mémoire infini dont le contenu peut être consulté et modifié,
et une machine se déplaçant le long de ce ruban et en modifiant le contenu en fonction de quelques règles très simples constituant le programme de cette machine.

On peut voir une telle machine de Turing comme calculant le résultat d'une fonction f :

on commence par écrire sur le ruban un paramètre e,

on démarre la machine puis, lorsqu'elle s'arrête,

on lit le ruban pour obtenir le

résultat f(e).

Une fonction calculable selon Turing est alors définie comme une fonction pour laquelle il existe une machine.

Le programme réalisé par une machine de Turing est décrit par un ensemble de règles de transition qui, en fonction de l'état actuel de la machine et de l'information lue à la position observée du ruban, donnent trois éléments:

une instruction d'écriture, indiquant ce qui doit être écrit à la position actuelle du ruban à la place de l'imformation actuelle;
une instruction de déplacement, indiquant s'il faut déplacer la machine le long du ruban et dans quel sens;
l'état dans lequel passera la machine après cette étape.

On peut comprendre l'état de la machine comme une indication de notre situation dans l'exécution du programme, indication similaire à ce que serait un numéro de ligne pour un programme Python.

L'idée des machines de Turing donne ainsi les germes de la programmation impérative, avec des instructions exécutées successivement et agissant sur une mémoire.

L'information que peut contenir chaque case du ruban est définie par un ensemble fini de symboles appelé alphabet.

On prendra typiquement comme base un ensemble de trois symboles:

0, 1 et ⚈,

dans lequel 0 et 1 représentent des bits et ⚈ (prononcer «blac») indique une case vide.

Ces symboles sont parfois combinés avec des marqueurs permettant de repérer une position sur le ruban.

Ainsi, un nombre entier positif pourra être représenté en binaire sur un morceau de ruban contenant des symboles 0 et 1, délimité de chaque côté par un symbole ⚈.

Voici un fragment de ruban représentant le nombre 19, c'est-à-dire 10011 en binaire:

Une machine incrémentant un tel entier de 1, en supposant un démarrage à l'extrémité gauche du nombre, pourrait fonctionner en deux étapes :

d'abord se déplacer jusqu'à l'extrémité droite,
puis ajouter 1 au bit de poids faible, et revenir vers la gauche autant que nécessaire pour propager les retenues.

On pourrait donner à une telle machine trois états possibles:

un état de départ A pour la première phase de déplacement,
un état B pour la phase d'incrément,
et un état final F indiquant que le calcul est terminé.

Dans l'état A, la machine se déplace vers la droite sans modifier le contenu du ruban ni changer d'état tant qu'elle y observe des bits.

Lorsque la machine vient de dépasser le dernier bit, c'est-à-dire lorsqu'elle observe ⚈, elle revient alors d'une case en arrière et passe à l'état B.

Dans cet état, tant que la machine bserve des 1 elle les remplace par des 0 et poursuit son retour vers la gauche.

Ce retour s'arrête dès que la machine lit un 0 ou un ⚈, auquel cas ce symbole est remplacé par un 1 et la machine passe à son état final F et s'arrête.

L'ensemble de ces règles de transitions est résumé dans la table suivante:

Dans cette version, on suppose qu'il y a suffisamment de symboles blancs ⚈ à gauche du nombre pour qu'il en reste bien toujours un, même après la propagation d'une retenue.

Les trois états de la machine et leurs successions possibles au cours d'un calcul peuvent être résumés dans le graphe orienté suivant, appelé automate.

Dans ce graphe, chaque sommet correspond à un état et chaque arc à une transition possible.

On a étiqueté chaque arc par les symboles dont la lecture peut déclencher la transition correspondante, et on pourrait compléter pour préciser chaque action de déplacement et d'écriture associée.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Machine de Turing universelle

L'un des coups de force de Turing, qui a montré que ses machines sont capables de réaliser des algorithmes complexes, est la définition d'une machine universelle.

Cette machine prend en entrée une autre machine de Turing M et une entrée e pour la machine M, et simule l'exécution de la machine M sur l'entrée e.

On peut faire un parallèle entre cette machine et nn interprète Python qu'on aurait écrit dans le langage Python lui-même.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Universalité de la calculabilité

Dès 1936, Turing établit que les fonctions pouvant être définies comme

des fonctions λ-calculables de Church et les fonctions pouvant être calculées par des machines de Turing sont exactement les mêmes.

Autrement dit, les deux approches, si différentes soient-elles, décrivent la même notion de fonction calculable.

Cette convergence entre les résultats obtenus par deux approches si radicalement différentes à vite étayé l'idée, baptisée thèse de Church-Turing, que l'on venait effectivement de réussir à capturer la vraie notion de fonction calculable.

De ce point de vue, la compétition qu'on

aurait pu attendre entre ces deux approches n'eut donc jamais lieu.

Depuis, cette notion commune sert donc d'étalon et l'on qualifie de Turing-complets les modèles d'algorithmes et les langages de programmation permettant de calculer les mêmes choses que les machines de Turing.

Et de fait, la thèse de Church-Turing n'a jamais été démentie depuis.

Les autres manières de caractériser ce qui est calculable par algorithme développées par la suite ont encore été démontrées équivalentes à ces deux premières, c'est-à-dire Turing-complètes.

Tous les langages de programmation ordinaires, quels que soient les paradigmes qu'ils empruntent, sont de

même Turing-complets.

Certains langages permettent de résoudre plus naturellement que d'autres certains problèmes, mais il n'existe aucune tâche

qui puisse être réalisée par un programme écrit dans un langage de programmation donné qui ne soit pas réalisable dans tous les autres.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Autrement dit, tout problème de calcul dont on peut démontrer qu'il ne peut pas être résolu par une machine de Turing, par une fonction de Church ou par un programme Python, est officiellement hors de portée de l'algorithmique et de la programmation.

En particulier l'impossibilité de détecter à coup sûr à l'aide d'un programme Python les programmes effectuant une division par zéro, que nous avons montrée au début de cette séquence, à bien une portée universelle et n'est pas liée à une limitation du langage.

Pour cette section, nous prendrons donc le langage Python comme référence pour raisonner sur la calculabilité et ses limites :

par algorithme nous entendrons fonction Python, à distinguer de la notion de fonction mathématique qui n'est pas nécessairement calculable.

","title":"Limites de la calculabilité","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Les premiers résultats d'incalculabilité

Turing et Church ont chacun, en même temps qu'ils introduisaient leur modèle de calcul, explicité un problème dont ils ont montré que la solution n'était pas calculable.

Church a démontré qu'il ne pouvait exister de fonction calculable prenant en paramètres deux fonctions f et g et déterminant leur égalité, c'est-à-dire

répondant vrai si pour tout paramètre e, f(e) = g(e), et faux sinon.

Turing à démontré qu'il ne pouvait exister de machine de Turing prenant en paramètres une machine M et une entrée e, et déterminant si l'exécution de la machine M sur l'entrée e termine un jour ou au contraire se poursuit indéfiniment.

Ce deuxième problème, appelé problème de l'arrêt, est encore aujourd'hui un point de référence majeur que nous allons détailler ci-dessous.

L'un et l'autre en ont déduit, chacun dans son système, que l'Entscheidungsproblem ne pouvait être résolu par un algorithme.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Problèmes de décision

On s'intéresse souvent à la calculabilité de fonctions particulières, dont le résultat est oui où non.

On parle dans ce cas d'un problème de décision.

Le problème de l'arrêt, le problème de l'égalité de deux fonctions, ou encore le problème de la détection d'erreur en Python sont des problèmes de décision.

Le problème de la résolution d'une équation du second degré n'en est pas.

On appelle décidable un problème de décision dont la solution est calculable, et indécidable un problème de décision dont la solution n'est pas calculable.

Parmi les problèmes indécidables, on nomme semi-décidables ceux pour lesquels on possède un algorithme qui répond à coup sûr lorsque la réponse attendue est oui, mais qui est susceptible de ne jamais s'arrêter lorsque la réponde attendue est non.

Notre détecteur naïf pour la division par zéro avait justement cette propriété, et montre donc que notre problème de détection d'erreur est semi-décidable.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Problème de l'arrêt

Dans le problème de l'arrêt, reformulé pour les algorithmes assimilés à des fonctions Python, on s'intéresse à la fonction mathématique qui prend en paramètre une fonction Python f et une entrée e pour cette fonction Python, et qui renvoie le résultat True si l'exécution de f sur l'entrée e finit par s'arrêter, et False si au contraire elle ne s'arrête jamais.

On démontre qu'il n'existe pas d'algorithme calculant cette fonction mathématique, par un raisonnement par l'absurde similaire à celui tenu à propos du détecteur parfait.

Supposons donc qu'il existe un algorithme

arret prenant deux paramètres f et e et renvoyant en un temps fini soit True soit False selon que l'exécution de f sur e s'arrête ou non.

On définit grâce à arret un nouvel algorithme qu'on appelle paradoxe, qui attend un entier n et agit comme suit.

def paradoxe (n) :

if arret(paradoxe , n):

while True:

pass

else:

return n

Est-ce que l'application paradoxe(0) de cet algorithme au paramètre 0 produit un résultat, et si oui lequel?

Supposons que paradoxe(0) renvoie un résultat r. Cela signifie que cette exécution s'arrête et donc que arret(paradoxe, 0) va renvoyer True.

Autrement dit, l'algorithme paradoxe va déclencher la boucle infinie et ne jamais s'arrêter, ce qui est une contradiction.

Supposons à l'inverse que paradoxe(0) ne renvoie pas de résultat, car ne s'arrête jamais. Alors arret(paradoxe, 0) va répondre False et l'algorithme paradoxe renverra ainsi 0, ce qui est à nouveau une contradiction.

L'algorithme paradoxe ne peut donc pas exister.

Notez que le paramètre n attendu par paradoxe n'a pas de rôle particulier dans la preuve :

il a seulement été ajouté car on a énoncé le problème de l'arrêt pour des couples algorithme/entrée.

On aurait également pu énoncer le problème de l'arrêt pour des algorithmes sans paramètre et obtenir le même résultat.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

À propos des fonctions passées en paramètre

En général, passer une fonction f en paramètre à une fonction g comme on le fait facilement en programmation fonctionnelle permet à g d'appeler f, maïs pas nécessairement d'étudier le code de f.

On pourrait alors arguer que, dans notre

étude de la calculabilité, passer la fonction en paramètre plutôt que le code source lui-même n'est pas suffisant.

En Python, cependant, où tout est toujours un peu plus mélangé que dans là plupart des autres langages, il est possible d'obtenir le bytecode d'une fonction passée en paramètre grâce aux fonctions du module dis, et la différence entre les deux versions n'importe donc pas.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Indécidabilité : cas général, cas particuliers.

La notion d'indécidabilité algorithmique concerne une fonction à laquelle on demande de répondre à coup sûr, sur toutes les entrées possibles.

Le fait que le problème général soit indécidable n'empêche pas que lon sache y répondre dans certains cas particuliers.

Ainsi, bien que le problème de l'arrêt soit indécidable, il reste tout à fait envisageable, un algorithme étant donné, de démontrer que cet algorithme particulier s'arrête sur une entrée particulière, ou même sur toute entrée.

La notion de variant de boucle vue en première permet justement de produire une telle démonstration dans certains cas.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Autres problèmes indécidables et réductions

La connaissance d'un problème indécidable permet de justifier plus simplement l'indécidabilité de nombreux autres problèmes, à l'aide de techniques dites de réduction.

Considérons par exemple le problème de l'équivalence de deux algorithmes.

Étant donnés deux algorithmes f et g, on souhaite savoir si, pour toute entrée e, les appels f(e) et g(e) ont le même comportement, c'est-à-dire soit les deux produisent le même résultat, soit les deux s'interrompent avec la même exception, soit aucun ne termine.

Le problème de l'équivalence de deux algorithmes est indécidable.

Pour le justifier, supposons qu'il existe une fonction Python équivalentes prenant en paramètres deux fonctions f1 et f2 et renvoyant True si f1 et f2 sont équivalentes et False sinon.

Montrons que cette hypothétique fonction pourrait être détournée pour résoudre le problème de l'arrêt.

Définissons une fonction arret prenant en paramètres une fonction f et une entrée e pour f, qui va déterminer si f s'arrête sur e.

def arret(f, e):

On construit à partir de f une nouvelle fonction f1 qui, quelle que soit l'entrée, exécute f(e) et ne s'arrête donc que si f(e) s'arrête également.

def f1(x):

return f(e)

Notez qu'il s'agit d'une définition de fonction locale, placée à l'intérieur de la définition de arret.

Une telle fonction peut faire référence aux éléments locaux de la fonction englobante, ici en l'occurrence aux paramètres de arret.

Elle n'est en contrepartie pas directement accessible depuis l'extérieur.

On définit de même une fonction f2 qui ne s'arrête sur aucune entrée.

def f2(x):

while True:

pass

Ainsi, la fonction f1 est équivalente à la fonction f2 si et seulement si elle

ne s'arrête pour aucune entrée, c'est-à-dire si f(e) ne s'arrête pas.

Il suffit de nier le résultat de equivalentes(f1, f2) pour obtenir la réponse au problème de l'arrêt de f sur e.

return not equivalentes(f1, f2)

Nous aurions donc pu, à l'aide de la fonction equivalentes, définir une fonction décidant l'indécidable problème de l'arrêt.

Cette fonction equivalentes ne peut donc exister, et le problème de l'équivalence de deux algorithmes n'est donc pas décidable.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Pas d'indécidabilité sans infini

Aucun problème n'est indécidable lorsque l'on à la possibilité d'en explorer toutes les configurations en un temps fini, puisqu'il suffit alors de mener cette exploration exhaustive avant de renvoyer True où False.

Le problème de l'arrêt est indécidable

car le ruban de mémoire d'une machine de Turing est infini et qu'on ne peut donc pas borner à priori le nombre de configurations différentes de ce ruban rencontrées dans une exécution.

Ainsi, à strictement parler, l'arrêt d'un programme Python sur un ordinateur donné est décidable, du fait de la finitude de la mémoire de cet ordinateur.

Le nombre de configurations possibles (deux puissance le nombre de bits de la mémoire) est cependant tel que cette décidabilité n'est que théorique.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Indécidabilité mathématique / indécidabilité algorithmique.

La notion d'indécidabilité que nous décrivons ici, liée à Palgorithmique, est

absolument différente de celle existant en mathématiques.

En mathématique, on qualifie d'indécidable un énoncé dont on a pu

justifier qu'il ne pouvait ni être démontré ni être réfuté, un ensemble

d'axiomes étant donné. La notion concerne donc une formule qui n'est ni vraie ni fausse, et on parle également dans ce cas d'indépendance.

En algorithmique en revanche, nous avons vu que l'indécidabilité est une propriété d'un problème de décision, désignant l'impossibilité d'établir un algorithme répondant à coup sûr à une question donnée, pour toutes les entrées possibles.

On pourrait parler ici d'incalculabilité.

Le lien entre ces deux notions n'est pas conceptuel, mais historique :

l'indécidabilité mathématique est apparue avec les travaux de Kurt Güdel

en 1930, dont certaines techniques ont été réutilisées dans les travaux de Church et Turing sur l'indécidabilité algorithmique (en particulier une manière d'établir des correspondances entre des objets complexes et les nombres entiers, appelées codages de Güdel).

On prétend pourtant parfois que les concepts sont également liés, car le point de départ de l'indécidabilité algorithmique est l'Entscheidungsproblem, c'est-à-dire un problème de décision lié à la logique, mais il s'agit d'une contingence apportant plus de confusion qu'autre chose :

l'indécidabilité mathématique est une propriété d'une seule formule, alors que l'indécidabilité algorithmique de l'Entscheidungsproblem est une propriété d'un problème de décision relatif à l'ensemble des formules.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Indécidabilité des propriétés des programmes.

Avec les problèmes de détection des divisions par zéro, de l'arrêt, et de l'équivalence de deux algorithmes, nous avons déjà pu énoncer plusieurs propriétés des programmes qui étaient indécidables.

Il se trouve que, de manière générale, toute propriété non triviale à propos des programmes est de même indécidable.

La forme précise (et démontrée!) de cette allégation est appelée théorème de Rice.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Problème de correspondance de Post : un problème indécidable qui ne parle pas de programmes

Voici un petit puzzle:

on dispose d'un ensemble de dominos affichant de chaque côté une suite de symboles

et d'un domino de départ, par exemple celui de gauche.

On cherche à disposer des dominos côte à côte à la suite de notre domino de départ, de sorte à pouvoir lire la même suite de symboles en haut et en bas.

On se donne le droit d'utiliser chaque domino autant de fois que nécessaire.

On a par exemple ici la solution suivante dans laquelle les deux lignes jouent (pas exactement ensemble) la même mélodie «la re sol sol sol do re sol sol».

Notez que l'un des dominos à servi deux fois.

Si en revanche on n'avait eu à notre disposition que les dominos de gauche et de droite, ce puzzle n'aurait pas eu de solution.

Considérons maintenant le problème de décision suivant :

étant donnés un ensemble de dominos et un domino de départ, le puzzle correspondant a-t-il une solution?

Ce problème de décision est l'une des variantes du problème de correspondance de Post, du nom d'Emil Post son créateur.

Il s'agit d'un problème indécidable.

L'une des clés de l'indécidabilité de ce problème est que, lors de la construction d'une solution, le décalage entre la ligne du haut et la ligne du bas peut devenir arbitrairement grand.

On ne sait alors pas à coup sûr si les deux lignes finiront par se rattraper, terminant la construction.

La prouve d'indécidabilité du problème de Post, hors de portée du programme de lycée, montre que les dominos de Post et les suites de symboles qu'ils forment peuvent être utilisés pour simuler l'exécution de toute machine de Turing.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Un problème de décision est une question s'appliquant aux éléments d'un ensemble et à laquelle Ia réponse est, pour chaque

élément, soit oui soit non.

Un tel problème est dit décidable lorsqu'il existe un algorithme qui, pour chaque élément, calcule à coup sûr et en temps fini la réponse correspondante.

Il existe des problèmes qui ne sont pas décidables, à commencer par le problème de l'arrêt, qui s'applique à l'ensemble des algorithmes et demande de répondre à la question «l'exécution de cet algorithme s'arrête-t-elle ?».

La notion de décidabilité est indépendante du langage de programmation.

","title":"Conclusion","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Montrer qu'il n'existe pas de fonction Python prenant en entrée une fonction Python f, sans paramètre, et renvoyant True si et seulement si l'exécution f() de f s'arrête.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

En supposant qu’une telle fonction arret existe, on peut écrire la fonction paradoxale suivante.

def paradoxe ():

if arret (paradoxe):

while True:

pass

else:

return None

"}],[{"text":"

Simulation de la machine de Turing

On se propose d'écrire un programme simulant l'exécution d'une machine de Turing.

Fixons tout d'abord certains choix de représentation.

Un état de la machine est identifié par une chaîne de caractères.
Le symbole écrit dans une case du ruban est représenté par une chaîne de caractères.
L'ensemble des règles de transition de la machine est matérialisé par un dictionnaire dont les clés sont les états. Consulter ce dictionnaire pour un état donné fournit l'ensemble des règles applicables à partir de cet état, à nouveau sous la forme d'un dictionnaire, dont les clés sont les symboles manipulés par la machine et les valeurs sont les actions associées.
Les actions à effectuer à la lecture d'un symbole donné dans un état donné sont représentées par un triplet (e,d,s) où :

e est le symbole à écrire (une chaîne de caractères);
d est le déplacement éventuel:
—1 pour aller à gauche,
0 pour ne pas bouger,
1 pour aller à droite;
s est l'état suivant (une chaîne de caractères).

Une machine de Turing est donnée par un état de départ, un état final et un dictionnaire de règles de transition.

Lors de l'exécution de la machine, on fait évoluer une configuration formée d'un ruban mémoire, d'une identification de la position et de l'état courant de la machine.

Pour représenter le ruban, on utilise un tableau bidirectionnel tel que décrit dans la séquence 8 ( programmation objet).

class TaBiDir:

def __init__(self, g, d):

self.gauche = g[::-1]

self.droite = d[:]

def imin(self):

return - len(self.gauche)

def imax(self):

return len(self.droite) - 1

def append(self, v):

self.droite.append(v)

def prepend(self, v):

self.gauche.append(v)

def __getitem__(self, i):

if i >= 0:

return self.droite[i]

else:

return self.gauche[-i-1]

def __setitem__(self, i, v):

if i >= 0:

self.droite[i] = v

else:

self.gauche[-i-1] = v

Ce tableau ne pouvant pas être infini il ne contiendra que les cases effectivement utilisées, toutes les positions au-delà de ce qui est représenté dans le tableau étant réputées contenir le symbole ⚈.

Pour cela, le ruban est initialisé au début de l'exécution avec l'ensemble des cases représentant l'entrée, puis il est étendu à gauche ou à droite à chaque fois que la machine se déplace en dehors des

limites courantes.

Écrire une fonction prenant en paramètres la description d'une machine de ‘Turing M et une entrée e pour cette machine, et simulant l'exécution de la machine M sur l'entrée e.

Il est possible d'utiliser une ou plusieurs classes pour structurer les données manipulées et le code.

Tester ce simulateur avec la machine d'incrément de 1 donnée en exemple dans cette séquence.

regles_incr = {

'A': {'0' : ('0', 1, 'A'),

'1' : ('1', 1, 'A'),

None: (None, -1, 'B')},

'B': {'0' : ('1', 0, 'F'),

'1' : ('0', -1,'B'),

None: ('1', 0, 'F')}

}

machine_incr = MachineDeTuring('A','F',regles_incr)

calcule(machine_incr, ['1','0','0','1','1'])

calcule(machine_incr, ['1','1','1'])

calcule(machine_incr, [None])

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On propose de définir une première classe pour regrouper les différents éléments définissant une machine de Turing

class MachineDeTuring:

\"\"\"description d’une machine de Turing\"\"\"

def __init__(self, etat_initial, etat_final, regles):

self.etat_initial = etat_initial

self.etat_final = etat_final

self.regles = regles

et une seconde pour représenter une configuration de l’exécution.

class Configuration:

\"\"\"configuration d’une machine de Turing,

ruban bi-infini\"\"\"

def __init__(self, etat, entree):

self.etat = etat

self.pos = 0

self.ruban = TaBiDir([], entree)

Par convention, on placera l'entrée à partir de l'indice 0, qui est aussi l’indice de départ de la machine.

On inclut dans la classe Configuration une méthode pour l'affichage, qui donne le tableau des cases utilisées en ajoutant entre parenthèses l’état de la machine à côté du symbole de la case où se trouve la machine.

Les méthodes lit et evolue permettent respectivement d'obtenir le symbole lu par la machine et de faire évoluer la configuration en fonction du triplet indiqué par une règle de transition.

Notez que nous utilisons ici None pour représenter le symbole ⚈.

def __str__(self):

return str([str(self.ruban[i]) + '(' + self.etat + ')'

if i == self.pos

else str(self.ruban[i])

for i in range( self.ruban.imin(),

self.ruban.imax()+1)])

def lit(self):

return self.ruban[self.pos]

def evolue(self, e, d, s):

self.ruban[self.pos] = e

self.pos += d

if self.pos < self.ruban.imin():

self.ruban.prepend(None)

if self.pos > self.ruban.imax():

self.ruban.append(None)

self.etat = s

La fonction principale crée une configuration avec l'entrée fournie et l’état initial de la machine, puis applique les règles de transition jusqu’à atteindre l’état final de la machine.

def calcule(machine, entree):

config = Configuration(machine.etat_initial, entree)

print(config)

while config.etat != machine.etat_final:

e, d, s = machine.regles[config.etat][config.lit()]

config.evolue(e, d, s)

print(config)

print ('Calcul terminé')

Pour tester ce simulateur il faut d’abord construire une instance de

MachineDeTuring avec le bon dictionnaire de règles.

regles_incr = {

'A': {'0' : ('0', 1, 'A'),

'1' : ('1', 1, 'A'),

None: (None, -1, 'B')},

'B': {'0' : ('1', 0, 'F'),

'1' : ('0', -1,'B'),

None: ('1', 0, 'F')}

}

machine_incr = MachineDeTuring('A','F',regles_incr)

Ne reste plus qu’à observer le travail de la machine sur différentes entrées.

Notez que dans le code que nous avons donné, on suppose que la case d'indice 0 du ruban existe.

Si on veut donner l’entrée vide, il faut donc explicitement placer le symbole ⚈ (c’est-à-dire None) dans cette case.

calcule(machine_incr, ['1','0','0','1','1'])

calcule(machine_incr, ['1','1','1'])

calcule(machine_incr, [None])

"}],[{"text":"

Voici un ensemble de règles de transition pour une machine de Turing.

Son état initial est P et son état final F.

Avec quel alphabet travaille cette machine?

Quels sont les états de la machine?

L'exécuter sur l'entrée ['1', '0', '0', '1'],

puis sur l'entrée ['1', '1', '1', '0'],

en considérant à chaque fois qu'en dehors de cette entrée, la ruban est intégralement rempli avec le symbole blanc ⚈.

Comment se comporte-t-elle dans chacun des états?

Que fait cette machine?

Il ne faut pas hésiter à tester la machine sur d'autres entrées, y compris en utilisant le simulateur de l'exercice précédent.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

La machine travaille sur l'alphabet {0,1,⚈}, et ses états sont P, D0, D1, V0, Vi, R, E et F.

Les deux exécutions peuvent être

résumées ainsi en indiquant l’état de la machine dans la case correspondant à sa position.

Dans l’état P, la machine efface une case et retient son contenu.

Dans les états D0 et D1 elle se déplace jusqu’au bout de l’entrée.

Dans les états V0 et V1 elle vérifie que le contenu de la case correspond à la valeur mémorisée (et efface la case).

Dans l’état R elle revient au début de l’entrée pour reprendre à P.

Dans l’état E elle efface le ruban puis s'arrête.

Cette machine vérifie si l’entrée est un palindrome.

À la fin de l’exécution elle a vidé le ruban et simplement laissé écrit un 1 si l'entrée était un palindrome, et un 0 sinon.

Le retour à l’état P peut être vu comme un appel récursif à notre algorithme de vérification de palindrome, sur une entrée dont le premier et le dernier symbole ont été effacés.

Question subsidiaire : comment est gérée la reconnaissance des palindromes de longueur impaire?

Réponse : le plus simple pour cela est de

regarder le comportement de la machine sur une entrée composée d’un seul symbole.

On y voit notamment l’action des règles (C0,⚈) et (C1, ⚈).

"}],[{"text":"

Définir une machine de Turing qui décale son entrée d'une case vers la droite.

On supposera que l'entrée est composée des symboles 0 et 1 et bordée de symboles blancs ⚈.

On supposera également que la position

de départ de la machine est à l'extrémité gauche de l'entrée.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Exercice 136, page 282

On se donne un état initial Z, dans lequel la machine va écrire un symbole blanc à la place du premier symbole de l’entrée, puis deux états D0 et D1 indiquant qu'on est en train de décaler respectivement un 0 ou un 1.

La machine se déplace uniquement vers la droite et mémorise donc avec l’état D0 ou D1 le symbole lu sur la case précédente pour l’écrire à la case suivante.

La machine s’arrête (état final F) lorsqu'elle rencontre le symbole blanc suivant l'entrée.

"}],[{"text":"

Définir une machine de Turing qui, partant de l'extrémité gauche de son entrée, parcourt cette entrée à la recherche du symbole 0.

Si le symbole est trouvé elle devra écrire 1 dans la case précédent l'entrée, et sinon elle devra y écrire 0.

On supposera que l'entrée est composée de

symboles 0 et 1 et bordée de symboles blancs ⚈.

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On utilise trois états C, P et À en plus de l’état final F.

Dans l’état C (qui est l’état initial), la machine cherche une occurrence de 0.

Dans les états P et A, la machine revient à écrire son verdict.

La machine passe dans l’état P (présent) dès qu’elle observe un symbole 0.

Elle passe dans l’état A si elle atteint le blanc suivant l’entrée sans avoir rencontré de 0.

Notez que nous n’avons pas inclus de règles pour (P,0) et (A,0) car ces

situations ne doivent jamais se produire: la machine faisant demi-tour au premier 0 rencontré elle ne trouvera jamais un 0 sur son chemin retour.

La stratégie de cette machine peut faire penser au code de la fonction Python suivante.

def chercher_zero(entree):

for x in entree:

if x == 0:

return True

return False

"}],[{"text":"

Modifier la machine de l'exercice précédent pour détecter non pas les occurrences de 0 mais, les occurrences de plus de deux symboles 0 consécutifs.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On remplace l’unique état C' par trois états C, D1 et D2 signifiant respectivement «on cherche», «on vient de voir une occurrence de 0 » et « on vient de voir deux occurrences de 0 ».

Lors d’une séquence de plusieurs 0 consécutifs on progresse de C à D1 à D2 puis à P, mais dès que la séquence est coupée par un 1 on revient à C.

"}],[{"text":"

Supposons un ruban de machine de Turing dont une case contient le symbole 0, et tout le reste le symbole blanc ⚈.

Supposons que la machine se trouve à une certaine position du ruban, dont on ne sait pas si elle est à gauche ou à droite du symbole 0.

Donner un ensemble de règles permettant, à coup sûr, d'arriver en temps fini à la position contenant un 0.

On pourra utiliser un symbole au choix, par exemple l'astérisque *, pour laisser une marque sur une case.

Un objectif facultatif consiste à nettoyer le ruban de toutes les marques * utilisées avant de s'arrêter.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Il n’est pas envisageable de partir directement à gauche ou à droite jusqu’à rencontrer le 0, car on pourrait alors ne jamais s'arrêter si l’on choisissait la mauvaise direction.

On peut à la place aller alternativement vers la gauche ou la droite, à chaque fois d’une case plus loin que la précédente, en laissant des marques * dans les cases déjà explorées.

On utilise pour cela deux états D (exploration vers la droite) et G (exploration vers la gauche) en plus de l’état final F.

On peut choisir l'état initial arbitrairement entre G et D.

Pour nettoyer les marques il faut en plus, une fois le 0 trouvé, repartir en sens arrière jusqu’à un blanc, puis revenir.

Cela demande au total quatre états supplémentaires (aller et retour, avec le 0 trouvé à gauche ou à droite de la position de départ).

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 18 Octobre 2020; Mis à jour : 12 Décembre 2020; Clics : 1681

[[{"posi":0,"text":"

*******

Dans cette séquence, on s'intéresse au problème de la recherche des occurrences d'une chaîne de caractères, que l'on appellera motif, dans une autre chaîne de caractères, que l'on appellera texte.

Par exemple, il y a deux occurrences du motif \"bra\" dans le texte \"abracadabra\".

Plus précisément, on va chercher à quelles positions dans le texte le motif apparaît.

En numérotant les positions à partir de 0, on a donc une occurrence de \"bra\" à la

position 1 (le deuxième caractère du texte) et une autre à la position 8 (le

neuvième caractère du texte).

Notre objectif dans cette séquence est d'écrire une fonction recherche qui affiche les positions de toutes les occurrences d'un motif dans un texte.

Ainsi, l'appel à

recherche(\"bra\", \"abracadabra\")

devra afficher ceci:

occurrence à la position 1

occurrence à la position 8

On commence par quelques rappels sur les chaînes de caractères de Python.

Une chaîne de caractères peut être écrite au choix entre apostrophes (caractère ') ou entre guillemets (caractère \").

Ainsi, on peut écrire indifféremment 'abracadabra' ou \"abracadabra\".

Nous utiliserons la seconde forme, plus répandue dans les autres langages de programmation.

La longueur d'une chaîne s est obtenue avec len(s).

Les caractères sont numérotés à partir de 0.

Le (i + 1)-ième caractère est obtenu avec s[i] pour 0 ≤ i < len(s).

La sous-chaîne de s contenant les caractères i inclus à j exclu est obtenue avec s[i:j]. Il s'agit d'une nouvelle chaîne de caractères, la chaîne s n'étant pas modifiée.

D'une manière plus générale, les chaînes

de caractères sont immuables.

Les caractères et les chaînes peuvent être comparés avec l'opérateur ==.

Dans tout cette séquence, on note m le motif que l'on recherche et t le texte dans lequel on le recherche.

On note M la longueur du motif et N la

longueur du texte.

Une première remarque évidente est qu'il ne peut y avoir une occurrence de< m dans t que si M≤N.

Plus précisément, une occurrence de m dans t à la position i est contrainte par l'inégalité 0 ≤ i < N - M. En particulier, la chaîne vide \"\", qui à une longueur N = 0, apparaît à toutes les positions dans le texte t, pour N + 1 occurrences au total.

Il est utile de se représenter une occurrence de m dans t à la position i

comme ceci:

Au dessus, on a représenté les indices des caractères du texte, qui vont de 0

inclus à N exclu.

En dessous, on a représenté les indices des caractères du motif, qui vont de 0 inclus à M exclu.

S'ii y a une occurrence à la position i, alors les caractères t[i],...,t[i + M - 1] du texte coïncident avec les caractères m[0],...,m[M — 1] du motif.

","title":"Recherche textuelle","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Commençons par une première version de notre fonction recherche, la plus simple possible.

Il suffit de considérer successivement toutes les positions possibles pour une occurrence, c'est-à-dire tous les entiers entre 0 et N—M, et de tester pour chacun si la sous-chaîne de t à cette position est égale au motif m.

On peut le faire en trois lignes de code:

def recherche(m, t):

for i in range(0, len(t) - len(m) + 1):

if t[i : i + len(m)] == m :

print (\"occurrence à la position\", i)

Tester la fonction recherche avec le code suivant:

recherche(\"bra\",\"abra-abracadabra\")

Ici, on a utilisé l'opération d'extraction de sous-chaîne de Python pour extraire la chaîne constituée des len(m) caractères situés à la position i dans t, pour la comparer ensuite à m.

Bien que très simple à écrire, cette fonction est assez naïve. En effet, on

va systématiquement construire la sous-chaîne, avec l'opération t[:], pour ensuite la comparer à m.

Or, l'extraction de la sous-chaîne a un coût, qui est proportionnel au nombre de caractères, ici M=len(m).

Comme on va répéter cette opération N — M + 1 fois, on a un coût total Mx(N - M +1).

Si par exemple on cherche un motif de 1000 caractères dans un texte de 2000 caractères, on va faire un peu plus d'un million d'opérations. Or, s'il s'avère que la comparaison échoue rapidement, on aura construit toutes ces sous-chaînes inutilement.

C'est le cas par exemple si on recherche un motif qui contient 1000 caractères a dans un texte qui contient 2000 caractères b.

La comparaison va échouer ystématiquement sur le tout premier caractère, mais on aura néanmoins construit 1001 fois une chaîne de longueur 1000.

","title":"Un algorithme simple","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Pour y remédier, il suffit de comparer directement la chaîne m avec la sous-chaîne contenue dans t à la position i, caractère par caractère, sans utiliser l'opération t[i:i+len(m)].

On peut le faire avec une boucle qui parcourt les caractères de m et les compare aux caractères de t.

On l'écrit sous la forme d'une fonction occurrence(m, t, i) qui renvoie True si et seulement s'il y a une occurrence de m dans t à la position i.

Cette fonction est donnée dans le programme ci-dessous.

Programme — recherche textuelle simple

def occurrence(m, t, i):

\"\"\"indique s'il y a une occurrence de la chaîne m

dans la chaîne t à la position i\"\"\"

if i < 0 or i > len(t) - len(m):

return False

for j in range(len(m)):

if t[i + j] != m[j]:

return False

return True

def recherche1(m, t):

\"\"\"affiche toutes les occurrences de m dans t\"\"\"

for i in range(0, len(t) - len(m) + 1):

if occurrence(m, t, i):

print(\"occurrence à la position\", i)

Elle commence par exclure les cas absurdes où i ne désigne par une position légale dans le texte.

Dans notre cas, nous l'appellerons toujours avec une position légale, mais un code un peu défensif est une bonne pratique.

La fonction compare ensuite les caractères un par un, avec une boucle for, et renvoie False dès qu'il y a une différence.

C'est là tout l'intérêt par rapport à notre première solution.

Si enfin on sort de la boucle, c'est que tous les caractères sont identiques et la fonction renvoie True.

Il est facile d'en déduire une nouvelle fonction recherche, plus efficace.

Elle est donnée dans le programme ci-dessus.

C'est la même fonction que notre première version, où le test occurrence(m,t,i) remplace le test t[i:i+len(m)] == m.

On peut se persuader que cette deuxième version est plus efficace que la première en reprenant l'exemple de la recherche d'un motif contenant 1000 caractères a dans un texte contenant 2000 caractères b.

On a toujours une boucle testant les 1001 valeurs possibles pour i, mais chaque test est maintenant instantané car la fonction occurrence renvoie False dès sa première comparaison.

On a donc au total un millier d'opérations, au lieu d'un million précédemment.

Dans d'autres cas de figure, cependant, notre second programme n'est pas meilleur que le premier.

C'est le cas si tous les caractères doivent être comparés à chaque fois.

Ainsi, si on recherche un motif formé uniquement de caractères a dans un texte également formé uniquement de caractères a, alors on aura un nombre maximal de comparaisons, à savoir Mx(N — M +1).

Le même phénomène peut également se produire sans qu'il y ait pour autant d'occurrence.

Ainsi, si on ajoute un caractère b à la fin du motif, c'est-à-dire si l'on cherche le motif aa...ab dans un texte aa.....aa, alors on fera également Mx(N — M +1) comparaisons au total. En effet, seule la dernière comparaison effectuée par la fonction occurrence est négative.

On peut cependant faire mieux que cet algorithme simple, et c'est ce que nous allons voir maintenant.

Tester la fonction recherche avec le code suivant:

recherche(\"bra\",\"abra-abracadabra\")

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Le programme précédent effectue une comparaison entre le motif cherché et

chacune des sous-chaînes de longueur M du texte.

Cette comparaison elle-même est accélérée, dans le sens où elle s'interrompt à la première différence trouvée, mais elle doit bien être faite pour tous les indices i de départ jusqu'à la valeur maximale plausible N — M.

","title":"Accélération de la recherche"},{"edit":"

"}],[{"text":"

Accélérer en sautant certaines sous-chaînes

Une deuxième idée consiste à ne pas appliquer la comparaison à toutes les sous-chaînes, en ignorant certains indices à pour lesquels on a des raisons

d'être certain que le résultat ne peut pas être positif.

Pour l'illustrer, considérons la recherche du motif

m = \"bra\"

dans le texte t = \"bricabrac\".

Lorsque l'on compare le troisième caractère du motif “bra\" avec le caractère correspondant de la sous-chaîne \"bri\" commençant à l'indice i = 0, on apprend certes que cette première sous-chaîne n'est pas une occurrence du motif, mais on remarque également au passage que

le caractère à l'indice 2 est un 'i'. Or, notre motif ne contient aucune occurrence de ce caractère!

Ainsi, aucune sous-chaîne du texte contenant ce caractère \"i\" ne peut être une occurrence du motif.

Il est donc inutile de considérer les sous chaîne \"ri\" et\"Ica\" commençant aux indices i = 1 et i = 2, et l'on peut directement passer à la sous-chaîne \"cab\" commençant à l'indice i = 3.

Considérons maintenant la recherche du motif

m = \"adabrica\"

dans le texte

t = “abracadabracadabricadabra\",

et en particulier la comparaison avec la sous-chaîne \"adabraca\" commençant à l'indice i = 5.

La comparaison du sixième caractère (à l'indice j = 5) nous apprend que cette sous-chaîne n'est pas une occurrence du motif, mais aussi que le caractère à l'indice i + j = 10 dans le texte est un \"a\".

Ainsi, on sait qu'à moins de dépasser complètement cette partie du texte, seuls les indices i faisant en sorte que ce 'a' du texte corresponde à l'un des 'a' du motif sont intéressants. Faisons l'inventaire des occurrences du caractère 'a' dans le motif :

nous en avons trois, aux indices j=0, j=2 et j=7.

Ces trois occurrences sont en correspondance avec le caractère 'a' à

l'indice i + j = 10 dans le texte pour les valeurs respectives 10, 8 et 3 de i.

À l'inverse, on déduit qu'il est inutile de considérer les valeurs 4,5,6,7 et 9 de t, car elles placeraient des caractères différents de 'a' en correspondance avec le 'a' situé à l'indice i + j = 10 du texte.

Parmi les trois valeurs 3, 8 et 10, laquelle choisir comme indice de début de la prochaine sous-chaîne à prendre en compte?

L'indice i = 3, correspondant à l'occurrence de ‘a' à l'indice j=7 dans le motif, est hors jeu:
notre exploration était déjà arrivée i = 5 et ne fait que progresser.
L'indice i = 10, correspondant à l'occurrence de 'a' à l'indice j = 0 dans le motif, serait tentant car c'est lui qui fait progresser le plus vite dans la lecture du texte. Il risquerait cependant d'aller trop vite et de nous faire manquer une occurrence intermédiaire du motif.

L'indice i = 8, correspondant à l'occurrence de 'a' à l\"indice j = 2 dans

le motif, est le seul candidat possible.

Notez que cette occurrence peut être caractérisée comme «la dernière occurrence de 'a' avant l'indice j=5 du

motif».

En synthétisant les deux exemples précédents, on peut proposer la stratégie suivante:

Si la sous-chaîne commençant à l'indice i est égale au motif cherché, indiquer une occurrence et reprendre à l'indice i+1.
Sinon, si l'on a observé une différence entre le caractère à l'indice j du motif et le caractère à l'indice i + j = k du texte, incrémenter i jusqu'à ce que:

soit i dépasse k,
soit le caractère à l'indice k-i du motif soit égal au caractère à l'indice i du texte.

Puis reprendre avec le i ainsi obtenu.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Accélérer en précalculant les sauts

La stratégie que nous venons d'énoncer semble gagner en efficacité par rapport à celle d'origine, puisqu'elle permet de sauter certaines valeurs de i.

Ces sauts ne sont cependant pas complètement gratuits:

chacun revient à parcourir une partie du motif, à la recherche de la dernière occurrence passée du caractère observé.

Or, si l'on recherche le même motif m dans plusieurs textes différents, ou dans un texte très grand, les mêmes recherches de dernière occurrence d'un certain caractère risquent d'être faites un grand nombre de fois.

Il peut alors être avantageux d'effectuer un pré-traitement du motif afin de pré-calculer tous les sauts dont on pourra avoir besoin et les enregistrer dans une structure de données adaptée.

Dans ce cas, au moment où viendra une opportunité de sauter certains indices i, il suffira de consulter cette structure de données pour savoir directement le nombre d'indices qui peuvent être sautés.

Avec un tel pré-traitement, on sacrifie un peu de temps avant de commencer la recherche, pour ensuite accélérer la recherche elle-même.

Une telle opération a de bonnes chances d'être gagnante si les opérations accélérées arrivent souvent.

L'algorithme de Boyer-Moore que nous allons voir maintenant réalise cette stratégie avec prétraitement, en y ajoutant une dernière optimisation peut-être un peu plus surprenante.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

L'algorithme de Boyer-Moore utilise un pré-traitement du motif m à chercher dans un texte t pour accélérer cette recherche.

Son principe est le suivant:

On va tester l'occurrence du motif m dans le texte t à des positions i de plus en plus grandes, en partant de i=0. Cela n'est pas différent pour l'instant de ce que nous avons fait dans les sections précédentes.
Pour une position i donnée, on va comparer les caractères de m et de t de la droite vers la gauche, c'est-à-dire en comparant d'abord m[M-1]
et t[i+ M — 1], puis m[M — 2] et t[i + M — 2], etc. Il s'agit là du sens inverse de celui utilisé au début de cette séquence. Le changement peut paraître anecdotique, mais en pratique il permet d'avancer plus vite dans certains cas (dont nous discuterons plus loin).
Si tous les caractères coïncident, on à trouvé une occurrence. Sinon, soit j l'indice de la première différence, c'est-à-dire le plus grand entier tel que 0 ≤ j < M et m[j] ≠ t[i+j].

Appelons c le caractère t[i+j].

L'idée de l'algorithme de Boyer-Moore consiste à augmenter alors la valeur de i de:

la grandeur j — k où k est le plus grand entier tel que 0 ≤ k < j et m[k] = c, si un tel k existe (de manière à amener un caractère c de m sous le caractère t[i+ j]),
la grandeur j + 1 sinon.

Plutôt que de rechercher un tel k à chaque fois, on peut pré-calculer

une table de décalages contenant, à la case indexée par l'entier j et le caractère c, le plus grand entier k tel que 0 ≤ k < j et m[k] = c s'il existe, et rien sinon.

","title":"Un algorithme plus efficace : Boyer-Moore"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Exemple

Supposons que l'on recherche le motif m = \"abracadabra\".

On est en train de tester l'occurrence de ce motif à une certaine position i dans le texte.

Comme indiqué précédemment, on procède de droite à gauche, en commençant par la fin du motif.

Supposons que les cinq premières comparaisons de caractères ont été positives, c'est-à-dire que les cinq dernières lettres du motif (dabra) coïncident avec les caractères «en face» dans le texte.

Supposons enfin que le caractère suivant

dans le texte ne coïncide pas, car il

s'agit du caractère b alors que le motif a un caractère 'a' à cette position.

La situation s'illustre donc ainsi:

On consulte alors la table de décalages, pour l'indice j = 5 (la position dans

le motif) et pour le caractère b (le caractère du texte).

La table indique la valeur 4, ce qui veut dire qu'il faut décaler le motif de quatre positions vers la droite.

Cela a pour effet d'amener le caractère b en deuxième position dans le motif sous le caractère b du texte.

Si en revanche le caractère du texte avait été z, alors la table n'aurait pas contenu d'entrée pour ce caractère, car il n'y a pas d'occurrence de z dans les cinq premiers caractères du motif.

On aurait alors décalé le motif de j + 1 = 6 positions vers la droite.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Représenter la table de décalages

La table de décalages est une table à deux clés:

d'une part l'indice j du caractère du motif qui diffère et d'autre part le caractère c du texte.

Pour la première clé, c'est-à-dire l'indice j, on peut utiliser un tableau de taille M.

Pour la seconde clé, c'est-à-dire le caractère c, on ne va en revanche pas utiliser un tableau, car les caractères possibles sont trop nombreux et la table occuperait trop de place en mémoire.

En effet, seuls les caractères apparaissant effectivement dans le motif sont pertinents comme entrées dans cette table, car il s'agit de décalages amenant un caractère du motif sous celui du texte.

Ainsi, pour le motif m = \"abracadabra\", seuls cinq caractères sont significatifs, à savoir a, b, r, c et d.

D'autre part, certaines entrées de la table sont vides, quand il n'y à pas de décalage possible.

D'où l'idée d'utiliser un dictionnaire associant à certains caractères un décalage, et ne mentionnant pas les autres caractères.

On à représenté ci-contre la table de décalages pour le motif m=\"abracadabra\".

Il s'agit d'un tableau de taille M = 11, où chaque élément, c'est-à-dire chaque ligne ici, est un dictionnaire dont les clés constituent un sous-ensemble de {a,b,r,c,d}.

Dans cette table, on retrouve par exemple l'entrée pour j = 5 et c = b prise en exemple plus haut, avec la valeur 1.

Cette valeur est l'indice de l'occurrence du caractère b le plus à droite dans le motif avant l'indice j = 5.

Le décalage s'en déduit comme j — 1 = 5 — 1 = 4.

On prendra le temps de bien comprendre cette table.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Utilisation de la table de décalages

Avant d'expliquer comment construire cette table, montrons comment l'utiliser.

Notre objectif est toujours d'écrire une fonction recherche recevant m et t en arguments.

On commence par construire la table de décalages, avec une fonction table_bm que nous détaillerons plns loin.

def recherche(m, t):

d = table_bm(m)

Il s'agit ensuite de tester des positions successives du motif dans le texte.

Comme on ne va pas tester toutes les positions, on utilise une boucle while

plutôt qu'une boucle for.

On démarre avec la position i = 0.

    i = 0\n    while i <= len(t) - len(m):

On va maintenant comparer les caractères un par un, en partant de la droite.

On retient dans une variable k le décalage trouvé, le cas échéant.

        k = 0\n        for j in range(len(m) - 1, -1, -1):\n

Dès qu'il y a une différence entre le motif ct le texte, on calcule le décalage

avec une fonction decalage, détaillée plus loin, qui reçoit en arguments la table de décalages d, l'indice j et le caractère du texte.

           if t[i + j] != m[j]:\n                k = decalage(d, j, t[i + j])\n                break

Une fois sorti de la boucle, il y à deux cas de figure.

Soit une différence a été trouvée entre le motif et le texte, et alors la valeur de k est différente de 0. (On verra plus loin que la fonction decalage a toujours un résultat au moins égal à 1.)

Soit k vaut toujours 0, ce qui signifie qu'on a trouvé une occurrence.

On affiche alors l'occurrence et on donne à k la valeur 1, de manière à avancer dans le texte.

         if k == 0:\n          print(\"occurrence à la position\", i)\n            k = 1\n

Enfin, on passe à la position suivante en ajoutant à i la valeur de k, ce qui est correct dans les deux cas de figure.

       i += k

Le code de cette nouvelle fonction recherche est donné dans le programme ci-dessous.

Ce programme contient également le code de la fonction decalage.

Cette fonction consulte la table d pour l'indice j et le caractère c, en prenant soin de tester si l'entrée existe ou non.

Pour cela, elle teste si c est une clé du dictionnaire d[j], avec le booléen c in d[j]. Le cas échéant, elle renvoie le décalage, c'est-à-dire la différence j - d[j][c].

Dans le cas contraire, cela signifie que le caractère c n'apparaît pas dans m[0:j] et le décalage renvoyé est donc j+1.

Programme — L'algorithme de Boyer-Moore

def table_bm(m):

\"\"\"construit la table de décalages de Boyer-Moore :

d[j][c] est le plus grand k < j tel que m[k] == c,

s'il existe, et n'est pas défini sinon\"\"\"

d = [{} for _ in range(len(m))]

for j in range(len(m)):

for k in range(j):

d[j][m[k]] = k

return d

def decalage(d, j, c):

\"\"\"utilise la table d lorsque le caractère j est c

au lieu du caractère attendu\"\"\"

if c in d[j]:

# c apparaît en d[j][c] et on décale de la différence

return j - d[j][c]

else:

# c n'apparaît pas du tout dans m[0..j-1]

return j + 1

def recherche2(m, t):

\"\"\"affiche toutes les occurrences de m dans t

avec l'algorithme de Boyer-Moore\"\"\"

d = table_bm(m)

i = 0

while i <= len(t) - len(m):

k = 0

for j in range(len(m) - 1, -1, -1):

if t[i + j] != m[j]:

k = decalage(d, j, t[i + j])

break

if k == 0:

print(\"occurrence à la position\", i)

k = 1

i += k

Tester la fonction recherche2 avec le code suivant:

recherche2(\"bra\",\"abra-abracadabra\")

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Construction de la table de décaiages

Il reste à expliquer comment construire la table de décalages, ce qui correspond à la fonction table_bm.

Cette fonction reçoit le motif m en argument.

def table_bm(m):

Elle commence par construire un tableau de taille len(m), où chaque élément est un dictionnaire vide.

     d = [{} for _ in range(len(m))]

Comme pour une matrice, on prend bien soin de ne pas écrire [{}] * m.

On remplit alors tous ces dictionnaires, avec une double boucle sur tous les indices j et sur tous les indices k < j.

    for j in range(len(m)):\n        for k in range(j):\n

Pour chaque paire d'indices j et k, il suffit de renseigner la clé m[k] du dictionnaire d[j] avec la valeur k.

            d[j][m[k]] = k

Comme on parcourt les indices k du plus petit au plus grand, plusieurs occurrences d'un même caractère vont donner plusieurs affectations dans le dictionnaire, chacune écrasant la précédente.

Ainsi, on aura bien au final dans d[j][c] le plus grand k tel que k < j et m[k] = c.

On termine en renvoyant la table.

    return d

Le code de cette fonction table_bm est également donné dans le programme précédent.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Efficacité

Quelle est l'efficacité de l'algorithme de Boyer-Moore?

Commençons par rappeler que le coût de l'appel à la fonction decalage est constant. En effet, on y fait d'abord un accès dans un tableau, avec d[j], puis une recherche dans un dictionnaire, avec c in d[j] et d[j][c].

Toutes ces opérations sont de temps constant en Python.

Dans le pire des cas, la comparaison entre le motif et le texte se fait systématiquement jusqu'au bout du motif, c'est-à-dire jusqu'à j = 0.

C'est le cas par exemple si on recherche le mot abbb...btb dans le texte bbbb.. bb (aucune occurrence) ou le mot bbb...bb dans ce même texte bbbb...bb (une occurrence à chaque position}.

Dans les deux cas, le nombre total de comparaisons de caractères est Mx(N — M +1), ce qui n'est pas meilleur qu'avec

la recherche simple du programme recherche.

C'est même pire dans le premier cas.

Dans le meilleur des cas, en revanche, la comparaison peut être négative immédiatement, dès Le premier caractère testé, c'est-à-dire pour j = M —1, et le décalage être aussi grand que M.

C'est le cas par exemple si on recherche

le mot aaa...aa dans le texte bbb...bb.

Le nombre total de comparaisons sera alors N/M, car on ne compare plus qu'un caractère sur M.

Ainsi, si on cherche les occurrences d'un motif contenant 1000 caractères a dans un

texte contenant 2000 caractères b, on ne fora que deux comparaisons!

Cet exemple extrême illustre notamment l'intérêt d'avoir procédé de la droite vers la gauche.

Entre ces deux cas de figure, on trouve une multitude de situations intermédiaires, où le coût de la recherche varie beaucoup avec le motif et avec le texte.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Plus efficace encore

La table de décalages de l'algorithme de Boyer-Moore peut être encore améliorée.

Reprenons l'exemple donné plus haut où, après avoir comparé avec succès les cinq derniers caractères du motif “abracadabra\", on tombe sur le caractère b dans le texte:

Telle qu'elle est construite actuellement, notre table indique un décalage de 4 caractères (pour amener le b en seconde position du motif sous le b

du texte).

Cependant, cela aura pour effet de placer les caractères racad sous les caractères déjà reconnus dabra.

Comme ils ne coïncident pas, on voit qu'on aurait pu proposer un décalage encore plus grand.

En l'occurrence, on aurait pu décaler de 7 caractères, pour amener ici le abra du début du motif sous le abra contenu dans le texte.

Comme de tels décalages ne font intervenir que des caractères du motif, ils peuvent également être pré-calculés.

Mais cela dépasse largement le programme

de terminale.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

La recherche textuelle consiste à rechercher la première occurrence, ou toutes les occurrences, d'une chaîne de caractères dans une autre.

Une recherche naïve peut avoir un coût prohibitif.

Ainsi, chercher un motif de mille caractères dans un texte de quelques milliers de caractères peut demander des millions d'opérations.

Il existe cependant des algorithmes plus efficaces, tels que l'algorithme de Boyer-Moore.

Ce dernier effectue un pré-traitement du motif, afin d'accélérer sa recherche dans un texte très grand où dans plusieurs textes.

","title":"Conclusion","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

def occurrence(m, t, i):

\"\"\"indique s'il y a une occurrence de la chaîne m

dans la chaîne t à la position i\"\"\"

if i < 0 or i > len(t) - len(m):

return False

for j in range(len(m)):

if t[i + j] != m[j]:

return False

return True

def recherche1(m, t):

\"\"\"affiche toutes les occurrences de m dans t\"\"\"

for i in range(0, len(t) - len(m) + 1):

if occurrence(m, t, i):

print(\"occurrence à la position\", i)

Avec le programme ci-dessous, combien de comparaisons de caractères sont effectuées pendant le calcul de

recherche1(\"chercher\",\" chercher, rechercher et chercher encore\")

Indice : Vous pouvez ajouter un compteur dans la fonction.

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Il y a 65 comparaisons au total, certaines positives, d’autres négatives.

"}],[{"text":"

Écrire une fonction

premiere_occurrence(m, t)

qui renvoie la position de la première occurrence de m dans t, s'il y en a une, et None sinon.

On pourra se resservir de la fonction occurrence du programme recherche1.

def occurrence(m, t, i):

\"\"\"indique s'il y a une occurrence de la chaîne m

dans la chaîne t à la position i\"\"\"

if i < 0 or i > len(t) - len(m):

return False

for j in range(len(m)):

if t[i + j] != m[j]:

return False

return True

Tester avec:

print(premiere_occurrence(\"chercher\",\" chercher, rechercher et chercher encore\"))

print(premiere_occurrence(\"trouver\",\" chercher, rechercher et chercher encore\"))

Résultat:

None

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def premiere_occurrence(m, t):

\"\"\"renvoie la première occurrence de m dans t,

Le cas échéant, et None sinon\"\"\"

for i in range(0, len(t) - len(m) + 1):

if occurrence(m, t, i):

return i

return None

"}],[{"text":"

Construire (à la main) la table de décalages de l'algorithme de Boyer-Moore pour le motif \"banane\".

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On note que le caractère e n’apparaissant qu’en dernière position, on a une colonne entièrement vide.

"}],[{"text":"

Construire (à la main) la table de décalages de l'algorithme de Boyer-Moore pour le motif \"chercher\".

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

"}],[{"text":"

Exercice 132

En utilisant le résultat de l'exercice précédent, dérouler manuellement l'exécution du programme recherche2 pendant le calcul de

recherche2(\"chercher\", \"chercher, rechercher et chercher encore\")

en donnant notamment les valeurs successives de la variable i.

Indiquer le nombre total de comparaisons de caractères.

Comparer avec le résultat du programme recherche 1.

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

La variable i prend successivement les valeurs :

0 (occurrence, qui donne le décalage 1)
1 (qui donne le décalage 8),
9 (décalage 3),
12 (occurrence, décalage 1),
13 (décalage 8),
21 (décalage 3),
24 (occurrence, décalage 1),
25 (décalage 8).

La dernière valeur prise par i est 33 et on sort alors de la boucle car cette valeur dépasse len(t) — len(m) = 39 - 8 = 31.

Il y a 29 comparaisons au total (certaines positives, d’autres négatives).

"}],[{"text":"

def recherche(m, t):

for i in range(0, len(t) - len(m) + 1):

if t[i : i + len(m)] == m :

print (\"occurrence à la position\", i)

Écrire une fonction mesure_rec1 qui renvoie le temps de recherche de toutes les occurrences d’un motif dans un texte avec l’algorithme naif.

Testez-la avec le texte suivant :

\"Apprendre à coder, c'est comme apprendre la musique : il faut connaître ses gammes pour devenir un Mozart ou un Beethoven de l'informatique.\"

et le motif : \"Mozart\"

Modifier le programme recherche pour ajouter un un compteur pour déterminer le nombre de comparaisons effectuées avec cet algorithme.

Tester avec:

texte = \"Apprendre à coder, c'est comme apprendre la musique : il faut connaître ses gammes pour devenir un Mozart ou un Beethoven de l'informatique.\"

motif = \"Mozart\"

mesure_rec1(motif,texte)

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Temps:

def mesure_rec1(m,t):

start = time.time()

recherche(m ,t)

end = time.time() - start

print(\"algo naif\",end)

Compteur:

def recherche(m, t):

cpt = 0

for i in range(0, len(t) - len(m) + 1):

cpt+=1

if t[i : i + len(m)] == m :

print (\"occurrence à la position\", i)

print(\"Nb comparaisons : \",cpt)

"}],[{"text":"

def table_bm(m):

\"\"\"construit la table de décalages de Boyer-Moore :

d[j][c] est le plus grand k < j tel que m[k] == c,

s'il existe, et n'est pas défini sinon\"\"\"

d = [{} for _ in range(len(m))]

for j in range(len(m)):

for k in range(j):

d[j][m[k]] = k

return d

def decalage(d, j, c):

\"\"\"utilise la table d lorsque le caractère j est c

au lieu du caractère attendu\"\"\"

if c in d[j]:

# c apparaît en d[j][c] et on décale de la différence

return j - d[j][c]

else:

# c n'apparaît pas du tout dans m[0..j-1]

return j + 1

def recherche3(m, t):

\"\"\"affiche toutes les occurrences de m dans t

avec l'algorithme de Boyer-Moore\"\"\"

d = table_bm(m)

i = 0

while i <= len(t) - len(m):

k = 0

for j in range(len(m) - 1, -1, -1):

if t[i + j] != m[j]:

k = decalage(d, j, t[i + j])

break

if k == 0:

print(\"occurrence à la position\", i)

k = 1

i += k

Écrire une fonction qui renvoie le temps de recherche de toutes les occurrences d’un motif dans un texte avec l’algorithme Boyer-Moore-Horspool.

Testez-la avec le texte suivant :

\"Apprendre à coder, c'est comme apprendre la musique : il faut connaître ses gammes pour devenir un Mozart ou un Beethoven de l'informatique.\"

et le motif : \"Mozart\"

Modifier le programme recherche pour ajouter un un compteur pour déterminer le nombre de comparaisons effectuées avec cet algorithme.

Tester avec:

texte = \"Apprendre à coder, c'est comme apprendre la musique : il faut connaître ses gammes pour devenir un Mozart ou un Beethoven de l'informatique.\"

motif = \"Mozart\"

mesure_rec2(motif,texte)

Comparer les 2 algorithmes de recherches par rapport à vos résultats.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Temps :

def mesure_rec2(m,t):

start = time.time()

recherche3(m ,t)

end = time.time() - start

print(\"algo Boyer-Moore\",end)

Compteur :

def recherche3(m, t):

\"\"\"affiche toutes les occurrences de m dans t

avec l'algorithme de Boyer-Moore\"\"\"

d = table_bm(m)

i = 0

cpt=0

while i <= len(t) - len(m):

k = 0

for j in range(len(m) - 1, -1, -1):

cpt+=1

if t[i + j] != m[j]:

k = decalage(d, j, t[i + j])

break

if k == 0:

print(\"occurrence à la position\", i)

k = 1

i += k

print(\"Nb comparaisons : \",cpt)

"}],[{"text":"

Maintenant vous allez comparer les deux algorithmes sur un texte plus long en faisant varier le motif.

1. Télécharger (ici) et importer le fichier texte livre.txt qui propose le roman «Le Rouge et le Noir» écrit en 1830 par l’écrivain Stendhal (1783-1842).

2. Testez vos fonctions de recherche sur ce texte avec quelques mots comme \"Mozart\", \"esprit\", \"est\", \"les\".

Puis avec la lettre \"e\",

Que remarquez-vous?

3. Mettez les résultats dans un tableau avec le nombre de comparaison.

Conclure.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

with open(\"livre.txt\",\"r\") as f:

texte = f.read()

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 18 Octobre 2020; Mis à jour : 7 Décembre 2020; Clics : 1687

[[{"text":"

Alice pose le problème suivant à Basile.

Elle dessine sur une feuille de papier une petite grille 2 x 3

et demande à Basile combien de chemins mènent du coin supérieur gauche (D) au coin inférieur droit (A), en se déplaçant uniquement le long de traits horizontaux vers la droite et le long de traits verticaux vers le bas.

Basile entame une énumération exhaustive mais perd rapidement le compte des chemins qu'il a ou non déjà construits.

Basile à alors l'idée de noter, à côté de chaque intersection, le nombre total de chemins qui mènent au coin inférieur droit.

Il commence naturellement par la fin et procède vers le haut et vers la gauche.

Ainsi, Basile n'a pas besoin de recompter à chaque fois le nombre de chemins pour les intersections qu'il à déjà traitées et il ne se perd plus dans ses caiculs.

Il parvient rapidement à ses fins avec la grille ainsi complétée qu'il montre fièrement à Alice en lui indiquant que la réponse est 10.

Alice remarque alors que chaque nombre est la somme du nombre situé à droite et du nombre situé en-dessous, ce que Basile confirme en expliquant qu'un chemin partira soit vers la droite, soit vers le bas.

Tout excités, Alice et Basile mettent à profit cette idée pour calculer en quelques instants qu'il y a 184756 chemins sur une grille 10 x 10.

Alice et Basile viennent d'inventer la programmation dynamique.

D'une manière générale, la programmation dynamique est une technique consistant à faire en sorte de ne pas calculer plusicurs fois la même chose, en stockant des résultats intermédiaires dans une structure de données.

Dans l'exemple ci-dessus, un tableau à deux dimensions permettrait de stocker les nombres de chemins déjà calculés.

Dans cette séquence, on illustre la programmation dynamique sur deux exemples

le rendu de monnaie
et l'alignement de séquences.

D'autres exemples sont proposés en exercices, dont le calcul des chemins donné en exemple ci-dessus.

","title":"Programmation dynamique","tagtitle":"h1"},{"edit":"

"}],[{"text":"

Considérons le problème du rendu de monnaie, déjà abordé dans le programme de première.

On suppose un système monétaire utilisant des pièces, avec un certain nombre de pièces de différentes sortes, chacune ayant une valeur entière différente.

Par exemple, on peut imaginer un système avec trois sortes de pièces, avec les valeurs 1, 2 et 5. $\"Pièces$

Source:https://123montessori.fr/monnaie-pieces-et-billets-en-euro-259

On se pose alors la question, pour un système donné, du nombre minimal de pièces qui est nécessaire pour réaliser une somme donnée.

Ainsi, il faut au minimum 3 pièces pour réaliser la somme 12 avec le système ci-dessus.

Mais il n'en faudrait que 2 dans un système qui proposerait des pièces de valeurs 1, 6 et 10.

Dans le programme de première, on a vu qu'un algorithme glouton, qui favorise toujours la pièce la plus grande possible, répond au problème du rendu de monnaie sous certaines conditions.

C'est le cas notamment pour un système monétaire comme les euros, c'est-à-dire

(1,2,5,10,20,50,100,200).

Dans le cas général, cependant, l'algorithme glouton ne donne pas toujours la réponse optimale.

Ainsi, pour faire la somme 12 avec le système (1,6, 10), l'algorithme glouton donne la réponse 3, correspondant à 10 + 1 + 1, au lieu de 2 (6 + 6).

Dans cette section, on étudie un autre algorithme de rendu de monnaie qui donne toujours la solution optimale quelque soit le système monétaire utilisé.

On cherche à écrire sous la forme d'une fonction :

rendu_monnaie(pieces, s)

où pieces est la liste des valeurs des pièces, telle que [1, 2, 5] par exemple, et s la somme que l'on souhaite obtenir.

La fonction doit renvoyer le nombre minimal de pièces pour obtenir s.

On suppose que la liste pieces contient toujours la valeur 1. Ainsi, toute somme peut être obtenue, dans le pire des cas, comme 1+1+ ... +1.

L'algorithme que nous proposons n'est pas vraiment subtil:

il va considérer toutes les façons possibles de parvenir à la somme s.

Pour cela, il procède récursivement. Le cas de base est la somme s = 0, pour laquelle il ne faut aucune pièce.

On renvoie donc 0.

Lorsque s > 0, on considère chaque valeur p dans la liste pieces et on calcule récursivement le nombre minimal de pièces pour faire la somme s—p.

À chacune des valeurs obtenues on ajoute 1 (la pièce de valeur p) et on prend le minimum de toutes ces réponses.

Le programme ci-dessous contient le code Python d'une fonction récursive rendu_monnaie qui réalise cet algorithme.

Programme — Rendu de monnaie, naïf

def rendu_monnaie(pieces, s):

\"\"\"renvoie le nombre minimal de pièces pour faire

la somme s avec le système pieces\"\"\"

if s == 0:

return 0

r = s # s = 1 + 1 + ... + 1 dans le pire des cas

for p in pieces:

if p <= s:

r = min(r, 1 + rendu_monnaie(pieces, s - p))

return r

On prendra le temps de bien lire et de bien comprendre ce programine.

Le programme fonctionne correctement mais il est assez peu performant.

","title":"Rendu de monnaie","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

On constate que le programme ne termine tout simplement pas pour la somme 100.

Essayons de comprendre ce qui se passe, en comptant le nombre d'appels à la fonction rendu_monnaie.

Lorsqu'on l'appelle avec 100 comme argument, elle se rappelle deux fois récursivement, une fois avec 99 comme argument et une fois avec 98 comme argument.

Puis l'appel sur 99 va provoquer deux appels récursifs, sur 98 et 97 respectivement.

On constate qu'on va donc faire deux fois un appel avec 98 comme argument, ce qui provoquerait au total trois appels avec 97 comme argument. Et ainsi de suite d'une façon rapidement dramatique.

Essayons d'être plus précis encore, en calculant pour chaque valeur de s le nombre exact d'appels à la fonction rendu_monnaie.

Pour s = 0, il n'y a qu'un seul appel, à savoir l'appel initial.

Pour s = 1, à y en a deux, à savoir l'appel initial et l'appel sur s = 0.

Dans le cas général, il faut compter l'appel initial et les nombres d'appel pour s — 1 ct s — 2, c'est-à-dire les deux nombres obtenus précédemment.

Pour les premières valeurs de s, en partant de 0, on obtient la suite suivante :

1,2,4,7,12,20,33,...

Si on ajoute un à ces valeurs, on reconnaît la célèbre suite de Fibonacci:

2,3,5,8,13,21,34,...

Dit autrement, le nombre d'appels à rendu_monnaie dans le calcul de

rendu_monnaie([1, 2], n)

est égal à F_n+3 — 1 où F_n désigne le n-ième terme de la suite de Fibonacei.

Or, c'est là une suite qui croît exponentiellement rapidement.

Ainsi, F₅₀ = 12 586 269 025, ce qui veut dire que le calcul de rendu_monnaie([1, 2], 47) demanderait plus de 12 milliards d'appels.

Il n'est pas étonnant que le calcul de rendu_monnaie([1, 2], 100) ne semblait pas terminer, quand on sait que F103 dépasse 1500 milliards de milliards.

Bien évidemment, dans le cas précis du système [1,2] la réponse est tellement simple qu'on peut la calculer de tête.

Mais cet exemple minimal montre à quel point notre solution récursive est rapidement trop coûteuse.

Mieux encore, il nous a permis d'identifier la source du problème :

on appelle la fonction rendu_monnaie de très nombreuses fois sur le même argument.

Ainsi, pendant le calcul de rendu_monnaie([1,2], 35), qui prend plus de 8 secondes, on appelle 1346 273 fois la fonction rendu_monnaie avec s = 5.

C'est là qu'intervient l'idée de la programmation dynamique :

faire en sorte de ne pas calculer plusieurs fois la même chose.

","title":""},{"edit":"

"}],[{"text":"

La mise en œuvre de cette idée n'est pas si difficile que cela. On va utiliser un tableau dans lequel on va stocker successivement la réponse de la fonction rendu monnaie pour toutes les valeurs de 0 jusqu'à s.

Ainsi, on ne recalculera jamais deux fois la même réponse pour une certaine somme:

on se contentera de lire sa valeur dans ce tableau.

Notre nouvelle fonction rendu_monnaie commence donc par allouer un tableau, appelé nb pour «nombre de pièces», dont les indices vont de 0 à s inclus.

def rendu_monnaie(pieces, s):

nb = [0] * (s+1)

Ce tableau est ici initialisé avec 0, ce qui est notamment la bonne valeur pour la somme 0.

Ainsi, la première case du tableau est correctement initialisée.

Il s'agit maintenant de remplir ce tableau pour toutes les sommes de 1 à s.

On le fait avec une boucle for. Pour chaque indice n, c'est-à-dire pour chaque

On le fait avec une boucle for. Pour chaque indice n, c'est-à-dire pour chaque somme n, on commence par initialiser nb[n] avec n car on sait que, dans le pire des cas, on peut faire la somme n avec n pièces, à savoir :

n = 1+1+ ... + 1.

for n in range(i, s + 1):

nb[n] = n

Il faut maintenant se poser la question de savoir si on peut faire mieux.

Comme dans le programme récursif rendu_monnaie, on considère successivement toutes les valeurs de la liste pieces.

Pour chaque valeur p, on a une solution

en 1 + nb[n - p] pièces, à savoir une pièce de valeur p et la meilleure solution possible pour la somme n - p, déjà calculée.

for p in pieces:

if p<=n:

nb[n] = min(nb[n], 1 + nb[n - p])

Avec cette boucle, on calcule donc le minimum de toutes les solutions possibles, ce qui donne bien la solution pour la somme n.

Une fois sorti de ces deux boucles, on à calculé la solution pour toutes les sommes jusqu'à s inclus.

Il n'y à donc plus qu'à renvoyer la valeur de nb[s].

return nb[s]

Le programme ci-dessous contient l'intégralité du code.

Programme — Rendu de monnaie par programmation dynamique

def rendu_monnaie1(pieces, s):

\"\"\"renvoie le nombre minimal de pièces pour faire

la somme s avec le système pieces\"\"\"

nb = [0] * (s + 1)

for n in range(1, s + 1):

nb[n] = n # n = 1 + 1 + ... + 1 dans le pire des cas

for p in pieces:

if p <= n:

nb[n] = min(nb[n], 1 + nb[n - p])

return nb[s]

On constate qu'il a la même structure que le programme précédent, si ce n'est que l'appel récursif est maintenant remplacé par la consultation du tableau nb.

Tester la fonction rendu_monaie1 avec les instructions suivantes :

r = rendu_monnaie1([1, 2], 10)

print(r)

et ensuite avec:

r = rendu_monnaie1([1, 2], 47)

print(r)

et enfin avec:

r = rendu_monnaie1([1, 2], 100)

print(r)

Conclure

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Efficacité

Notre version de rendu monnaie qui utilise la programmation dynamique est bien plus efficace que la version récursive initiale.

Ainsi, le calcul de rendu _monnaie([1,2], 47), qui demandait beaucoup de temps, est maintenant instantané.

En effet, on a maintenant l'allocation d'un tableau de taille 48, une boucle qui parcourt 47 valeurs possibles pour la variable n et, pour chacune, une boucle interne qui parcourt deux valeurs possibles pour la variable p.

Le nombre total d'opérations est donc de l'ordre de la centaine, ce qui est ridicule.

D'une manière générale, le coût est maintenant proportionnel à

len(pieces) x s

en temps et à s en espace (pour le tableau nb).

C'est potentiellement plus coûteux que l'algorithme glouton, mais cela fonctionne maintenant pour tous les systèmes monétaires.

","title":""},{"edit":"

"}],[{"text":"

Construire une solution

Notre programme renvoie le nombre minimal de pièces pour obtenir la somme s mais il ne donne pas la solution pour autant, c'est-à-dire la liste des pièces à utiliser pour atteindre ce minimum.

Il est cependant facile de le modifier pour construire une telle solution.

Il suffit d'ajouter ur second tableau qui contient, pour chaque somme entre 0 et s, une solution minimale pour cette somme.

On remplit ce tableau exactement au même moment où on remplit le tableau nb.

Le programme ci-dessous contient une version du programme rendu_monnaie modifié en suivant cette idée.

Programme — Rendu de monnaie, avec solution

def rendu_monnaie_solution(pieces, s):

\"\"\"renvoie une liste minimale de pièces pour faire

la somme s avec le système pieces\"\"\"

nb = [0] * (s + 1)

sol = [[]] * (s + 1)

for n in range(1, s + 1):

nb[n] = n

sol[n] = [1] * n

for p in pieces:

if p <= n and 1 + nb[n - p] < nb[n]:

nb[n] = 1 + nb[n - p]

sol[n] = sol[n - p].copy()

sol[n].append(p)

return sol[s]

Le second tableau s'appelle sol. Pour chaque indice n, l'élément sol[n] est un tableau d'entiers, de taille nb[n], qui donne une solution pour la somme n.

On initialise sol avec un tableau vide dans chaque case, ce qui est en particulier correct pour n = 0.

La structure du programme est la même qu'auparavant.

Pour chaque somme n, de 1 jusqu'à s, on commence par stocker un tableau contenant n fois la valeur 1 dans sol[n], ce qui correspond à la solution 1+1+...+1.

Puis on examine toutes les pièces possibles et, lorsqu'une pièce p permet d'améliorer la solution, la valeur des deux tableaux est mise à jour.

Pour mettre à jour la valeur de sol[n], on commence par faire une copie du tableau sol[n - op], avec la méthode copy, puis on y ajoute la valeur p, avec la méthode append.

Tester la fonction rendu_monaie_solution avec les instructions suivantes :

r = rendu_monnaie_solution([1, 2], 10)

print(r)

et ensuite avec:

r = rendu_monnaie([1, 2], 47)

print(r)

Conclure

Pour une somme donnée, il n'y à pas nécessairement une solution unique.

Ainsi, avec le système [1, 3, 6, 7, 10], il y a deux solutions minimales pour faire la somme 13, à savoir 3 + 10 ct 6 + 7.

Tester avec:

r = rendu_monnaie_solution([1, 3, 6, 7, 10], 13)

print(r)

Notre programme va renvoyer une seule de ces solutions.

En l'occurrence, ici, il va renvoyer le

tableau [10, 3] correspondant à la première solution.

En effet, lorsque le programme parvient à n = 13, il considère les pièces par ordre croissant.

Pour p = 1, il détermine qu'on obtient une solution à trois pièces en considérant la solution déjà calculée 12 = 6 + 6 à deux pièces.

Puis, pour p = 3, il détermine qu'on obtient de nouveau une meilleure solution, à deux pièces cette fois, en considérant la solution déjà calculée pour la somme 10, à une seule pièce, ce qui nous fait une solution à deux pièces 3 + 10.

Quand on considère ensuite p - 6, on obtient de nouveau une solution à deux pièces, qui n'est donc pas strictement meilleure et qui n'est donc pas considérée.

De même quand on considère p = 7 et p = 10. On est donc resté sur la solution 13=3+10, qui est celle renvoyée au final.

On pourrait encore modifier le programme ci-dessous pour qu'il renvoie toutes les solutions pour faire la somme s en minimisant le nombre de pièces.

Il suffirait pour cela que le tableau sol stocke, pour chaque somme, non pas une solution minimale mais toutes les solutions minimales.

Mais il faut être alors conscient que le temps et l'espace consacrés au stockage de toutes les solutions vont dégrader les performances de notre programme.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Dans le contexte de la bio-informatique, un problème algorithmique essentiel est celui de l'alignement de séquences, typiquement pour comparer des séquences d'ADN.

Source: https://en.wikipedia.org/wiki/DNA_sequencing

On peut le formaliser en ces termes:

étant données deux chaînes de caractères, il s'agit de mettre en correspondance «le plus possible» les caractères de la première chaîne avec ceux de la seconde, en conservant l'ordre des caractères mais en s'autorisant à insérer des trous dans l'une ou l'autre chaîne.

Si on considère par exemple les chaînes \"GENOME\" et \"ENORME\", on peut aligner leurs caractères de la façon suivante, où le caractère - est utilisé pour désigner un trou:

GENO-ME

ENORME

Bien entendu, il existe de nombreuses autres façons d'aligner ces deux chaînes.

En voici une:

G--ENOME

—ENOR--ME

La seule contrainte est que l'on doit utiliser tous les caractères de chaque chaîne, dans l'ordre, et que l'on n'aligne jamais deux trous (c'est-à-dire deux caractères - ).

Parmi tous les alignements possibles, on cherche celui qui donne le score maximal.

Le score est ainsi calculé:

l'alignement de deux caractères identiques donne un point;

en revanche, l'alignement de deux

caractères différents, ce qui inclut l'alignement avec le caractère -, enlève un point.

Ainsi, le premier alignement proposé ci-dessus donne le score 3, car on a 5 caractères correctement alignés et deux mauvais alignements.

Parmi tous les alignements possibles des chaînes \"GENOME\" et \"ENORME\", c'est celui

qui a le score maximal.

À noter que les deux chaînes n'ont pas forcément la même longueur.

Ainsi, l'alignement

ASTUCIEUX

-STUDIEUX

a le score 5, ce qui est là encore maximal.

Comme pour le problème du rendu de monnaie de la section précédente, nous allons commencer par chercher une solution récursive à notre problème (mais cette fois sans écrire le code Python), puis en améliorer l'efficacité grâce à la programmation dynamique.

Reprenons l'exemple des mots \"GENOME\" et \"ENORME\" et voyons ce qu'il en est de leur dernier caractère.

Ici, il s'agit du caractère E dans les deux cas.

Il y à trois cas de figure :

soit ces deux E sont alignés, on marque un point et on doit aligner les mots “GENOM\" et \"ENORM\";
soit le E final de \"GENOME\" est aligné avec -, on perd un point et on doit aligner le mot \"GENOM\" avec le mot \"ENORME\";
soit enfin le E final de \"ENORME\" est aligné avec -, on perd un point et on doit aligner le mot \"GENOME\" avec le mot \"ENORM\",

Comme il n'y a pas d'autre cas possible, le score maximal sera le maximum des trois scores ainsi obtenus. Et comme on s'est ramené à des mots plus petits, plus précisément à une longueur totale des deux mots strictement plus petite, on peut procéder récursivement.

Ainsi, dans le premier cas on calcule le score maximal de l'alignement de \"GENOM\" et \"ENORM\", dans le deuxième cas de \"GENOM\" et \"ENORME\", et dans le troisième cas de \"GENOME\" ct \"ENORM\",

À chaque fois, il y à de nouveau trois cas de figure, qui nous ramènent à des mots plus courts. Et ainsi de suite.

Le processus termine lorsque l'un des deux mots n'a plus de caractères.

Quand par exemple on parvient au calcul du score de l'alignement du mot vide \"\" et du mot \"GE\", la réponse est —2 car il n'y à pas d'autre choix que d'aligner les deux caractères de \"GE\" avec des caractères -.

On pourrait ainsi écrire une fonction récursive aligne qui applique l'algorithme ci-dessus.

Mais exactement comme pour le rendu de monnaie, elle serait très inefficace car elle passerait son temps à recalculer ia même chose.

En effet, si l'on examine les trois cas ci-dessus, on voit que dans le deuxième

cas, le calcul de l'alignement de \"GENOM\" et \"ENORME\" va nous ramener en particulier au calcul de l'alignement de \"GENOM\" et \"ENORM\", déjà fait dans le

premier cas. Et de même, dans le troisième cas, le calcul de l'alignement de \"GENOME\" et \"ENDRM\" va nous ramener une troisième fois au calcui de l'alignement de \"GENOM\" et \"ENORM\".

Ce phénomène de duplication des calculs

va se répéter à chaque étape, provoquant une explosion exponentielle des appels récursifs et donc du temps de calcul.

Ainsi, le calcul du meilleur alignement de deux mots de 10 caractères chacun prend plus de 3 secondes et celui de deux mots de 20 caractères chacun ne se termine pas en un temps raisonnable.

Mais comme pour le rendu de monnaie, on

peut améliorer notre programme en évitant les calculs redondants grâce à la programmation dynamique.

","title":"Alignement de séquences","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Dans le cas du rendu de monnaie, on à utilisé un tableau dans lequel on a stocké, pour chaque somme, la solution optimale.

Ici, on va utiliser un tableau à deux dimensions dans lequel on va stocker, pour chaque paire de mots, le score maximal.

Plus précisément, pour deux entiers i et j, on va stocker dans la case (i,j) de ce tableau le score maximal de l'alignement

des à premiers caractères du premier mot et des j premiers caractères du second mot.

Notre fonction aligne commence par calculer la longueur de chacun des deux mots et par allouer un tableau sc de la bonne taille.

def aligne(s1, s2):

\"\"\"le score du meilleur alignement de s1 et s2\"\"\"

n1, n2 = len(s1), len(s2)

sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]

Il y a plusieurs remarques importantes ici. D'une part, le premier indice va

de 0 à n1 inclus et le second de 0 à n2 inclus. C'est pourquoi on à écrit n1+1

(resp. n2+1). Le tableau à donc la taille (n1 +1) x (n2 + 1).

D'autre part, on a utilisé la construction par compréhension pour construire ce tableau à deux dimensions.

Écrire simplement [[0] * (n2+1)] * (n1+1) aurait été incorrect.

Enfin, on à initialisé les cases de ce tableau avec la valeur 0. En particulier, c'est la bonne valeur pour la case (0,0) c'est-à-dire l'alignement de deux mots vides.

Il faut maintenant remplir toutes les autres cases de ce tableau, en mettant dans sc[i][j] le score de l'alignement maximal des mots s1[0:i] et s2[0:j].

On va le faire en progressant dans le sens des indices croissants.

En effet. le calcul de sc[i][j] va utiliser les trois valeurs :

sc[i-1][j],sc[i][j-1] et sc[i-1][j-1].

Il faut donc les avoir calculées auparavant.

En particulier, on peut commencer par initialiser les valeurs sc[0][j], c'est-

à-dire la première ligne, et sc[i][0], c'est-à-dire la première colonne.

Dans les deux cas, il s'agit de l'alignement avec un mot vide, pour lequel la réponse est facile à calculer:

il faut supprimer tous les caractères, ce qui produit un score égal à l'opposé de la longueur du mot considéré.

for i in range(1, n1 + 1):

sc[i][0] = -i

for j in range(1, n2 + 1):

sc[0][j] = -j

On peut maintenant attaquer le remplissage du reste du tableau, avec une

double boucle pour parcourir toutes les cases restantes.

for i in range(1, n1 + 1):

for j in range(1, n2 + 1):

Pour chaque case sc[i][j], il s'agit de calculer le score maximal pour aligner les mots s1[0:i] et s2[0:j].

Comme expliqué plus haut, il y a trois cas de figure, selon l'alignement du dernier caractère de chacun de ces deux mots.

On commente par les deux cas où l'un de ces deux caractères est aligné avec -. Le score est alors obtenu avec un point de pénalité et l'alignement maximal, déjà calculé, pour un mot raccourci d'un caractère, c'est-à-dire soit sc[i-1][j], soit sc[i][j-1].

s = max(-1 + sc[i - 1][j], -1 + sc[i][j - 1])

1] reste alors le cas où les deux derniers caractères sont alignés.

Dans ce cas, on marque un point si les caractères coïncident et on perd un point sinon.

Dans les deux cas, on utilise l'alignement maximal déjà calculé pour les deux mots raccourcis chacun d'un caractère, c'est-à-dire sc[i-1][j-1].

if s1[i - 1] == s2[j - 1]:

sc[i][j] = max(s, 1 + sc[i - 1][j - 1])

else:

sc[i][j] = max(s, -1 + sc[i - 1][j - 1])

Une fois sorti de la double boucle, le tableau est correctement rempli. Il ne reste plus qu'à renvoyer la valeur située dans la toute dernière case, qui correspond au score d'alignement des deux mots complets.

return sc[n1][n2]

Le programme ci-dessous contient l'intégralité du code:

Programme — Alignement de séquences

def aligne(s1, s2):

\"\"\"le score du meilleur alignement de s1 et s2\"\"\"

n1, n2 = len(s1), len(s2)

sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]

# première ligne et première colonne

for i in range(1, n1 + 1):

sc[i][0] = -i

for j in range(1, n2 + 1):

sc[0][j] = -j

# le reste

for i in range(1, n1 + 1):

for j in range(1, n2 + 1):

s = max(-1 + sc[i - 1][j], -1 + sc[i][j - 1])

if s1[i - 1] == s2[j - 1]:

sc[i][j] = max(s, 1 + sc[i - 1][j - 1])

else:

sc[i][j] = max(s, -1 + sc[i - 1][j - 1])

return sc[n1][n2]

Tester la fonction aligne avec:

s2 = \"ENORME\"

s1 = \"GENOME\"

sc = aligne(s1,s2)

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Il est utile de visualiser et de bien comprendre le tableau sc que ce programme construit. Si on reprend l'exemple des mots \"GENOME\" et \"ENORME\", le tableau obtenu au final est celui-ci:

On peut examiner par exemple comment a été calculé le résultat final, c'est-

à-dire sc[6][6]. Puisque les caractères s1[5] et s2[5] coïncident, on a :

sc[6][6] = max(1+sc[5][5],—1+sc[5][6], —1 + sc[6][5])

= max(1+2,-1+1,-1+1)

= 3

Si on prend un autre cas de figure où les caractères ne coïncident pas, comme par exemple le cas de sc[4][5], on a:

sc[4][5] = max(1+sc[3][4],—1+sc[3][5], —1 + sc[4][4])

= max(-1+-1,-1+-2,-1+1)

= 0

Une autre façon de lire ce tableau est la suivante:

quand on monte, c'est qu'on aligne le caractère correspondant à la ligne avec -;

quand on va à gauche, c'est qu'on aligne le caractère correspondant à la colonne avec -;

enfin, quand on va en diagonale vers le haut et la gauche, c'est qu'on aligne

les deux caractères correspondant à la ligne et à la colonne.

En particulier, le score maximal obtenu au final correspond à un certain chemin de la case en bas à droite jusqu'à la case en haut à gauche qui, à chaque étape, choisit entre aller vers le haut, aller vers la gauche ou aller en diagonale vers le haut et la gauche.

Comme pour le rendu de monnaie, il est possible de modifier le programme pour qu'il renvoie la solution, c'est-à-dire l'alignement réalisant le score maximal. Vous aurez à le faire dans un des exercices.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Efficacité

L'efficacité de ce programme est facile à évaluer. Si les deux mots s1 at s2 ont une longueur respective N et M, on a alloué un tableau de taille N x M.

On l'a ensuite rempli avec quelques calculs élémentaires pour chaque case, ce qui prend un temps proportionnel à N x M.

En particulier, le calcul de l'alignement de deux mots de 20 caractères chacun, qui n'aurait jamais terminé en un temps raisonnable avec une simple fonction récursive, termine maintenant instantanément, avec quelques centaines d'opérations élémentaires seulement.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Mémoïsation

La programmation dynamique n'est pas la seule façon d'éviter les calculs redondants.

Une autre technique consiste à utiliser

un dictionnaire, dans lequel on stocke les calculs déjà effectués.

Plus précisément, pour effectuer le calcul de f(a), on commence par regarder

dans le dictionnaire, indexé par a, si la valeur de f(a) est déjà connue.

Le cas échéant, on la renvoie. Sinon, on calcule la valeur v de f(a), on remplit le dictionnaire avec a -> v, puis on renvoie v.

Ainsi, si on cherche plus tard à recalculer f pour la même valeur a, alors le calcul sera immédiat.

Voici par exemple le programme rendu_monnaie réécrit avec cette idée.

def rendu_monnaie2(pieces, s):

if s in memo:

return memo[s]

r=s

for p in pieces:

if p <= s:

r = min(r, 1 + rendu_monnaie(pieces, s - p))

memo[s] = r

return r

Tester le code avec:

from time import time

start = time()

r = rendu_monnaie2([1, 3, 6, 7, 10], 30)

print(\"appel fct 1ère fois\",time()-start,\"s\")

print(r)

start = time()

r = rendu_monnaie2([1, 3, 6, 7, 10], 30)

print(\"appel fct 2ème fois avec memo\",time()-start,\"s\")

print(r)

Conclure sur l'avantage de la mémoïsation.

IL a toujours la structure récursive du programme rendu_monnaie mais il est maintenant aussi efficace que le programme rendu_monnaie1 (modulo les limites de la récursion de Python).

La programmation dynamique et la mémoïsation sont deux techniques différentes pour atteindre le même objectif, à savoir améliorer la complexité en évitant de calculer deux fois la même chose.

Dans l'immense majorité des cas, elles sont interchangeables.

Il existe cependant quelques cas de figure où la programmation dynamique permet un contrôle plus fin de la mémoire utilisée (en «oubliant» des valeurs précédemment calculées dont on sait qu'elles ne seront plus utiles).

À l'inverse, la mémoïsation est bien plus simple à mettre en œuvre. Mais tout ceci dépasse le cadre du programme de terminale.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Lien avec la technique «diviser pour régner»

La programmation dynamique présentée dans cette séquence n'est pas sans rapport avec la technique «diviser pour régner» présentée dans la séquence précédente.

En effet, il n'est pas rare de commencer par concevoir une décomposition récursive d'un problème, comme dans la séquence précédente, pour se rendre compte ensuite que certains appels récursifs vont être effectués plusieurs fois avec les mêmes arguments.

On peut alors employer la programmation dynamique ou la mémoïsation pour y

remédier.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

La programmation dynamique est une technique pour améliorer l'efficacité d'un algorithme en évitant les calculs redondants.

Pour cela, on stocke dans un tableau les résultats intermédiaires du calcul, afin de les réutiliser au lieu de les recalculer.

Les problèmes du rendu de monnaie ou de l'alignement de séquences sont deux exemples où la programmation dynamique améliore grandement l'efficacité par rapport à une solution récursive.

","title":"Conclusion"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Expliciter (à la main) tous les appels récursifs à la fonction rendu_monnaie (version naïve) quand on lance rendu_monnaie([1, 2], 3).

Identifier les calculs redondants.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Il y a sept appels au total (en comptant le tout premier):

rendu_monnaie([1,2], 3)

rendu_monnaie([1,2], 2)

rendu_monnaie([1,2], 1)

rendu_monnaie([1,2], 0)

rendu_monnaie([1,2], 1)

rendu_monnaie([1,2], 0)

On constate qu’on a fait deux fois l’appel pour s = 1 et trois fois l’appel

pour s = 0.

"}],[{"text":"

Quel est le tableau construit par le programme rendu_monnaie2 quand on

calcule rendu_monnaie2([1, 6, 10], 12)? (Le calculer à la main.)

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

[0, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 2]

La réponse est dans la dernière case (donc 2 ici).

"}],[{"text":"

def rendu_monnaie1(pieces, s):

\"\"\"renvoie le nombre minimal de pièces pour faire

la somme s avec le système pieces\"\"\"

nb = [0] * (s + 1)

for n in range(1, s + 1):

nb[n] = n # n = 1 + 1 + ... + 1 dans le pire des cas

for p in pieces:

if p <= n:

nb[n] = min(nb[n], 1 + nb[n - p])

return nb[s]

Modifier le programme rendu_monnaie1 pour qu'il renvoie, plutôt que le nombre minimal de pièces nécessaires, la liste des pièces constituant la solution optimale.

Tester avec:

print(rendu_monnaie3([1,2,5],47))

Résultat:

[2, 5, 5, 5, 5, 5, 5, 5, 5, 5]

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

À côté du tableau nb qui contient le nombre minimal

de pièces nécessaires pour chaque entier, on ajoute un second tableau, sol,

qui contient la solution, sous la forme d’une liste de pièces.

def rendu_monnaie3(pieces, s):

\"\"\"renvoie le nombre minimal de pièces pour faire

la somme s avec le système pieces\"\"\"

nb = [0] * (s + 1)

sol = [[]] * (s + 1)

for n in range(1, s + 1):

nb[n] = n # n = 1 + 1 + ... + 1 dans le pire des cas

sol[n] = [1] * n

for p in pieces:

if p <= n:

nb[n] = min(nb[n], 1 + nb[n - p])

sol[n] = sol[n - p].copy()

sol[n].append(p)

return sol[s]

"}],[{"text":"

La suite de Fibonacci est la suite d'entiers (F_n) définie par

F₀ = 0,

F₁ = 1

et pour n>1, on a Fn = Fn-1 + Fn-2

Écrire une fonction fibonacci(n) qui calcule la valeur de Fn en utilisant la programmation dynamique.

Tester avec:

print(fib(1200))

Résultat:

373026809482509284562310031170172380127627214493597616743856443016039972205847405917634660750474914561879656763268658528092195715626073248224067794253809132219056382939163918400

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On se sert d’un tableau f dans lequel on calcule successivement toutes les valeurs F₀, F₁,...,F_n.

def fib(n):

f = [0] * (n+1)

f[1] = 1

for i in range(2, n + 1):

f[i] = f[i - 1] + f[i - 2]

return f[n]

"}],[{"text":"

Calculer à la main le tableau des scores d'alignement pour les deux mots \"CHAT\" et \"CAT\".

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

C A T

0 -1 -2 -3

C -1 1 0 -1

H -2 0 0 -1

A -3 -1 1 0

T -4 -2 0 2

Le score maximal est donc 2.

"}],[{"text":"

Quel est le score maximal de l'alignement des mots \"AAAAAAAAAA\" et \"BBBBBBBBBB\" (10 caractères chacun)?

Quelle est la forme du tableau calculé par le programme aligne(s1,s2) sur ces deux mots?

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Le score maximal est -10.

Le tableau a la forme suivante:

B B B B B B B B B B

0 -1 -2 -3 -4 -5 -6 -7 -8 -9-10

A -1 -1 -2 -3 -4 -5 -6 -7 -8 -9-10

A -2 -2 -2 -3 -4 -5 -6 -7 -8 -9-10

A -3 -3 -3 -3 -4 -5 -6 -7 -8 -9-10

A -4 -4 -4 -4 -4 -5 -6 -7 -8 -9-10

A -5 -5 -5 -5 -5 -5 -6 -7 -8 -9-10

A -6 -6 -6 -6 -6 -6 -6 -7 -8 -9-10

A -7 -7 -7 -7 -7 -7 -7 -7 -8 -9-10

A -8 -8 -8 -8 -8 -8 -8 -8 -8 -9-10

A -9 -9 -9 -9 -9 -9 -9 -9 -9 -9-10

A-10-10-10-10-10-10-10-10-10-10-10

"}],[{"text":"

Écrire une fonction affiche(s1, s2, sc) qui affiche la table des scores calculée par le programme aligne(s1, s2), sous la forme suivante:

E N O R M E

0 -1 -2 -3 -4 -5 -6

G -1 -1 -2 -3 -4 -5 -6

E -2 0 -1 -2 -3 -4 -4

N -3 -1 1 0 -1 -2 -3

O -4 -2 0 2 1 0 -1

M -5 -3 -1 1 1 2 1

E -6 -4 -2 0 0 1 3

Pour obtenir un tel alignement, on pourra utiliser la commande:

print('{:>3}'.format(n), end=\"\")

qui affiche la valeur n sur exactement trois caractères, qu'il s'agisse d'un entier ou d'un caractère.

Tester avec:

def aligne(s1, s2):

\"\"\"le score du meilleur alignement de s1 et s2\"\"\"

n1, n2 = len(s1), len(s2)

sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]

# première ligne et première colonne

for i in range(1, n1 + 1):

sc[i][0] = -i

for j in range(1, n2 + 1):

sc[0][j] = -j

# le reste

for i in range(1, n1 + 1):

for j in range(1, n2 + 1):

s = max(-1 + sc[i - 1][j], -1 + sc[i][j - 1])

if s1[i - 1] == s2[j - 1]:

sc[i][j] = max(s, 1 + sc[i - 1][j - 1])

else:

sc[i][j] = max(s, -1 + sc[i - 1][j - 1])

#return sc[n1][n2]

return sc

s2 = \"ENORME\"

s1 = \"GENOME\"

sc = aligne(s1,s2)

affiche(s1,s2,sc)

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def affiche(s1, s2, sc):

print (\" \", end=\"\")

for c in s2:

print ('{:>3}'.format(c), end=\"\")

print()

for i in range(len(sc)):

if i > 0:

print ('{:>3}'.format(s1[i - 1]), end=\"\")

else:

print(\" \", end=\"\")

for v in sc[i]:

print ('{:>3}'.format(v), end=\"\")

print()

"}],[{"text":"

Modifier le programme aligne(s1,s2) pour qu'il renvoie également la solution donnant le meilleur score, sous la forme d'un couple de chaînes de caractères de même longueur contenant d'éventuels caractères -.

Ainsi, sur les deux chaînées \"GENOME\" et \"ENORME\", le programme doit renvoyer:

(3, (\"GEND-ME\", \"-ENORME\"))

On pourra s'inspirer de ce qui à été fait

dans le programme rendue_monnaie_solution.

Tester avec:

s2 = \"ENORME\"

s1 = \"GENOME\"

print(aligne2(s1,s2))

Résultat:

(3, ('GENO-ME', '-ENORME'))

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Comme dans le programme rendu_monnaie_solution, on ajoute un second tableau, sol, à côté du tableau sc, l’idée étant que so1[i][j] contient une solution pour l'alignement des chaînes s1[0:i] et s2[0:j].

L’initialisation se fait avec des couples de chaînes vides:

sol = [[(\"\", \"\")] * (n2 + 1) for _ in range(n1 + 1)]

Pour initialiser les bords du tableau, on écrit respectivement

sol[i][0] = (s1[0:i], \"-\" * i)

sol[0][j] = (\"-\" * j, s2[0:j])

ce qui correspond à des alignements avec le caractère -. Enfin, il y a quatre

cas de figure pour déterminer so1[i] [j], selon la situation qui maximise le

score. On peut réécrire la double boucle ainsi:

# le reste

for i in range(1, n1 + 1):

for j in range(1, n2 + 1):

s = -1 + sc[i - 1][j]

x,y = sol[i - 1][j]

sol[i][j] = (x + s1[i - 1], y + \"-\")

if s < -1 + sc[i][j - 1]:

s = -1 + sc[i][j - 1]

x,y = sol[i][j - 1]

sol[i][j] = (x + \"-\", y + s2[j-1])

if s1[i-1] == s2[j-1] and s < 1 + sc[i-1][j-1]:

s = 1 + sc[i - 1][j - 1]

x,y = sol[i - 1][j - 1]

sol[i][j] = (x + s1[i - 1], y + s2[j - 1])

if s1[i-1] != s2[j-1] and s < -1 + sc[i-1][j-1]:

s = -1 + sc[i - 1][j - 1]

x,y = sol[i - 1][j - 1]

sol[i][j] = (x + s1[i - 1], y + s2[j - 1])

sc[i][j] = s

On constate qu’on ne se sert plus de la fonction max. En effet, le calcul de sol[i][j] est différent à chaaue fois.

Le programme complet est le suivant:

def aligne2(s1, s2):

\"\"\"le score du meilleur alignement de s1 et s2\"\"\"

n1, n2 = len(s1), len(s2)

sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]

sol = [[(\"\", \"\")] * (n2 + 1) for _ in range(n1 + 1)]

# première ligne et première colonne

for i in range(1, n1 + 1):

sc[i][0] = -i

sol[i][0] = (s1[0:i], \"-\" * i)

for j in range(1, n2 + 1):

sc[0][j] = -j

sol[0][j] = (\"-\" * j, s2[0:j])

# le reste

for i in range(1, n1 + 1):

for j in range(1, n2 + 1):

s = -1 + sc[i - 1][j]

x,y = sol[i - 1][j]

sol[i][j] = (x + s1[i - 1], y + \"-\")

if s < -1 + sc[i][j - 1]:

s = -1 + sc[i][j - 1]

x,y = sol[i][j - 1]

sol[i][j] = (x + \"-\", y + s2[j-1])

if s1[i-1] == s2[j-1] and s < 1 + sc[i-1][j-1]:

s = 1 + sc[i - 1][j - 1]

x,y = sol[i - 1][j - 1]

sol[i][j] = (x + s1[i - 1], y + s2[j - 1])

if s1[i-1] != s2[j-1] and s < -1 + sc[i-1][j-1]:

s = -1 + sc[i - 1][j - 1]

x,y = sol[i - 1][j - 1]

sol[i][j] = (x + s1[i - 1], y + s2[j - 1])

sc[i][j] = s

return (s , sol[n1][n2])

"}],[{"text":"

Dans le problème de l'alignement de séquences d'ADN, on utilise en pratique un calcul des scores plus subtil, qui dépend des caractères qui sont alignés (pour tenir compte du nombre d'acides aminés identiques ou similaires qui sont mis en correspondance).

Pour cela, on se donne une matrice de similarités.

Par exemple, pour des chaînes formées uniquement des caractères A, G, C et T, on peut se donner la matrice suivante:

Indiquer comment représenter une telle matrice en Python (dans une variable globale sim).

Par ailleurs, on se donne aussi une variable globale gap pour le score d'un alignement avec le caractère - (par exemple gap = -5).

Modifier le programme aligne(s1,s2) pour qu'il utilise ces deux variables dans le calcul du score.

Tester avec:

sim = {

'A':{'A':10, 'G':-1, 'C':-3, 'T':-4},

'G':{'A':-1, 'G':7 , 'C':-5, 'T':-3},

'C':{'A':-3, 'G':-6, 'C':9 , 'T':0 },

'T':{'A':-4, 'G':-3, 'C':0 , 'T':8 }

}

gap = 5

s1 = \"AGCT\"

s2 = \"AGCT\"

print(aligne3(s1,s2))

Résultat:

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On peut se donner la matrice de similarités sous la forme d’un dictionnaire de dictionnaires:

sim = {

'A':{'A':10, 'G':-1, 'C':-3, 'T':-4},

'G':{'A':-1, 'G':7 , 'C':-5, 'T':-3},

'C':{'A':-3, 'G':-6, 'C':9 , 'T':0 },

'T':{'A':-4, 'G':-3, 'C':0 , 'T':8 }

}

Le calcul du score est alors modifié ainsi. Pour les bords, on utilise respec-

tivement

sc[i][0] = i * gap

sc[0][j] = j * gap

Et dans la double boucle, on utilise maintenant :

s = max(gap + sc[i - 1][j], gap + sc[i][j - 1])

sc[i][j] = max(s, sim[s1[i - 1]][s2[j - 1]]

+ sc[i - 1][j - 1])

Le programme complet est le suivant:

global sim,gap

sim = {

'A':{'A':10, 'G':-1, 'C':-3, 'T':-4},

'G':{'A':-1, 'G':7 , 'C':-5, 'T':-3},

'C':{'A':-3, 'G':-6, 'C':9 , 'T':0 },

'T':{'A':-4, 'G':-3, 'C':0 , 'T':8 }

}

gap = 5

def aligne3(s1, s2):

\"\"\"le score du meilleur alignement de s1 et s2\"\"\"

global sim,gap

n1, n2 = len(s1), len(s2)

sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]

# première ligne et première colonne

for i in range(1, n1 + 1):

sc[i][0] = i * gap

for j in range(1, n2 + 1):

sc[0][j] = j * gap

# le reste

for i in range(1, n1 + 1):

for j in range(1, n2 + 1):

s = max(gap + sc[i - 1][j], gap + sc[i][j - 1])

sc[i][j] = max(s, sim[s1[i - 1]][s2[j - 1]]

+ sc[i - 1][j - 1])

return sc[n1][n2]

#return sc

"}],[{"text":"

Écrire une fonction chemins(n, m) qui calcule le nombre de chemins, sur une grille n x m, qui mènent du coin supérieur gauche au coin inférieur droit, en se déplaçant uniquement le long des traits horizontaux vers la droite et le long des traits verticaux vers le bas.

Vérifier les valeurs trouvées par Alice et Basile en introduction à cette séquence.

Tester avec:

print(chemins1(2,3))

Résultat:

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On crée un tableau de taille

(n+1) x (m+1),

comme pour le problème de l’alignement de séquences.

def chemins(n, m):

grille = [[1] * (m +1) for _ in range(n + 1)]

for i in range(1, n + 1):

for j in range(1, m + 1):

grille[i][j] = grille[i - 1][j] + grille[i][j - 1]

#print(grille[i][j])

return grille#[n][m]

ou avec for décroissant:

def chemins1(n, m):

grille = [[1] * (m +1) for _ in range(n + 1)]

for i in range(n-1, -1, -1):

for j in range(m-1,-1,-1):

grille[i][j] = grille[i + 1][j] + grille[i][j + 1]

#print(grille[i][j])

return grille#[n][m]

#return grille[0][]

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 18 Octobre 2020; Mis à jour : 30 Novembre 2020; Clics : 2037

[[{"text":"

Alice se décide à ranger ses bandes dessinées par ordre alphabétique de titre.

Le travail est fastidieux car elle en possède une bonne centaine.

Elle appelle son frère Basile à la rescousse. Ils se partagent les bandes dessinées et chacun d'eux trie sa moitié, sous la forme d'une pile de bande dessinées.

Ensuite, les bandes dessinées sont rangées dans la bibliothèque en fusionnant les deux piles, c'est-à-dire en prenant à chaque fois celle des deux bandes dessinées au sommet des deux piles qui vient avant l'autre dans l'ordre alphabétique.

Si la fratrie est plus grande, on peut même imaginer décomposer le travail plus encore.

Ainsi, la pile d'Alice ou de Basile pourrait être triée en étant elle-même décomposée.

Dans un contexte informatique, cette façon de procéder suggère que plusieurs ordinateurs ou plusieurs programmes pourraient collaborer pour effectuer une tâche telle qu'un tri.

C'est effectivement le cas. Mais d'une façon très surprenante, il s'avère que même un unique programme peut tirer avantage à ainsi décomposer un problème en sous-problèmes plus petits, ou plus

simples, qu'il va lui-même résoudre successivement.

Ainsi, même si Alice est seule pour trier ses bandes dessinées, elle peut tout à fait partager les bandes dessinées en deux tas égaux, les trier puis les fusionner.

Et pour trier chacun des deux tas, elle peut recommencer ainsi avec la même idée, jusqu'à ce que chaque tas soit suffisamment petit pour pouvoir être trié sans effort.

Alice vient ainsi d'inventer le tri fusion, une méthode extrêmement efficace pour trier.

C'est là une instance du principe «diviser pour régner».

D'une manière générale, ce principe consiste à décomposer un problème à résoudre en sous-problèmes, plus petits, puis à les résoudre, éventuellement en appliquant le même principe autant de fois que nécessaire, puis enfin à combiner les résultats des sous-problèmes pour en déduire le résultat du

problème initial.

L'idée de se ramener à la résolution de sous-problèmes plus petits a déjà été explorée dans la séquence consacré à la récursivité.

En effet, quand on calcule la factorielle de n récursivement, on se ramène au calcul de la factorielle de n — 1, un problème identique mais «plus petit».

De même, le principe «diviser pour régner» invite à penser la solution

d'un problème récursivement.

Cependant, les sous-problèmes «plus petits» traités récursivement seront généralement plus nombreux ou nettement plus petits.

Dans cette séquence, nous détaillons deux exemples d'application du principe «diviser pour régner».

La première application est la recherche dichotomique dans un tableau trié, déjà étudiée en classe de première, mais reformulée ici à l'aide de récursion.

La seconde application est celle du tri fusion, suggérée ci-dessus avec l'exemple des bandes dessinées.

Les exercices proposés contiennent d'autres applications, dont un algorithme pour effectuer la rotation d'une image de 90 degrés.

","title":"Diviser pour régner","tagtitle":"h1"},{"edit":"

"}],[{"text":"

On rappelle qu'il s'agit de déterminer si un entier v apparaît dans un tableau t, ce dernier étant supposé trié par ordre croissant.

Plus précisément, on cherche à écrire une fonction qui renvoie un indice où la valeur v apparaît dans t, en choisissant arbitrairement s'il y a plusieurs réponses possibles, et None si la valeur v n'apparaît pas dans t.

L'idée principale de la recherche dichotomique consiste à délimiter une portion du tableau dans laquelle la valeur v peut encore se trouver, avec deux indices g et d.

On peut illustrer ainsi la situation à chaque étape:

0 g. d

éléments < v

...

éléments > v

On compare alors la valeur au centre de cet intervalle avec la valeur v et, selon le cas, on signale qu'on a trouvé la valeur v ou on se déplace vers la moitié gauche ou la moitié droite.

Il s'agit bien là d'une instance de l'idée «diviser pour régner», car on réduit le problème de la recherche dans

l'intervalle g ... d à celui de la recherche dans un intervalle plus petit.

Dans le programme de première, nous avions écrit la recherche dichotomique sous la forme d'une boucle while, en modifiant la valeur de g ou de d à chaque étape.

Cette fois, nous allons l'écrire sous la forme d'une fonction récursive, ce qui illustre encore mieux le principe «diviser pour régner».

En effet, l'appel récursif va directement exprimer la résolution d'un problème identique mais nlus petit.

Nous écrivons done une fonction récursive qui prend quatre arguments:

le tableau,
la valeur recherchée
et les deux indices délimitant la portion dans laquelle se fait la recherche:

def recherche(t, v, g, d):

On commence par traiter le cas d'un intervalle qui ne contient aucune valeur, c'est-à-dire lorsque la borne gauche g est plus grande que la borne droite d.

Dans ce cas, on renvoie None pour signaler l'échec de la recherche.

if g > d:

return None

Si l'intervalle n'est pas vide, on calcule la position centrale de cet intervalle, en faisant la moyenne de g et d.

Ensuite, on compare la valeur v à la valeur t[m].

Si elle est plus grande, cela veut dire qu'il faut poursuivre la recherche dans la moitié droite, délimitée par les indices m+1 et d.

On rappelle donc récursivement la fonction recherche sur cet intervalle.

if tm] < v:

return recherche(t, v, m + 1, d)

Attention à ne pas oublier le return devant l'appel à recherche, car il s'agit de renvoyer le résultat de l'appel récursif.

C'est justement là qu'on exprime l'idée que la solution de notre problème est ramenée à la solution d'un problème plus petit.

D'une façon symétrique, on rappelle récursivement la fonction sur la moitié gauche de l'intervalle, délimitée par les indices g et m-1, si la valeur v est plus petite que la valeur t[m]:

elif t[ml > v:

return recherche(t, v, g, m - 1)

Enfin, il ne reste que le cas où la valeur v vient d'être trouvée à la position m que l'on renvoie alors.

else:

return m

Le programme complet de la recherche dichotomique s'en déduit en appelant la fonction recherche sur l'intégralité du tableau.

def recherche _dichotomique(t, v):

return recherche(t, v, 0, len(t) - 1)

Le code complet est le suivant:

Programme — Recherche dichotomique dans un tableau trié

def recherche(t, v, g, d):

\"\"\"renvoie une position de v dans t[g..d],

supposé trié, et None si elle ne s'y trouve pas\"\"\"

if g > d:

return None

m = (g + d) // 2

if t[m] < v:

return recherche(t, v, m + 1, d)

elif t[m] > v:

return recherche(t, v, g, m - 1)

else:

return m

def recherche_dichotomique(t, v):

\"\"\"renvoie une position de v dans le tableau t,

supposé trié, et None si elle ne s'y trouve pas\"\"\"

return recherche(t, v, 0, len(t) - 1)

Tester le cpde avec les instructions suivantes:

t1 = [randint(0,10000) for _ in range(10000)]

t1.sort()

v1 = randint(0,10000)

print(recherche_dichotomique(t1,v1))

","title":"Retour sur la recherche dichotomique","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Correction et efficacité

Il est important de se persuader que ce programme ce termine toujours.

L'argument n'est pas différent de celui utilisé en première avec la boucle while:

la quantité d - g est un variant de notre fonction récursive. En effet, il s'agit d'une quantité entière qui décroît strictement à chaque appel récursif, tout en restant positive ou nulle.

On peut également se persuader qu'il n'y a pas de risque d'obtenir l'erreur RecursionError à cause d'un trop grand nombre d'appels récursifs. En effet, la taille de l'intervalle étant divisée par deux à chaque étape, il faudrait un tableau de plus de 2¹⁰⁰⁰ éléments pour que la fonction recherche soit appelée récursivement plus de 1000 fois. Or, la mémoire d'un ordinateur n'autorise aujourd'hui que des tableaux de quelques

milliards d'éléments, c'est-à-dire de l'ordre de 2³⁰. Il n'y a donc aucun risque de provoquer l'erreur RecursionError.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Supposons que l'on veuille trier une liste chaînée contenant des entiers par ordre croissant. Plus précisément, on cherche à écrire une fonction qui reçoit en argument une liste chaînée et renvoie une nouvelle liste contenant les mêmes éléments mais triés par ordre croissant.

On pourrait tout à fait utiliser le tri par sélection ou le tri par insertion vus

au programme de première.

Cependant, le principe «diviser pour régner» peut être avantageusement utilisé pour concevoir un algorithme de tri plus efficace encore, appelé tri fusion.

L'idée a été évoquée dans l'introduction.

Elle consiste à séparer les éléments de la liste en deux listes de même taille, à un élément près.

Ensuite, on trie chacune des deux listes avec le tri fusion, récursivement.

Enfin, on fusionne les deux listes triées, ce qui est facile car il suffit d'examiner uniquement le premier élément de chaque liste.

Il s'agit bien là d'une application du principe «diviser pour régner» car on ramène le problème du tri d'une liste aux sous-problèmes du tri de deux listes plus petites, jusqu'à parvenir à des listes d'au plus un élément, pour lesquelles il n'y a rien à faire.

Le code Python qui traduit cette idée est le suivant:

def tri_fusion(lst):

if 1st is None or lst.suivante is None:

return lst

l1, l2 = coupe(lst)

return fusion(tri_fusion(l1), tri_fusion(l2))

Bien entendu, il reste à réaliser les fonctions coupe et fusion mais le principe «diviser pour régner» est capturé entièrement par la fonction tri fusion et c'est pour cela que nous la donnons tout de suite.

Écrivons maintenant la fonction coupe qui sépare les éléments d'une liste donnée dans deux listes de même taille, à un près, qui sont renvoyées sous la forme d'un couple de listes.

Il y a plusieurs façons de procéder. On pourrait par exemple commencer par calculer la longueur n de la liste, puis mettre les n/2 premiers éléments dans la première liste et le reste dans la seconde.

Üne autre solution consiste à considérer les éléments deux par deux, en en mettant un dans chaque liste.

Pour éviter de faire un cas particulier pour un éventuel dernier élément, dans le cas d'un nombre impair d'éléments, on peut adopter une troisième approche:

on considère les éléments un par un, en les mettant alternativement dans la première et dans la seconde liste,

Une façon élégante de réaliser cela consiste à échanger à chaque étape le rôle des deux listes. C'est cette dernière approche que nous adoptons.

Le code de la fonction coupe est donné dans le programme ci-dessous.

Enfin, il nous reste à écrire la fonction fusion qui reçoit deux listes triées en arguments et renvoie une liste triée contenant les éléments de ces deux listes.

Nous allons l'écrire comme une fonction récursive, car c'est là le plus simple.

La fonction fusion reçoit en argument deux listes l1 et l2, supposées triées par ordre croissant.

def fusion(l1, l2):

Elle doit renvoyer une liste contenant les mêmes éléments que l1 et l2, triée par ordre croissant.

On commence par le cas où l'une des deux listes est vide => il suffit alors de renvoyer l'autre.

if l1 is None:

return l2

if l2 is None:

return l1

Sinon, cela veut dire que les deux listes sont non vides.

On peut donc sans risque examiner maintenant le premier élément de chaque liste.

Le plus petit des deux sera le premier élément du résultat, car les deux listes sont triées.

On compare donc les deux éléments l1.valeur et l2.valeur.

Si le plus petit provient de la première liste, on le place en tête du résultat et le reste de la liste est construit en fusionnant récursivement le reste de l1 avec l2.

if l1.valeur <= l2.valeur:

return Cellule(l1.valeur, fusion(l1.suivante, l2))

Dans le cas contraire, c'est l'inverse:

le premier élément de l2 est placé en tête du résultat et le reste de la liste est construit en fusionnant l1 avec le reste de l2.

else:

return Cellule(l2.valeur, fusion(l1, l2.suivante))

Ceci achève le code de la fonction fusion.

Le code complet du tri fusion est le suivant:

Programme — Tri fusion d'une liste chaînée

def coupe(lst):

\"\"\"sépare une liste en deux listes ayant le même nombre

d'éléménts, à un près\"\"\"

l1, l2 = None, None

while lst is not None:

l1, l2 = Cellule(lst.valeur, l2), l1

lst = lst.suivante

return l1, l2

def fusion(l1, l2):

\"\"\"fusionne deux listes triées\"\"\"

if l1 is None:

return l2

if l2 is None:

return l1

if l1.valeur <= l2.valeur:

return Cellule(l1.valeur, fusion(l1.suivante, l2))

else:

return Cellule(l2.valeur, fusion(l1, l2.suivante))

def tri_fusion(lst):

\"\"\"trie une liste avec le tri fusion\"\"\"

if lst is None or lst.suivante is None:

return lst

l1, l2 = coupe(lst)

return fusion(tri_fusion(l1), tri_fusion(l2))

Tester avec:

def creer_lst_hasard(n,maxhasard):

\"\"\"Creer une liste chainée de nombres aux hasards\"\"\"

lst = None

while n>0 :

lst = Cellule(randint(0,maxhasard),lst)

n -= 1

return lst

def affiche_lst(lst):

\"\"\"affiche le contenue d'une liste chainée\"\"\"

print(lst.valeur,end=\" \")

c = lst.suivante

while c.suivante is not None:

print(c.valeur,end=\" \")

c = c.suivante

print()

#Création de la liste chainée

lst1 = creer_lst_hasard(500,5000)

affiche_lst(lst1)

#Tri de la liste

lst2 = tri_fusion(lst1)

affiche_lst(lst2)

Tester avec 1000 éléments dans la liste lst1 et conclure.

","title":"Tri fusion","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Limites de la récursion

Si on cherche à trier une liste de plus de mille éléments avec notre fonction

tri_fusion, on obtient l'erreur RecursionError, qui signifie qu'on a fait un trop grand nombre d'appels récursifs imbriqués.

Plus précisément, c'est la fonction fusion qui est responsable de cette erreur.

Une solution consiste à augmenter le nombre maximal d'appels, avec setrecursionlimit. Une autre solution consiste À réécrire la fonc-

tion fusion avec une boucle while, ce que propose lexercice 112. C'est

cependant un peu plus délicat à écrire que la version récursive.

La fonction tri_fusion, bien que récursive, ne conduira en revanche

jamais à l'erreur RecursionError. En effet, la taille de la liste étant divisée par deux à chaque fois, il faudrait une liste de plus de 21000 éléments pour conduire à une erreur.

La mémoire de notre machine ne nous permet pas de construire une liste aussi grande.

Et quand bien même nous le pourrions, le tout premier appel à la fonction coupe ne termincrait pas avant très longtemps.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Efficacité

Il est intéressant de se demander si le tri fusion constitue une bonne méthode de tri. En particulier, on peut chercher à le comparer aux tris par sélection et par insertion du programme de première.

Par exemple. nous avions observé que le tri par sélection nous permettait de trier 16 000 valeurs en un peu moins de 7 secondes (sur notre machine).

Avec notre tri fusion, il ne faut que 0,28 secondes pour trier autant de valeurs.

Plus généralement, voici un tableau comparatif, à gauche, et un tracé des performances du tri fusion, à droite.

taille	sélection	fusion
1000	0,06s	0,01s
2000
4000
8000
16000
32000
64000

Comme on le constate, la courbe n'est pas tout à fait linéaire.

Néanmoins, les performances sont bien meilleures qu'avec le tri par sélection et il en serait de même si l'on comparait avec le tri par insertion.

Pour être précis, rappelons que, dans le pire des cas, les tris par sélection

et par insertion peuvent prendre un temps quadratique, c'est-à-dire proportionnel à N² où N désigne le nombre d'éléments à trier.

Ainsi, chaque fois que le nombre d'éléments à trier double, le temps est multiplié par quatre.

Le tri fusion, en revanche, demande un temps qui est proportionnel à N.log₂N, où

log2 désigne la fonction logarithme.

Le logarithme est une fonction qui croît

relativement lentement.

Ainsi, log2(10³⁰) < 30.

Ccla veut dire que lorsque le nombre d'éléments à trier double, le coût du tri fusion fait un peu plus que doubler, mais pas beaucoup plus.

On peut l'observer empiriquement dans le tableau ci-dessus.

Pour être complet, mentionnons qu'une telle complexité en N.log2N est optimale pour le problème du tri par comparaison.

En effet, la théorie nous dit que, dès lors qu'on ne connaît rien quant aux valeurs à trier, notamment leur distribution, et qu'on peut seulement les comparer deux à deux, alors il faut au moins N.log2N comparaisons, dans le pire des cas, pour trier N valeurs, et donc un temps au moins proportionnel à N.log2N.

Le tri fusion est donc optimal.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Remarque : Trier un tableau

Il est possible d'utiliser le tri fusion pour trier un tableau.

Cependant, c'est assez délicat à mettre en œuvre, car réaliser la fusion en place dans le tableau est extrêmement difficile.

Du coup, on utilise un second tableau comme espace de travail temporaire pour

réaliser la fusion et le code s'en trouve tout de suite un peu compliqué.

Il existe un autre algorithme de tri mettant en œuvre le principe «diviser

pour régner» qui s'adapte mieux au cas d'un tableau.

Il s'agit du tri rapide. H consiste à choisir une valeur arbitraire apparaissant dans le tableau et s'en servir comme “pivot”, c'est-à-dire déplacer les éléments dans le tableau pour mettre à gauche les éléments plus petits que le pivot et à droite les éléments plus grands que le pivot, et enfin à trier récursivement les deux moitiés.

Il reste cependant difficile à mettre en

œuvre efficacement. Le tri rapide n'est pas au programme de terminale.

","title":""},{"edit":"

"}],[{"text":"

Le principe «diviser pour régner» consiste à décomposer un problème en un ou plusieurs sous-problèmes de même nature, mais plus petits:

résoudre ces sous-problèmes, éventuellement en les décomposant à leur tour récursivement en problèmes plus petits encore;
déduire des solutions des sous-problèmes la solution du problème initial.

Le tri fusion est un algorithme de tri efficace qui met en œuvre la technique «diviser pour régner».

","title":"Conclusion","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Donner la séquence des appels à la fonction recherche pendant l'évaluation des deux appels suivants :

recherche_dichotomique([0,1,1,2,3,5,8,13,21], 13)

recherche_dichotomique([0,1,1,2,8,5,8,13,21], 12)

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

recherche(t, 13, O0, 8)

recherche(t, 13, 5, 8)

recherche(t, 13, 7, 8)

À ce moment-là, on obtient m = 7, position à laquelle on trouve la valeur 13.

recherche(t, 12, O0, 8)

recherche(t, 12, 5, 8)

recherche(t, 12, 7, 8)

recherche(t, 12, 7, 6)

À ce moment-là, on a g > d et la recherche termine avec le résultat None.

"}],[{"text":"

Quelles sont les deux listes renvoyées par la fonction coupe() lorsqu'on lui passe la liste 8 1 3 0 1 2 5?

L'ordre relatif des éléments est-il préservé?

Est-ce important?

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

La première liste est 5 1 3 8

et la seconde 2 0 1.

On constate que l’ordre relatif est inversé, car les premiers éléments de la

liste l sont ajoutés en premier dans les deux listes l1 et l2.

Ce n’est pas important, car les deux listes vont être triées avant d’être fusionnées.

"}],[{"text":"

Réécrire La fonction fusion à l'aide d'une boucle while plutôt que comme une fonction récursive.

Indication : Construire le résultat en

ordre décroissant, puis le renverser avec une seconde boucle while.

Tester avec:

def creer_lst_hasard(n,maxhasard):

\"\"\"Creer une liste chainée de nombres aux hasards\"\"\"

lst = None

while n>0 :

lst = Cellule(randint(0,maxhasard),lst)

n -= 1

return lst

def affiche_lst(lst):

\"\"\"affiche le contenue d'une liste chainée\"\"\"

print(lst.valeur,end=\" \")

c = lst.suivante

while c.suivante is not None:

print(c.valeur,end=\" \")

c = c.suivante

print()

#Création de la liste chainée

lst1 = lsthasard(1000,5000)

affiche_lst(lst1)

#Tri de la liste

lst2 = tri_fusion(lst1)

affiche_lst(lst2)

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def coupe(lst):

\"\"\"sépare une liste en deux listes ayant le même nombre

d'éléménts, à un près\"\"\"

l1, l2 = None, None

while lst is not None:

l1, l2 = Cellule(lst.valeur, l2), l1

lst = lst.suivante

return l1, l2

def fusion(l1, l2):

lst = None

while l1 is not None or l2 is not None:

if l1 is not None and \\

(l2 is None or l1.valeur <= l2.valeur):

lst, l1 = Cellule(l1.valeur, lst), l1.suivante

else:

lst, l2 = Cellule(l2.valeur, lst), l2.suivante

# puis on renverse lst

r = None

while lst is not None:

r, lst = Cellule(lst.valeur, r), lst.suivante

return r

def tri_fusion(lst):

\"\"\"trie une liste avec le tri fusion\"\"\"

if lst is None or lst.suivante is None:

return lst

l1, l2 = coupe(lst)

return fusion(tri_fusion(l1), tri_fusion(l2))

"}],[{"text":"

Le problème des tours de Hanoï est un jeu célèbre constitué de trois tiges verticales sur lesquelles sont empilés des disques de diamètres différents.

Il s'agit de déplacer tous les disques de la première tige (dessin de gauche) vers la dernière tige (dessin de droite) en respectant deux contraintes:

d'une part, on ne peut déplacer qu'un seul disque à la fois;
d'autre part, on ne peut pas poser un disque sur un disque de diamètre plus petit.

Sur l'exemple ci-dessus, avec quatre disques, il ne faut pas moins de 15 déplacements pour y parvenir.

Écrire une fonction hanoiï(n) qui affiche la solution du problème des tours de Hanoï pour n disques, sous la forme de déplacements élémentaires désignant les trois tiges par les entiers 1, 2 et 3, de la manière suivante:

déplace de 1 vers 3

déplace de 1 vers 2

Indication: Commencer par une fonction récursive deplace(a, b, c, k) qui résout le problème plus général du déplacement de k disques de la tige a vers la tige b en se servant de la tige c comme stockage intermédiaire.

Tester avec:

hanoi(4)

Résultat:

déplace de 1 vers 2

déplace de 1 vers 3

déplace de 2 vers 3

déplace de 1 vers 2

déplace de 3 vers 1

déplace de 3 vers 2

déplace de 1 vers 2

déplace de 1 vers 3

déplace de 2 vers 3

déplace de 2 vers 1

déplace de 3 vers 1

déplace de 2 vers 3

déplace de 1 vers 2

déplace de 1 vers 3

déplace de 2 vers 3

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On suit l'indication. Il n’est pas nécessaire de faire un cas particulier pour k = 1, c’est-à-dire un seul disque.

Il suffit de ne rien faire lorsque k = 0.

def deplace(a, b, c, k):

\"\"\"déplace k disques de La tour a vers la tour b,

en se servant de la tour c comme intermédiaire\"\"\"

if k > 0:

deplace(a, c, b, k - 1)

print(\"déplace de\", a, \"vers\", b)

deplace(c, b, a, k - 1)

#La solution s’en déduit facilement :

def hanoi(n):

deplace(1, 3, 2, n)

"}],[{"text":"

Dans le problème des tours de Hanoï (exercice précédent), combien faut-il de déplacements élémentaires au total pour déplacer les N disques de la tour de départ à la tour d'arrivée?

Indication : Regarder les 3 vidéos pour vous aider.

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Pour déplacer 1 disque, il suffit d’un seul mouvement.

Pour déplacer 2 disques, il faut 1 + 1 + 1 = 3 déplacements.

Pour déplacer 3 disques, il faut 3 + 1 + 3 = 7 déplacements (on en déplace deux,

puis le grand, puis on en déplace deux de nouveau).

En continuant ainsi, on trouve ensuite les valeurs 15, 31, 63, ...,

c’est-à-dire les nombres de la forme :

2^N - 1.

On peut le prouver à l’aide d’une récurrence.

En effet, c’est bien le cas pour N = 1, car 2¹ - 1 = 1 et s’il faut 2^N-1 - 1 déplacements pour N — 1 tours, alors on aura au total (2N-1 -1)+ 1 +(2N-1 -1) = 2N - 1 déplacements pour N tours.

"}],[{"text":"

Reprendre l'exercice sur les tours de Hanoï en utilisant trois piles, chacune contenant des entiers qui représentent les tailles des disques que cette pile contient.

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Les trois arguments a, b, c ne sont plus des entiers mais des piles. Dans le code de la fonction deplace, il suffit de remplacer la ligne

print (\"déplace de\", a, \"vers\", b)

par la ligne

b.empiler(a.depiler())

Dans le code de la fonction hanoi, il faut construire les trois piles, la première contenant les n disques.

def deplace2(a, b, c, k, posi):

\"\"\"déplace k disques de La tour a vers la tour b,

en se servant de la tour c comme intermédiaire\"\"\"

if k > 0:

deplace2(a, c, b, k - 1,[posi[0],posi[2],posi[1]])

b.empiler(a.depiler())

#affichage contenu pile

for i in range(3):

if posi[i] == 0 :

tab = afficher_pile(a)

print(tab)

elif posi[i] == 1 :

tab = afficher_pile(b)

print(tab)

else :

tab = afficher_pile(c)

print(tab)

print()

deplace2(c, b, a, k - 1,[posi[2],posi[1],posi[0]])

def hanoi2(n):

a = Pile()

for i in range(1,n+1):

a.empiler(i)

print(afficher_pile(a))

deplace2(a, Pile(), Pile(), n,[0,1,2])

def afficher_pile(pile:Pile):

if pile.contenu is None:

return []

tab = [pile.contenu.valeur]

c = pile.contenu.suivante

while c is not None:

tab.append(c.valeur)

c = c.suivante

return tab

On a pris soin d’empiler les diamètres en partant du plus grand. Suggestion :

ajouter un affichage du contenu des trois piles après chaque déplacement.

"}],[{"text":"

Dans cet exercice, on cherche à écrire une fonction qui effectue la rotation d'une image de 90 degrés en utilisant le principe «diviser pour régner».

Pour manipuler une image en Python, on peut utiliser par exemple la bibliothèque PIL (Python Image Library) et plus précisément son module Image.

Avec les quatre lignes suivantes:

from PIL import Image

im = Jmage.open(\"image.png\")

largeur, hauteur = im.size

px = im.load()

on charge l'image contenue dans le fichier image.png, on obtient ses dimensions dans les variables largeur et hauteur, et la variable px est la matrice

des pixels constituant l'image.

Pour 0 < x < largeur et 0 < y < hauteur, la couleur du pixel (x, y) est donnée par px[x, y].

Une couleur est un triplet donnant les composantes rouge, vert et bleu, sous la forme d'entiers entre 0 et 255.

On peut modifier la couleur d'un pixel avec une affectation de la forme px[x,y]=c où c est une couleur.

Dans cet exercice, on suppose que l'image est carrée et que sa dimension est une puissance de deux, par exemple 256 x 256.

Notre idée consiste à découper l'image en quatre, à effectuer la rotation de 90 degrés de chacun des quatre morceaux, puis à les déplacer vers leur position finale.

On peut illustrer les deux étapes ainsi:

Afin de pouvoir procéder récursivement, on va définir une fonction rotation_aux(px, x, y, t) qui effectue la rotation de la portion carrée

de l'image comprise entre les pixels (x,y) et (x+t,y+t).

Cette fonction ne renvoie rien. Elle modifie le tableau px pour effectuer la rotation de cette portion de l'image, au même endroit.

On suppose que t est une puissance de 2.

Écrire le code de la fonction rotation_aux.

En déduire une fonction rotation(px, taille) qui effectue une rotation de l'image toute entière, sa dimension étant donnée par le paramètre taille.

Une fois la rotation effectuée, on pourra sauvegarder le résultat dans un autre fichier avec la commande im.save(\"rotation.png\").

Tester avec:

from PIL import Image

im = Image.open(\"image1.png\")

largeur, hauteur = im.size

px = im.load()

rotation(px, largeur)

im.save(\"rotation.png\")

et l'image suivante (Clique droit enregistrer sous):

Résultat en ouvrant rotation.png:

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On commence par traiter le cas d’une région réduite

à un unique pixel. Dans ce cas, il n’y a strictement rien à faire :

def rotation_aux(px, x0, y0, t):

if t == 1:

return

#Sinon, on peut découper la région en quatre sous-régions, de dimension deux

#fois plus petite, dont on effectue la rotation récursivement :

t //=2

rotation_aux(px, x0 , y0 , t)

rotation_aux(px, x0+t , y0 , t)

rotation_aux(px, x0 , y0+t , t)

rotation_aux(px, x0+t , y0+t , t)

#Il faut ensuite déplacer chacune des quatre régions, ce que l’on peut faire

#élégamment avec une double boucle et une affectation simultanée des quatre

#pixels qui échangent leur position :

for x in range(x0, x0+t):

for y in range(y0, y0+t):

px[x,y+t],px[x+t,y+t],px[x+t,y],px[x,y] \\

= px[x,y], px[x,y+t], px[x+t,y+t], px[x+t,y]

La rotation de l’image toute entière est obtenue avec une région qui couvre

toute l’image:

def rotation(px, taille):

rotation_aux(px, 0, 0, taille)

"}],[{"text":"

Dans cet exercice, on se propose d'appliquer le principe «diviser pour régner» pour multiplier deux entiers, avec la méthode de Karatsuba.

Le principe est le suivant. Supposons deux entiers x et y ayant chacun 2ⁿchiffres en base 2.

On peut les écrire sous la forme

x = a2ⁿ+b

y = c2n+d

avec 0 < a,b,c,d < 2ⁿ, c'est-à-dire avec quatre entiers a, b, c, d qui s'écrivent

chacun sur n chiffres en base 2.

Dès lors, on peut calculer le produit de x et y de la façon suivante:

xy = (a2n + b)(c2n + d)

= ac22n + (ad + bc)2n + bd

= ac2n + (ac + bd — (a — b)(c — d))2n + bd

Cette dernière forme, d'apparence inutilement compliquée, fait apparaître

seulement trois produits, à savoir ac, bd et (a — b}(c — d).

Ainsi, on a ramené la multiplication de deux entiers de 2n chiffres à trois multiplications d'entiers de n chiffres.

Pour faire chacune de ces trois multiplications, on peut appliquer le même principe, et ainsi de suite jusqu'à obtenir de petits entiers dont la multiplication est immédiate.

Au final, cela permet d'effectuer la multiplication en un temps proportionnel à n1,58 (environ) au lieu de n2, ce qui est un gain significatif lorsque le nombre de chiffres n est grand.

1. Écrire une fonction taille(x) qui renvoie le nombre de chiffres de l'entier x lorsqu'il est écrit en base 2.

2. Écrire une fonction karatsuba(x, y, n) qui calcule le produit de x et y par la méthode de Karatsuba, en supposant que x et y s'écrivent sur n chiffres en base 2.

Indication : On peut calculer 2n en Python avec l'expression 1 << n.

On peut décomposer x sous la forme a2n+b

avec a, b = x>>n, x % (1 << n).

3. En déduire une fonction mult(x, y) qui calcule le produit de x et y.

Remarque : Il n'est pas nécessaire d'utiliser la base 2. On pourrait tout aussi bien utiliser la base 10 par exemple. Mais les opérations liées à la base deux (multiplication, division ou reste par une puissance de deux sont faciles à réaliser pour la machine).

Tester avec:

print(mult(31478987896658567686786785446,2311675667575656756575765757554))

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Pour la fonction taille, il suffit de diviser x par deux jusqu’à obtenir zéro.

def taille(x):

n=1

while x > 0:

x //= 2

n += 1

return n

Pour la fonction karatsuba, on suit l’algorithme proposé, en s’arrêtant lorsqu'il ne reste qu’un seul chiffre.

def karatsuba(x, y, n):

\"\"\"multiplie x et y par La méthode de Karatsuba\"\"\"

if n <= 1:

return x * y

n //=2

m = 1<<n

a , b = x >> n , x % m

c , d = y >> n , y % m

ac = karatsuba(a, c, n)

bd = karatsuba(b, d, n)

abcd = karatsuba(a - b, c - d, n)

return (ac << ( 2 * n ) ) + ((ac + bd - abcd) << n ) + bd

Enfin, la fonction mult calcule la valeur de n comme le maximum des deux tailles (l'algorithme reste correct si l’un des deux entiers a moins que n chiffres).

def mult(x, y):

n = max(taille(abs(x)), taille(abs(y)))

return karatsuba(x, y, n)

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 18 Octobre 2020; Mis à jour : 29 Novembre 2020; Clics : 2216

[[{"text":"

On a coutume de dire que pour sortir d'un labyrinthe il suffit de toujours suivre le mur situé sur notre droite.

En particulier, on emprunte ainsi toujours la première porte que l'on rencontre sur notre droite et, si on arrive à un cul de sac, cela a pour effet de nous faire faire un demi-tour.

Ceux qui ont un peu réfléchi à cette idée, voire qui ont essayé de la mettre

en pratique, savent plusieurs choses.

D'une part, cette méthode peut échouer

dans certains cas, où on se retrouve à « tourner en rond » autour d'un bloc.

Pour y remédier, ü suffit de marquer au sol les endroits par lesquels on est déjà passé.

Dès lors, quand on revient sur un embranchement qui est marqué, on procède comme s'il s'agissait d'un cul de sac.

D'autre part, on peut tout aussi bien suivre le mur sur la gauche plutôt que sur la droite.

On peut même changer d'avis à chaque nouvelle salle et emprunter à sa guise

n'importe laquelle des portes qui la quittent.

Ces deux idées combinées, à savoir emprunter les embranchernents de façon arbitraire et marquer les endroits par lesquels on est déjà passé, constituent un algorithme fondamental appelé parcours en profondeur. Il s'applique à n'importe quel graphe et permet de déterminer tous les sommets

$\"graphe10.png$

sommet
visité

action

..C

...E

....B

...E

..C

...F

..C

..E

marquer A, emprunter arc A—>B

marquer B, emprunter arc B—>C

marquer C, emprunter arc C—>E

marquer E, emprunter arc E—>B

déjà vu, terminé

pas d'autre arc, terminé

emprunter arc C—>F

marquer F, aucun arc, terminé

pas d'autre arc, terminé

emprunter arc A—>D

marquer D, emprunter arc D—>E

déjà vu, terminé

pas d'autre arc, terminé

Figure 1 — Parcours en profondeur, à partir du sommet A.

","title":"S.D. : Parcours en profondeur et en largeur un graphe","tagtitle":"h1"},{"edit":"

"}],[{"text":"

Avant de programmer le parcours en profondeur en Python, illustrons

son fonctionnement en détail sur un exemple. La figure 1 détaille les

différentes étapes du parcours en profondeur du graphe à partir du sommet A.

$\"graphe10.png$

La première chose que l'on fait est de marquer le sommet A comme déjà vu. En effet, il pourrait y avoir un cycle qui nous ramènerait sur le sommet A (ce n'est pas le cas ici, mais on ne peut pas le

savoir a priori) et avoir marqué le sommet A nous permettra d'interrompre

le parcours et de revenir en arrière.

On considère ensuite les arcs sortants du

sommet A. Il y en a deux, à savoir A—>B et A—>D. Comme on l'a expliqué dans l'introduction, on choisit de façon arbitraire un arc à considérer en premier.

Choisissons par exemple d'emprunter l'arc A—>B. On se retrouve donc maintenant à visiter le sommet B. On commence par le marquer puis on examine ses arcs.

Ici, il n'y en a qu'un seul, à savoir B—>C. On l'emprunte donc et on se retrouve à visiter le sommet C, que l'on commence par marquer.

Il y a 2 arcs sortants du sommet C et là encore on choisit arbitrairement celui qui est considéré en premier.

Ici, on choisit l'arc C—>E, ce qui nous

conduit à marquer E puis à considérer l'unique arc E—>B issu de E.

On se retrouve alors dans une situation nouvelle, où pour la première fois on retombe sur un sommet déjà marqué, à savoir B. On revient donc en arrière, pour se retrouver sur le sommet E.

Comme il n'y avait pas d'autre arc issu

de E, on revient une fois de plus en arrière, pour se retrouver sur le sommet C.

Là, on avait considéré l'arc C—>E mais il y a également l'arc C—>F, que l'on emprunte donc maintenant.

On visite donc le sommet F, que l'on marque.

Comme il n'y a aucun arc sortant du sommet F, on a terminé et on revient

au sommet C.

Cette fois, tous les arcs issus de C ont été examinés, et on a donc terminé la visite de C.

On revient donc au sommet B, donc la visite est également terminée.

On revient donc au sommet A.

Là, il y avait encore l'arc A->D à considérer.

On visite donc le sommet D, que l'on marque avant de considérer l'arc D—>E.

On retombe alors sur le sommet E, déjà visité.

On revient donc en arrière, sur le sommet D, puis encore en arrière, sur le sommet A.

Là, il n'y a plus d'arc à considérer et la visite de A est terminée, ce qui achève notre parcours en profondeur.

Une fois le parcours terminé, tous les sommets atteignables à partir de A

ont été marqués, à savoir A, B, C, D,E et F.

Inversement, le sommet G, qui n'est pas atteignable à partir de A, n'a pas été marqué. C'est là une propriété fondamentale du parcours en profondeur.

Venons-en à la programmation du parcours en profondeur. Le code, ci-dessous repose sur deux ingrédients. Le premier est l'utilisation d'un ensemble pour le marquage des sommets, que l'on appelle vus. Le second ingrédient est l'utilisation d'une fonction récursive pour réaliser le parcours proprement dit.

Cette fonction appelée parcours reçoit en arguments le graphe g, l'ensemble vus et un sommet s à partir duquel réaliser le parcours.

En quatre lignes seulement, elle s'écrit comme elle s'énonce :

«si le sommet s n'est pas dans vus, l'y ajouter et parcourir récursivement tous ses voisins».

Programme — Parcours en profondeur

def parcours(g, vus, s):

\"\"\"parcours en profondeur depuis le sommet s\"\"\"

if s not in vus:

vus.add(s)

for v in g.voisins(s):

parcours(g, vus, v)

def existe_chemin(g, u, v):

\"\"\"existe-t-il un chemin de u à v?\"\"\"

vus = set()

parcours(g, vus, u)

return v in vus

Tester le programme existe_chemin sur le graphe suivant:

$\"graphe10.png$

#réalisation du graphe

g2 = Graphe2()

g2.ajouter_arc(\"A\",\"B\")

g2.ajouter_arc(\"B\",\"C\")

g2.ajouter_arc(\"A\",\"D\")

g2.ajouter_arc(\"D\",\"E\")

g2.ajouter_arc(\"E\",\"B\")

g2.ajouter_arc(\"C\",\"E\")

g2.ajouter_arc(\"C\",\"F\")

g2.ajouter_arc(\"G\",\"C\")

g2.afficher()

#Test si il existe un chemin

print(\"A->F?\",existe_chemin(g2,\"A\",\"F\"))

print(\"A->G?\",existe_chemin(g2,\"A\",\"G\"))

print(\"D->F?\",existe_chemin(g2,\"D\",\"F\"))

","title":"Parcours en profondeur","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Déterminer l'existence d'un chemin entre deux sommets

Une application immédiate du parcours en profondeur consiste à déterminer s'il existe un chemin entre deux sommets u et v. En effet, il suffit de lancer un parcours en profondeur à partir du sommet u puis, une fois qu'il est terminé, de regarder si le sommet v fait partie de l'ensemble des sommets marqués.

Le progrannne contient une fonction existe_chemin qui réalise cette idée.

Elle crée un nouvel ensemble vus, appelle la fonction parcours à partir du sommet u puis vérifie enfin si le sommet v à été visité pendant le parcours.

Bien entendu, on pourrait interrompre le parcours en profondeur dès que le sommet v est atteint. Mais il faudrait modifier pour cela la fonction parcours.

","title":""},{"edit":"

"}],[{"text":"

Construire le chemin

Si on veut construire le chemin, il faut se fatiguer un peu plus.

Au lieu d'un ensemble vus, on prend un dictionnaire, qui associe à chaque sommet le sommet qui à permis de l'atteindre (la

première fois) pendant le parcours en profondeur.

Pour le sommet de départ u, on lui associe None dans ce dictionnaire.

Une fois le parcours en profondeur terminé, on ne se contente pas de regarder si le sommet d'arrivée v est dans vus, mais on «remonte» le dictionnaire, en partant de v, jusqu'à arriver à u.

Vous réaliserez ce programme dans les exercices.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Utilisation

Illustrons l'utilisation de notre parcours en profondeur sur le graphe des régions de la figure ci-dessous:

On a la variable regions qui contient une représentation de ce graphe.

******

On peut tester la présence de chemins, par exemple comme ceci :

assert existe_chemin(regions, \"Bretagne\", \"Occitanie\")

assert not existe_chemin(regions, \"Bretagne\", \"Mayotte\")

Ici, où vérifie l'existence d'un chemin entre la région Bretagne et la région

Occitanie et l'absence d'un chemin entre la région Bretagne et la région Mayotte.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Efficacité

Le parcours en profondeur est un algorithme très efficace, dont

******

pendant ce parcours.

En effet, l'arc u—>v est examiné au plus une fois, à savoir la première fois que la fonction parcours est appelée sur le sommet u.

En effet, si la fonction parcours est rappelée plus tard sur ce même sommet u, alors il sera trouvé dans l'ensemble vus et la fonction se terminera immédiatement, sans rien faire.

Dans le pire des cas, tous les sommets sont atteignables et tout le graphe est donc parcouru.

Le coût est moindre lorsque certains sommets ne sont pas atteignables depuis le sommet de départ.

Le coût en mémoire est celui de l'ensemble vus, qui contient au final tous les sommets atteignables.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Limites de la récursion

La fonction parcours étant récursive, il y a un risque de provoquer RecursionError si le graphe contient beaucoup de sommets.

Ainsi, un parcours en profondeur à partir du sommet 1 sur le graphe

1 -> 2 ... <> 2000

va provoquer cette erreur, car on va dépasser le nombre maximal d'appels récursifs imbriqués (1000 par défaut).

Comme expliqué dans la séquence sur les fonctions récursives, on peut modifier cette limite avec la fonction setrecursionlimit.

Une autre solution consiste à réécrire la fonction parcours avec une boucle while.

Pour cela, on utilise une pile dans laquelle on stocke les sommets qu'il faut parcourir.

Le programme ci-dessous donne le code de cette nouvelle fonction parcours.

On n'a pas besoin de savoir ici comment la pile est réalisée.

C'est un exemple de modularité. La fonction existe_chemin reste inchangée.

Programme — Parcours en profondeur avec une pile

from modPile import *

def parcours2(g, vus, s):

\"\"\"parcours en profondeur depuis le sommet s\"\"\"

pile = Pile()

pile.empiler(s)

while not pile.est_vide():

s = pile.depiler()

if s in vus:

continue

vus.add(s)

for v in g.voisins(s):

pile.empiler(v)

def existe_chemin2(g, u, v):

\"\"\"existe-t-il un chemin de u à v?\"\"\"

vus = set()

parcours2(g, vus, u)

return v in vus

Tester avec :

g2 = Graphe2()

g2.ajouter_arc(\"A\",\"B\")

g2.ajouter_arc(\"B\",\"C\")

g2.ajouter_arc(\"A\",\"D\")

g2.ajouter_arc(\"D\",\"E\")

g2.ajouter_arc(\"E\",\"B\")

g2.ajouter_arc(\"C\",\"E\")

g2.ajouter_arc(\"C\",\"F\")

g2.ajouter_arc(\"G\",\"C\")

g2.afficher()

print(\"A->F?\",existe_chemin2(g2,\"A\",\"F\"))

print(\"A->G?\",existe_chemin2(g2,\"A\",\"G\"))

print(\"D->F?\",existe_chemin2(g2,\"D\",\"F\"))

Conclure sur k'avantage de l'utilisation d'une pile par rapport à une fonction récursive.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Le parcours en profondeur permet également de détecter la présence d'un

cycle dans un graphe orienté.

En effet, puisque l'on marque les sommets

avant de considérer leurs voisins, pour justement éviter de tourner en rond dans un cycle, alors on doit pouvoir être à même de détecter la présence d'un cycle.

Il y a cependant une petite subtilité, car lorsqu'on retombe sur un sommet déjà marqué, on ne sait pas pour autant si on vient de découvrir un cycle.

Considérons par exemple le parcours en profondeur des deux graphes suivants, à partir du sommet A à chaque fois:

Dans le graphe de gauche, on retombe sur le sommet C.

Il n'y a pas de cycle pour autant, mais seulement un chemin parallèle.

Dans le graphe de droite, on retombe sur le sommet B, cette fois à cause d'un cycle.

Tel qu'il est écrit, notre parcours en profondeur ne nous permet pas de distinguer ces deux situations.

Dans les deux cas, on constate que le sommet est déjà dans l'ensemble vus, sans pouvoir en tirer de conclusion quant à l'existence d'un cycle.

Pour y remédier, on va distinguer dans l'ensemble vus deux sortes de sommets:

ceux pour lesquels le parcours en profondeur n'est pas encore terminé et ceux pour lesquels il est au contraire terminé.

On pourrait utiliser pour cela deux ensembles, ou encore un dictionnaire qui associe à chaque sommet déjà rencontré un booléen indiquant si son parcours en profondeur est terminé.

Mais traditionnellement on utilise un marquage à trois couleurs:

- on marque en blane les sommets non encore atteints par le parcours en profondeur,

- en gris les sommets déjà atteints dont le parcours en profondeur est en cours

- et enfin en noir les sommets atteints dont le parcours est terminé.

Dans l'exemple de gauche ci-dessus, le sommet C sera colorié en noir quand on retombera dessus la deuxième fois.

Dans l'exemple de droite, en revanche, il sera encore gris quand on retombera dessus et on en déduira la présence d'un cycle.

Nous adoptons ici cette solution utilisant trois couleurs.

Le parcours en profondeur est modifié de la façon suivante.

Lorsque l'on visite un sommet s, on procède ainsi :

s'il est gris, c'est qu'on vient de découvrir un cycle;
s'il est noir, on ne fait rien;
sinon, c'est qu'il est blanc, et on procède ainsi:

on colore le sommet s en gris;
on visite tous ses voisins, récursivement;
enfin, on colore le sommet s en noir.

Comme on le voit, les voisins du sommet s sont examinés après le moment où s est colorié en gris et avant le moment où s est colorié en noir.

Ainsi, s'il existe un cycle nous ramenant sur s, on le trouvera comme étant gris et

le cycle sera signalé.

Le programme ci-dessous contient une fonction cycle qui réalise cette détection de cycle. Il s'agit 1à d'une modification du parcours en profondeur où un dictionnaire couleur remplace l'ensemble vus.

Programme — Détecter la présence d'un cycle dans un graphe

BLANC, GRIS, NOIR = 1, 2, 3

def parcours_cy(g, couleur, s):

\"\"\"parcours en profondeur depuis le sommet s\"\"\"

if couleur[s] == GRIS:

return True

if couleur[s] == NOIR:

return False

couleur[s] = GRIS

for v in g.voisins(s):

if parcours_cy(g, couleur, v):

return True

couleur[s] = NOIR

return False

def cycle(g):

couleur = {}

for s in g.sommets():

couleur[s] = BLANC

for s in g.sommets():

if parcours_cy(g, couleur, s):

return True

return False

La fonction parcours est toujours une fonction récursive, mais elle renvoie désormais un résultat, à savoir un booléen indiquant la présence d'un cycle.

Enfin, la fonction cycle colorie tous les sommets en blanc puis lance un parcours en profondeur à partir de tous les sommets du graphe.

Si l'un de ces parcours renvoie True, on transmet re résultat. Sinon. on renvoie False.

Dans cette version, on cherche à détecter la présence d'un cycle n'importe où dans le graphe. C'est pourquoi on lance un parcours en profondeur à partir de tous les sommets du graphe,

Pour beauconp de ces sommets, le parcours est passé par là, car ils étaient accessibles depuis des sommets déjà parcourus, et la fonction parcours se termine immédiatement sans rien faire.

Le temps total passé dans la détection de cycle reste proportionnel à la taille du graphe. Si on lance un parcours en profondeur à partir d'un seul sommet s, alors on détecte uniquement la présence d'un cycle atteignable à partir de s.

Tester avec les graphes suivants:

g1 = Graphe2()

g1.ajouter_arc(\"A\",\"B\")

g1.ajouter_arc(\"B\",\"C\")

g1.ajouter_arc(\"A\",\"D\")

g1.ajouter_arc(\"D\",\"C\")

g1.afficher()

print(cycle(g1))

g2 = Graphe2()

g2.ajouter_arc(\"A\",\"B\")

g2.ajouter_arc(\"B\",\"C\")

g2.ajouter_arc(\"D\",\"B\")

g2.ajouter_arc(\"C\",\"D\")

g2.afficher()

print(cycle(g2))

Conclure sur les résultats donnés par la fonction cycle.

","title":"Détecter la présence d'un cycle dans un graphe orienté"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Le parcours en profondeur nous permet de déterminer l'existence d'un chemin entre deux sommets, et même d'en construire un, mais il ne détermine pas pour autant la distance entre deux sommets, c'est-à-dire la longueur minimale d'un chemin entre ces deux sommets.

Si on considère par exemple le graphe des régions et que l'on cherche un chemin entre la région Bretagne et la région Grand Est avec notre parcours en profondeur, alors on trouve le chemin suivant :

Bretagne—>Normandie—>Hauts-de-France—>Île-de-France—>Bourgogne-Franche-Comté —> Grand Est

Ce chemin à la longueur 5, alors qu'il existe un chemin de longueur 3, à savoir

Bretagne—>Normandie—>Île-de-France—>Grand Est

Le fait est que le parcours en profondeur détermine un chemin arbitraire parmi tous les chemins possibles (sans répétitions), car il emprunte les arcs dans un ordre arbitraire.

Si on veut en revanche déterminer la distance entre deux sommets, c'est-à-dire un plus court chemin entre ces deux sommets, alors il faut utiliser un autre algorithme, à savoir le parcours en largeur.

Comme pour le parcours en profondeur, on se donne un sommet de départ, pour initier le parcours. On l'appelle la source.

Et comme pour le parcours en profondeur, on va déterminer peu à peu tous les sommets atteignables à partir de ce sommet de départ.

Ce qui diffère, c'est l'ordre dans lequel ces sommets vont être visités.

Dans le parcours en largeur, on explore le graphe «en cercles concentriques» à partir de la source, c'est-à-dire qu'on visite d'abord tous les sommets à distance 1 de la source, puis tous les sommets à distance 2 de la source, et ainsi de suite, jusqu'à ce que tous les sommets atteignables depuis la source aient été visités.

","title":"Parcours en largeur"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

$\"graphe10.png$

Si on reprend l'exemple du graphe ci-dessus et qu'on effectue un parcours en largeur à partir du sommet A,

alors on va examiner d'abord les sommets B et D, situés à distance 1 de A,
puis les sommets C et E, situés à distance 2,
puis enfin le sommet F, situé à distance 3.

Comme pour le parcours en profondeur, le sommet G n'est pas visité, car il n'est pas atteignable depuis A.

Pour mettre en œuvre le parcours en largeur, et l'idée de cercles concentriques, on peut se servir de deux ensembles.

Le premier, appelé courant, contient des sommets situés à distance d de la source.

C'est notamment dans cet ensemble qu'on pioche le prochain sommet à examiner.

Le second ensemble, appelé suivant, contient des sommets situés à distance d de la source, que l'on examinera après ceux de l'ensemble courant.

À côté de ces deux ensembles, on utilise également un dictionnaire, appelé dist, qui associe à chaque sommet déjà atteint sa distance à la source.

Le parcours en largeur procède ainsi :

initialement, la source est placée dans l'ensemble courant et sa distance est fixée à D:
tant que l'ensemble courant n'est pas vide,
(a) on en retire un sommets,

(b) pour chaque voisin v de s qui n'est pas encore dans dist

* on ajoute v à l'ensemble suivant,

* on fixe dist[v] à dist[s]+1

suivant.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

La figure 2 détaille les différentes étapes de cet algorithme sur l'exemple

du graphe

$\"graphe10.png$

en partant du sommet A. La figure illustre le contenu des deux ensembles, ainsi que les différentes affectations effectuées dans le dictionnaire dist.

courant	suivant	action
A		initialisation, dist[A]=0
	B,D	on retire le sommet A, dist\|B]=1. dist[D]=1
B,D		l'ensemble suivant est vide => échange
D	C	on retire le sommet B, dist\|C]=2
	C,E	on retire le sommet D, dist[E]=2
C,E		l'ensemble suivant est vide => échange
E		on retire le sommet C, dist[F]=3
F		on retire le sommet E
		on retire le sommet F terminé

Figure 2 — Parcours en largeur, à partir du sommet A.

On prendra le temps de bien comprendre cet algorithme.

Le programme ci-dessous réalise cet algorithme en Python. La fonction parcours_largeur réalise un parcours en largeur en partant du sommet

source, à l'aide d'une boucle while.

Programme — Parcours en largeur

def parcours_largeur(g, source):

\"\"\"parcours en largeur depuis le sommet source\"\"\"

dist = {source: 0}

courant = {source}

suivant = set()

while len(courant) > 0:

s = courant.pop()

for v in g.voisins(s):

if v not in dist:

suivant.add(v)

dist[v] = dist[s] + 1

if len(courant) == 0:

courant, suivant = suivant, set()

return dist

def distance(g, u, v):

\"\"\"distance de u à v (et None si pas de chemin)\"\"\"

dist = parcours_largeur(g, u)

return dist[v] if v in dist else None

Les deux ensembles courant et suivant sont des variables locales à la fonction parcours. Une fois le parcours terminé, la fonction parcours renvoie le dictionnaire dist.

Une seconde fonction distance renvoie la distance entre deux sommets u et v, en lançant un parcours en largeur à partir de u puis en consultant la valeur de dist[v].

Si v n'a pas été atteint, on renvoie None.

Tester le programme avec les instructions suivantes :

g2 = Graphe2()

g2.ajouter_arc(\"A\",\"B\")

g2.ajouter_arc(\"B\",\"C\")

g2.ajouter_arc(\"A\",\"D\")

g2.ajouter_arc(\"D\",\"E\")

g2.ajouter_arc(\"E\",\"B\")

g2.ajouter_arc(\"C\",\"E\")

g2.ajouter_arc(\"C\",\"F\")

g2.ajouter_arc(\"G\",\"C\")

g2.afficher()

print(\"distance A F\",distance(g2,\"A\",\"F\"))

print(\"distance A F\",distance(g2,\"A\",\"G\"))

justifier les résultats.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Une file, pour quoi faire une file?

$\"pile_file1.png$

Le parcours en largeur est traditionnellement réalisé avec une file, dans laquelle on ajoute à la fin les nouveaux sommets (ceux que notre code met dans l'ensemble suivant) et dans laquelle on retire au début le prochain sommet à examiner (celui que notre code retire de l'ensemble courant).

Dans cette file, des sommets à la distance d de la source précède des sommets à distance d + 1, ce que l'on peut visualiser ainsi :

L'ordre des sommets situés à une même distance de la source important peu, notre solution avec deux ensembles convient tout aussi bien. Mais surtout, elle explicite la raison pour laquelle notre parcours en largeur est correct, ce que ne montre absolument pas la file.

En terme d'efficacité, il n'y à absolument aucune différence.

","title":""},{"edit":"

"}],[{"text":"

Utilisation

Illustrons l'utilisation de notre parcours en largeur sur le graphe des régions.

Nous avons la variable regions qui contienne la représentation de ce graphe:

regions = Graphe3() #non orienté

regions.ajouter_sommet(\"Guadeloupe\")

regions.ajouter_sommet(\"Martinique\")

regions.ajouter_sommet(\"Guyane\")

regions.ajouter_sommet(\"Corse\")

regions.ajouter_sommet(\"Mayotte\")

regions.ajouter_sommet(\"La Reunion\")

regions.ajouter_arc(\"Hauts-de-France\",\"Normandie\")

regions.ajouter_arc(\"Hauts-de-France\",\"Ile-de-France\")

regions.ajouter_arc(\"Hauts-de-France\",\"Grand Est\")

regions.ajouter_arc(\"Ile-de-France\",\"Grand Est\")

regions.ajouter_arc(\"Ile-de-France\",\"Hauts-de-France\")

regions.ajouter_arc(\"Pays de la Loire\",\"Bretagne\")

regions.ajouter_arc(\"Normandie\",\"Bretagne\")

regions.ajouter_arc(\"Normandie\",\"Pays de la Loire\")

regions.ajouter_arc(\"Pays de la Loire\",\"Centre-Val de Loire\")

regions.ajouter_arc(\"Centre-Val de Loire\",\"Normandie\")

regions.ajouter_arc(\"Pays de la Loire\",\"Nouvelie-Aquitaine\")

regions.ajouter_arc(\"Nouvelie-Aquitaine\",\"Centre-Val de Loire\")

regions.ajouter_arc(\"Ile-de-France\",\"Centre-Val de Loire\")

regions.ajouter_arc(\"Bourgogne-Franche Comte\",\"Centre-Val de Loire\")

regions.ajouter_arc(\"Bourgogne-Franche Comte\",\"Grand Est\")

regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Centre-Val de Loire\")

regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Bourgogne-Franche Comte\")

regions.ajouter_arc(\"Ile-de-France\",\"Bourgogne-Franche Comte\")

regions.ajouter_arc(\"Ile-de-France\",\"Normandie\")

regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Occitanie\")

regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Provence-Alpes-Cote d'Azur\")

regions.ajouter_arc(\"Occitanie\",\"Provence-Alpes-Cote d'Azur\")

regions.ajouter_arc(\"Occitanie\",\"Nouvelie-Aquitaine\")

regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Nouvelie-Aquitaine\")

On peut vérifier la distance entre des régions:

assert distance(regions, \"Bretagne\", \"Occitanie\") == 3

assert distance(regions, \"Bretagne\", \"Bretagne\") == 0

assert distance(regions, \"Bretagne\", \"Mayotte\") == None

Ici, on vérifie que la distance d'une région a elle-même est bien 0 et que la fonction distance renvoie bien None pour deux régions entre lesquelles il n'existe pas de chemin.

Tester les codes et conclure sur les résultats.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Efficacité

Comme pour le parcours en profondeur, le parcours en largeur a un coût directement proportionnel à la taille de la partie du graphe qui a été explorée. En effet, chaque sommet est placé au plus une fois dans l'ensemble suivant, la première fois qu'il est rencontré, c'est-à-dire lorsqu'il n'est pas encore dans le dictionnaire dist.

À ce moment-là, on fixe sa distance, ce qui fait qu'il ne sera pas considéré de nouveau.

De même, chaque arc s —> v est examiné au plus une fois, lorsque le sommet s est retiré de l'ensemble courant.

Le coût en mémoire est celui des deux ensembles et du dictionnaire, au pire proportionnel au nombre total de sommets du graphe.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Étant donnés un graphe et un sommet dans ce graphe, le parcours eu profondeur et le parcours en largeur sont deux algorithimes fondamentaux pour explorer le graphe en partant de ce sommet.

Ces deux parcours déterminent l'ensemble des sommets accessibles depuis le sommet de départ.

Le parcours en profondeur permet de détecter la présence d'un cycle dans un graphe orienté.

Le parcours en largeur permet de déterminer la distance entre le sommet de départ et tout sommet accessible, c'est-à-dire le plus petit nombre d'arcs pour

relier ces deux sommets.

","title":"Conclusion","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Dérouler à la main le parcours en profondeur sur le graphe

pour différentes valeurs du sommet de départ.

Donner à chaque fois la valeur finale de l'ensemble vus, c'est-à-dire l'ensemble des sommets atteints par le parcours.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

sommet | valeur finale

de départ de vus

0 {0,1,3,2}

1 {1,2}

2 C2}

3 {3,1,2}

"}],[{"text":"

Dérouler à la main le parcours en largeur sur le graphe suivant

pour différentes valeurs du sommet de départ.

Donner à chaque fois la valeur finale du dictionnaire dist, c'est-à-dire la distance à la source de chaque sommet atteint par le parcours.

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

sommet valeur finale

de départ de dist

0 {0H0,1H1,38m1,2r 2}

1 {1H0,2H 1}

2 {25 0}

3 {3-0,1H1,2r 2}

"}],[{"text":"

On peut se servir d'un parcours en profondeur pour déterminer si un graphe non orienté est connexe, c'est-à-dire si tous ses sommets sont reliés entre eux par des chemins.

Pour cela, il suffit de faire un parcours en profondeur à partir d'un sommet quelconque, puis de vérifier que tous les sommets ont été atteints par ce parcours.

Écrire une fonction est_connexe() qui réalise cet algorithme.

On pourra se servir de la méthode sommets() de la classe Graphe et de la fonction parcours.

Tester avec les 2 graphes suivants :

g1 :

g2:

print(\"g1 connexe?\",est_connexe(g1))

print(\"g2 connexe?\",est_connexe(g2))

Résultat :

True

False

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

g1 = Graphe3()

g1.ajouter_arc(\"A\",\"B\")

g1.ajouter_arc(\"B\",\"C\")

g1.ajouter_arc(\"A\",\"D\")

g1.ajouter_arc(\"D\",\"C\")

g2 = Graphe3()

g3.ajouter_arc(\"A\",\"B\")

g3.ajouter_arc(\"B\",\"C\")

g3.ajouter_arc(\"A\",\"D\")

g3.ajouter_arc(\"D\",\"C\")

g2.ajouter_arc(\"E\",\"F\")

On suit l’algorithme proposé, en faisant uniquement attention au cas d’un graphe qui ne contiendrait aucun

sommet.

def est_connexe(g):

\"\"\"le graphe est-il connexe?

(uniquement pour un graphe non orienté)\"\"\"

ts = g.sommets()

if len(ts) == 0:

return True

s = ts.pop()

vus = set()

parcours(g, vus, s)

for s in ts:

if s not in vus:

return False

return True

"}],[{"text":"

Dans cet exercice, on se propose d'utiliser le parcours en profondeur pour construire un chemin entre deux sommets, lorsque c'est possible.

On le fait avec deux fonctions, comme dans le programme parcours en profobdeur.

def parcours_ch(g, vus, org, s):

\"\"\"parcours depuis Le sommet s, en venant de org\"\"\"

...

def chemin(g, u, v):

\"\"\"un chemin de u à v, Le cas échéant, None sinon\"\"\"

...

L'idée est que l'attribut vus n'est plus un ensemble mais un dictionnaire, qui associe à chaque sommet visité le sommet qui a permis de l'atteindre pendant le parcours en profondeur.

La fonction parcours_ch prend un argument supplémentaire, org (pour origine), qui est justement le sommet qui a permis d'atteindre s, en empruntant l'arc org —>s.

Écrire le code de la fonction parcours_ch.

Il est très semblable à celui de la fonction parcours du programme parcours en profondeur.

Écrire ensuite le code de la fonction chemin qui renvoie un chemin entre les sommets u et v, le cas échéant, None s'il n'existe pas de chemin entre ces deux sommets.

Pour cela, lancer un parcours en profondeur à partir du sommet u, en donnant à org la valeur None, puis, si

le sommet v a été atteint, construire le chemin dans un tableau en «remontant» le dictionnaire vus de v jusqu'à u.

Tester avec le graphe suivant:

$\"graphe10.png$

print(\"A->F?\",chemin(g2, \"A\", \"F\"))

print(\"A->G?\",chemin(g2, \"A\", \"G\"))

Résultat:

A->F? ['A', 'D', 'E', 'B', 'C', 'F']

A->G? None

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Pour parcours_ch, l'ajout dans un ensemble de-

vient un ajout dans un dictionnaire.

def parcours_ch(g, vus, org, s):

\"\"\"parcours depuis le sommet s, en venant de org\"\"\"

if s not in vus:

vus[s] = org

for v in g.voisins(s):

parcours_ch(g, vus, s, v)

Pour chemin, on prend soin de tester si v a été atteint par le parcours. Dans

le cas contraire, on renvoie None. Sinon, on construit le chemin avec une

boucle while.

def chemin(g, u, v):

\"\"\"chemin de u à v, le cas échéant, None sinon\"\"\"

vus = {}

parcours_ch(g, vus, None, u)

if v not in vus:

return None

ch = []

s=v

while s is not None:

ch.append(s)

s = vus[s]

ch.reverse()

return ch

De fait, le chemin est construit à l'envers. On prend soin de le renverser avec

la méthode reverse avant de le renvoyer.

"}],[{"text":"

Dans cet exercice, on se propose d'utiliser le parcours en largeur pour construire un chemin de longueur minimale entre deux sommets.

On le fait avec deux fonctions, comme dans le programme parcours en largeur.

def parcours_largeur_ch(g, source):

\"\"\"parcours depuis le sommet source\"\"\"

...

def chemin(g, u, v):

\"\"\"un chemin de u à v, le cas échéant, None sinon\"\"\"

L'idée est qu'un dictionnaire vus remplace le dictionnaire dist.

Ce dictionnaire vus associe à chaque sommet visité le sommet qui à permis de l'atteindre pendant le parcours en largeur.

Écrire le code de la fonction parcours_largeur_ch.

Il est très semblable à celui de la fonction parcours_largeur du programme parcours en largeur.

Pour le sommet source, on lui associe la valeur None dans le dictionnaire vus.

Écrire ensuite le code de la fonction chemin qui renvoie un chemin réalisant la distance entre les sommets u et v, le cas échéant, et None s'il n'existe pas de chemin entre ces deux sommets.

Pour cela, lancer un parcours en largeur à partir du sommet u puis, si le sommet v a été atteint, construire le chemin dans un tableau en «remontant» le dictionnaire vus de v jusqu'à u.

Tester avec le graphe suivant:

$\"graphe10.png$

print(\"A->F?\",chemin(g2, \"A\", \"F\"))

print(\"A->G?\",chemin(g2, \"A\", \"G\"))

Résultat:

A->F? ['A', 'B', 'C', 'F']

A->G? None

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On garde la structure du programme 42, le diction-

naire vus prenant la place du dictionnaire dist.

def parcours_largeur_ch(g, source):

\"\"\"parcours depuis Le sommet source\"\"\"

vus = {source: None}

courant = {source}

suivant = set()

while len(courant)>0:

s = courant.pop()

for v in g.voisins(s):

if v not in vus:

suivant.add(v)

vus[v] = s

if len(courant) == 0:

courant, suivant = suivant, set()

return vus

La seconde partie, à savoir la reconstruction du chemin, n’est pas différente

de celle effectuée dans l’exercice précédent pour un parcours en profondeur.

def chemin(g, u, v):

\"\"\"chemin de u à v, Le cas échéant, None sinon\"\"\"

vus = parcours_largeur_ch(g, u)

if v not in vus:

return None

ch = []

s=v

while s is not None:

ch.append(s)

s = vus[s]

ch.reverse()

return ch

"}],[{"text":"

Les nœuds d'un arbre binaire peuvent être vus comme les sommets d'un graphe non orienté.

En particulier, on peut donc parcourir les nœuds d'un arbre avec un parcours en profondeur ou en largeur.

Pour le parcours en profondeur, il s'agit d'un parcours que nous avons déjà présenté, à savoir le parcours préfixe.

Dans cet exercice, on se propose de parcourir les nœuds d'un arbre binaire avec un parcours en largeur.

Écrire une fonction largeur(a) qui reçoit un arbre binaire a en argument et imprime les valeurs de ses différents nœuds dans un ordre donné par un parcours en largeur, c'est-à-dire la valeur contenue dans la racine, puis les valeurs contenues dans les nœuds immédiatement en-dessous (niveau 1), puis celles contenues dans les nœuds encore en-dessous (niveau 2), etc.

Tester le programme avec l'arbre ci-dessus et le code suivant:

largeur(a1)

Résultat:

Indication : Il faut utiliser les classes suivantes pour construire l'arbre a1:

class Noeud:

\"\"\"un noeud d'un arbre binaire\"\"\"

def __init__(self, g, v, d):

self.gauche = g

self.valeur = v

self.droit = d

def __eq__(self, n):

return n is not None \\

and self.gauche == n.gauche \\

and self.valeur == n.valeur \\

and self.droit == n.droit

class ABR:

\"\"\"arbre binaire de recherche\"\"\"

def __init__(self):

self.racine = None

def ajouter(self, x):

if self.racine is None :

self.racine = Noeud(None,x,None)

else :

self.__ajoute__(x,self.racine)

def contient(self, x):

return self.__appartient__(x, self.racine)

def affiche(self):

self.__afficher__(self.racine)

print(\"\\n\")

def __afficher__(self,a):

if a is None:

return

print (\"(\", end=\"\")

self.__afficher__(a.gauche)

print(a.valeur, end=\"\")

self.__afficher__(a.droit)

print(\")\", end=\"\")

def __ajoute__(self,x,a):

if x < a.valeur:

if a.gauche is None:

a.gauche = Noeud(None, x, None)

else:

self.__ajoute__(x,a.gauche)

elif x > a.valeur:

if a.droit is None:

a.droit = Noeud(None, x, None)

else:

self.__ajoute__(x,a.droit)

def __appartient__(self,x, a):

\"\"\"détermine si x apparaît dans l'ABR\"\"\"

if a is None:

return False

if x < a.valeur:

return self.__appartient__(x, a.gauche)

elif x > a.valeur:

return self.__appartient__(x, a.droit)

else:

return True

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On crée l'arbre a1:

a1 = ABR()

a1.ajouter(8)

a1.ajouter(4)

a1.ajouter(12)

a1.ajouter(2)

a1.ajouter(6)

a1.ajouter(10)

a1.ajouter(14)

a1.ajouter(1)

a1.ajouter(3)

a1.ajouter(7)

a1.ajouter(9)

a1.ajouter(13)

a1.ajouter(15)

a1.affiche()

Le programme en largeur est le suivant:

def largeur(a):

h = hauteur(a.racine)

for i in range(1, h+1):

affiche_niveau(a.racine, i)

print()

def affiche_niveau(Noeud, niveau):

if Noeud is None:

return

if niveau == 1:

print(Noeud.valeur)

elif niveau > 1:

affiche_niveau(Noeud.gauche, niveau-1)

affiche_niveau(Noeud.droit, niveau-1)

def hauteur(Noeud):

if Noeud is None:

return 0

else:

lheight = hauteur(Noeud.gauche)

rheight = hauteur(Noeud.droit)

return 1+max(lheight, rheight)

"}],[{"text":"

Nous avons le labyrinthe suivant:

Il est représenté part un liste à 2 dimensions en Python

grid = [[1, 0, 1, 1, 1, 1, 1 ,1],

[1, 0, 0, 0, 0, 0, 1 ,1],

[1, 1, 1, 0, 0, 0, 1 ,1],

[1, 0, 0, 0, 1, 0, 0 ,1],

[1, 0, 1, 1, 0, 0, 1 ,1],

[1, 0, 1, 0, 0, 1, 0 ,1],

[1, 0, 1, 0, 0, 0, 0 ,1],

[1, 1, 1, 1, 1, 1, 0 ,1]]

Avec :

O pour un passage;
1 pour un mur;
l'entrée est en haut à gauche en (1,0);
la sortie est en bas à droite en (len(grid[0])-2,len(grid)-1).

En le modélisant par un graphe et en le parcourant en largeur à l'aide de la fonction chemin, on détermine le moyen pour en sortir:

Vous allez donc écrire une fonction generer_graphe qui a comme argument une grille de labyrinthe et qui retourne son graphe non orienté (Graphe3).

En effet, grace au graphe du labyrinthe et à la fonction chemin, vu précédemment, nous pourrons déterminer le chemin pour en sortir.

Indications : Pour déterminer le graphe, il faut parcourir le labyrinthe et pour chacune des cases ajouter ou non des arcs.

Par exemple :

on ajoute pour cette cellule l'arc correspondant :

glaby.ajouter_arc((x,y),(x+1,y))

et pas :

glaby.ajouter_arc((x,y),(x,y+1))

car il y a un mur.

Tester avec le code suivant :

graphe_laby = generer_graphe(grid)

itineraire = chemin(graphe_laby,(1,0),(len(grid[0])-2,len(grid)-1))

print(itineraire)

Pour notre grille le résultat est le suivant:

[(1, 0), (1, 1), (2, 1), (3, 1), (3, 2), (4, 2), (5, 2), (5, 3), (5, 4), (4, 4), (4, 5), (4, 6), (5, 6), (6, 6), (6, 7)]

Donc avec les fonctions generer_graphe et chemin, nous pouvons déterminer les parcours pour des labyrinthe plus complexes:

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def generer_graphe(grille):

glaby = Graphe3()

for i in range(0,len(grille)-1):

for j in range(0,len(grille[0])-1):

if grille[i][j] == 0 and grille[i][j+1]==0:

glaby.ajouter_arc((j,i),(j+1,i))

if grille[i][j] == 0 and grille[i+1][j]==0:

glaby.ajouter_arc((j,i),(j,i+1))

j+=1

if grille[i][j]==0 and grille[i+1][j]==0:

glaby.ajouter_arc((j,i),(j,i+1))

i+=1

for j in range(0,len(grille[0])-1):

if grille[i][j] == 0 and grille[i][j+1]==0:

glaby.ajouter_arc((j,i),(j+1,i))

return glaby

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 18 Octobre 2020; Mis à jour : 23 Novembre 2020; Clics : 1669

Page 43 sur 79

1ère Générale NSI

Term. Générale NSI

Terminale STI2D SIN

Bts Ccst

Technico-commercial 3.0

Vidéos YouTube

tnsi json sequence 26 Calculabilité

tnsi json sequence 25 Algo - Recherche textuelle

tnsi json sequence 24 Programmation dynamique

tnsi json sequence 23 S.D. : Diviser pour régner

tnsi json sequence 23 S.D. : Parcours en profondeur et en largeur un graphe