DS 1 MP* Corrigé (X-ENS 2023)#

Partie I : Diﬀérentiels par positions ﬁxes#

Question 1#

La complexité est en O(\(n\)) où \(n\) est la taille de texte1 (égal à la taille de texte2).

def textes_égaux(texte1, texte2):
    if len(texte1) != len(texte2):
        return False
    for i in range(len(texte1)):
        if texte1[i] != texte2[i]:
            return False
    return True

Question 2#

La complexité est clairement O(\(n\)).

def distance(texte1, texte2):
    d = 0
    for i in range(len(texte1)):
        if texte1[i] != texte2[i]:
            d += 1
    return d

Question 3#

On note \(n_1\) et \(n_2\) les tailles de texte1 et texte2. La complexité est en O(\(n_1+n_2\)) d’après les annotations ci-dessous.

def aucun_caractère_commun(texte1, texte2):
    d = {}
    for c in texte1: # O(n1)
        d[c] = True
    for c in texte2: # O(n2)
        if c in d: # O(1)
            return False
    return True

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))

Question 4#

La complexité totale de la fonction ci-dessous correspond à la somme des longueurs des tranches, car texte1[i:j] est en O(\(j-i\)). La complexité est donc bien O(\(n\)).

def différentiel(texte1, texte2):
    L, i = [], 0
    while True:
        d = {}
        while i < len(texte1) and texte1[i] == texte2[i]:
            i += 1
        if i == len(texte1):
            return L
        j = i + 1
        while j < len(texte1) and texte1[j] != texte2[j]:
            j += 1
        L.append(tranche(i, texte1[i:j], texte2[i:j]))
        i = j
    return L

texte1 = list("Le grand château fort")
texte2 = list("Le petit chien a soif")
d = différentiel(texte1, texte2)
d

[{'début': 3,
  'avant': ['g', 'r', 'a', 'n', 'd'],
  'après': ['p', 'e', 't', 'i', 't']},
 {'début': 11,
  'avant': ['â', 't', 'e', 'a', 'u'],
  'après': ['i', 'e', 'n', ' ', 'a']},
 {'début': 17, 'avant': ['f'], 'après': ['s']},
 {'début': 19, 'avant': ['r', 't'], 'après': ['i', 'f']}]

Question 5#

La concaténation ci-dessous est en O(\(n\)) (car il faut recopier la chaîne de caractères en totalité, de taille \(n\)).
Si diff est de taille \(k\), la complexité totale est donc O(\(nk\)).

def applique(texte1, diff):
    texte2 = texte1.copy()
    for d in diff:
        texte2[début(d):début(d) + len(avant(d))] = après(d)
    return texte2

applique(texte1, d)

['L',
 'e',
 ' ',
 'p',
 'e',
 't',
 'i',
 't',
 ' ',
 'c',
 'h',
 'i',
 'e',
 'n',
 ' ',
 'a',
 ' ',
 's',
 'o',
 'i',
 'f']

Question 6#

La fonction suivante est clairement en O(\(k\)).

def inverse(diff):
    diff2 = []
    for d in diff:
        diff2.append(tranche(début(d), après(d), avant(d)))
    return diff2

inverse(d)

[{'début': 3,
  'avant': ['p', 'e', 't', 'i', 't'],
  'après': ['g', 'r', 'a', 'n', 'd']},
 {'début': 11,
  'avant': ['i', 'e', 'n', ' ', 'a'],
  'après': ['â', 't', 'e', 'a', 'u']},
 {'début': 17, 'avant': ['s'], 'après': ['f']},
 {'début': 19, 'avant': ['i', 'f'], 'après': ['r', 't']}]

def versionne(texte):
    return {'courant' : texte, 'historique' : [] }
def courant(texte_versionné):
    return texte_versionné['courant']
def remplace_courant(texte_versionné, texte):
    texte_versionné['courant'] = texte
def historique(texte_versionné):
    return texte_versionné['historique']

Question 7#

modifie(texte_versionné, texte) utilise différentiel en O(\(n\)) et des opérations en O(\(1\)) donc est en O(\(n\)).
annule(texte_versionné) utilise inverse en O(\(k\)), applique en O(\(nk\)), modifie en O(\(n\)) et des opérations en O(\(1\)). Donc la complexité de annule(texte_versionné) est en O(\(nk\)).

def modifie(texte_versionné, texte):
    historique(texte_versionné).append(différentiel(courant(texte_versionné), texte))
    remplace_courant(texte_versionné, texte)

def annule(texte_versionné):
    if len(historique(texte_versionné)) == 0:
        return
    texte = applique(courant(texte_versionné), inverse(historique(texte_versionné).pop()))
    remplace_courant(texte_versionné, texte)
    return texte

texte_versionné = versionne(['a', 'v', 'i', 's'])
modifie(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', 'i', 's', 'a']),
différentiel(['v', 'i', 's', 'a'], ['v', 'i', 't', 'a']),
différentiel(['v', 'i', 't', 'a'], ['l', 'i', 's', 'a'])
]
print(annule(texte_versionné))
print(annule(texte_versionné))
print(annule(texte_versionné))
print(texte_versionné)

['v', 'i', 't', 'a']
['v', 'i', 's', 'a']
['a', 'v', 'i', 's']
{'courant': ['a', 'v', 'i', 's'], 'historique': []}

Partie II : Diﬀérentiels sur des positions variables#

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 tr['début_avant']
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))

Question 8#

La complexité est clairement O(\(n\)) avec \(n\) le nombre de tranches.

def poids(diff):
    s = 0
    for d in diff:
        s += len(avant(d)) + len(après(d))
    return s

Question 9#

\[\begin{split}M[i + 1][j + 1] = \left\{ \begin{array}{ll} M[i][j] & \text{si } texte1[i] = texte2[j] \\ 1 + \min(M[i][j + 1], M[i + 1][j]) & \text{sinon} \end{array} \right.\end{split}\]

Si \(texte1[i] = texte2[j]\), il suffit de faire correspondre les \(i\) premiers caractères de texte1 avec les \(j\) premiers caractères de texte2.
Sinon, il y a deux possibilités :

faire correspondre les \(i\) premiers caractères de texte1 avec les \(j + 1\) premiers caractères de texte2 et ajouter \(texte2[j]\) à la fin \(texte1\) ;
ou faire correspondre les \(i + 1\) premiers caractères de texte1 avec les \(j\) premiers caractères de texte2 et supprimer \(texte1[i]\).

Question 10#

On utilise le cas de base \(M[0][j] = j\) et \(M[i][0] = i\).

def levenshtein(texte1, texte2):
    n1, n2 = len(texte1), len(texte2)
    M = [[0]*(n2 + 1) for _ in range(n1 + 1)]
    for i in range(n1 + 1):
        M[i][0] = i
    for j in range(n2 + 1):
        M[0][j] = j
    for i in range(n1):
        for j in range(n2):
            if texte1[i] == texte2[j]:
                M[i + 1][j + 1] = M[i][j]
            else:
                M[i + 1][j + 1] = 1 + min(M[i][j + 1], M[i + 1][j])
    return M

levenshtein(['A','B','C','D','C','E','F'],  ['U','A','B','C','C','X','Y','Z'])

[[0, 1, 2, 3, 4, 5, 6, 7, 8],
 [1, 2, 1, 2, 3, 4, 5, 6, 7],
 [2, 3, 2, 1, 2, 3, 4, 5, 6],
 [3, 4, 3, 2, 1, 2, 3, 4, 5],
 [4, 5, 4, 3, 2, 3, 4, 5, 6],
 [5, 6, 5, 4, 3, 2, 3, 4, 5],
 [6, 7, 6, 5, 4, 3, 4, 5, 6],
 [7, 8, 7, 6, 5, 4, 5, 6, 7]]

Question 11#

On parcourt la matrice comme sur la figure 3, en commencant par la case en bas à droite. À chaque fois que l’on va en haut, une lettre est supprimée de \(texte1\) donc il faut la rajouter à avant. De même à chaque fois que l’on va à gauche, une lettre est insérée dans \(texte2\) donc il faut la rajouter à après. Quand deux lettres sont égales, on ajoute la tranche trouvée et on calcule la tranche suivante.

def différentiel(texte1, texte2, M):
    L, i, j = [], len(texte1), len(texte2)
    avant, après = [], []
    while i > 0 or j > 0:
        if i > 0 and j > 0 and texte1[i - 1] == texte2[j - 1]:
            if len(avant) > 0 or len(après) > 0:
                L.append(tranche(i, avant, j, après))
                avant, après = [], []
            i, j = i - 1, j - 1
        else:
            if i > 0 and (j == 0 or M[i][j - 1] > M[i - 1][j]):
                avant = [texte1[i - 1]] + avant
                i -= 1
            else:
                après = [texte2[j - 1]] + après
                j -= 1
    if len(avant) > 0 or len(après) > 0:
        L.append(tranche(i, avant, j, après))
    return L[::-1]

Question 12#

On parcourt diff1 et diff2 en passant à chaque itération la tranche qui se termine en premier. On parcourt donc les tranches par ordre croissant de leur indice de fin.

def conflit(diff1, diff2):
    i, j = 0, 0
    while i < len(diff1) and j < len(diff2):
        if fin_avant(diff1[i]) <= début_avant(diff2[j]):
            i += 1
        elif fin_avant(diff2[j]) <= début_avant(diff1[i]):
            j += 1
        else:
            return True
    return False

texte = ['l', 'e', ' ', 'c', 'h', 'a', 't', ' ', 'a', ' ', 's', 'o', 'i', 'f']
texte1 = ['l', 'e', ' ', 'c', 'h', 'a', 't', ' ', 'a', ' ', 't', 'r', 'è', 's',
' ', 's', 'o', 'i', 'f']
texte2 = ['l', 'e', ' ', 'c', 'h', 'i', 'e', 'n', ' ', 'a', ' ', 's', 'o', 'i', 'f']
diff1 = différentiel(texte, texte1, levenshtein(texte, texte1))
print(diff1)
diff2 = différentiel(texte, texte2, levenshtein(texte, texte2))
print(diff2)
assert diff2 == [tranche(5, ['a', 't'], 5, ['i', 'e', 'n'])]
assert not conflit(diff1, diff2)

[{'début_avant': 9, 'avant': [], 'début_après': 9, 'après': [' ', 't', 'r', 'è', 's']}]
[{'début_avant': 5, 'avant': ['a', 't'], 'début_après': 5, 'après': ['i', 'e', 'n']}]

Question 13#

def fusionne(diff1, diff2):
    diff = []
    i, j = 0, 0
    while i < len(diff1) and j < len(diff2):
        if fin_avant(diff1[i]) <= début_avant(diff2[j]):
            diff.append(diff1[i])
            i += 1
        else:
            diff.append(diff2[j])
            j += 1
    for k in range(i, len(diff1)):
        diff.append(diff1[k])
    for k in range(j, len(diff2)):
        diff.append(diff2[k])
    return diff

def applique(texte1, diff):
    texte2 = texte1
    d = 0
    for t in diff:
        texte2 = texte2[:début_avant(t) + d] + après(t) + texte2[fin_avant(t) + d:]
        d += len(après(t)) - len(avant(t))
    return texte2

print(applique(texte, fusionne(diff1, diff2)))

['l', 'e', ' ', 'c', 'h', 'i', 'e', 'n', ' ', 'a', ' ', 't', 'r', 'è', 's', ' ', 's', 'o', 'i', 'f']

Question 14#

def successeurs(texte1, texte2, sommet):
    x, y = sommet
    succ = [(x + 1, y, 1), (x, y + 1, 1)]
    if texte[sommet[0]] == texte2[sommet[1]]:
        succ.append((x + 1, y + 1, 0))
    return succ

Question 15#

Propriété de l’algorithme de Dijkstra : à chaque fois qu’un sommet v est extrait de la file, dist[v] contient la distance entre entrée et v dans le graphe.
dist_final contient la distance de entrée à chaque sommet du graphe (dist_final[v] contient la distance de entrée à v). L’ensemble des clés de dist_final est l’ensemble des sommets visités du graphe.

Question 16#

Soient \(n_1\) et \(n_2\) les tailles de texte1 et texte2.
Chaque sommet est extrait au plus une fois de la file, donc il y a \(n_1 n_2\) itérations du while.
Chacune de ces itérations est en O(\(\log(n_1 n_2)\)) car il y a au plus \(3n_1 n_2\) arcs donc au plus \(3n_1 n_2\) éléments dans la file et que les fonctions extraire_min et ajoute sont en complexité logarithmique.
Donc la complexité de l’algorithme de Dijkstra est O(\(n_1 n_2 \log(n_1 n_2)\)).

La complexité est donc moins intéressante que celle de l’algorithme de programmation dynamique (en O(\(n_1 n_2\))). Cependant, si le sommet sortie peut être visité avant la fin de l’algorithme de Dijkstra, ce qui peut diminuer sa complexité.

Question 17#

On peut utiliser \(h((i, j)) = |i - j|\) comme heuristique. \(h\) est admissible car s’il y a une différence de taille entre les deux textes alors il faut au moins \(|i - j|\) opérations pour les rendre identiques.

levenshtein(['A', 'B', 'C'], ['B', 'X'])

[[0, 1, 2], [1, 2, 3], [2, 1, 2], [3, 2, 3]]

Informatique commune en 2ème année de CPGE

DS 1 MP* Corrigé (X-ENS 2023)

Contents