palgo

Preuves et Analyses des Algorithmes
module I41 année 2006-2007

Planches de Travaux-Pratiques :

au format ps: [ TP 1 ] [ TP 2 ] [ TP 3 ] [ TP 4 ] [ TP 5 ] [ TP 6 ]
au format pdf: [ TP 1 ] [ TP 2 ] [ TP 3 ] [ TP 4 ] [ TP 5 ] [ TP 6 ]
sources latex: [ TP 1 ] [ TP 2 ] [ TP 3 ] [ TP 4 ] [ TP 5 ] [ TP 6 ]
solutions: [ TP 1 ] [ TP 2 ] [ TP 3 ] [ TP 4 ] [ TP 5 ] [ TP 6 ]

Sujets :

[ examen ecrit juin 2006 ] [ examen de Tps juin 2006 ]

Liste des Algorithmes Fondamentaux :

Les algorithmes ci-dessous sont au programme de l'examen de travaux-pratiques. Il s'agit de les connaitres parfaitement : invariants, complexité, et implantation en langage C. Il faut être capable de mettre en evidence ces points avec les outils de base : gdb, gprof et gnuplot.

Numération
- Algorithme additifs
- Décomposition des nombres
- Suite de Fibonacci
Enumération des t-uplets
- énumération des (x₁, x₂, ... x_n) 1 <= x_i <= b
- énumération des (x₁, x₂, ... x_n) 1 <= x_i <= i
Exponentiation modulaire

méthode naive
méthode du paysan russe

Racine carrée d'un entier

dichotomie
méthode de Héron.

Calcul de PGCD

Algorithme additif
Algorithme d'Euclide

Automate et recherche de Motifs

reconnaissance de motif

table de transition