PROJET ETUDIANT : Algorithmes et Data Science
Hello,
Dans ce projet, j’ai travaillé sur la résolution du problème du sac à dos, un cas classique d’algorithmique et d’optimisation combinatoire, appliqué ici à une problématique de stratégie d’investissement. L’objectif était de sélectionner la combinaison optimale d’éléments maximisant le bénéfice tout en respectant une contrainte de capacité, en tenant compte des performances de calcul.
J’ai d’abord implémenté une solution brute-force, permettant d’explorer l’ensemble des combinaisons possibles afin de garantir l’exactitude du résultat. J’ai ensuite optimisé cette approche en concevant un algorithme plus efficace, réduisant significativement le temps de calcul tout en conservant la fiabilité des résultats. L’analyse de la complexité algorithmique à l’aide de la notation Big O a été un élément central du projet, me permettant de comparer objectivement les différentes solutions.
Enfin, j’ai procédé à un backtesting des algorithmes développés afin d’évaluer et comparer leurs performances, tant en termes de rapidité que de pertinence des résultats. Ce projet m’a permis de renforcer ma capacité à décomposer des problèmes complexes, concevoir des algorithmes adaptés, analyser leur efficacité et justifier des choix techniques — des compétences essentielles pour le développement logiciel et la résolution de problématiques à grande échelle.
En quelques mots-clés :
-
Python
-
Algorithmique
-
Problème du sac à dos
-
Optimisation combinatoire
-
Résolution de problèmes
-
Décomposition de problèmes complexes
-
Brute-force
-
Optimisation d’algorithmes
-
Analyse de performances
-
Notation Big O
-
Complexité temporelle
-
Comparaison d’algorithmes
-
Backtesting
-
Fiabilité et validation des résultats
-
Logique algorithmique
J’ajouterai ci-dessous les améliorations apportées à ce projet. La dernière version, en date, en tête de page.
V01
Le code source : repository GitHub
Exemple d’exécution des deux algorithmes (brute-force et programmation dynamique) sur la liste d’actions fournies :
On voit que la solution est la même avec les deux algorithmes. Cependant le temps d’exécution est tout autre selon la méthode. Voir le détail dans le document ci-après.
Enfin, voici le fichier recensant les diapositives de présentation de mon travail sur ce projet, le contexte et les objectifs, et l’analyse de données sur les deux ensembles de données fournis par une collègue de travail fictive ainsi que le backtest et l’optimisation réalisés.
A bientôt ! 😉