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 cpge-paradise.com -- 1 of 15 -- 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 Pest 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, · · · , Kr, on dit que A a une complexité en O(/(K 1 ,. • • , Kr)) s'il existe une constante C > 0 telle que, pour toutes les valeurs de K 1, • • • , Kr suffisamment grandes (c'est-à-dire plus grandes qu'un cer- tain seuil), pour toute instance du problème de paramètres K 1 , · · · , Kr, 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 : • len(l) renvoie la longueur de la liste 1, c'est-à-dire le nombre d'éléments qu'elle contient. Complexité en 0(1) . • 11 == 12 teste l'égalité des listes 11 et 12. Complexité en O(n) avec n le minimum de len(l1) et len(l2). • l[i] désigne le i-ème élément de la liste 1 , où l'indice i est compris entre O et len(l)-1. Complexité en 0(1). • l[i: j] construit la sous-liste [l[i] , ... , l[j-1] J . Complexité en O(j -i). L'usage d~ variantes l[i: J à la place de l[i: len (1) J, et de l[: j] à la place de l[O: j J est aussi autorisé. 1 cpge-paradise.com -- 2 of 15 -- • l.append(e) modifie la li ste 1 en lui a jout a nt l'élément e en dernière position. Complexité en 0(1) (*). • l .pop() renvoie le dernier élément de la liste 1 (supposée non vide) et supprime l'occurrence de cet éléme nt en dernière position dan s la liste. Complexité en 0(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 O(n ) (*). • d [key] 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 0(1) (*). • d [key] = 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 0(1) (*). • key in d teste si la clé key est présente dans d. Complexité en 0(1) (*). 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(texte1, texte2) qui teste si deux textes sont égaux. Donner la complexité de cette fonction. Exemples >>> textes_égaux(['v', ' . ' ]. , 's' , 'a'] , [ 'v', 'a', ' . ' ]. , 's '])False >>> textes_égaux(['v', ' . ' ]. , 's' , 'a'] , [ 'v', ' . ' ]. , 's' , 'a']) True Dans la suite de ce sujet, on pourra utiliser == sur les listes plutôt que cette fonction. 2 cpge-paradise.com -- 3 of 15 -- 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 i (0 ~ i < n) telles que les caractères en position i sont différents dans les deux textes. Question 2. Écrire une fonction distance (texte1, texte2) qui calcule cette quantité. On supposera que les deux textes ont le même nombre de caractères. Donner la complexité de ce tte fonction. Exemples >>> distance(['v', ' . ' 1 ' 's' ' 'a'] ' [ 'v'' 'a ' '' 'i' ' 's ']) 3 >>> distance ( ['a' , 'V' ' ' . ' 1 ' 's '] ' [ 'v'' ' . ' 1 ' 's' ' 'a']) 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(texte1, texte2) qui renvoie True si et seulement si l'ensemble des caractères qui apparaissent dans texte1 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(texte1) + len(texte2)). Exemples >>> aucun_caractère_c , omm1:111( [· 'a' :, 'v', , 'i', '. s'], ['v', False >>> aucu:n_ca:i:actère_commun(['a', 'v', True ' . ' 1 ' 's '] ' ' . ' 1 ' 'r'' 's', 'a']) 'n'' 'e ']) 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 (texte1, texte 2) 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 1 L e g r a n d c h f o r t texte 2 L e p • t t. c h a. S 0 f 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 (texte1, 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' l , avant ' et 'après'. La valeur associée à la clé 'début' est le premier indice de la tranche, les 3 cpge-paradise.com -- 4 of 15 -- 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. Dan s la suite de cette par t ie, on s'appuiera su r 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 tr['début'] def après(tr): return tr['après'] def avant(tr): return tr['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 traitercette structure de données comme une structure immuable 1 . [ ] On peut représenter le différentiel de l,a FIG U RE 1, par la liste suivante : tranche ( 3, [ 'g' , 'r' , 'a' , 'n' , 'd'] , [ 'p ' , 'e ' , 't ' , ' i ' , 't '] ) , tranche(11, ['â', 't', 'e', 'a', · 'u'], ['i', 'e', 'n', ' ', 'a']), tranche ( 17, [' f '] , [' s '] ) , tranche(19, ['r', 't'], ['i', 'f']) La structure de données différentiel. Un différentiel est tine liste (potentiellement vide) de tranches [tr 1 , ... , trk] représentant des modifications touchant des zones distinctes d'untexte, telle que • début(tr 1 ) < fin(tr1) < ... < début(trk) < fin(trk) • pour tout j E [1, k],_pour tout i E [O, len(avant(trj)) - 1 ], avant(trj)[i] =/- après(trj)[ i] Existence et unicité d'un différentiel par positions fixes. Pour deux textes texte 1 et texte 2 de même longueur n, il existe un unique différentiel [ tr 1 , . .. , trk] tel qu e : 1. On rappelle qu 'une stru c ture im muable est une st ructure qui n' est jamais modifiée. C'est par exemple le cas des chaînes et des tuples en Python . · 4 cpge-paradise.com -- 5 of 15 -- • si k > 0, alors O ~ début(tr 1) et fin(trk) ~ n • pour tout j E [1 , k], texte 1 [début(trj): fin(trj)] = avant(tr j ) • pour tout j E [1 , k], texte 2 [début(trj) : fin(trj)] = après(trj) • pour tout i E [O, n-1], si i >> texte versionné = versionne(['a', 'v', 'i', 's']) >>> mod.ifie(texte_versionné, ['v', 'i', 's', 'a']) >>> modifie(texte_versionné, ['v', 'i', 't', 'a']) >>> modifie(texte_versionné, ['l', 'i', 's', 'a']) >>> assert courant(texte_versionné) == ['l', 'i', 's', 'a'] >>> assert historique(texte_versionné) == [ différentiel(['a', 'v', . 'i', 's'], ['v', 'a']) , . ' , s, . 1 • ] différentiel(['v', différentiel(['v', 'i' • 'i' • >>> annule(texte_versionné) ['v', 'i', 't', 'a']) >>> annule(texte_versionné) ['v', 'i', 's', 'a']) >>> annule(texte_versionné) ['a', 'v', 'i', 's'] 's'. 't'. 'a'] , 'a'] • 6 ['V'• [ 'l' , ' . , 1 , , . ,1 , , t' • 's, • 'a']), , a']) cpge-paradise.com -- 7 of 15 -- Partie II : Différentiels sur des positions variables - d'ff' tiels de textes dont les longueurs ne Dans cette partie, nous nous intéressons a des l e~en ition de tranche et de différentiel. La sont plus forcément égales. Nous adaptons pour cela la defin , nter le di·ae'rent· 1 ( t ) dont on va represe u 1e FIGURE 2 présente un exemple de couple texte1 , tex 82 C tt f • 1 t h · ' ur la figure). e e ms, es ranc es par une liste de tranches (représentées par des zones gnsees s . . , • , , · ment de la même longueur, m ahgne es. désignent des portions de textes qm ne sont pas necessa1re texte1 ILl•I lclhi ~ tlolrltl-1 ILl• ~ I lclhl ~~ l-1 textez O 1 2 3 4 5 6 7 B g 10 11 12 13 14 15 16 17 18 19 FIGURE 2 - Exemple de couple (texte 1, texte 2 ) dont on veut calculer le différentiel sur des positions variables. Nouvelle structure de données tranche. Un différentiel d'un texte texte2 vis-à-vis d'un texte texte1 est toujours une liste de tranches mais chaque tranche comporte maintenant 4 clés : • la clé 'début_avant' représente la position i d'un sous-texte avant qui a été supprimé de texte1; • la clé 'avant' est associée au texte avant ; • la clé 'début_après' représente la position dans texte 2 d'un sous-texte après, qui a été ajouté à la place du sous-texte avant en position i dans texte 1 ; • la clé 'après ' est associée au texte après. Dans la suite de cette partie, on s'appuiera sur les fonctions sui·vantes · 1 tte pour man1pu er ce structure. def tranche(arg_début_avant, arg_avant, arg_début_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 tr['début_avant'] 7 arg_après): cpge-paradise.com -- 8 of 15 -- def début_après(tr): return tr['début_après>] def après(tr): return tr['après'] def avant(tr): return tr['avant'] · def fin_avant(tr): return début_avant(tr) + len(avant(tr)) def 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, ... , trk] telle que • début_avant(tr1) $ fin_avant(tr 1) < ... < début_avant(trk) $ fin_avant(trk) • début_après(tr1) $ fin_après(tr 1) < ... < début_après(trk) $ fin_après(trk) • pour tout j E [1, k], aucun_ caractère_commun(avant(trj), après(trj)) = True • pour tout j E (1, k], len(avant(trj)) > 0 ou len(après(trj)) > 0 Notion de différentiel valide vis-à-vis de deux textes. Pour deux textes texte1 et texte2 de même longueur n, un différentiel valide de texte2 vis-à-vis de texte 1 est une liste diff = [tr 1, ... , trk] de tranches telle que : • si k > O, alors O $ début_avant(tr1) et fin_avant(trk) $ len(texte 1) • si k > O, alors O $ début_après(tri) et fin_après(trk) $ len(texte2) • pour tout j E (1, k], textei(début_avant(trj): fin_avant(trj)] = avant(trj) • pour tout j E (1, k], texte2[début_après(trj): fin_après(trj)] = après(trj) • pour tout j E (1, k -1], les sous-textes textei[fin_avant(trj): début_avant(trj+1)] et texte 2 [fin_après(trj): début_après(trj+1)] sont égaux • si k = O alors les textes texte1 et texte2 sont égaux • si k > o alors texte 1 [0 : début_avant(tr1)] = texte2[0 : début_après(tr1)] et textei(fin_avant(tq): len(texte1)] = texte2[fin_après(trk): len(texte2)] On peut représenter le différentiel de la FIGURE 2, par la liste suivante : 8 cpge-paradise.com -- 9 of 15 -- [ tranche( 2, [], 2, [' ' 'b' ' '0' ' 'n']), ' tranche( 5, [, â' ' 't,] ' 9, ['i']), tranche( 8, [], 11, [ 'n' ' ' ']) ' tranche( 9, ['u']' 14, [])' tranche(11, ['f']' 15, ['s'])' tranche(13, [' r, ' , t,] ' 17, [, . , 1 ' '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'], 0, ['t', 'r', 'o', 't', 't']), tranche(2, ['c', 'y', 'c · ', 'l'], 6, ['n'])]) 11 On s'intéresse à la distance d'édition 3 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 1 et texte 2 fixés, et pour O :Si :S len(texte1) et O :S j :S len(texte2), on note M[i][j] la distance d'édition pour passer de textei[O : i] à texte2[0 : j] . La matrice 4 M est appelée matrice de distance d'édition entre texte1 et texte2. La FIGURE 3 présente la matrice M pour texte1 = ['A', 'B', 'C', 'D', 'C', 'E', 'F'] et texte2 = [ 'U' , 'A' , 'B' , 'C' , 'C' , 'X' , 'Y' , 'Z'] . Question 9. Donnez une équation de récurrence qui exprime M[i + ll[j + 1] en fonction de M[i][j], M[i][j + 1], M[i + l][j], texte1[i] et texte2[jl, pour O :S i < len(texte 1) et O :S j < len(texte 2). Justifier brièvement la validité de cette équation, sans rédiger une preuve complète. Question 10. Écrire une fonction levenshtein(texte1, texte2) de complexité polynomiale qui renvoie la matrice M. Préciser sa complexité. On utilisera l'instruction M = [ [ 0 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. 9 cpge-paradise.com -- 10 of 15 -- A B C D C E F 0 1 2 3 4 5 6 7 U .A B C C X Y Z • > 1 2 3 4 5 6 7 8 2 1 2 3 4 ',5 6 7 3 1 2 1 2 3 ;4 5 6 4 3 2 1 2 ,3 4 5 5 4 3 2 3 4 5 6 6 5 4 .3 2 3 4 5 7 6 5 4 3 4 5 6 8 7 6 5 4 5 6 7 FIGURE 3 - Exemple de matrice de distance d'édition Question 11. Écrire une fonction différentiel (texte!, texte2, M) qui calcule un différen- tiel du texte texte2 vis-à-vis du texte texte!, en s'aidant de la matrice de distance M donnée par levenshtein(texte1, texte2). Le différentiel renvoyé doit être de poids minimal. La fonc- tion devra avoir une complexité O(len(texte1) + len(texte2)). Justifier cette complexité etexpliquer 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 texte! 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 diff.2 le différentiel correspondant. Exemple >>>texte= [' l'' >>> texte! [, l'' ' ' ' >» texte2 = = , e'' ' ' 'C' ' 'h'' 'a' ' ~ e, ' , , 'C > ' 'h'' , a, ' 's', '0' ' ' . ' 1 , 'f'] 't' ' , , , a, , , , , s, ' , 0' ' ' . ,1 ' 'f'] , t' ' , , , a, , , ' 't' , 'r' , ' -, e , > s' , ['l', 'e', ' ' 'c', 'h', 'i', 'e', 'n' , ' ', 'a', ' ', 's', 'o', 'i', 'f'] >>> diff1 = différentiel(texte, texte!, levenshtein(texte, texte!)) >>> assert diff1 == [tranche(9, [], 9, [' ', 't', 'r', 'è', 's'])] >>> diff2 = différentiel(texte, texte2, levenshtein(texte, texte2)) »> assert diff2 =· .;, [tranche(5, ['a', 't'l t 5, ['i', 'e', 'n'])] 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 'a pplication du différentiel diff1, puis de la nouvelle versi9n de diff2 sur le texte initial. Dans , , 1 fin 1 tt d t · ['l' 'e' ' ' 'c' 'h' '1· ' ' ' ' , l'exemple precedent, e texte a a en u es • , , , , , , e , n , ' , 'a' , , 't' 'r' 'è' 's', ' ', 's', 'o', 'i', 'f'] . ' ' ' ' , ' 10 cpge-paradise.com -- 11 of 15 -- , 1 bl ue les modifications apportées ne Nous allons être prudents en nous assurant au prea a e q concernent pas les même zones du texte initial. . . . . . ff2) . rend en argument deux diffé- Question 12. Ecrire une fonction conf11t(diffi, . di qm P d d'ff1 et rentiels diff 1 et diff2 et renvoie True si et seulement s'il existe une tranche tr1 ans 1 une tranche tr2 dans dif f 2 telles que [début_avant(tr 1), fin_avant(tr 1 )] n [début_avant(tr2), fin_avant(tr2)] # 0 Cette fonction devra avoir une complexité O(len(diff1) + len(diff2)) que l'on juSt ifiera. Question 13. Écrire une fonction fusionne(diff1, diff2) qui renvoie un nouveau d_ifférentiel représentant la mise à jour de diff 2. Il est attendu que poids (fusionne (diff 1, di~f 2 )) = poids (diff2). On suppose que les deux différentiels dif f 1 et dif f 2 ne sont pas en conflit. Cette fonction devra avoir une complexité O(len(diff1) + len(diff2)). Exemple >» assert not conflit(diff1, diff2) >>> print(applique(applique(texte, diff1), fusiom1e(diff1, diff2))) ['l', 'e', ' ' 'c', 'h', 'i', · 'e', 'n', ' ', 'a', ' ', 't', 'r', 'è', 's', ' ' 's', '-0', 'i', '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 1 et texte 2, on considère une grille de dimension (len(texte1)+l) x (len(texte2)+l) dont chaque · cellule est un sommet du graphe. On appelle sommet un couple (i,j) tel que O::; i::; len(texte 1) et O :'.S j :'.S len(texte2). Chaque sommet (i,j) aura au plus trois arcs sortants vers des sommets parmi (i + 1,j), (i,j + 1) et (i + 1,j + 1) . On appelle entrée du graphe le sommet (0, 0) et sortie le sommet (len(texte1), len(texte2)). La FIGURE 4 présente la matrice de distance d'édition pour texte 1 = [ 'b', 'i', 'e', 'n,] et texte2 = [ 'b' , 'o' , 'n' , 'n' , 'e '], ainsi que le graphe associé, sans les poids des arcs. Le graphe ne sera jamais explicitement représenté, mais nous somm~s en mesure de calculer l'ensemble des arcs sortants de chaque sommet. Question 14. Écrire une fonction successeurs(texte1, 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 texte1 et texte 2 : pour tout sommet (i,j) du graphe, M[i][j] coïncide avec la longueur d'un plus court chemin de (0, 0) à (i, j). Démontrer cette propriété avec une récurrence. 11 cpge-paradise.com -- 12 of 15 -- b 0 n n e b 0 n n e b 0 1 2 3 4 5 b 1 0 1 2 3 4 2 1 2 3 4 5 e e 3 2 3 4 5 4 n 4 3 4 3 4 5 n 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 arçs sont ici remplacés par ... ) > ï> > textel = ['h' ., 'i', · ,e,, 'n'] 0 >>> texte2 = ['b', 'o', 'n ' , 'n', 'e'] »> successeurs(texte1, t · exte2, { 2,4)) , H<3, 4) _. . .•. ), ((2, . 5), .. ._) _.' q ~. 5), ... )J 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 0 différentes opérations élémentaires. • La fonction vide() construit une file vide (de cardinal 0) en 0(1) . • La fonction est_vide(file) teste si la file file est vide en 0(1) . 1 • La fonction e;x:traire_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 (i, j) le plus petit pour l'ordre lexicographique 5 parmi les sommets de priorité minimale. Sa complexité est en O(log(cardinal(file))). · • La fonction ajoute(file, sommet, priorité) ajoute à la file file un sommet sommet avec une priorité p i- iori té . 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 (i 1 , j 1 ) ~ (i 2 , J2) si et seulement si i1 < i2 ou (i1 = i2 et j1 < J2) . ' 12 cpge-paradise.com -- 13 of 15 -- def dijkstra(texte1, texte2): entrée= (0, 0) sortie= (len(texte1), len(texte2)) file = vide() dist = {} vue={} horloge= 0 ajoute(file, entrée, 0) dist[entrée] = 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(texte1, texte2, sommet): d = dist[sommet] + distance assert False if not voisin in distord< dist[voisin]:dist[voisin] = d ajoute(file, voisin, d) 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 1 et texte2. 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 II. 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 [sortie] 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(texte1, texte2, s) est inférieure ou égale à la longueur pondérée d'un plus court chemin des jusqu'à la sortie du graphe. Question 17. Donner une fonction h qui satisfait cette hypothèse, avec une complexité en 0(1), et qui permet un gain de temps de calcul (vis-à-vis du nombre de sommets extraits de lafile avant de rencontrer la sortie) sur l'exemple texte 1 = ['A' , 'B' , 'C '], texte2 = [' B' , 'X']. Justifier en comparant les dictionnaires dist_final renvoyés par les deux algorithmes sur cet exemple. 13 cpge-paradise.com -- 14 of 15 -- def astar(texte1, texte2): entrée= (0, 0) sortie= (len(texte1), len(texte2)) . file = vide() dist = {} vue={} horloge= 0 ajoute(file, entrée, 0) dist[entrée] = 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(texte1, texte2, sommet): d = dist[sommet] + distance if not voisin in distord< dist[voisin]:dist[voisin] = d ajoute(file, voisin, d + h(texte1, texte2, voisin)) assert False FIGURE 6 - Algorithme A*. * * * 14 cpge-paradise.com -- 15 of 15 --