On distribue [des images en noir et blanc](./support/fig/grids.pdf) et on demande aux élèves de trouver les plus grand carré blanc à l'intérieur en précisant la taille et le coin inférieur droit. Ce premier travail est à faire seul.
Ils doivent ensuite,en groupe, déterminer au crayon une stratégie/algorithme pour trouver les solutions à ce problème et préparer une façon d'exposer leur méthode à leur camarades. Ils sont invité à faire des schémas, écrire l'algorithme ou encore présenter des relations.
Quand les élèves ont trouvé, un temps de plénière est organisé pour que les élèves présentent leur méthode. Pendant qu'un groupe présente, les autres prennent des notes. À la fin de la présentation, des questions/réponses sont organisés pour que tous les élèves aient saisi le principe de chaque méthode. Elles pourront mener à l'amélioration des algorithme présenté. Des méthodes peuvent s'avérer invalide, ce sera l'occasion d'en discuter.
Quand toutes les méthodes ont été présentées, il sera intéressant les caractérisée (récursif, balayage, mémoïsation, glouton...).
Il sera important que l'enseignant anime et regroupe les groupes qui ont la même méthode.
Ce travail de présentation pourra mener à une note sur le modèle du grand oral.
### Coder
Chaque élève choisi la méthode qu'il a le mieux comprise et la code.
Spécifications: le programme devra comporter une fonction `trouve_plus_taille_grand_carre`. Cette fonction prend en argument une grille avec des 1 et des 0 (1 correspond à un obstacle/noir, et 0 par une case libre/blanc) sous la forme d'une liste de lignes. La fonction devra renvoyer la taille du plus grand carré possible (la taille d'un seul de ses côtés).
Les meilleurs élèves seront poussé à respecter ces spécifications mais pourront ajouter une fonction `trouve_plus_grands_carres` qui donnera la taille des plus grands carré et la liste des coins inférieurs droits de chaque carrés.
Les élèves mettent en commun leur programmes.
### Comparer
Les élèves choisissent 3 programmes qui implémentent si possible des méthodes différentes.
Si la méthode qui utilise la programmation dynamique n'a pas été trouvé ou n'a as réussi à être codée, l'enseignant pourra mettre à disposition une implémentation à tester.
La comparaison se fera sur le temps mis à trouver la taille du plus grand carré en fonction de la surface de la grille. On leur demandera alors de reconnaître la complexité temporelle des programmes étudiés.
En fonction de là où en est la progression, on pourra demander aux élèves de tracer les graphiques de ces comparaisons avec matplotlib.
### Coder avec la programmation dynamique
Le cours sur l'algorithme utilisant la programmation dynamique a été distribué aux élèves à la suite de temps réservé à la programmation de leur méthode. Ils devront l'implémenter à leur tour.
Les élèves qui auraient déjà réussi à l'implémenter, ont un problème supplémentaire de programmation dynamique `trouver le plus grand rectangle d'un histogramme`. La méthode est expliquée, ils doivent l'implémenter.
