###### 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
| ?-
```
Google Drive
Gist
Clipboard
Sign in with Wallet
