Aller au contenu

version pdf

Correction du DM n°3⚓︎

Question 1⚓︎

🐍 Script Python
def corrige(cop, corr):
    assert len(cop) == len(corr)
    return [cop[i] == corr[i] for i in range(len(cor))]

Question 2⚓︎

🐍 Script Python
def note(cop, corr):
    assert len(cop) == len(corr)
    n = 0
    for i in range(len(cop)):
        if cop[i] == corr[i]:
            n = n + 1
    return n

Question 3⚓︎

🐍 Script Python
def notes_paquet(p, corr):
    notes = dict()
    for c in p:
        notes[c] = note(p[c])
    return notes

Question 4⚓︎

On ne peut pas utiliser une liste de noms comme clés du dictionnaire car le type list est mutable et les clefs d'un dictionnaire doivent être immuables : leur valeur de hachage ne doit jamais changer car c'est elle qui permet d'accéder aux index du tableau stockant les valeurs dans une table de hachage.

Question 5⚓︎

On peut ajouter un numéro au prénom, puis stocker comme clef le haché du couple (nom, prénom + numéro) plutôt que de le stocker en clair.

Questions 6 et 7⚓︎

🐍 Script Python
def enigme(notes):
    a = None
    b = None
    c = None
    d = {}
    for nom in notes:
        tmp  = c
        if a == None or notes[nom] > a[1]:
            c = b
            b = a 
            a = (nom, notes[nom])
        elif b == None or notes[nom] > b[1]:
            c = b
            b = (nom, notes[nom])
        elif c == None or notes[nom] > c[1]:
            b = (nom, notes[nom])
        else:
            d[nom] = notes[nom]
        if tmp != c and tmp != None:
            d[tmp[0]] = tmp[1]
    return (a, b, c, d)

enigme({('Tom','Matt'): 6, ('Lambert', 'Ginne'): 4, ('Carl', 'Roth'): 2, ('Kurt', 'Jett'): 4, ('Ayet', 'Finzerb'): 3}) renvoie le tuple : ((('Tom','Matt'), 6), (('Lambert', 'Ginne'), 4), (('Kurt', 'Jett'), 4), {('Carl', 'Roth'): 2, ('Ayet', 'Finzerb'): 3}). Ce tuple est constitué de trois tuples ((nom, prénom), note) des élèves aves les meilleures notes par ordre décroissant et d'un dictionnaire associant aux autres élève leur note.

Question 8⚓︎

S'il y a strictement moins de 3 entrées dans le dictionnaire, la fonction enigme renvoie un ou deux tuples avec le nom, le prénom et la note des meilleurs élèves, puis None pour compléter jusqu'à trois et un dictionnaire vide.

Question 9⚓︎

🐍 Script Python
def classement(notes):
    ordre = []
    n = len(notes)
    reste = notes
    c = 0
    while c < n:
        res = enigme(reste)
        for k in range(3):
            if res[k] != None:
                ordre.append(res[k])
                c += 1
        reste = res[3]
    return ordre

Question 10⚓︎

🐍 Script Python
def renote_express(copcorr):
    """Recherche séquentielle de la première réponse fausse"""
    c = 0
    while copcorr[c]:
        c = c + 1
    return c

def renote_express2(copcorr):
    gauche = 0
    droite = len(copcorr)
    while droite - gauche > 1:
        milieu = (gauche + droite) // 2
        if copcorr[milieu]:
            gauche = milieu  + 1
        else:
            droite = milieu
    if copcorr[gauche]:
        return droite
    else:
        return gauche

Question 11⚓︎

Le coût en temps d'un programme est le produit du coût en opérations atomiques (affectations, comparaisons, opérations arithmétiques) par une constante dépendant de la machine. On peut exprimer le coût en opérations atomiques en fonction de la taille \(n\) de la liste copcor.

Les deux fonctions renote_express et renote_express2 permettent de déterminer le nombre de valeurs True dans la liste copcor.

renote_express est une recherche séquentielle donc son coût en opérations atomiques dans le pire des cas (aucune réponse vraie) est majoré par \(n \times k\) où \(k\) est une constante. On parle dans ce cas de complexité linéaire, en \(O(n)\).

renote_express2 est une recherche dichotomique donc son coût en opérations atomiques dans le pire des cas (aucune réponse vraie) est majoré par \(\log_{2}(n) \times k\) où \(k\) est une constante. On parle dans ce cas de complexité logarithmique, en \(O(\log_{2}(n))\).

Question 12⚓︎

🐍 Script Python
def renote_express3(cop, corr):
    gauche = 0
    droite = len(copcorr)
    while droite - gauche > 1:
        milieu = (gauche + droite) // 2
        if cop[milieu] == corr[milieu]:
            gauche = milieu  + 1
        else:
            droite = milieu
    if copcorr[gauche] == corr[gauche]:
        return droite
    else:
        return gauche