X/ENS Informatique B MP-PC-PSI 2023

ECOLE POLYTECHNIQUE - ESPCI
ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMISSION 2023

JEUDI 20 AVRIL 2023
16h30 - 18h30

FILIERES MP-PC-PSI
Epreuve n° 8

INFORMATIQUE B (XELSR)

Durée : 2 heures

L'utilisation des calculatrices n'est pas
autorisée pour cette épreuve

Gestion de versions de grands textes

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve. Le 
langage de
programmation sera obligatoirement Python.

Dans ce sujet, on s'intéresse à des textes de grande taille auxquels plusieurs 
auteurs apportent
des modifications au cours du temps. Ces textes peuvent par exemple être des 
programmes
informatiques développés par de multiples auteurs. Il est important de pouvoir 
efficacement
gérer les différentes versions de ces programmes au cours de leur développement 
et limiter le
stockage et la transmission d'informations redondantes. Nous allons pour cela 
nous intéresser à
une notion de différentiels entre textes.

Complexité. La complexité, ou le temps d'exécution, d'une fonction P est le 
nombre d'opé-
rations élémentaires (addition, multiplication, affectation, test, etc...) 
nécessaires à l'exécution
de P dans le cas le pire. Lorsque la complexité dépend d'un ou plusieurs 
paramètres K1,--: ,kKry,
on dit que À à une complexité en O(f(K1,---,K,)) s'il existe une constante C' > 
0 telle que,
pour toutes les valeurs de #K1,:--,K, suffisamment grandes (c'est-à-dire plus 
grandes qu'un cer-
tain seuil), pour toute instance du problème de paramètres #1,---:,K,, la 
complexité est au plus

C'- f(K1, "+ , kr).

Lorsqu'il est demandé de donner la complexité d'un programme, le candidat devra 
justifier
cette dernière si elle ne se déduit pas directement de la lecture du code.

Rappels concernant le langage Python. Ce sujet utilise les types Python listes 
et diction-
naires, mais seules les opérations mentionnées ci-dessous sont autorisées dans 
vos réponses. Quand
une complexité est indiquée avec un symbole (+), cela signifie que nous faisons 
une hypothèse
simplificatrice sur sa complexité. La justification de cette simplification est 
hors-programme.

Si 1, 11, 12 désignent des listes en Python :

e len(1) renvoie la longueur de la liste 1, c'est-à-dire le nombre d'éléments 
qu'elle contient.
Complexité en O(1).

e 11 == 12 teste l'égalité des listes 11 et 12. Complexité en Ofn) avec n le 
minimum de
len(11) et len(12).

e 1[i]l désigne le i-ème élément de la liste 1, où l'indice i est compris entre 
0 et len(1)-1.
Complexité en O(1).

e 1[i:j] construit la sous-liste [1[i], ..., 1[j-1]] . Complexité en O(j ---i). 
L'usage des
variantes 1[i:] à la place de 1[i:len(1)1, et de 1[:j] à la place de 1[0:j] est 
aussi
autorisé.
e l.append(e) modifie la liste 1 en lui ajoutant l'élément e en dernière 
position. Complexité

en O(1) (+).

e l.pop() renvoie le dernier élément de la liste 1 (supposée non vide) et 
supprime l'occurrence
de cet élément en dernière position dans la liste. Complexité en O(1) (+).

On pourra aussi utiliser la fonction range pour réaliser des itérations.

Si d est un dictionnaire Python :

{key_1: v_1, ..., key _n: v_n} crée un nouveau dictionnaire en associant chaque 
valeur
v_i à une clé key_i. Complexité en Ofn) (+).

dfkey]l renvoie la valeur associée à la clé key dans d et lève une erreur si la 
clé key n'est
pas présente. Complexité en O(1) (+).

dikey] = v modifie d pour associer la valeur v à la clé key, même si la clé key 
n'est pas
présente dans d initialement. Complexité en O(1) (+).

key in d teste si la clé key est présente dans d. Complexité en O(1) (x).

Sauf mention contraire, les fonctions à écrire ne doivent pas modifier leurs 
entrées.

La structure de données texte. Dans ce sujet, on appelle texte une liste de 
caractères. Par
exemple, ['b?, ?'i?, n°, ?g?, ?'o?] est un texte de longueur 5.

Partie I : Différentiels par positions fixes

Dans cette partie, nous traitons le problème avec une hypothèse simplificatrice 
: les textes
comparés ont toujours la même taille.

Question 1. Sans utiliser le test == sur les listes, écrire une fonction 
textes_égaux(textel,
texte2) qui teste si deux textes sont égaux. Donner la complexité de cette 
fonction.

Exemples

>>> textes_égaux(l[l'v?, ?i?, ?s?, ?a?'], [?v?, ?a?, ?i?, ?s?])
False
>>> textes_égaux(l[l'v?, ?i?, ?s?, ?a?], [?v?, ?1?, ?s?, ?a?])
True

Dans la suite de ce sujet, on pourra utiliser == sur les listes plutôt que 
cette fonction.
Si deux textes ne sont pas égaux mais ont la même longueur n, on souhaite 
compter le nombre
de positions qui diffèrent, c'est à dire déterminer combien il existe de 
positions 4 (0 < à < n) telles que les caractères en position ? sont différents dans les deux textes. Question 2. Écrire une fonction distance(textel, texte2) qui calcule cette quantité. On supposera que les deux textes ont le même nombre de caractères. Donner la complexité de cette fonction. Exemples 3 4 Question 3. En vous aidant d'un dictionnaire dont les clés sont des caractères, écrire une fonc- tion aucun_caractère_commun(textel, texte2) qui renvoie True si et seulement si l'ensemble des caractères qui apparaissent dans textei est disjoint de l'ensemble des caractères qui appa- raissent dans texte2. Les deux textes peuvent avoir ici des longueurs différentes. Cette fonction devra avoir une complexité O(len(texte1i) + len(texte2)). Exemples >>> aucun_caractère_commun(['a?, ?v?, 1°, ?s?], ['v?, 1°, ?s?, ?a°])
False
>>> aucun_caractère_commun(['a?', ?v?, 1°, ?'s?'], ['u', ?'r°, °n°, ?'e'l)
True

Nous introduisons maintenant une structure de données spécifique pour 
représenter un diffé-
rentiel par positions fixes entre deux textes.

La FIGURE 1 présente un exemple de couple de textes (textei,texte2) qui 
diffèrent sur 4
tranches (représentées par des zones grisées sur la figure). En dehors des 
tranches, les textes sont
égaux.

texte: Lie grain dl jcihlältlelalu. iflolr|t).
tete |[Lle| |pleltlilt| [clhlileln| Ja) |s)oli)s).
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

FIGURE 1 -- Exemple de couple (textei,texte2) dont on veut calculer le 
différentiel (sur des
positions fixes).

La structure de données tranche. Une tranche est un dictionnaire avec trois 
clés ? début".
'avant" et 'après"'. La valeur associée à la clé ?'début"? est le premier 
indice de la tranche, les
textes associés aux clés 'avant" et après" représentent les textes (de même 
longueur) de la
tranche avant et après modification. Dans la suite de cette partie, on 
s'appuiera sur les fonctions
suivantes pour manipuler cette structure.

def tranche(arg_début, arg_avant, arg_après):
return {'début': arg_ début, 'avant': arg_avant, 'après': arg_après}

def début (tr):
return trl'début"]

def après(tr):
return trl'après?]

def avant(tr):
return trl'avant"?|

def fin(tr):
return début(tr) + len(après(tr))

Nous ne fournissons pas de fonction pour modifier une tranche car nous 
souhaitons traiter
cette structure de données comme une structure immuable !.

On peut représenter le différentiel de la FIGURE 1, par la liste suivante :

C
tranche(3, L'g?, 'r', a', ?'n?, 'd'], [L'p"?, 'e?, ?t?, 'i?, t]),
tranche(11, ['4?, +', ?e?, ?'a?, 'u°], ['i?, 'e', n°, ? ?, 'a°]),
tranche(17, ['f?], ['s?]),
tranche(19, ['r?, ?'t'], [?1°, 'f?])

]

La structure de données différentiel. Un différentiel est une liste 
(potentiellement vide)
de tranches [tri, ..., try] représentant des modifications touchant des zones 
distinctes d'un
texte, telle que

e début(tr1) < fin(tri) <...< début(try) < fin(try) e pour tout j EUR [1,k], pour tout à EUR [0,len(avant(tr;)) -- 1}, avant(tr;)[i] £ après(tr;)|il Existence et unicité d'un différentiel par positions fixes. Pour deux textes texte: et texte de même longueur n, il existe un unique différentiel [tr1, ..., try] tel que : 1. On rappelle qu'une structure immuable est une structure qui n'est jamais modifiée. C'est par exemple le cas des chaînes et des tuples en Python. si k > O0, alors 0 < début(tr1) et fin(try) >> texte_versionné = versionne(['a?', ?v', '1°, 's'l)

>>> modifie(texte_versionné, ['v?, 1°, ?'s?, ?'a°])

>>> modifie(texte_versionné, ['v?, 1°, °'t?', ?'a°])

>>> modifie(texte_versionné, ['1?, 1°, ?'s?', ?'a°])

>>> assert courant(texte_versionné) == [?1?, ?i°, ?'s?, ?'a?]

>>> assert historique(texte_versionné) == [
différentiel([?a?, ?v?, ?i?, ?s'], [?'v?, 1°, ?s?, 'a°]),
différentiel([?v?', ?i?, ?s?, ?'a'], [?'v?, 1°, ?'t?, 'a°]),
différentiel([?v?, ?i?, 't', ?'a'], [?'1?, 'i?, ?s°, 'a°])

]

>>> annule(texte_versionné)

L'v?, 1, ?t?, 'a°])

>>> annule(texte_versionné)

L'v?, 71?, 7S?, a?])

>>> annule(texte_versionné)

['a?, 2v?, 71?, s?]
Partie IT : Différentiels sur des positions variables

Dans cette partie, nous nous intéressons à des différentiels de textes dont les 
longueurs ne
sont plus forcément égales. Nous adaptons pour cela la définition de tranche et 
de différentiel. La
FIGURE 2 présente un exemple de couple (texte1,texte2) dont on va représenter 
le différentiel
par une liste de tranches (représentées par des zones grisées sur la figure). 
Cette fois, les tranches
désignent des portions de textes qui ne sont pas nécessairement de la même 
longueur, ni alignées.

ets [Llel lenlältelall [lol

texte Le. bloin. jcihlileln. a. islo)ilf|.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

FIGURE 2 -- Exemple de couple (textei,texte2) dont on veut calculer le 
différentiel sur des
positions variables.

Nouvelle structure de données tranche. Un différentiel d'un texte textes 
vis-à-vis d'un
texte texte, est toujours une liste de tranches mais chaque tranche comporte 
maintenant 4 clés :

la clé 'début_avant" représente la position ? d'un sous-texte avant qui a été 
supprimé de
texte];

e la clé 'avant" est associée au texte avant ;

e la clé 'début_après' représente la position dans texte2 d'un sous-texte 
après, qui a été
ajouté à la place du sous-texte avant en position ? dans texte: ;
e la clé après' est associée au texte après.

Dans la suite de cette partie, on s'appuiera sur les fonctions suivantes pour 
manipuler cette
structure.

def tranche(arg_début_avant, arg_avant, arg_début_après, arg_après):
return {'début_avant': arg_début_avant,
'avant"': arg_avant,
'début_après': arg_début_après,
'après': arg_après}

def début _avant(tr):
return trl'début _avant"?|
def

def

def

def

def

début_après(tr):
return trl'début_après?]

après (tr):
return trl'après?]

avant (tr):
return trl'avant"?|

fin_avant(tr):
return début _avant(tr) + len(avant(tr))

fin_après (tr):
return début_après(tr) + len(après(tr))

Nouvelle structure de données différentiel. Un différentiel est une liste 
(potentiellement
vide) de tranches [tr1, ..., try] telle que

e début avant(tri) < fin avant(tri) <...< début avant(tr;) < fin avant(try) e début après(tri) < fin après(tri) <...< début après(try;) < fin après(try) e pour tout j E [1,k], aucun caractère commun(avant(tr;),après(tr;)) -- True e pour tout j EUR [1,k|, len(avant(tr;)) > 0 ou len(après(tr;)) > 0

Notion de différentiel valide vis-à-vis de deux textes. Pour deux textes texte] 
et textes
de même longueur n, un différentiel valide de texte2 vis-à-vis de texte: est 
une liste diff =

Ctr: ,

., trz] de tranches telle que :

si k > 0, alors 0 < début avant(tri)et fin avant(try) < texte) en( si k > 0, alors 0 < début après(tr:) et fin après(trz) < len(texte)) pour tout j E [1,k|, texteildébut avant(tr;):fin avant(tr;)] = avant(tr;) ) ) : pour tout j EUR [1,k], textesldébut après(tr;):fin après(tr;)] = après(tr,;) pour tout j EUR [1,k -- 1}, les sous-textes textei[fin avant(tr;):début avant(tr;,1)]et texteblfin après(tr;):début après(tr;}1)] sont égaux si & = 0 alors les textes texte: et texte2 sont égaux si k > 0 alors texte1[0 : début avant(tri)] -- texte){[0 : début après(tri)] et
texteilfin avant(try):len(textei)| -- texte[fin après(try):len(texte:)

On peut représenter le différentiel de la FIGURE 2, par la liste suivante :
tranche( 2, [], 2, L? ?, ?b?, 'o?°, 'n']l),
tranche( 5, ['4°, 't'], 9, ['i']),

tranche( 8, [], 11, [?'n°?, ? ?]),

tranche( 9, ['u'], 14, []),

tranche(11, ['f'], 15, ['s']),

tranche(13, ['r', 't'], 17, ['i', "f°])

On admet que, comme dans la partie précédente, on peut écrire des fonctions 
applique
et inverse satisfaisant les mêmes propriétés que précédemment sur cette 
nouvelle notion de
différentiel. On définit le poids d'un différentiel comme la somme des 
longueurs des sous-textes
avant (tr) et après(tr) pour toutes les tranches tr qui le composent.

Question 8. Écrire une fonction poids(diff) qui calcule le poids d'un 
différentiel diff. Donner
sa complexité.

Exemple

>>> poids([tranche(O, ['b°], O, L't?, ?r°, ?o°, 't?, °'t?]),
tranche(2, ['c?, 'y?, °c', °1°1, 6, ['n'])])
11

On s'intéresse à la distance d'édition® entre deux textes. Dans ce sujet, on 
définit cette
distance comme le nombre minimal de suppressions et d'insertions de caractères 
pour passer
d'un texte à un autre. On peut facilement se convaincre que cette distance 
coïncide avec le poids
minimal possible pour un différentiel entre les deux textes.

Nous allons calculer cette distance par programmation dynamique. Pour deux 
textes texte:
et texte) fixés, et pour 0 < à < len(textei) et 0 < j < len(texteb), on note M{i][j] la distance d'édition pour passer de texte1[0 : i] à texte2[0 : j]. La matrice M est appelée matrice de distance d'édition entre texte et texte. La FIGURE 3 présente la matrice M pour texte, -- ['A?°,?B?,?C?,?D°,?C?,°E°,'F°] et texte) -- ['U?,°A?,?B°,C?,°C?,°X°,Y°,7°]. Question 9. Donnez une équation de récurrence qui exprime Mi + 1][j + 1] en fonction de Mlill5}, Mlillj +1}, Mli + 1]{j|, texteili] et texte)[j], pour 0 < à < len(texte:) et 0 < 7j < len(texte2). Justifier brièvement la validité de cette équation, sans rédiger une preuve complète. Question 10. Écrire une fonction levenshtein(textel, texte2) de complexité polynomiale qui renvoie la matrice M. Préciser sa complexité. On utilisera l'instruction M = [T O for j in range(m)] for i in range(n) ] pour ini- tialiser une matrice M de n lignes et m colonnes avec des zéros. 3. Cette distance est communément appelée distance de Levenshtein. 4. Dans ce sujet, nous représenterons ces matrices par des listes de listes d'entiers. U ABCC XX Y Z À 011 2:314/56 7 8 8 112111234516 7 c 218312111/2,3 4516 D 314183/211/2,3|415 c 4514/31/23 4516 E 51615 4131/2/3|415 F 67/16 5141/31/45, 6 118 71615145) 6|\7 FIGURE 3 -- Exemple de matrice de distance d'édition Question 11. Écrire une fonction différentiel(textel, texte2, M) qui calcule un différen- tiel du texte texte2 vis-à-vis du texte textel, en s'aidant de la matrice de distance M donnée par levenshtein(textel, texte2). Le différentiel renvoyé doit être de poids minimal. La fonc- tion devra avoir une complexité O(len(texteli) + len(texte2)). Justifier cette complexité et expliquer brièvement pourquoi le différentiel calculé satisfait les propriétés attendues par un différentiel. On pourra s'aider de la FIGURE 3 pour comprendre quel parcours suivre dans la matrice M. Si on se place dans un scénario de travail collaboratif où deux auteurs différents modifient en parallèle le même texte texte, il est nécessaire de pouvoir fusionner leur travail. Nous notons textei le nouveau texte obtenu après le travail du premier auteur sur texte et diff1 le différen- tiel correspondant. De même, nous notons texte2 le texte obtenu après le travail du deuxième auteur sur le même texte texte, et diff2 le différentiel correspondant. Exemple >>> texte =
Re 7e?, 2 2, 2C?, 7h?, 7a?, 2t?, 2 2, 7a?, 2 2, 7S?, 70?, 21?, F2]
>>> textel =
Re 7e?, 2 2, 2C?, 7h?, 7a?, 2t?, 2 2, 7a?, 2 2, 2t?, 7r?, 8?, 7S?,
2 2, 7S?, 70?, 21?, f?]
>>> texte2 =
Re 7e?, 2 2, 2C?, 7h?, 21?, 7e?, n°, 2 2, 7a?, 2 2, 7S?, 70?, 217, f?]
>>> diffi = différentiel(texte, textel, levenshtein(texte, textel))

>>> assert diffi == [tranche(9, [1], 9, [?' ?, ?t?, 'r?, ?'è?, 's'])]
>>> diff2 = différentiel(texte, texte2, levenshtein(texte, texte2))
>>> assert diff2 == [tranche(5, ['a°, 't'], 5, ['i', 'e'°, 'n'l)]

Pour fusionner le travail des deux auteurs, on apporte des modifications à 
diff2 de façon
à ce que le texte final, qui inclut les modifications des deux auteurs, soit 
exprimable comme
l'application du différentiel diff1, puis de la nouvelle version de diff2 sur 
le texte initial. Dans
l'exemple précèdent, le texte final attendu est : ['1?, ?'e?', ? ?, ?c?, 'h°, 
?'1i?, ?e°, ?n',
2 2, 7a?, 2 2, 2T?, 7r?, è?, 2S?, 2 2, 7S?, 70?, 71°, F2],

10
Nous allons être prudents en nous assurant au préalable que les modifications 
apportées ne
concernent pas les même zones du texte initial.

Question 12. Écrire une fonction conflit(diffi, diff2) qui prend en argument 
deux diffé-
rentiels diff1i et diff2 et renvoie True si et seulement s'il existe une 
tranche tr dans diffi et
une tranche tr2 dans diff2 telles que

début avant(tri),fin avant(tri)|MN[début avant(tro), fin avant(tro)| £(

Cette fonction devra avoir une complexité O(len(diff1) + len(diff2)) que l'on 
justifiera.

Question 13. Écrire une fonction fusionne(diffi, diff2) qui renvoie un nouveau 
différentiel
représentant la mise à jour de diff2. Il est attendu que poids(fusionne(diff1i, 
diff2)) --
poids(diff2). On suppose que les deux différentiels diff1 et diff2 ne sont pas 
en conflit. Cette
fonction devra avoir une complexité O(len(diff1) + len(diff2)).

Exemple

>>> assert not conflit(diffi, diff2)

>>> print(applique(applique(texte, diffi), fusionne(diff1i, diff2)))

[°1?, 7e?, 2 2, 2C?, 7h?, 71?, 7e?, n°, 2 2, 7a?, 2 2, 2t?, 7r?, 78?, 7S?, 2 2,
7S?, 70?, 71?, f?]

Partie III : Calcul de différentiels par calcul de plus courts chemins

Dans cette partie on souhaite exprimer le problème de calcul de distance 
d'édition comme un
problème de calcul de plus court chemin dans un graphe orienté pondéré. Pour 
deux textes texte:
et texte), on considère une grille de dimension (1en(texte1)+1)x(1en(texte2)+1) 
dont chaque
cellule est un sommet du graphe. On appelle sommet un couple (4, j) tel que 0 < à < len(texte:) et 0 < j < len(texte2). Chaque sommet (4, j) aura au plus trois arcs sortants vers des sommets parmi (i+1,3), (à,j +1) et (i+1,7+1). On appelle entrée du graphe le sommet (0,0) et sortie le sommet (1len(texte]),len(texteob)). La FIGURE 4 présente la matrice de distance d'édition pour texte; = ['b?,?71?,°e?,'n?] et texteo = ['b?,'0?,°n°,°n°,?'e?], ainsi que le graphe associé, sans les poids des arcs. Le graphe ne sera jamais explicitement représenté, mais nous sommes en mesure de calculer l'ensemble des arcs sortants de chaque sommet. Question 14. Écrire une fonction successeurs(textel, texte2, sommet) qui renvoie une liste de couples (voisin, distance), de taille au plus 3, représentant les sommets destinations des arcs sortant du sommet sommet, avec les poids associés. L'existence et la pondération des arcs devra permettre d'assurer la correspondance suivante entre le graphe et la matrice de distance d'édition de texte: et textes : pour tout sommet (i,j) du graphe, M{il[j] coïncide avec la longueur d'un plus court chemin de (0,0) à (4, j). Démontrer cette propriété avec une récurrence. 11 0112, 3)415 b 21112,3)415 | Hd Ki 81213) 41514 41314 8)415 NN FIGURE 4 -- Exemple de matrice de distance d'édition et de graphe associé (les poids des arcs ont été volontairement omis). Exemple (les poids des arcs sont ici remplacés par ...) >>> textel = ['b°, 'i', ?'e°', 'n?']
>>> texte2 = ['b', 'o°, 'n°, 'n', 'e']
>>> successeurs(textel, texte2, (2,4))

[CC3, 4), ...), C2, 5), ...), (C3, 5), ...)]

Pour calculer un plus court chemin, on peut utiliser une variante l'algorithme 
de Dijkstra,
présentée dans la FIGURE 5. Il s'appuie sur une structure de données de file de 
priorité sur les
sommets (i,j) du graphe, dont on ne précise pas l'implémentation mais dont on 
précise ici la
complexité des différentes opérations élémentaires.

e La fonction vide() construit une file vide (de cardinal 0) en O(1).
e La fonction est_vide(file) teste si la file file est vide en O(1).

e La fonction extraire_min(file) supprime l'élément de priorité minimale dans 
la file file
et le renvoie. En cas d'égalité de priorités, elle renvoie le sommet (4, j) le 
plus petit pour

l'ordre lexicographique*® parmi les sommets de priorité minimale. Sa complexité 
est en
O(log(cardinal(file))).

e La fonction ajoute(file, sommet, priorité) ajoute à la file file un sommet 
sommet
avec une priorité priorité. L'opération augmente de 1 le cardinal de la file si 
le sommet
n'est pas déjà présent avec cette priorité. Sa complexité est en 
O(log(cardinal(file))).

5. On rappelle que l'ordre lexicographique < sur les paires est défini par (i1,71) < (2,2) si et seulement si 11 < 12 OU (1 -- 12 et 71 < j2). 12 def dijkstra(textel, texte2): entrée = (0, 0) sortie = (len(textel), len(texte2)) file = vide() dist = {} vue = {} horloge = 0 ajoute(file, entrée, 0) dist{entréel] = 0 while not est_vide(file): sommet = extraire _min(file) if not sommet in vue: vue [sommet] = horloge horloge +=1 if sommet == sortie: dist_final = {sommet: dist{[sommet] for sommet in vue} return dist_final for voisin, distance in successeurs(textel, texte2, sommet): d = dist{[sommet] + distance if not voisin in dist or d < dist[voisinl]: dist{[voisin] = d ajoute(file, voisin, d) assert False FIGURE 5 -- Une variante de l'algorithme de Dijkstra. Question 15. En vous appuyant sur les propriétés de l'algorithme de Dijkstra vues en cours, expliquer pourquoi l'utilisation de la fonction dijkstra permet de calculer la distance d'édi- tion entre texte et textes. Préciser ce que contient le dictionnaire dist_final renvoyé, en caractérisant soigneusement l'ensemble des clés de ce dictionnaire. Question 16. Donner la complexité de la fonction dijkstra et commenter son intérêt par rapport à l'algorithme de programmation dynamique de la partie IT. On s'intéresse maintenant à l'algorithme A*, présenté dans la FIGURE 6. Il s'appuie sur une fonction heuristique h qui estime la distance de chaque sommet à la sortie du graphe. On admet que cet algorithme renvoie un dictionnaire dist_final tel que dist_final[sortiel est la longueur d'un plus court chemin de l'entrée à la sortie du graphe, si la fonction heuristique h utilisée est admissible, c'est à dire si pour tout sommet s du graphe, h(texte],texte2,s) est inférieure ou égale à la longueur pondérée d'un plus court chemin de s jusqu'à la sortie du graphe. Question 17. Donner une fonction h qui satisfait cette hypothèse, avec une complexité en O(1), et qui permet un gain de temps de calcul (vis-à-vis du nombre de sommets extraits de la file avant de rencontrer la sortie) sur l'exemple texte; -- ['A?,°B?,?C°], texte2 -- ['B°,?X?]. Justifier en comparant les dictionnaires dist_final renvoyés par les deux algorithmes sur cet exemple. 13 def astar(textel, texte2): entrée = (0, 0) sortie = (len(textel), len(texte2)) file = vide() dist = {} vue = {} horloge = 0 ajoute(file, entrée, 0) dist{entréel] = 0 while not est_vide(file): sommet = extraire _min(file) vue [sommet] = horloge horloge += 1 if sommet == sortie: dist_final = {sommet: dist{[sommet] for sommet in vue} return dist_final for voisin, distance in successeurs(textel, texte2, sommet): d = dist{[sommet] + distance if not voisin in dist or d < dist[voisinl]: dist{[voisin] = d ajoute(file, voisin, d + h(textel, texte2, voisin)) assert False FIGURE 6 -- Algorithme A*. 14