# TD 2 -- Introduction à l’Intelligence Artificielle

###### tags `TD` `M1 S1` `IA`
[Sommaire](/IAsAMpizSpawifCj1gZ__g)
> [time= 21 sept 2020]

[TOC]

## Exercice 1
### Enoncé
Voici le résultat de la commande `ls -R` (listage récursif de répertoire) sur le répertoire
courant

$ ls -R

.:
mon_repertoire rep tata toto tutu

./mon_repertoire: 
directory loto lulu

./mon_repertoire/directory: 
auto moto velo

./rep:
aaa chato gato rado rato

./rep/aaa:
fado java torot

On veut connaître la liste des fichiers (au sens large) de cette arborescence dont le nom contient la chaîne "to".
1. Donnez la réponse fournie par une recherche en largeur d’abord.
2. Donnez la réponse fournie par une recherche en profondeur d’abord.
3. Donnez la réponse fournie par une recherche en profondeur itérative, en commençant par la pro- fondeur 2.

### Réponse
#### 1)
- ./mon_repertoire
- ./toto
- ./mon_repertoire/directory
- ./mon_repertoire/loto
- ./rep/chato
- ./rep/gato
- ./rep/rado
- ./rep/rato
- ./mon_repertoire/directory/auto
- ./mon_repertoire/directory/moto
- ./rep/aaa/torot
#### 2)
- ./mon_repertoire
- ./mon_repertoire/directory
- ./mon_repertoire/directory/auto
- ./mon_repertoire/directory/moto
- ./mon_repertoire/directory/loto
- ./rep/aaa/torot
- ./rep/chato
- ./rep/gato
- ./rep/rado
- ./rep/rato

#### 3)
p2:
- ./mon_repertoire
- ./mon_repertoire/directory
- ./rep/chato
- ./rep/gato
- ./rep/rado
- ./rep/rato
---
p3:
- ./mon_repertoire
- ./mon_repertoire/directory
- ./mon_repertoire/directory/auto
- ./mon_repertoire/directory/moto
- ./mon_repertoire/directory/loto
- ./rep/aaa/torot
- ./rep/chato
- ./rep/gato
- ./rep/rado
- ./rep/rato

## Exercice 2
### Enoncé
On est dans la situation de départ de la figure 1 : sur une table sont posés trois cubes, les cubes A et B à même la table et le cube C sur le cube A. On a trois “abscisses” possibles pour les cubes et celles-ci sont indifférenciées : la situation de la figure 2, par exemple, est équivalente à celle de la figure 1.

On veut atteindre la situation d’arrivée présentée par la figure 3. On a juste le droit de soulever un cube qui n’est pas recouvert par un autre cube et de le reposer ailleurs.
1. Dessinez le graphe d’états. Quel est sa particularité ?
2. Proposez une solution avec l’algorithme de recherche en profondeur itérative, en commençant par la profondeur 4.

### Réponse
#### 1)

Digraph G {
140438326294320 [label="('', 'B', 'CA')"]

140438326294320 -> 140438326294320 [label="move B"]
140438326294320 -> 140438326413392 [label="move B"]
140438326294320 -> 140438326411952 [label="move C", color="blue"]
140438326294320 -> 140438326413968 [label="move C"]
#--------------------------------------------------#
140438326413968 [label="('', 'A', 'CB')"]

140438326413968 -> 140438326413968 [label="move A"]
140438326413968 -> 140438326202032 [label="move A"]
140438326413968 -> 140438326411952 [label="move C"]
140438326413968 -> 140438326294320 [label="move C"]
#--------------------------------------------------#
140438326202032 [label="('', '', 'ACB')"]

140438326202032 -> 140438326413968 [label="move A"]
140438326202032 -> 140438326413968 [label="move A"]
#--------------------------------------------------#
140438326411952 [label="('A', 'B', 'C')"]

140438326411952 -> 140438326413536 [label="move A"]
140438326411952 -> 140438326200976 [label="move A"]
140438326411952 -> 140438326201984 [label="move B"]
140438326411952 -> 140438326201792 [label="move B", color="blue"]
140438326411952 -> 140438326294320 [label="move C"]
140438326411952 -> 140438326413968 [label="move C"]
#--------------------------------------------------#
140438326201792 [label="('', 'A', 'BC')"]

140438326201792 -> 140438326201792 [label="move A"]
140438326201792 -> 140438326296528 [label="move A", color="blue"]
140438326201792 -> 140438326411952 [label="move B"]
140438326201792 -> 140438326201984 [label="move B"]
#--------------------------------------------------#
140438326296528 [label="('', '', 'ABC')"]

140438326296528 -> 140438326201792 [label="move A"]
140438326296528 -> 140438326201792 [label="move A"]
#--------------------------------------------------#
140438326201984 [label="('', 'BA', 'C')"]

140438326201984 -> 140438326411952 [label="move B"]
140438326201984 -> 140438326201792 [label="move B"]
140438326201984 -> 140438326201984 [label="move C"]
140438326201984 -> 140438326201312 [label="move C"]
#--------------------------------------------------#
140438326201312 [label="('', '', 'CBA')"]

140438326201312 -> 140438326201984 [label="move C"]
140438326201312 -> 140438326201984 [label="move C"]
#--------------------------------------------------#
140438326200976 [label="('', 'AC', 'B')"]

140438326200976 -> 140438326411952 [label="move A"]
140438326200976 -> 140438326413536 [label="move A"]
140438326200976 -> 140438326200976 [label="move B"]
140438326200976 -> 140438327541920 [label="move B"]
#--------------------------------------------------#
140438327541920 [label="('', '', 'BAC')"]

140438327541920 -> 140438326200976 [label="move B"]
140438327541920 -> 140438326200976 [label="move B"]
#--------------------------------------------------#
140438326413536 [label="('', 'AB', 'C')"]

140438326413536 -> 140438326411952 [label="move A"]
140438326413536 -> 140438326200976 [label="move A"]
140438326413536 -> 140438326413536 [label="move C"]
140438326413536 -> 140438327545520 [label="move C"]
#--------------------------------------------------#
140438327545520 [label="('', '', 'CAB')"]

140438327545520 -> 140438326413536 [label="move C"]
140438327545520 -> 140438326413536 [label="move C"]
#--------------------------------------------------#
140438326413392 [label="('', '', 'BCA')"]

140438326413392 -> 140438326294320 [label="move B"]
140438326413392 -> 140438326294320 [label="move B"]
#--------------------------------------------------#
140438326294320 [label="start=('', 'B', 'CA')", color="green"]
140438326296528 [label="end=('', '', 'ABC')", color="red"]
}

attention il y a des erreur dans mon graph.

Ce graph n'est en faite pas un graph dirigé.
On peut faire ne peut donc pas faire un parcour en largeur

## Exercice 3
### Enoncer
Résoudre le problème des 6 reines par l’algorithme de recherche en profondeur d’abord (le problème consiste à placer 6 reines sur un échiquier 6 × 6 sans que deux d’entre elles ne se menacent mutuellement), en tenant compte du fait qu’il y a exactement une reine par colonne.

## réponse
faire un arbre avec toute les permutation