### Exercice 1

# voir le fichier test_stm.py

### Exercice 2

#  Il suffit de faire une règle de trois :
#      6,8 s * 1_000_000^2 / 16_000^2
#    = 26 560 s
#    = 7 h 23 min

### Exercice 3

# 1. Les deux fonctions sont correctes.

# 2. La première a une complexité quadratique (N + N-1 + ... + 2 + 1),
#    la seconde une complexité linéaire.

#    Si on double la taille du tableau, le temps de calcul de est_trie1
#    est multiplié par 4, celui de est_trie2 par 2 seulement.

#    La fonction est_trie2 est clairement préférable.

### Exercice 4

# voir le fichier machine_turing.py

### Exercice 5

# On utilise trois états C, P et A en plus de l'état final F.
# Dans l'état C (qui est l'état initial), la machine cherche une
# occurrence de 0. Dans les états P et A, la machine revient
# écrire son verdict. La machine passe dans l'état P (présent) dès
# qu'elle observe un symbole 0. Elle passe dans l'état A si elle
# atteint le blanc suivant l'entrée sans avoir rencontré de 0.
#
#
#     état | lu    | écrit | dépl. | suiv
#     -----+-------+-------+-------+-------
#     C    | 0     | 0     | <-    | P
#     C    | 1     | 1     | ->    | C
#     C    | blanc | blanc | <-    | A
#     -----+-------+-------+-------+-------
#     P    | 1     | 1     | <-    | P
#     P    | blanc | 1     | reste | F
#     -----+-------+-------+-------+-------
#     A    | 1     | 1     | <-    | A
#     A    | blanc | 0     | reste | F
#     -----+-------+-------+-------+-------
#
# Notez que nous n'avons pas inclus de règles pour (P, 0) et
# (A, 0) car ces situations ne doivent jamais se produire : la
# machine faisant demi-tour au premier 0 rencontré elle ne trouvera
# jamais un 0 sur son chemin retour.

# La stratégie de cette machine peut faire penser au code de la
# fonction Python suivante.

def chercher_zero(entree)
    for x in entree:
        if x == 0:
            return True
    return False


### Exercice 6

# Il n'est pas envisageable de partir directement à gauche ou à droite
# jusqu'à rencontrer le 0, car on pourrait alors ne jamais s'arrêter
# si l'on choisissait la mauvaise direction. On peut à la place aller
# alternativement vers la gauche ou la droite, à chaque fois d'une
# case plus loin que la précédente, en laissant des marques * dans les
# cases déjà explorées. On utilise pour cela deux états D
# (exploration vers la droite) et G (exploration vers la gauche) en
# plus de l'état final F. On peut choisir l'état initial
# arbitrairement entre G et D.
#
#     état | lu    | écrit | dépl. | suiv
#     -----+-------+-------+-------+-------
#     D    | 0     | 0     | reste | F
#     D    | *     | *     | ->    | D
#     D    | blanc | *     | <-    | G
#     -----+-------+-------+-------+-------
#     G    | 0     | 0     | reste | F
#     G    | *     | *     | <-    | G
#     G    | blanc | *     | ->    | D
#     -----+-------+-------+-------+-------
#
# Pour nettoyer les marques il faut en plus, une fois le 0 trouvé,
# repartir en sens arrière jusqu'à un blanc, puis revenir. Cela
# demande au total quatre états supplémentaires (aller et retour, avec
# le 0 trouvé à gauche ou à droite de la position de départ).