# OLA, TD9: Ordre et terminaison

## Exercice 1: Petits trains

1. On considère une liste l d'entiers qui peuvent aller de 1 à autant qu'on veut. Chaque entier n représente un train de taille n. La liste l représente les trains non rangés

Pour t dans l faire:
si t = 1, alors retirer t de l
sinon, retirer t de l puis: ```l <- l ++ [1; t-1]```

Le nombre de trains non rangés, c'est la taille de la liste l.
Dans le cas t=1, le nombre de trains non rangés diminue.
Dans l'autre cas (t>1), le nombre de trains non rangés augmente.

Dans le cas t=1, le nombre de wagons non rangés diminue.
Dans le cas t > 1, le nombre de wagons non rangés ne change pas.

Dans le cas t=1, le nombre de trains de taille 1 diminue.
Dans le cas t > 1, le nombre de trains de taille t diminue, mais le nombre de trains de taille t-1 et de taille 1 augmente.

On choisit de représenter les choses un peu différemment: on considère une liste l de paires d'entiers ```l = [(x1, y1); ... ; (xn, yn)]```
La paire (x, y) dit qu'il y a x trains de taille y à ranger.

Par exemple, on commence avec la liste

après une étape on a : ```l1= [(0, 3); (3, 2); (2, 1)]``` -> le nombre de trains de taille maximale a diminué 

l1 < l
l2 = [(0, 3) ; (2, 2); (4, 1)]
l2 < l1
l3 = [(0, 3) ; (1, 2); (6, 1)]
l3 < l1
l4 = [(0, 3); (0, 2); (8, 1)]
l5= [(0, 3); (0, 2); (7, 1)]
l5 < l4

2. Une arête représente le fait que deux wagons appartiennent au même train. 
Ce qui diminue strictement, c'est S = nb d'arêtes plus nb de sommets

## Exercice 2: Terminaison de parcours de graphe


Code:

à_explorer = {s}
tant que à_explorer n’est pas vide
retirer un sommet s de à_explorer
...
pour chaque voisin v de s
si v n’est pas marqué alors
marquer v
ajouter v à à_explorer

1. Si les voisins sont marqués le nombre de sommets à explorer va diminuer, 
sinon il va augmenter.
Le nombre de sommets marqués augmente ou reste fixe (en tout cas il ne diminue jamais).

2. Durant un tour de boucle, l'une de ces deux instructions a forcément lieu: 
- marquer un sommet
- retirer un sommet de ```à_explorer```

Dans le premier cas, on diminue le nombre de sommets non marqués
Dans le deuxième cas, on diminue le nombre de sommets à explorer
Ce qui diminue strictement à chaque tour de boucle (donc qu'on soit dans le premier ou dans le deuxième cas), c'est la paire 
(nombre de sommets non marqués, nombre de sommets à explorer). 
Au bout d'un moment, on arrive sur la paire (0, 0) et l'algorithme s'arrête. 

## Exercice 3: Bug de terminaison

def search(e, t):
l = 0
u = len(t)
while l < u:
m = (l+u)//2
if t[m] == e:
return true
elif t[m] < e:
#(il faudrait écrire m + 1)
l = m
else:
u = m
return false

Essayons ```search(2, [1])```

l = 0
u = 1

m = 0

l = 0

On voit que la valeur de l ne change jamais et celle de u non plus. Donc on est coincé dans une boucle infinie. 

## Exercice 4: 

1.  00 < 1 (règle 2) et ensuite 100 < 11 (règle 1)
2. 00 < 0000 < 1
3. 
Equations pour test
$test(\epsilon, \epsilon)= 0$
Pour toute lettre x, pour tout mot m, 
$test(\epsilon, xm)= 1$
$test(xm, \epsilon)=0$
Pour tous mots $m_{1}$ et $m_{2}$
$test(0m_{1}, 1m_{2})=1$
$test(1m_{1}, 0m_{2})=0$
Pour tous mots $m_{1}$ et $m_{2}$ et pour toute lettre x, 
$test(xm_{1}, xm_{2})= test (m_{1}, m_{2})$

4.
 - $test(\epsilon, \epsilon)= 0$ et on a bien $\epsilon = \epsilon$
 - $test(xm, \epsilon)=0$ on a bien $\epsilon < xm$ par la règle 1
 - $test(1m_{1}, 0m_{2})=0$ et on a bien $0m_{2} <1m_{1}$ par la règle 2
 - Supposons que $test(xm_{1}, xm_{2})= 0$ alors par hypothèse de récurrence, on a $m_{2} < m_{1}$ et donc on applique la règle 3 pour conclure.