Aller au contenu

🏡 Programmation dynamique

Ce site propose un cours d'introduction à la programmation dynamique.

Il est destiné en premier lieu aux élèves de la spécialité Numérique et Sciences Informatiques de Terminale.

Fonctionnement général

Ce cours est interactif et alterne des phases de présentations de notions et d'autres, plus nombreuses, demandant de résoudre des exercices de programmation.

Le langage utilisé est Python 3.

Chaque exercice propose de tester sa solution face à des tests publics et d'autres privés. Le plus souvent, au bout de 10 essais infructueux, la solution est proposée.

Ce cours est divisé en plusieurs parties. Il n'est pas utile de toutes les traiter.

Une grenouille avec un sac à dos qui peint une clôture ??

Remarques générales

Comme indiqué plus haut, ce cours s'adresse en priorité à des élèves de la spécialité NSI de Terminale. Il n'a pas la prétention d'être un cours exhaustif sur le thème de la programmation dynamique.

Dans le même ordre d'idée, même si l'on cherche à y être le plus rigoureux possible, on essaie de le faire en restant d'un accès facile, voire même, on l'espère, agréable.

Dernier point : certains choix d'implantation des algorithmes ont été faits. Bien souvent, ils l'ont été à dessein, dans une optique didactique. Toutefois cette « optique » est aussi un point de vue : elle est propre à chacun...

On retiendra en particulier :

  • le souhait d'éviter au maximum la structure a = [0] * 10 afin de ne pas être amené à écrire une autre fois ab = [[0] * 10] * 3 ;

  • le choix d'utiliser préférentiellement des tableaux comme structure de mémoïsation et pas des dictionnaires ou functools.cache ;

  • la présentation d'une approche récursive des solutions (même si les solutions itératives sont toujours proposées avec le corrigé) ;

  • le souhait, bien souvent, d'être un peu plus explicite que nécessaire. On écrira donc bien souvent :

    if a >= 0:
    signe = "positif"
else:
    signe = "négatif"

    plutôt que :

    signe = "positif" if a >= 0 else "négatif"