2024-11-31 : rappel feuille de route 2024

Le plan des séances est changé après que celles-ci ont eu lieu.

Séance 1

Prises aux dames

Séance 2

Tests unitaires et classes toujours avec les dames

Prises aux dames

Séance 3

classes pour représenter un graphe

Fin des classes puis les itérateurs et numpy broadcast.

Séance 4

Nous garderons les dames et l’algortithme minimax pour une autre fois peut être. Cette séance à propos de la programmation dynamique. Le premier exercice consiste à déterminer le nombre minimal de pièces de monnaie pour écrire un montant et de retrouver la séquence minimale de pièces. On considère les pièces [1, 2, 4, 5].

<<<

def ecriture_minimale(n):
    pieces = [1, 2, 4, 5]
    min_pieces = [None for i in range(n + 1)]
    predecessor = [None for i in range(n + 1)]
    min_pieces[0] = 1
    for p in pieces:
        min_pieces[p] = 1
        predecessor[p] = p
    for i in range(n + 1):
        if min_pieces[i] is None:
            # écriture impossible
            continue
        for p in pieces:
            if i + p > n:
                break
            m = min_pieces[i] + 1
            if min_pieces[i + p] is None or m < min_pieces[i + p]:
                min_pieces[i + p] = m
                predecessor[i + p] = p
    composition = []
    while n > 0:
        composition.append(predecessor[n])
        n -= predecessor[n]
    return min_pieces[n], composition


print(ecriture_minimale(99))

>>>

    (1, [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4])

On bascule ensuite vers la Distance d’édition.

A propos de la distance d’édition, voir aussi Distance d’édition ou encore Distance entre deux mots de même longueur et tests unitaires.

Séance 5

Séance 6

Evocation de la Recherche à base de préfixes en terme algorithmique.

Autres variations autour du problème du voyageur de commerce, ou TSP pour Travelling Salesman Problem ou encore circuit hamiltonien: Circuit hamiltonien et Kohonen, Circuit hamiltonien et Kruskal.

Séance 7

Convertir une expression mathématique comme \(((34 + 6) - 2) / (7 - 4)\) en notation polonaise inverse. Voir aussi Algorithme Shunting-yard.

Séance 8

TD noté 1h30 en seconde partie. Classes et un algorithme. Enoncés des années précédentes : Séances minutées.