COURS d'ALGORITHMIQUE

Analyse de complexité (2)

   Rappel sur nb d'op, tailles des données, équations de récurrence.
   Tableaux sur les ordres de complexite's % temps.
   Exemples de tris, pseudo code maple.
   Exemples de pb difficile; pb NP-complet; de réduction: Sat < CS 

 
 Résolution de systemes lineaires (3)

   Gauss -> LU: QR
   Bareiss en exact
   p-adic; Dixon
   Mat. structure'e Toeplitz. Hankel/ FFT (deja fait).
  

 
 Résolution d'équations polynomiales (4)
  
   Newton
   Weierstrass
   Dichotomie -> Descartes
   Sturm
   Matrice compagnon + val/vect propres
   Homotopies pt(x)= t p(x) + (1-t) p0(x)
   iteration controlle'e: x-> x^ ; x-> 1/2(x+1/x)
  
 Graphes (2)
  
   Définitions; qq algorithmes de base