===== Algorithmique avancée =====


^ Enseignant ^ Site/Liens ^ Cours ^ TD ^ TP ^ ECTS ^
| M. Basile SAUVAGE | [[https://dpt-info.u-strasbg.fr/~sauvage/Enseignements/M1_S2_MAA.php|Materiel 2008]] ou [[http://dpt-info.u-strasbg.fr/~sauvage/#enseignements|Sauvage:enseignements]]| 18 | 18 |  | 3 |
^ Objectifs ^^^^^^
| savoir-faire et compétences -- Analyse d'algorithmes ||||||
^ Contenu ^^^^^^
| Etude des principales familles d'algorithmes : diviser pour régner, méthodes gloutonnes, programmation dynamique, algorithmes randomisés.  ||||||
|Algorithmes approchés pour la résolution de problèmes difficiles. ||||||
^ Prérequis ^^^^^^
| Algorithmique de base, structures de données, programmation impérative ||||||
^ Références ^^^^^^
| Cormen, Leiserson, Rivest et Stein, Introduction à l'algorithmique, Edition Dunod ||||||
| Alain Darte, Serge Vaudenay, Algorithmique et optimisation : Exercices corrigés, Edition Dunod||||||
^ Contrôle des Connaissances ^^^^^^
| Contrôle continu : coeff. 1/3  ||||||
| Examen écrit : coeff. 2/3 (durée : 2h) ||||||

==== Notes de cours ====

  * [[algos:algoplus_1|]] : 2 février 2010
    * [[algos:algoplus_ex_1|]]
  * [[algos:algoplus_1a|]] : 2 février 2010
    * Définitions
    * Tri par insertion (un exemple)
    * Bornes asymptotiques
    * Conventions
  * [[algos:algoplus_2|]] : 16 février 2010
  * [[algos:algoplus_2a|]] : 16 février 2010
  * [[algos:algoplus_3|]] : 23 février 2010
    * Tri Rapide
    * Algo de Strassen (multiplication des matrices)
    * Calcul de l'enveloppe convexe en 2D
    * [[algos:algoplus_3_ex|]] recherche d'une valeur dans un tableau trié
    * et [[algos:algoplus_3_ex#multiplication_de_deux_polynomes|multiplication de deux polynômes]]
  * [[algos:algoplus_4_ex|]] sous-suite de somme maximale
  * [[algos:algoplus_4|]] programmation dynamique -- intro, principes
    * [[algos:algoplus_5_ex_1|]] plus longue sous-séquence commune
    * [[algos:algoplus_5_ex_2|]] sous-suite ascendante maximale


==== Notes de TD ====

  * [[algos:algoplus_2|]] : 16 février 2010

==== Contrôle Terminal ====

  * [[algoplus_ct|]]