> *🎯 Objectif : Réduire un problème complexe à un problème **NP-complet connu** afin de proposer une stratégie de résolution pour un problème algorithmique difficile.* # 👥 Encadrement - **Responsable :** [[Julien DUQUENNOY]] - **Domaine :** [[Programmation]] - **XP attribués :** 🧪 **20** - **Modalité d'évaluation** : Projet - **Pré-requis :** [[Python 3]], [[Graphes]] # 🔗 Connexions ```mermaid graph TD A["Python 3"] --> B["Python 4"] C[Graphes] --> B ``` ## 🧠 Intention pédagogique Ce module marque une **rupture conceptuelle** avec les précédents niveaux de Python. Ici, l’enjeu n’est plus uniquement : - d’écrire un algorithme correct, - ni d’optimiser un code existant, mais de **raisonner sur la difficulté intrinsèque d’un problème**. L’étudiant apprend à : - reconnaître un problème *difficile*, - comprendre pourquoi une solution efficace est hors de portée, - **réduire** ce problème à un problème **NP-complet de référence**, - exploiter cette réduction pour proposer une résolution exploitable (exacte, approchée ou heuristique). ## 📚 Contenu pédagogique — Cours ### 00 — Introduction à la complexité algorithmique - 🎥 **Vidéo introductive :** *Nos algorithmes pourraient-ils être BEAUCOUP plus rapides ? (P = NP ?)* **Créateur :** : [ScienceEtonnante](https://www.youtube.com/@ScienceEtonnante) **URL :** https://www.youtube.com/watch?v=AgtOCNCejQ8 ### 01 — Complexité algorithmique - 📎 **Ressource :** https://github.com/unilasalle-apex/Python/blob/main/Complexite_algorithmique.ipynb - **Notions clés :** - complexité en temps (notation en O), - comparaison de croissances (linéaire, quadratique, exponentielle), - distinction entre problèmes _traitables_ et _non traitables_ en pratique, - introduction des classes **P** et **NP**. ### 02 — Le problème du sac à dos - 📎 **Ressource :** https://github.com/unilasalle-apex/Python/blob/main/Le_probleme_du_sac_a_dos.ipynb - **Notions clés :** - modélisation d’un problème d’optimisation combinatoire, - contraintes et fonction objectif, - exploration exhaustive vs stratégies intelligentes - compréhension de la NP-complétude à travers un cas concret. ### 03 — Satisfaisabilité (SAT) - 📎 **Ressource :** https://github.com/unilasalle-apex/Python/blob/main/Satisfaisabilit%C3%A9_(SAT).ipynb - **Notions clés :** - variables booléennes et clauses, - formulation logique d’un problème, - lien entre contraintes et satisfaisabilité, - rôle central de SAT dans les preuves de NP-complétude. ## 🧩 Activités pédagogiques — Ateliers ### 🧪 Atelier 1 — Poudre de perlimpinpin - 📎 Sujet : https://github.com/unilasalle-apex/Python/blob/main/Poudre_de_perlimpinpin.ipynb - 📎 Corrigé : https://github.com/unilasalle-apex/Python/blob/main/Poudre_de_perlimpinpin_corrige.ipynb - **Compétence travaillée :** - analyser un problème applicatif apparemment simple, - identifier une structure de choix combinatoire, - montrer que le problème est assimilable à un problème NP-complet, - justifier pourquoi une solution naïve ne passe pas à l’échelle. ### 🧪 Atelier 2 — Professeur populaire - 📎 Sujet : https://github.com/unilasalle-apex/Python/blob/main/Professeur_populaire.ipynb - 📎 Corrigé : https://github.com/unilasalle-apex/Python/blob/main/Professeur_populaire_corrige.ipynb - **Compétence travaillée :** - modéliser un problème de sélection sous contraintes, - expliciter les liens avec un problème classique de type sac à dos, - proposer une stratégie de résolution raisonnée, - discuter les limites de la solution proposée. ### 🧪 Atelier 3 — Professeur débordé - 📎 Sujet : https://github.com/unilasalle-apex/Python/blob/main/Professeur_deborde.ipynb - 📎 Corrigé : https://github.com/unilasalle-apex/Python/blob/main/Professeur_deborde_corrige.ipynb - **Compétence travaillée :** - gérer des contraintes multiples et parfois contradictoires, - reformuler le problème sous forme logique ou combinatoire, - discuter l’assimilation à SAT ou à un problème équivalent, - argumenter la NP-complétude implicite du problème. # ✅ Modalités d’évaluation - **Type :** Projet - **Description :** Choisis un Puzzle _Difficile_ et résous le intégralement en autonomie en l'assimilant à un problème NP-Complet connu. La validation de la compétence se fait lors d'une Soutenance individuelle - **Durée totale :** ~15 minutes ### 🧾 Déroulé de l’évaluation Une fois prêt, contacte le responsable pour planifier ta soutenance. Tu devras : 1. **Présenter l’énoncé** du puzzle de niveau *Difficile* choisi (2 min) 2. **Expliquer ta stratégie** à l’aide d’un schéma : comment as-tu assimilé le problème à un problème NP-Complet connu ? (2 min) 3. **Montrer l’élément le plus malin** ou optimisé de ta solution (extrait de code) (2 min) 4. **Répondre à des questions ciblées** sur ton code (5 min) - fonctionnement précis d’une fonction - compréhension d’un paramètre ou d’un retour - justification d’un choix algorithmique (test, boucle, structure) 5. **Adapter ta solution en direct** selon une consigne du jury (5 min) > 🔍 Ce test permet de vérifier que tu as **développé toi-même** la solution, sans LLM ou assistance extérieure. > Les réponses doivent être **précises, immédiates et maîtrisées** pour valider la compétence. ## 🗓️ Historique - **Dernière mise à jour :** `06 février 2026` - **Rédigé par :** [[Julien DUQUENNOY]]