Les algorithmes utilisés
========================

Choix de la notion de score
---------------------------

C'est le noeud de l'algorithme. Un mauvais choix et le programme ne fonctionne pas du tout.

Voici une représentation de l'image bitmap du caractère `a` minuscule :

|   |   |   |   |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |

supposons que ce caractère ait été coupé par la broyeuse en deux bandelettes :

- bandelette `g` :

|   |   |
|---|---|
| 0 | 0 |
| 0 | 1 |
| 0 | 0 |
| 0 | 1 |
| 1 | 0 |
| 1 | 0 |
| 1 | 1 |

- bandelette `d` :

|   |   |
|---|---|
| 0 | 0 |
| 1 | 0 |
| 0 | 1 |
| 1 | 1 |
| 0 | 1 |
| 0 | 1 |
| 1 | 1 |

1. Le score doit être élevé lorsque les pixels allumés de la deuxième colonne de `g` correspondent
   aux pixels allumés de la première colonne de `d`. 
   
   - Combien de pixels allumés correspondent en collant `g` à `d` ? <!-- 3 -->
   - Combien de pixels allumés correspondent en collant `d` à `g` ? <!-- 3 aussi -->
   - Peut-on se contenter de comptabiliser le nombre de pixels correspondants ?

2. le score doit également prendre en compte les non aligements :
   - Dans le sens `g` / `d` :
        - Quel est le nombre d'alignements `10` ? <!-- 0 -->
        - Quel est le nombre d'alignements `01` ? <!-- 0 -->
   - Dans le sens `d` / `g` :
        - Quel est le nombre d'alignements `10` ? <!-- 2 -->
        - Quel est le nombre d'alignements `01` ? <!-- 0 -->
   - Comment prendre en compte ces mauvais alignements pour diminuer le score obtenu à la question 1 ? <!-- en divisant -->
  

Seuillage
---------

En pratique, les images ne sont pas toute noir ou toute blanche. On décide qu'un pixel est allumé
lorsque sa **luminosité** est **inférieure** à un certain seuil.

Lorsque les pixels sont représentés par un triplet `(r, v, b)` d'entiers codés sur 8 bits, on peut
définir la luminosité comme la somme des trois composantes, divisée par `3*255` (l'utilisation de
coefficients permet d'affiner cette notion). On obtient alors une mesure de la luminosité sous la
forme d'un nombre flottant compris entre 0 (le moins lumineux) et 1 (le plus lumineux). 

Un pixel est considéré comme allumé si sa luminosité est inférieure à un certain seuil. Il s'agit
d'un paramètre de l'algorithme.


Programmation Orientée Objet
----------------------------

Il peut être utile de définir : 

- une classe `Bande` pour gérer les bandelettes :

``` mermaid
classDiagram

class Bande {
   +Bande(im: Image)
   +dimensions() : tuple[int]
   +image() : Image
   +scoreParPixels(autre: Bande) -> float
}
```

- une classe `Pixel` pour gérer les pixels situés sur les bords des bandelettes :
  
``` mermaid
classDiagram
class Pixel {
   +Pixel(im, x, y)
   +coords() : tuple[int]
   +luminosite() : float
   +est_allume() : bool
}
```

- un module ou une classe `algo`, dans laquelle sera implanté l'algorithme de résolution.


Résolution du problème des bandelettes 
--------------------------------------

Plusieurs algorithmes de résolution peuvent être envisagés.

Si le critère est suffisamment discriminant, alors un algorithme glouton est suffisant

### résolution gloutonne

- choisir la bandelette dont les scores sont les plus faibles. On considère que cette bandelettes
  sera la bandelette la plus à droite 
- soit n le nombre de bandelettes 
- Pour i allant de 1 à n-1 
    - choisir la bandelette pas encore choisie qui maximise le score 
    - ajouter cette bandelette à la solution
- Fin Pour


### Résolution en récursif


Lorsque le score n'est pas suffisamment discriminant, il faut explorer plusieurs solutions

resoud_bandelette(debut, suite):

- si suite est vide, alors renvoyer une liste contenant début
- sinon,

    - si aucune bandelette ne réalise un bon score avec le début, alors renvoyer une liste vide
    - sinon 
    
        - sol = liste vide
        - pour toute bandelette `b` de suite qui réalise un bon score avec le debut
            - concaténer sol et resoud_bandelette(debut + b, suite - b) 
        - fin pour
        - renvoyer sol
        
La notion de "bon score" peut être celle d'un score dépassant un seuil donné.

### Résolution en itératif

On peut dérécursiver l'algorithme précédent en utilisant une pile.

resoud_bandelette(debut):

- P = pile_vide()
- P.empile(debut)
- tant que P n'est pas vide :
    - perm = P.depiler()
    - Si on a atteint le nombre de bandelette, alors ajouter perm aux solutions
    - sinon empiler toutes les bandes b n'appartenant pas à perm qui réalise
      un bon score avec la dernière bande de perm.
- renvoyer les solutions
