X ENS Informatique Commune MP PC PSI 2023Sujet, corrigé et rapport du jury

CONCOURS D'ADMISSION 2023

Gestion de versions de grands textes

• len (1) renvoie la longueur de la liste 1 , c'est-à-dire le nombre d'éléments qu'elle contient. Complexité en O(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).
• 1 [i] désigne le i-ème élément de la liste 1 , où l'indice i est compris entre 0 et len (l)-1 Complexité en O(1).
• 1 [i:j] construit la sous-liste [1 [i], ..., l[j-1]]. Complexité en O(j − i). L'usage des variantes 1[i : ] à la place de 1[i : len(1)], et de 1[ : j] à la place de 1[0 : j] est aussi autorisé.
• l. append(e) modifie la liste l en lui ajoutant l'élément e en dernière position. Complexité en O(1)(∗).
• l.pop() renvoie le dernier élément de la liste l (supposée non vide) et supprime l'occurrence de cet élément en dernière position dans la liste. Complexité en O(1)(∗).

• {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 O(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 O(1)(∗).
• key in d teste si la clé key est présente dans d. Complexité en O(1)(∗).

Partie I : Différentiels par positions fixes

Exemples

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

>>> distance(['v', 'i', 's', 'a'], ['v', 'a', 'i', 's'])
3
>>> distance(['a', 'v', 'i', 's'], ['v', 'i', 's', 'a'])
4

>>> aucun_caractère_commun(['a', 'v', 'i', 's'], ['v', 'i', 's', 'a'])
False
>>> aucun_caractère_commun(['a', 'v', 'i', 's'], ['u', 'r', 'n', 'e'])
True

Figure 1 - Exemple de couple ( texte _1, texte _2 ) dont on veut calculer le différentiel (sur des positions fixes).

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

[
    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'])
]

• début (tr_1) < fin(tr_1) < … < début(tr_k) < fin(tr_k)
• pour tout j ∈ [1, k], pour tout i ∈ [0, len(avant(tr_j)) − 1], avant (tr_j)[i] ≠ après(tr_j)[i]

• si k > 0, alors 0 ≤ début (tr_1) et fin(tr_k) ≤ n
• pour tout j ∈ [1, k], texte _1[ début (tr_j) : fin(tr_j)] = avant(tr_j)
• pour tout j ∈ [1, k], texte _2[ début (tr_j) : fin(tr_j)] = après(tr_j)
• pour tout i ∈ [0, n − 1], si i ∉ ⋃_(1 ≤ j ≤ k)[ début (tr_j), fin(tr_j) − 1], alors texte _1[i] = texte _2[i]

• les tranches sont présentées par indices de début croissants, sans se chevaucher, ni se toucher ;
• chaque tranche tr couvre un intervalle de positions [début(tr), fin(tr) - 1] sur lequel texte _1 et texte _2 diffèrent à chaque position, et dont les sous-textes sur ces intervalles correspondent à avant(tr) pour texte _1 et après(tr) pour texte _2.

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']

>>> 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'])
]
>>> annule(texte_versionné)
['v', 'i', 't', 'a'])
>>> annule(texte_versionné)
['v', 'i', 's', 'a'])
>>> annule(texte_versionné)
['a', 'v', 'i', 's']

Partie II : Différentiels sur des positions variables

Figure 2 - Exemple de couple (texte _1, texte _2 ) dont on veut calculer le différentiel sur des positions variables.

• la clé 'début_avant' représente la position i d'un sous-texte avant qui a été supprimé de texte _1;
• 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.

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

• début_avant (tr_1) ≤ fin_avant (tr_1) < … < début_avant (tr_k) ≤ fin_avant (tr_k)
• début_après (tr_1) ≤ fin_après (tr_1) < … < début_après (tr_k) ≤ fin_après (tr_k)
• pour tout j ∈ [1, k], aucun_caractère_commun(avant (tr_j), après (tr_j)) = True
• pour tout j ∈ [1, k], len(avant(tr_j)) > 0 ou len(après (tr_j)) > 0

• si k > 0, alors 0 ≤ début_avant (tr_1) et fin_avant (tr_k) ≤ len(texte_1)
• si k > 0, alors 0 ≤ début_après (tr_1) et fin_après (tr_k) ≤ len(texte_2)
• pour tout j ∈ [1, k], texte _1 [début_avant (tr_j) : fin_avant (tr_j)] = avant(tr_j)
• pour tout j ∈ [1, k], texte _2 [début_après (tr_j) : fin_après (tr_j)] = après (tr_j)
• pour tout j ∈ [1, k − 1], les sous-textes texte 1 [fin_avant ( tr _j) : début_avant ( tr _(j + 1))] et texte _2[ fin_après ( tr _j) : début_après ( tr _(j + 1))] sont égaux
• si k = 0 alors les textes texte _1 et texte _2 sont égaux
• si k > 0 alors texte 1[0 : début_avant (tr_1)] = texte_2[0 : début_après (tr_1)] et texte_1[finavanttr_k) : len(texte_1)] = texte_2[finaprès(tr_k) : len(texte_2)]

[
    tranche( 2, [], 2, [' ', 'b', 'o', 'n']),
    tranche( 5, ['â', 't'], 9, ['i']),
    tranche( 8, [], 11, ['n', ']),
    tranche( 9, ['u'], 14, []),
    tranche(11, ['f'], 15, ['s']),
    tranche(13, ['r', 't'], 17, ['i', 'f'])
]

>>> poids([tranche(0, ['b'], 0, ['t', 'r', 'o', 't', 't']),
    tranche(2, ['c', 'y', 'c', 'l'], 6, ['n'])])
1 1

>>> 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))
>>> assert diff1 == [tranche(9, [], 9, [' ', 't', 'r', 'è', 's'])]
>>> diff2 = différentiel(texte, texte2, levenshtein(texte, texte2))
>>> assert diff2 == [tranche(5, ['a', 't'], 5, ['i', 'e', 'n'])]

>>> assert not conflit(diff1, diff2)
>>> print(applique(applique(texte, diff1), fusionne(diff1, diff2)))
['l', 'e', ', 'c', 'h', 'i', 'e', 'n', ', 'a', ', 't', 'r', 'è', 's', ',
    's', 'o', 'i', 'f']

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

>>> texte1 = ['b', 'i', 'e', 'n']
>>> texte2 = ['b', 'o', 'n', 'n', 'e']
>>> successeurs(texte1, texte2, (2,4))
[((3, 4), ...), ((2, 5), ...), ((3, 5), ...)]

• La fonction vide() construit une file vide (de cardinal 0) en O(1).
• La fonction est_vide(file) teste si la file file est vide en O(1).
• 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 (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é 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))).

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
                if not voisin in dist or d < dist[voisin]:
                    dist[voisin] = d
                    ajoute(file, voisin, d)
    assert False

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 dist or d < dist[voisin]:
                dist[voisin] = d
                ajoute(file, voisin, d + h(texte1, texte2, voisin))
    assert False