Want to make creations as awesome as this one?

Transcript

PRESENTAtIoN

Algorithme

Bruteforce

Analyse de données et complexité d'algorithme

4. Comparaison des résultats

Index

29

1. Analyse de l'algorithme de BRUTE FORCE

2. organigramme ET pseudocode

3. Comparaison des performances (force brute vs. optimisée)

Compléxité exponentielle (O(n6))

1.

Analyse de l'algorithme de BRUTEFORCE

Entrée

Liste d'actions

name, cost, profit

Traitement

Boucle qui passe par toutes les combinaisons possibles

Calcule le coût total et le profit pour chaque combinaison

Sortie

Meilleurs investissements

Traitement long

Budget
60 459 énumérations
Compléxité temporelle O(nW)

1.

Analyse de l'algorithme de BRUTEFORCE optimisé

Entrée

Liste d'actions

name, cost, profit

Traitement

Programmation dynamique avec une matrice

stocke en sous-problèmes et décide (ou non) de traiter une solution

Sortie

Meilleurs investissements

Traitement plus rapide

Budget
10020 énumérations

n = nombre d'actionsw = budget

SI encore du budget on continue d'itérer sur la boucle en cours.

Stockage de la meilleure action

Profit = cout * beneficePOUR chaque budget (w): SI cout < budget = on ajoute l'action comme un investissement important dans la matriceSINON : On garde l'ancienne action

Boucle sur chaque action (n)

Matrice (boîte) : dp[n][W]

2. Organigramme

Solution dynamique

Dépend du nombre d'actions et du budget.

3. programmation dynamique

Bruteforce vs optimisé

Optimisé

5X plus efficace

  • Complexité à croissance linéaire en fonction du nombre d'actions et du budget
  • Réduit significativement le temps d'éxécution en excluant les calculs inutiles
  • Une matrice utilise moins de mémoire pour stocker les profits
vs

Bruteforce

Trés lent

  • Doit gérer toutes les combinaisons possibles
  • Beaucoup d'itérations et de calculs
  • Ne gère pas de très grand ensembles de données

Moi :22 actionsCoût total: 499.96€Bénéfice: 397.09€

Sienna :1 actionCoût total: 498.76€ Bénéfice: 196.61€

4.Comparaison des résultats

Premier tableau

On peut noter que l'algorithme optimisé permet de diversifier les sources d'investissements et de placer le maximum d'argent possible en maximisant les profits.

Moi :22 actionsCoût total: 499.92€Bénéfice: 395.93€

Sienna :18 actionsCoût total: 489.24€ Bénéfice: 193.78€

4.Comparaison des résultats

Deuxième tableau

Merci