« Les Gags || Cell phone deal »
Posted: chaaban on Sep 18 | Tarek, University news
This Post if for French user … since i dont have enough time to translate , it’s the Alogorythm course that i’m taken … i see this as a good way to review what i took and maybe let other visitors of this blog learn something new .
Pourquoi Étudier les algorithmes :
Les Algorithme sont le noyau de l’informatique .
Importance Pratique :
- Boite a outils avec algos connus .
- Conception et analyse des algorithme pour de nouveau problèmes .
Problèmes “non difficile” :
* Stratégie vorace “Glouton” .
* Stratégie diviser pour régner .
* Programmation dynamique
* Programmation en marche arrière (exemple du labyrinthe)
* Séparation et l’évaluation Progressive “Branch and Bound”
Problèmes Difficile :
- Heuristique - Déterministe
- Approximation
- Algorithme probabiliste (Monte Carlo , Las Vegas , évaluation du nombre pi)
- Problème NP (Ne peuvent pas être résolue de façon déterministe dans un temps polynomiale)
- Problème P
- Problème Np-Complet (On ne sait pas si c’est polynomiale ou non … on suppose que c’est non)
Méthode Euclide : PGCD (Plus grand commun dénominateur)
PGCD (m,n) ; m,n > 0 et m > n
PGCD (m,n) = PGCD (m , m-n) // || (n , m mod n)
Base : PGCD(m,0) = m
PGCD (60,24) => PGCD(24,12) => PGCD(12,0) = 12
Temps = O(lg n)
Facteurs Premier
m = (p1^a1) * (p2^a2) * (p3^a3) * …. * (pj^aj)
n = (p1^b1) * (p2^b2) * (p3^b3) * …. * (pj^bj)
PGCD (m,n) = (p1^min(a1,b1)) * …. * (p1^min(aj,bj))
Example :
60 = 2^2 * 3 * 5
24 = 2^3 * 3
PGCD(60,24) = 2^2 * 3 = 4*3 = 12
Force Brute :
x divise m ? si oui x divise n ? sinon x <- x -1
Temps : ordre du plus petit des deux nombres .
Problème Computationnelle
* TRI .
* Fouille .
* Le plus court chemin dans un graphe .
* Arbre Minimale de Recouvrement . // Ordre Polynomiale
- Test de Primalite . (si un nombre est premier ou non)
- Voyageur de commerce .
- Sac a dos .
- Jeu d’échecs
- Tour de Hanoi (facile a implémenté mais le temps est exponentiel)
* Terminaison d’un programme // Indécidable (pas de solution)
Questions de Base :
Stratégies :
Analyse :
Qualité de l’algorithme :
Existe-t-il un meilleur algorithme ?
Fini : Termine apres un nombre fini de pas .
Caractère défini : Spécification rigoureuse et sans ambiguïtés .
Entrées Valides et Clairement Spécifiés .
On peut (doit) prouver la production d’une sortie correcte pour une entrée valide .
Analyse Theorique de l’efficacite (Temps)
Le nombre de repetitions de l’operation de base en fonction de la taille de l’entree T(n) ~ #de fois qu’on execute * constante .
On s’interresse generalement au pire des cas ou au cas moyen , Le pire des cas depend de l’entree .
Pour les cas moyen on va calculer la probabilite .
salut
est ce que tu pourrais m’envoyer stp des cours ou des exams corrigés d’algo.
Merci
Nb: j’ai un examen demain dans cette matière