Chaînes de caractères

a) 17
b) 'o'
c) 'MPSI'
d) 'INFORMATIQUE MPSI'
e) 3          ('informatique mpsi' contient trois 'i')
f) ['Informatique', 'MPSI']
g) 'Informat!que MPSI'      (le I majuscule n'est pas touche)
h) 'Informatique-MPSI'
i) 13
j) ValueError : substring not found      (find aurait renvoye -1)
k) ''
l) ''

Retenir la difference entre find (renvoie \(-1\)) et index (leve une exception) : on choisit selon que l'absence est un cas normal ou une anomalie.

def renverse(s):
    """Chaine renversee. Theta(n) grace a join (une concatenation en boucle serait Theta(n^2))."""
    lettres = []
    for i in range(len(s) - 1, -1, -1):
        lettres.append(s[i])
    return "".join(lettres)

def compte(s, c):
    """Nombre d'occurrences de c dans s. Theta(n)."""
    n = 0
    for x in s:
        if x == c:
            n += 1
    return n

def majuscules(s):
    """Minuscules non accentuees converties en majuscules. Theta(n)."""
    res = []
    for c in s:
        if "a" <= c <= "z":
            res.append(chr(ord(c) - 32))
        else:
            res.append(c)
    return "".join(res)

def sans_espaces(s):
    """Supprime tous les caracteres blancs. Theta(n)."""
    return "".join(c for c in s if not c.isspace())

assert renverse("MPSI") == "ISPM"
assert compte("banane", "a") == 2
assert majuscules("MPSI 2024 !") == "MPSI 2024 !"
assert majuscules("mpsi") == "MPSI"
assert sans_espaces(" a b\tc\n") == "abc"

Toutes ces fonctions sont en \(\Theta(n)\) a condition d'accumuler dans une liste puis de joindre. Avec s += c, elles seraient toutes en \(\Theta(n^2)\).

def est_anagramme_tri(m1, m2):
    """Theta(n log n) : on compare les lettres triees."""
    return sorted(m1.lower()) == sorted(m2.lower())

def est_anagramme(m1, m2):
    """Theta(n) : on compare les tables de frequences."""
    if len(m1) != len(m2):
        return False
    f = {}
    for c in m1.lower():
        f[c] = f.get(c, 0) + 1
    for c in m2.lower():
        if c not in f:
            return False
        f[c] -= 1
        if f[c] == 0:
            del f[c]
    return len(f) == 0

def groupe_anagrammes(mots):
    """Regroupe les mots par classe d'anagrammes."""
    classes = {}
    for m in mots:
        cle = "".join(sorted(m.lower()))      # signature canonique
        classes.setdefault(cle, []).append(m)
    return list(classes.values())

assert est_anagramme("chien", "niche")
assert not est_anagramme("chien", "chiens")
print(groupe_anagrammes(["chien", "niche", "chine", "porte", "poter"]))
# [['chien', 'niche', 'chine'], ['porte', 'poter']]

def cesar(s, k):
    """Chiffrement par decalage de k, casse et ponctuation preservees."""
    res = []
    for c in s:
        if "a" <= c <= "z":
            res.append(chr((ord(c) - 97 + k) % 26 + 97))
        elif "A" <= c <= "Z":
            res.append(chr((ord(c) - 65 + k) % 26 + 65))
        else:
            res.append(c)
    return "".join(res)

def casse_cesar(chiffre):
    """Cle probable, en supposant que la lettre la plus frequente code un 'e'."""
    f = {}
    for c in chiffre.lower():
        if "a" <= c <= "z":
            f[c] = f.get(c, 0) + 1
    if not f:
        return 0
    plus_freq = max(f, key=f.get)
    return (ord(plus_freq) - ord("e")) % 26

def vigenere(s, cle, sens=1):
    """Chiffre (sens=1) ou dechiffre (sens=-1) s par la cle. cle : lettres minuscules."""
    cle = [ord(c) - 97 for c in cle.lower() if "a" <= c <= "z"]
    if not cle:
        return s
    res, j = [], 0
    for c in s:
        if "a" <= c.lower() <= "z":
            base = 97 if c.islower() else 65
            d = sens * cle[j % len(cle)]
            res.append(chr((ord(c) - base + d) % 26 + base))
            j += 1                    # la cle n'avance que sur les lettres
        else:
            res.append(c)
    return "".join(res)

texte = "Bonjour, MPSI !"
assert cesar(cesar(texte, 7), -7) == texte
assert vigenere(vigenere(texte, "cle"), "cle", -1) == texte

message = cesar("le message secret est bien cache dans ce texte assez long", 11)
print(casse_cesar(message))       # 11

5. Dans Cesar, une meme lettre claire donne toujours la meme lettre chiffree : la distribution des frequences est simplement permutee, et le pic du e reste visible. Dans Vigenere, la lettre e est chiffree differemment selon sa position (modulo la longueur \(L\) de la cle) : les frequences sont lissees et le pic disparait.

La cryptanalyse de Vigenere se fait en deux temps : d'abord retrouver \(L\) (test de Kasiski, ou indice de coincidence), puis appliquer une analyse frequentielle sur chacune des \(L\) sous-chaines de positions congrues modulo \(L\), qui sont chacune chiffrees par un simple Cesar. Le chiffrement n'est inconditionnellement sur que si la cle est aleatoire, aussi longue que le message et utilisee une seule fois : c'est le masque jetable de Vernam.

PONCTUATION = ".,;:!?'\"()[]{}-—…«»\n\t"

def mots(texte):
    """Liste des mots en minuscules, ponctuation retiree."""
    propre = "".join(" " if c in PONCTUATION else c for c in texte.lower())
    return propre.split()

def frequences_mots(texte):
    f = {}
    for m in mots(texte):
        f[m] = f.get(m, 0) + 1
    return f

def top(texte, k=5):
    """k mots les plus frequents, ordre decroissant puis alphabetique."""
    f = frequences_mots(texte)
    return sorted(f.items(), key=lambda c: (-c[1], c[0]))[:k]

def longueur_moyenne(texte):
    m = mots(texte)
    return sum(len(x) for x in m) / len(m) if m else 0.0

def mots_plus_longs(texte, k=3):
    """k mots distincts les plus longs."""
    distincts = set(mots(texte))
    return sorted(distincts, key=lambda m: (-len(m), m))[:k]

t = """Le petit chat dort. Le chat mange, puis le petit chien dort aussi !
Le chien et le chat dorment beaucoup."""
print(top(t))                    # [('le', 5), ('chat', 3), ...]
print(f"{longueur_moyenne(t):.2f}")
print(mots_plus_longs(t))        # ['beaucoup', 'dorment', 'aussi']

La construction de propre remplace la ponctuation par des espaces plutot que de la supprimer : ainsi "chat,chien" donne bien deux mots.

def parentheses_correctes(s):
    """Version a un seul type de delimiteur : un compteur suffit."""
    c = 0
    for x in s:
        if x == "(":
            c += 1
        elif x == ")":
            c -= 1
            if c < 0:            # une fermeture sans ouverture
                return False
    return c == 0

def delimiteurs_corrects(s):
    """Version generale, avec pile."""
    ouvrants = {")": "(", "]": "[", "}": "{"}
    pile = []
    for x in s:
        if x in "([{":
            pile.append(x)
        elif x in ouvrants:
            if not pile or pile.pop() != ouvrants[x]:
                return False
    return not pile

def premiere_erreur(s):
    """Position de la premiere erreur, ou -1 si l'expression est correcte."""
    ouvrants = {")": "(", "]": "[", "}": "{"}
    pile = []
    for i, x in enumerate(s):
        if x in "([{":
            pile.append((x, i))
        elif x in ouvrants:
            if not pile or pile[-1][0] != ouvrants[x]:
                return i                     # fermeture orpheline ou mal appariee
            pile.pop()
    return pile[0][1] if pile else -1        # ouverture jamais fermee

assert parentheses_correctes("(()())") and not parentheses_correctes("())(")
assert delimiteurs_corrects("{[()]}")
assert not delimiteurs_corrects("([)]")      # correct pour un compteur, faux ici
assert premiere_erreur("([)]") == 2
assert premiere_erreur("(()") == 0
assert premiere_erreur("(())") == -1

2. Un compteur ne retient que combien de delimiteurs sont ouverts, pas lesquels ni dans quel ordre. La chaine "([)]" a autant d'ouvrants que de fermants de chaque type, mais l'imbrication est incorrecte. Il faut memoriser l'ordre : c'est exactement le role d'une pile (dernier ouvert, premier ferme).

3. Invariant. Apres avoir lu le prefixe \(s[0..i-1]\), la pile contient, de bas en haut, la suite des delimiteurs ouverts et non encore fermes, dans l'ordre de leur ouverture.

• Initialisation : prefixe vide, pile vide. Vrai.
• Conservation : si \(s_i\) est un ouvrant, il devient le dernier ouvert non ferme, et on l'empile au sommet : correct. Si \(s_i\) est un fermant, le seul delimiteur qu'il peut legalement fermer est le dernier ouvert, c'est-a-dire le sommet ; on verifie la correspondance et on depile : l'invariant est retabli. Si la pile est vide ou le sommet ne correspond pas, l'expression est irremediablement incorrecte et l'on s'arrete.
• Conclusion : a la fin, l'invariant dit que la pile contient les delimiteurs ouverts non fermes. L'expression est correcte si et seulement si cette pile est vide.

Complexite : chaque caractere est traite une fois, avec un nombre constant d'operations de pile : \(\Theta(n)\) temps, \(\Theta(n)\) espace dans le pire cas ("((((...").

def recherche_naive(texte, motif):
    """Positions d'apparition, avec comptage des comparaisons."""
    n, m = len(texte), len(motif)
    positions, comparaisons = [], 0
    for i in range(n - m + 1):
        j = 0
        while j < m and texte[i+j] == motif[j]:
            comparaisons += 1
            j += 1
        if j < m:
            comparaisons += 1
        if j == m:
            positions.append(i)
    return positions, comparaisons

print(recherche_naive("a"*20 + "b", "a"*5 + "b")[1])   # ~ 100 comparaisons

2. Le pire cas est texte = "aaaa...a" (longueur \(n\)) et motif = "aaa...ab" (longueur \(m\)) : chaque position teste \(m-1\) caracteres identiques avant d'echouer sur le dernier, soit \(\Theta((n-m)m)\) comparaisons.

def rabin_karp(texte, motif, base=257, module=(1 << 61) - 1):
    """Recherche par hachage roulant. Theta(n + m) en moyenne."""
    n, m = len(texte), len(motif)
    if m == 0 or m > n:
        return []
    # base^(m-1) mod module, pour retirer le caractere sortant
    puissance = pow(base, m - 1, module)

    h_motif = 0
    h_fenetre = 0
    for j in range(m):
        h_motif = (h_motif * base + ord(motif[j])) % module
        h_fenetre = (h_fenetre * base + ord(texte[j])) % module

    positions = []
    for i in range(n - m + 1):
        if h_fenetre == h_motif and texte[i:i+m] == motif:   # verification
            positions.append(i)
        if i < n - m:
            # on retire texte[i], on decale, on ajoute texte[i+m] : Theta(1)
            h_fenetre = ((h_fenetre - ord(texte[i]) * puissance) * base
                         + ord(texte[i+m])) % module
    return positions

import random, string
for _ in range(200):
    t = "".join(random.choice("ab") for _ in range(random.randint(0, 40)))
    m = "".join(random.choice("ab") for _ in range(random.randint(1, 5)))
    assert rabin_karp(t, m) == recherche_naive(t, m)[0]
print("Rabin-Karp valide")

4. Le calcul des empreintes initiales coute \(\Theta(m)\), et chaque decalage \(\Theta(1)\) : la boucle est en \(\Theta(n)\). La verification explicite texte[i:i+m] == motif ne se declenche qu'en cas d'egalite des empreintes, donc pour les vraies occurrences et pour les rares faux positifs. Avec un module premier de l'ordre de \(2^{61}\), la probabilite de collision par position est de l'ordre de \(m/2^{61}\), negligeable : le cout moyen est \(\Theta(n+m)\).

Dans le pire cas (adversaire choisissant le texte pour provoquer des collisions, ou module trop petit), toutes les positions declenchent une verification en \(\Theta(m)\) : on retombe a \(\Theta(nm)\). C'est pourquoi Rabin-Karp est un algorithme probabiliste, alors que Knuth-Morris-Pratt garantit \(\Theta(n+m)\) de facon deterministe.

def est_sous_suite(u, s):
    """u est-elle une sous-suite de s ? Theta(|s|), algorithme glouton."""
    i = 0
    for c in s:
        if i < len(u) and c == u[i]:
            i += 1
    return i == len(u)

assert est_sous_suite("ace", "abcde")
assert not est_sous_suite("aec", "abcde")

Correction. Invariant : « i est le plus grand entier tel que \(u[0..i-1]\) soit une sous-suite du prefixe de \(s\) deja lu ». L'initialisation est immediate. Pour la conservation, il faut voir que consommer u[i] des sa premiere occurrence possible ne fait jamais perdre de solution : si un plongement de \(u\) dans \(s\) utilise une occurrence ulterieure de u[i], on peut la remplacer par la premiere sans gener les caracteres suivants, qui sont tous plus a droite. C'est un argument d'echange, typique des algorithmes gloutons.

2. En comparant les derniers caracteres :

\[ L(i,j) = \begin{cases} 0 & \text{si } i = 0 \text{ ou } j = 0,\\ L(i-1,j-1) + 1 & \text{si } u_{i-1} = v_{j-1},\\ \max\bigl(L(i-1,j),\, L(i,j-1)\bigr) & \text{sinon.} \end{cases} \]

Justification : si les derniers caracteres coincident, on peut toujours supposer qu'ils sont apparies dans une PLSC optimale (argument d'echange). Sinon, l'un des deux au moins n'est pas utilise, d'ou le maximum sur les deux sous-problemes.

def plsc_longueur(u, v):
    """Longueur de la plus longue sous-suite commune. Theta(nm) temps et memoire."""
    n, m = len(u), len(v)
    L = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if u[i-1] == v[j-1]:
                L[i][j] = L[i-1][j-1] + 1
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])
    return L[n][m], L

def plsc(u, v):
    """Une plus longue sous-suite commune (reconstruction par remontee)."""
    _, L = plsc_longueur(u, v)
    i, j, res = len(u), len(v), []
    while i > 0 and j > 0:
        if u[i-1] == v[j-1]:
            res.append(u[i-1]); i -= 1; j -= 1
        elif L[i-1][j] >= L[i][j-1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(res))

assert plsc_longueur("ABCBDAB", "BDCABA")[0] == 4
print(plsc("ABCBDAB", "BDCABA"))       # 'BCBA' (ou 'BDAB', plusieurs solutions)
assert est_sous_suite(plsc("ABCBDAB", "BDCABA"), "ABCBDAB")

3. Deux boucles imbriquees remplissant une table \((n+1)\times(m+1)\) en \(\Theta(1)\) par case : \(\Theta(nm)\) en temps et en memoire. Si seule la longueur est demandee, deux lignes suffisent, d'ou \(\Theta(\min(n,m))\) memoire.

4. La remontee part de la case \((n,m)\) et suit le chemin des decisions : elle coute \(\Theta(n+m)\), chaque etape diminuant \(i+j\) d'au moins 1.