Skip to content

Latest commit

 

History

History
108 lines (96 loc) · 8.25 KB

projet_sepc.md

File metadata and controls

108 lines (96 loc) · 8.25 KB
Raw

Objectif du Projet L'objectif de ce projet est de :

  • Implémenter un algorithme célèbre en Python.
  • Utiliser deux structures de données différentes pour obtenir des complexités différentes.
  • Appliquer la Programmation Orientée Objet (POO) dans vos implémentations.
  • Écrire des tests unitaires pour vos implémentations en utilisant pytest.
  • Fournir la meilleure représentation graphique possible de l'algorithme.
  • Expliquer l'algorithme de manière simple pour le grand public.
  • Organiser votre projet selon une arborescence spécifique, incluant un script main.py, des fichiers de librairies, et des tests.
  • Publier le projet sur un dépôt GitHub public avec un README clair et détaillé.

Description du Projet Vous devrez :

  1. Choisir un algorithme célèbre (par exemple, Dijkstra, A*, algorithme de Kruskal…)

  2. Rédiger une description simple de l'algorithme, destinée au grand public. Cette description doit expliquer le fonctionnement de l'algorithme de manière accessible, sans jargon technique.

  3. Implémenter cet algorithme en Python de deux manières différentes en utilisant deux structures de données distinctes. Cela devrait entraîner des complexités temporelles ou spatiales différentes.

    • Utiliser la Programmation Orientée Objet (POO) pour structurer votre code.
    • Créer des classes et méthodes appropriées pour modéliser les éléments de l'algorithme.
    • Séparer votre code en modules : un script principal main.py, des fichiers de librairies, et des tests unitaires.

  4. Écrire des tests unitaires pour vos implémentations en utilisant pytest.

    • Les tests doivent couvrir les cas d'utilisation principaux, les cas limites, et vérifier la correction des résultats.
    • Les tests doivent être placés dans un répertoire dédié (tests/) et être clairement organisés.

  5. Analyser les complexités (temps et espace) des deux implémentations et comparer leurs performances.

  6. Créer une représentation graphique de l'algorithme pour illustrer son fonctionnement interne. Cela peut être sous forme de diagrammes, animations ou visualisations interactives.

  7. Publier votre code sur un dépôt GitHub public. Assurez-vous que le dépôt contient :

    • Le code source des deux implémentations, utilisant la POO.
    • Les tests unitaires pour chaque implémentation.
    • La description simple de l'algorithme pour le grand public.
    • Les fichiers ou scripts nécessaires pour générer la représentation graphique.
    • Un README clair expliquant :
      • Le choix de l'algorithme.
      • La description simple de l'algorithme.
      • Les structures de données utilisées.
      • L'utilisation de la POO dans vos implémentations.
      • Les différences de complexité entre les implémentations.
      • Comment exécuter les tests avec pytest.
      • Comment exécuter le code et visualiser les résultats.
      • Toute dépendance ou instruction spéciale.

Livrables

  • Description Simple de l'Algorithme : Un document (description_simple.md) expliquant l'algorithme de manière accessible au grand public.
  • Code Source : Deux implémentations de l'algorithme en Python, utilisant la POO, bien documentées et commentées.
  • Tests Unitaires : Des tests pour chaque implémentation, utilisant pytest, situés dans le répertoire tests/.
  • Représentation Graphique : Une visualisation claire du fonctionnement de l'algorithme, avec le code associé (visualisation.py).
  • Analyse Comparative : Un document (analyse_complexite.md) détaillant l'analyse des complexités et comparant les performances des deux implémentations.
  • Dépôt GitHub : Un lien vers le dépôt public contenant tout le matériel ci-dessus, organisé selon l'arborescence spécifiée.

Critères d'Évaluation

  • Clarté de la Description Simple : Capacité à expliquer l'algorithme de manière accessible et compréhensible pour le grand public.
  • Correction et Efficacité du Code : Fonctionnalité et performance des deux implémentations.
  • Utilisation de la POO : Bonne application des concepts de la POO (classes, héritage, encapsulation, etc.).
  • Qualité des Tests Unitaires : Couverture des tests, pertinence des cas de test, organisation des fichiers de test.
  • Qualité de la Représentation Graphique : Clarté et pertinence de la visualisation.
  • Analyse des Complexités : Compréhension et explication des différences de complexité.
  • Organisation du Projet : Respect de l'arborescence demandée et bonne organisation des fichiers.
  • Documentation : Clarté, exhaustivité et organisation du README et des autres documents.
  • Bonnes Pratiques de Programmation : Lisibilité du code, commentaires, respect des conventions de codage.

Instructions Supplémentaires

  • Choix de l'Algorithme : Sélectionnez un algorithme suffisamment complexe pour permettre une analyse intéressante, mais gérable dans le temps imparti.
  • Description Simple : Votre explication doit être rédigée en termes simples, en évitant les termes techniques complexes. Utilisez des analogies ou des exemples concrets pour faciliter la compréhension.
  • Structures de Données : Utilisez différentes structures de données pour vos implémentations (par exemple, listes, tas, graphes, arbres).
  • Programmation Orientée Objet : Utilisez la POO pour structurer votre code. Créez des classes pour représenter les éléments clés de l'algorithme. Pensez à l'héritage si pertinent.
  • Tests avec pytest :
    • Installez pytest si nécessaire (pip install pytest).
    • Organisez vos tests dans le répertoire tests/ en suivant les conventions de nommage de pytest (test_*.py).
    • Incluez des instructions dans le README sur la façon d'exécuter les tests (pytest ou python -m pytest).
  • Outils de Visualisation : Utilisez des bibliothèques Python comme Matplotlib, Plotly, ou des outils dédiés pour créer des animations (par exemple, Pygame).
  • Gestion du Versionnement : Commitez régulièrement votre travail sur GitHub pour montrer l'évolution de votre projet. Date de Remise
  • Date limite : jeudi (+1 pour livraison avant vendredi) ou bien vendredi

Ressources Utiles

Comment Soumettre

  • Créez un dépôt GitHub public nommé projet-algorithme-[votre_nom].
  • Organisez votre projet selon l'arborescence spécifiée.
  • Assurez-vous que le dépôt contient tout le code, les tests, la description simple, les fichiers de visualisation et le README.
  • Mettre le lien du dépôt sur le google sheet de la classe a coté de votre repo de la semaine

Conseils

  • Planification : Commencez tôt pour avoir le temps d'explorer les différentes implémentations, d'écrire des tests, et de créer une visualisation de qualité.
  • Description Simple : Prenez le temps de bien expliquer l'algorithme de manière accessible. Faites relire votre description par des personnes non spécialisées pour vérifier sa clarté.
  • POO : Réfléchissez à la manière dont vous pouvez modéliser les éléments de l'algorithme en utilisant des classes et des objets.
  • Tests Unitaires : Écrivez des tests au fur et à mesure que vous développez votre code. Cela vous aidera à détecter les bugs tôt.
  • Documentation : Commentez votre code et expliquez vos choix dans le README.
  • Tests : Vérifiez que vos implémentations fonctionnent correctement avec différents jeux de données.
  • Originalité : Soyez créatif dans la visualisation et n'hésitez pas à ajouter des fonctionnalités supplémentaires si le temps le permet.

Si vous avez des questions ou rencontrez des difficultés, n'hésitez pas à me faire un ticket et me ping par teams/discord/email sur les heures de bureau. Bonne chance à tous et au plaisir de découvrir vos projets !