Planche 1
Planche 2
Plan
- La récursivité comme principe d'induction
<Diviser pour régner>
- QuickSort, tri Fusion
- Entrées graphiques
- Courbes de Bézier (spline)
Planche 3
Un premier exemple: maxima consécutifs partiels
On donne un tableau d'entiers relatifs. Trouver les sommes maximales
de sous-séquences consécutives. (cf livre de Bentley, Programming Pearls)
static int maximum (int a[]) {
int n = a.length;
int res = 0;
int s = 0;
for (int g = 0; g < n; ++g)
for (int d = g; d < n; ++d) {
s = 0;
for (int i = g; i <= d; ++i)
s = s + a[i];
res = Math.max (res, s);
}
return res;
}
Complexité?
Planche 4
Maxima consécutifs partiels -- bis
static int maximum (int a[]) {
int n = a.length;
int res = 0;
int s = 0;
for (int g = 0; g < n; ++g)
s = 0;
for (int d = g; d < n; ++d) {
s = s + a[d];
res = Math.max (res, s);
}
return res;
}
Complexité?
Planche 5
Maxima consécutifs partiels -- ter
static int maximum (int[] a, int g, int d) {
int n = a.length;
int res = 0, s = 0, maxG = 0, maxD = 0;
if (g > d) return 0;
else if (g == d)
return Math.max (0, a[g]);
else {
int m = (g + d) / 2;
s = 0; maxG = 0;
for (int i = m; i >= g; --i) {
s = s + a[i];
maxG = Math.max (maxG, s);
}
s = 0; maxD = 0;
for (int i = m+1; i <= d; ++i) {
s = s + a[i];
maxD = Math.max (maxD, s);
}
int maxACheval = maxG + maxD;
int maxAGauche = maximum (a, g, m);
int maxADroite = maximum (a, m+1, d);
return Math.max (maxACheval, max(maxAGauche, maxADroite));
}
}
Complexité?
Planche 6
Maxima consécutifs partiels -- 4
static int maximum (int[] a) {
int n = a.length;
int maxSoFar = 0, maxEndingHere = 0;
for (int i=0; i < n; ++i) {
maxEndingHere = Math.max (maxEndingHere, 0);
maxSoFar = Math.max (maxSoFar, MaxEndingHere):
}
return maxSoFar;
}
Complexité?
Si n est grand, la différence de complexité entre ces 4 programmes
peut se révéler critique.
Planche 7
Tri récursif
Principe: on coupe en 2, on trie les 2 moitiés et on réarrange le
résultat. C'est le principe du tri fusion, qui est ttefois un peu plus
dûr à programmer que QuickSort [Hoare 1960], où on essaie de
deviner une bonne décomposition.
Quicksort. On prend un élément au hasard, on le met en place avec à sa
gauche des plus petits ou égal, et à sa droite des plus grands ou égal
et on recommencre récursivement sur les 2 moitiés.
static void qSort(int g, int d) {
if (g < d) {
v = a[g];
Partitionner le tableau autour de la valeur v
et mettre v à sa bonne position m
qSort (g, m-1);
qSort (m+1, d);
}
}
Planche 8
QuickSort
static void qSort(int g, int d) {
int i, m, x, v;
if (g < d) {
v = a[g];
m = g;
for (i = g+1; i <= d; ++i)
if (a[i] < v) {
++m;
x = a[m]; a[m] = a[i]; a[i] = x;
}
x = a[m]; a[m] = a[g]; a[g] = x;
qSort (g, m-1);
qSort (m+1, d);
}
}
Complexité?
Planche 9
QuickSort -- coût moyen [Sedgewick]
CN est le nombre moyen de comparaisons. On a C0 = C1 = 0, et
pour N ³ 2
CN = N + 1 + 1 / N S1 £ k £ N (Ck-1 + CN-k)
= N + 1 + 2 / N S1 £ k £ N Ck-1
D'où
N CN = (N+1) CN-1 + 2 N
D'où le coût moyen
CN » 1,38 N log2 N très bon
Planche 10
Entrées graphiques en Ocaml
Pour lire des points à la souris, on peut faire de l'attente active
(polling) avec des événements multiplexés clavier/souris:
let wait_button_down() =
while not button_down() do () done;;
let wait_button_up() =
while button_down() do () done;;
let get_next_point () =
wait_button_down();
wait_button_up();
mouse_pos();;
et, par exemple, on s'arrête qd on met le curseur dans une zone
spécifique de l'écran.
Planche 11
Entrées graphiques en Ocaml -- bis
Il y a plus sophistiqué (et non séquentiel) en utilisant le driver d'événements:
let e = wait_next_event [Button_down; Key_pressed] in
if e.keypressed then begin
match e.key with
'q' -> ....
end else
if e.button then begin
Planche 12
Entrées graphiques en Java
Les deux fonctions suivantes sont dans la bibliothèque MacLib.
static void waitClickDown () { while (!g.button()) ; }
static void waitClickUp () { while (g.button()) ; }
On peut les utiliser pour lire à la souris les coordonnées d'un point
sur un front montant d'un click de la souris.
static Point getNextPoint () {
g.waitClickDown();
g.waitClickUp();
Point p = g.getMouse();
g.paintCircle (p.h, p.v, 3);
return p;
}
Planche 13
Entrées graphiques multiplexées en Java
g.keyPressed() teste s'il y a un caractère sur l'entrée clavier?
g.getKey() pour lire ce caractère
while (!g.button() && !g.keyPressed()) do
;
if (g.keyPressed()) {
int c = g.getKey();
switch (c) {
case 'q': ...
} else
if (g.button()) {
C'est une attente active multiplexée entre clavier et souris.
Au début du programme, ne pas oublier les ordres de la nouvelle MacLib
avec la classe orientée-objet Grafport:
static GrafPort g = new GrafPort();
g.showDrawing();
Planche 14
Splines
Interpolation entre plusieurs points (coniques, cubiques, etc). Les
cubiques sont les plus utilisées en CAO, en graphique interactif, pour
générer des polices de caractères (PostScript, Metafont). Les plus
simples à décrire sont les courbes paramétriques de Bézier (ingénieur
de Renault) et de Casteljau.
Les cubiques de Bézier (splines) sont données par 4 points, P0,
P1, P2, P3. La cubique est tangente en P0 et P3, les
vecteurs P0 P1 et P2 P3 représentent les valeurs des
dérivées en P0 et P3. La cubique est toujours inscrite dans le
quadrilatère P0 P1 P2 P3.
On les dessine facilement avec une méthode Diviser pour Régner, car on
trouve une définition récursive, en prenant les milieux:
P1,1 de [P0 P1],
P2,1 de [P1 P2],
P3,1 de [P2 P3],
P2,2 de [P1,1 P2,1],
P3,2 de [P2,1 P3,1],
P3,3 de [P2,2 P3,2]
et en considérant les courbes de Bézier pour P0 P1,1 P2,2
P3,3 et P3,3 P3,2 P3,1 P3. (Il suffit de tracer le
segment [P0 P3] pour un quadrilatère de petite surface).
Planche 15
Splines -- bis
Un expert est Lyle Ramshaw (DEC/SRC
Tech
Report 19). On en parle au cours Graphique de Puech et Sillion dans
la majeure Math et Info, M1.
Planche 16
Exercices
- Animer le tri avec QuickSort, ou le Tri Fusion
- Dessiner une courbe de Bézier (spline), avec une continuité
C1 pour faire des contours de lettres.
This document was translated from LATEX by HEVEA.