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¶
Séance 2¶
Tests unitaires et classes toujours avec les 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¶
Pivot de Gauss, cet algorithme est la première étage pour inverser une matrice
TD noté 1h30 en seconde partie. Classes et un algorithme. Enoncés des années précédentes : Séances minutées.