Chapitre 10. Algorithmes avancés

Programmation dynamique

Activité introductive. La suite de Fibonacci

• Diaporama
• Cahier Jupyter à compléter (à venir !)
• Cahier Jupyter (correction)

À retenir

• Capsule vidéo
  • 00:00 Point de cours.
  • Exemple d’application avec l’alignement de séquence
    • 04:30 Exécution à la main sur des exemples : intéressant pour montrer que le problème se ramène à la recherche du plus court chemin dans un graphe.
    • 13:04 Implémentation de l’algorithme en Python : algorithme complexe faisant jouer des matrice et le module NumPy. Me semble inutilement compliqué à ce stade de la progression, réservé aux élèves voulant approfondir en autonomie en fin de chapitre.

Exercice d’application Le problème du rendu de monnaie

• Capsule vidéo
  • 00:00 Introduction
  • 03:20 Stratégie 1. Algorithme glouton (rappel de première)
  • 08:04 Stratégie 2. Algorithme de force brute (récursif)
  • 13:22 Stratégie 3. Programmation dynamique
• Cahier Jupyter à compléter (à venir)
• Cahier Jupyter (correction)

Algorithme de Boyer-Moore

• Capsule vidéo

  • 00:00 Recherche textuelle, grands principes
  • 01:50 Recherche naïve
  • 05:44 Optimisation de la recherche
  • 07:43 Boyer-Moore sur un exemple
  • 11:05 L’intérêt du prétraitement
  • 12:24 Bilan : l’algorithme de Boyer-Moore

• Cahier Jupyter (a compléter)