pierre.kunzli · 8b35a661
--- a/slides/cours_20.md

+ 71

− 20
+++ b/slides/cours_20.md

+ 71

− 20
 @@ -99,7 +99,7 @@ Son équivalent tri-dimensionnel est l'octree (chaque nœud a 8 enfants ou aucun

 . . .

-Image 64 pixels, arbre 25 neouds.
+Image 64 pixels, arbre 25 noeuds.

 ::::

 @@ -214,7 +214,7 @@ bool is_leaf(node *tree) {
    * Le remplir avec les valeurs des pixels.
 * Compression de l'image:
    * Si les pixels sont les mêmes dans le quadrant on supprime le sous-arbre (sans perte)
-    * Si les pixels dévident pas trop on supprime le quadrant (avec perte)
+    * Si les pixels dévient pas trop on supprime le quadrant (avec perte)

 # Fonctions utiles (1/N)

 @@ -237,7 +237,7 @@ arbre creer_arbre(prof)

 ```C
 node *qt_create(int depth) {
-    node *n = calloc(1, sizeof(*n));
+    node *n = calloc(1, sizeof(node));
    if (depth > 0) {
        for (int i = 0; i < 4; ++i) {
            n->child[i] = qt_create(depth-1);
 @@ -271,7 +271,7 @@ entier nombre_noeuds(arbre)
 . . .

 ```C
-inf size(node *qt) {
+int size(node *qt) {
    if (is_leaf(qt)) {
        return 1;
    } else {
 @@ -290,6 +290,7 @@ inf size(node *qt) {

 . . .

+\footnotesize
 ```C
 int max(int x, int y) {
   return  (x >= y ? x : y);
 @@ -306,8 +307,10 @@ int depth(node *qt) {
    if (is_leaf(qt)) {
        return 0;
    } else {
-        depths[i] = 1 + depth(qt->child[i]);
-        return max_depth(depths);
+        for (int i = 0; i < 4; ++i) {
+            depths[i] = depth(qt->child[i]);
+        }
+        return 1 + max_depth(depths);
    }
 }
 ```
 @@ -416,14 +419,44 @@ noeud position(li, co, arbre)
    retourn arbre
 ```

-. . .
-
-* Écrire le code `C` correspondant (5min, matrix)

 ::::

 :::

+# Fonctions utiles (4/N)
+
+\footnotesize
+
+## Pseudocode
+
+```C
+noeud position(li, co, arbre)
+    d = profondeur(arbre);
+    tant_que (d > 1)
+        index = 2 * ((li % 2^d) / 2^(d-1)) +
+            (col % 2^d) / 2^(d-1)
+        arbre = arbre.enfant[index]
+        d -= 1
+    retourn arbre
+```
+
+## Écrire le code `C` correspondant (5min, matrix)
+
+```C
+
+
+
+
+
+
+
+
+
+
+
+```
+
 # Remplir l'arbre

 ## A partir d'une matrice (pseudo-code, 5min, matrix)?
 @@ -444,6 +477,10 @@ arbre matrice_à_arbre(matrice)

 ## A partir d'une matrice (C, 5min, matrix)?

+. . .
+
+\footnotesize
+
 ```C
 node *matrix_to_qt(int nb_li, int nb_co, int matrix[nb_li][nb_co], int depth)
    node *qt = qt_create(depth);
 @@ -454,8 +491,12 @@ node *matrix_to_qt(int nb_li, int nb_co, int matrix[nb_li][nb_co], int depth)
        }
    }
    return qt;
+}
 ```

+
+<!-- 
+Deja fait plus haut
 # La profondeur?

 ## Comment implémenter la fonction profondeur?
 @@ -509,7 +550,7 @@ int depth(node *qt) {
        return max_depth(depths);
    }
 }
-```
+``` -->

 # Remplir la matrice

 @@ -530,6 +571,10 @@ matrice arbre_à_matrice(arbre)

 ## A partir de l'arbre (C, 3min, matrix)?

+. . .
+
+\footnotesize
+
 ```C
 void qt_to_matrix(node *qt, int nb_li, int nb_co, int matrix[nb_li][nb_co])
    for (int li = 0; li < nd_li; ++li) {
 @@ -580,6 +625,8 @@ void qt_to_matrix(node *qt, int nb_li, int nb_co, int matrix[nb_li][nb_co])

 . . .

+\footnotesize
+
 ```C
 matrice symétrie(matrice)
    pour i de 0 à nb_colonnes(matrice) / 2
 @@ -608,6 +655,8 @@ matrice symétrie(matrice)

 . . .

+\footnotesize
+
 ```C
 arbre symétrie(arbre)
    si !est_feuille(arbre)
 @@ -618,6 +667,8 @@ arbre symétrie(arbre)
    retourne arbre
 ```

+# La symétrie d'axe horizontal
+
 * Trivial de faire l'axe horizontal (exercice à la maison)

 # Rotation d'un quart de cercle
 @@ -751,14 +802,14 @@ void lossless_compression(node *qt) {
        for (int i = 0; i < CHILDREN; i++) {
            lossless_compression(qt->child[i]);
        }
-    }
-    if (is_last_branch(qt)) {
-        int val = -1;
-        if (last_value(qt, &val)) {
-            qt->info = val;
-            for (int i = 0; i < 4; ++i) {  
-                free(qt->child[i]);
-                qt->child[i] = NULL;
+        if (is_last_branch(qt)) {
+            int val = -1;
+            if (last_value(qt, &val)) {
+                qt->info = val;
+                for (int i = 0; i < 4; ++i) {  
+                    free(qt->child[i]);
+                    qt->child[i] = NULL;
+                }
            }
        }
    }
 @@ -813,7 +864,7 @@ bool last_value(node *qt, int *val) {

 ## Que devient l'arbre suivant si l'écart est petit?

-![](figs/quad_img_simple.svg)
+![](figs/quad_img_simple_variation.svg)

 . . . 

 @@ -839,7 +890,7 @@ bool last_value(node *qt, int *val) {
 . . .

 * Si $\sigma<\theta$, $\theta$ est la **tolérance**:
-    * Remplacer la valeur du pixel par la moyenne eds enfants.
+    * Remplacer la valeur du pixel par la moyenne des enfants.
    * Remonter les valeurs dans l'arbre.

 ## Quelle influence de la valeur de $\theta$ sur la compression?