Tarek Chaaban

Tarek Chaaban, M.Sc's official blog. It contains current web project portfolio, posts regarding his Canadian army experience, news, sports articles, and web tutorials on programming and using social networking technologies.

Algorithme

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 .

Introduction aux Algorithmes

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 :

  • Comment Concevoir des algorithme ?
  • Comment exprimer des algorithme ?
  • Prouver la Correctitude .
  • Efficacité (temps, espace-mémoire ,analyse théorique et empirique)
  • Optimalite .

Stratégies :

  • Forces Brute.
  • Diviser pour régner.
  • Diminuer et Conquérir.(On diminue de 2 a 3 pas , plus long que diviser pour régner)
  • Pré-traitement.
  • Vorace
  • Programmation dynamique.
  • Marche arrière.
  • Séparation et Évaluation

Analyse :

Qualité de l’algorithme :

  • Correctitude (Résultat Correcte ?)
  • Efficacité (temps – mémoire)

Existe-t-il un meilleur algorithme ?

  • Bornes Inférieurs
  • Optimalite

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 .

2 Comments

  1. 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 :(

  2. salut
    est ce que vous pouvez m’envoyer une methode de resolution pour les problémes de sprogramation dynamique
    Cordialement
    Nb: j’ai un examen demain dans cette matière

Leave a Response

Please note: comment moderation is enabled and may delay your comment. There is no need to resubmit your comment.