---
# System prepended metadata

title: TP Prolog - s05 - ISC IL 3a
tags: [prolog]

---

###### tags: `prolog`

# TP Prolog - s05 - ISC IL 3a
## Baudin Valentin et Braillard Simon

## Exercice 1
### a(Z)
```raw=
(2)
(3)
(5)
(8)
```
### b(Z)
```raw=
(2)
```
### c(Z)
```raw=
(2)
(3)
(5)
```
### d(Z)
```raw=
(2)
```
### e(Z)
```raw=
no
```
### f(Z)
```raw=
(8)
```
### g(Z, W)
```raw=
(2, 4)
```
### h(Z, W)
```raw=
(2, 4)
(2, 2)
```
### i(Z, W)
```raw=
(2, 4) 
(3, 4)
(5, 4)
```

## Exercice 2
```prolog=
myTrue.

myFail :- myFail(a).
myFail(b).
```

### Output
```
| ?- > myTrue .


yes
| ?- > myFail .


no
| ?- 
```

## Exercice 3
### a) Après un not( ...(...,E,...)), l'inconnue risque-t-elle d'être instanciée ? Autrement dit, comment le prédicat t suivant peut-il donner un succès ?
```prolog=
t :- var(E),
     not(p(E)),
     nonvar(E).
```
Pour avoir un succès sur le `not(p(E))`, il faut que `p(E)` soit un échec. Cependant, lorsqu'un prédicat échoue, les variables sont désinstanciées. Par conséquent, `not(p(E))` et `nonvar(E)` ne peuvent pas être un succès en même temps.

```
| ?- > t .


no
| ?- 
```

### b) La question owns(_,a) engendre un arbre infini... Que donne not(owns(_, a)) ? Et si on change l'ordre de déclaration des 2 règles owns ?
```
| ?- > not(owns(_, a)).


no
| ?- 
```

Si on inverse les deux règles, `not(owns(_, a))` génére un stack overflow.

```!
| ?- > not(owns(_, a)).

Fatal Error: local stack overflow (size: 16384 Kb, reached: 16384 Kb, environment variable used: LOCALSZ)

Process finished with exit code 1
```

### c) Dans le prédicat owns, il y a 3 endroits où on peut placer un Cut. Lesquels seraient des Cut "verts" ?
Le seul cut vert est le 2ème cut.
```prolog=
owns([X|_Xs], X) :- !.
owns([_Y|Ys], X) :- !, owns(Ys, X), !.
```

## Exercie 4
### Expliquer si les 4 versions suivantes sont fonctionnellement équivalentes au prédicat owns/2 ci-dessus : 
`owns1` teste si chaque élément de la liste est égal l'élément cherché. Si cela retourne un échec, à le même fonctionnement que `owns`, mais avec un ordre des solutions différantes.

`owns2` test chaque possibilité de liste qui contient l'élément et la compare avec la liste passée en entrée.

`owns3` a la même fonctionnalité.

`owns4` fonctionne presque la même chose, sauf que si l'élément recherché est à la 1ère position du tableau. Il y aura un success uniquement si le tableau contient 1 ou 2 élément.

### Donner la complexité en temps de calcul du prédicat owns3 (indication : commencer par discuter la hauteur de l'arbre de preuve pour des questions owns3([a,a,a,...,a],b) ).

`O(n)`

## Exercice 5
### Quelle est la différence entre le prédicat nth9/3 et sa version prédéfinie nth/3 ?
`nth9` compte l'index depuis la fin du tableau.
```
| ?- > nth9(X, [1,2,3,4,5], 2).


X = 4 ? > 


yes
| ?- > nth(X, [1,2,3,4,5], 2).


X = 2 ? > 


yes
| ?- 
```

### Que fait le prédicat z/2 ? Fonctionne-t-il "dans l'autre sens" ?
Il exécute l'algorithme de compression Lempel-ziv. Il effectue aussi la décompression.
```
| ?- > z([c,a,b,c,b], Zs).


Zs = [1,c,1,a,1,b,2,b]

yes
| ?- > 
> z(Zs, [1,c,1,a,1,b,2,b]).


Zs = [c,a,b,c,b]

yes
| ?- 
```