Cours 1 - rappel

name: inverse
layout: true
class: center, middle, inverse
---

# Introduction IA - CM 1
## Inès de Courchelle
## 2023-2024

![image](../img/CY-tech.png)

---
layout: false
# Lets go
## Objectifs

- Connaître la recherche aveugle et la recherche guidée
- Appliquer un algorithme A*

---
# Définition IA
.otro-blockquote[reproduire des comportements liés aux humains, tels que le raisonnement, la planification et la créativité. CNIL]

---
# Historique
## 1940
- Rorbert Wiener, pionnier de la cybernétique,
- « théorie entière de la commande et de la communication, aussi bien chez l’animal que dans la machine ».
-  Warren McCulloch et Walter Pitts dès 1943 un premier modèle mathématique et informatique du neurone biologique (neurone formel) avait été mis au point par.

## 1950
John Von Neumann et Alan Turing : transition entre les calculateurs à la logique décimale du XIXème siècle et des machines à la logique binaire
## 1956

conférence de Dartmouth - Le terme IA est inventé

---
# Historique
## 1960s
Terry Winograd SHRDLU (monde de blocs)
## 1970s
Systèmes experts : Mycin, Dendral
<img src="img/system.webp" width=400>

---
# Historique
## 1988
Puissance 4 résolu par Victor Allis et James Allen (indépendamment)
## 1997
Deep Blue bat Kasparov
## 2002
invention d’Arimaa, conçu pour être compliqué pour un ordinateur

---
# Historique
## Les assistants
#### 2007 - Siri
<img src="img/siri.jpeg" width=50>

#### 2014 - Alexa
<img src="img/alexa.png" width=100>

#### 2022 - Chat GPT
<img src="img/chatgt.png" width=50>
---
# Historique
## Années 2000
- 2015 : Alphago (google Deepmind) bat Fan Hui 5-0
- 2016 : Alphago - Lee Sedol 4-1
- 2016 : Google annonce la traduction automatique quasi parfaite GNMT
- 2017 : Alphago bat Ke Jie 3-0
- 2017 : Alphago Zero apprend à jouer sans expertise humaine
- 2017 : Humans are still better than AI at Starcraft - for now
- 2017 : Apple : iphone X, reconnaissance de visage par réseau de neurones
- 2018 : Uber : premier accident mortel impliquant une voiture autonome
- 2018 : FDA autorise le diagnostic autonome de la rétinopathie
- 2019 : Une IA de Starcraft bat les meilleurs joueurs mondiaux
- 2020 : Alphafold (une IA de Deepmind) replie les protéines
- 2020 : Une IA du MIT reconnaît le COVID

---
# Actualités
## Alexandre Astier
<a href="https://www.huffingtonpost.fr/culture/article/pour-alexandre-astier-l-ia-et-chatgpt-ne-menacent-pas-fondamentalement-la-creation-artistique_217987.html" target="_blank">Article huffingtonpost </a>

## Sam Altman
<a href="https://www.radiofrance.fr/franceculture/podcasts/un-monde-connecte/le-fondateur-d-openai-annonce-plethore-d-innovations-6420399" target="_blank">Article huffingtonpost </a>

## François Saltiel
<a href="https://www.radiofrance.fr/franceculture/podcasts/le-meilleur-des-mondes/intelligence-et-genre-comment-repenser-l-ia-avec-alan-turing-5873896" target="_blank">Repenser l'IA grâce à Turing </a>

---
# [Rappel] Généralités sur les arbres
## Qu'est ce qu'un arbre ?
<img src="img/arbre.webp" width=200>

## De manière générale
- Structure de stockage des fichiers sur un disque dur
- Expression formelle de calculs
- Arbres de décision
- ...

---
# Généralités sur les arbres
## Des exemples
<img src="img/exempleRG.jpg" width=350>
---
# Généralités sur les arbres
## En Vrai
<img src="img/lol.jpg" width=125>

## En Info
<img src="img/lol3.jpg" width=125>

---
# Définition d'un arbre
## Définition (Théorie des graphes)
.otro-blockquote[Un arbre est un graphe (orienté ou non), connexe et sans cycle.]
## Définition (Récursive)
.otro-blockquote[Un arbre est un arbre qui possède des liens ou des pointeurs vers d'autres arbres.]

---
# Le vocabulaire
## Un arc
<img src="img/arc.png" width=400>

<img src="https://c.tenor.com/HCtlf7gyqDwAAAAd/robin-hood-shoot.gif" width=100>
---
# Le vocabulaire
## Un noeud
<img src="img/noeud.png" width=400>

---
# Le vocabulaire
## Noeud externe ou feuille
<img src="img/feuille.png" width=400>

C'est un noeud qui n'a pas d'arc sortant !

---
# Le vocabulaire
## Noeud interne
<img src="img/interne.png" width=400>

C'est un noeud qui n'est pas externe !

---
# Le vocabulaire
## La racine
<img src="img/racine.png" width=400>

Tout en haut quoi !

---
# Le vocabulaire
## Noeud frères ou soeurs
<img src="img/frere.png" width=400>

---
# Le vocabulaire
<img src="img/ancetre.png" width=400>
#### Noeud ancêtre
1 est l'ancêtre de 9
#### Noeud descendant
9 est le descendant de 1

---
# Le vocabulaire
<img src="img/arbreEnracine.png" width=400>
#### La taille
C'est le nombre de noeud dans l'arbre (ici de 10)
####  Le nombre de feuille
C'est le nombre de feuille ou noeud externe (ici de 6)

---
# Le vocabulaire
<img src="img/noeudDegre.png" width=400>

#### Le degré d'un noeud
- C'est le nombre de descendants d'un noeud.
- Ce n'est pas tous les descendants, mais juste les fils (descendants du 1er niveau, mais pas encore dessous).

#### Le degré d'un arbre
C'est le plus grand des degrés de ses noeuds (ici de 5)

---
# Le vocabulaire
<img src="img/profondeurArbre.png" width=400>

#### Profondeur d'un noeud
c’est la distance du chemin qui relie la racine au nœud.
#### La hauteur
c’est la profondeur maximale de ses nœuds (ici de 2)

---
# Le vocabulaire
## Le cheminement
#### Longueur
La longueur de cheminement d'un arbre correspond à la somme des hauteurs de chacun des noeuds.

#### Externe
La longueur de cheminement externe d'un arbre correspond à la somme des hauteurs de chacune des feuilles.

#### Interne
La longueur de cheminement interne d'un arbre correspond à la somme des hauteurs des nœuds internes de l'arbre.

---
# Le vocabulaire
## Le cheminement
.pull-left[
- Longueur de cheminement (LC) => 15
- Longueur de cheminement externe (LCE) => 12
- Longueur de cheminement interne (LCI) => 3
]
.pull-right[
<img src="img/cheminement.png" width=200>
]

---
# Recherche aveugle
## Définition
Recherche dans laquelle aucune heuristique n’est disponible pour distinguer un chemin de recherche.
Elle s'oppose à la recherche guidée :  Il y a des heuristiques pour guider les choix, la recherche aveugle n'utilise aucune heuristique.

## En profondeur
.otro-blockquote[Si l'arbre n'est pas vide, le parcours de l'un des deux sous-arbres est terminé avant que ne commence celui de l'autre. On explore jusqu’au bout une branche pour passer à la suivante (on va vers les fils avant d'aller vers les frères)]

---
# Recherche aveugle
## En Largeur
.otro-blockquote[On explore les noeuds un par un sur un même niveau. On passe ensuite sur le niveau suivant, et ainsi de suite (on va vers les frères avant de parcourir les fils)]

---
# Recherche
# Parcours en profondeur
## Type Préfixe
- Chaque noeud est visité avant leur fils
- La racine est traitée avant les appels récursifs sur les sous-arbres gauche et droit

---
# Parcours en profondeur
## Type Préfixe
<img src="img/exempleGraph.png" width=500>

[0,1,2,7,3,4,5,8,9,6,10,12,13,15,14,16]

---
# Parcours en profondeur
## Type Infixe
- On visite chaque noeud après son fils à gauche et avant son fils à droite
- La racine est traitée entre les appels sur les sous-arbres gauches et droits
- .underR[Attention] : Le type infixe n'est que pour les arbres binaires, alors que le préfixe et postfixe peut être pour tous les types d'arbres

---
# Parcours en profondeur
## Type Infixe
<img src="img/exempleGraph.png" width=500>

[7,2,1,4,3,5,8,0,12,10,13,6,9,14,15,16]

---
# Parcours en profondeur
## Type Postfixe (ou suffixe)
- on visite chaque noeud après avoir visité chacun de ses fils
- la racine est traitée après les appels récursifs sur les sous-arbres gauche et droit

---
# Parcours en profondeur
## Type Postfixe (ou suffixe)
<img src="img/exempleGraph.png" width=500>

[7,2,4,8,5,3,1,12,13,10,6,14,16,15,9,0]

---
# Parcours en largeur
## Définition
- On visite l'arbre niveau par niveau
- Les nœuds de niveau 0 sont sont d'abord parcourus puis les nœuds de niveau 1 et ainsi de suite
- Dans chaque niveau, les nœuds sont parcourus de la gauche vers la droite
<img src="img/exempleGraph.png" width=450>

---
# Parcours en largeur
<img src="img/exempleGraph.png" width=500>

[0,1,9,2,3,6,15,7,4,5,10,14,16,8,12,13]

---
# Exemple d'utilisation
## Recherche d'un élément dans un arbre
Pour trouver un élément spécifique, vous pouvez utiliser une recherche en profondeur pour parcourir l'arbre et comparer l'élément recherché avec les nœuds.

## Résolution de jeux
Dans des jeux comme les échecs, les algorithmes de recherche aveugle, tels que la recherche en profondeur limitée ou la recherche en largeur, sont utilisés pour explorer les différentes combinaisons de mouvements possibles.

---
# Exemple d'utilisation
## Navigation sur un site web
Lorsqu'un moteur de recherche web explore et indexe les pages web, il utilise souvent des algorithmes de recherche en profondeur ou en largeur pour parcourir les liens entre les pages du site.

## Trouver le chemin le plus court dans un graphe
Les algorithmes de recherche en largeur (comme l'algorithme de Dijkstra) sont utilisés pour trouver le chemin le plus court entre deux nœuds dans un graphe pondéré.

## Résolution de labyrinthes
La recherche en profondeur et la recherche en largeur peuvent être utilisées pour résoudre des labyrinthes en trouvant un chemin à partir du point de départ jusqu'à la sortie.

---
# Cependant
## Problèmatique
Ce type de recherche es qualifié d'aveugle car on visite tout les noeuds de l'arbres
<img src="https://media.tenor.com/XQLVLptLIBEAAAAd/maes-b-lost-in-a-field.gif" width=200>

---
# Recherche guidée
## Qu'est ce que c'est ?
C'est une méthode de recherche qui utilise des informations supplémentaires pour orienter la recherche vers un objectif ou une solution de manière plus efficace que la recherche aveugle.

## Quand ?
- Systèmes de menu : avec des catégories et sous catégories
- Support de client en ligne pour diagnostiquer un problème
- ...

---
# Exemple de problème
## Robotique (Bloc)
Trouver une succession d'étapes (un plan) pour qu'un robot réarrange une pile de blocs. Le robot ne peut bouger qu'une pile de blocs à la fois. Un bloc ne peut être déplacé que s'il est au sommet d'une pile. Il peut alors être déplacé sur la table (nouvelle pile), ou sur une autre pile. L'objectif est de trouver une séquence de déplacements entre la situation initiale et une situation finale.

## Jeu (Taquin)
Résoudre un puzzle de 8 cases (jeu à un joueur). Un puzzle de 8 cases est constitué de 8 tuiles glissantes numérotées de 1 à 8, placées dans un tableau 3*3. Une des cases est donc vide, et chaque tuile adjacente à cette case vide peut y glisser, laissant une nouvelle case vide. La situation finale correspond à un arrangement particulier des tuiles dans le tableau.

---
# Modélisation informatique
## Robotique (Bloc)
#### Structure de données
liste de piles
#### Voisinage
déplacement d'un sommet de pile

## Jeu (Taquin)
####  Structure de données
liste ordonnée de coordonnées (vide,1,...,n)
####  Voisinage
permutation de la case vide avec une case voisine (distance de Manhattan = 1)
\\[ d_{Manhattan}=(x1−x2)+(y1−y2) \\]

---
# Algorithme A*
## Définition
L'algorithme A* est une technique de recherche guidée.
## Quand ?
Il est utiliser pour rechercher un chemin.
## Comment ?
Il utilise une fonction d'évaluation qui combine le coût actuel pour atteindre un nœud avec une estimation du coût restant pour atteindre l'objectif.

---
# Algorithme A*
## Principe

- Évaluer chaque nœud exploré en utilisant deux valeurs :
    - **Coût réel** pour atteindre ce nœud depuis le nœud de départ (coût g)
    - **Coût heuristique** estimation du coût restant pour atteindre l'objectif à partir de ce nœud
- L'algorithme maintient une "liste ouverte" de nœuds à explorer et sélectionne le prochain nœud à explorer en fonction d'une combinaison de ces deux coûts.

## Objectif
Minimiser la valeur f(n) = g(n) + h(n) pour le nœud en cours d'examen.

---
# Algorithme A*
## Différence avec Dijkstra
- L’algorithme de Dijkstra permet de prendre en compte des arêtes de poids différents (alors que pour le parcours en largeur, elles ont toutes le même).
- A* permet de prendre en compte une évaluation de la distance qui reste à parcourir alors que l’algorithme de Dijkstra ne prend en compte que la distance jusqu’au sommet considéré.
- A* est un algorithme de branch and bound (Un algorithme par séparation et évaluation)

---
# Algorithme A*
## Fonctions spécifiques
<center>
<a href="algoA.c" target="_blank" download> <img src="img/fichier.png" width=150>ALGO générique</a>
</center>

---
# Quelques liens utiles
## Dijkstra’s algorithm
<iframe width="560" height="315" src="https://www.youtube.com/embed/GazC3A4OQTE?si=6uTnkhZjUchxLr4M" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>

---
# Quelques liens utiles
## A* (A star) search algorithm
<iframe width="560" height="315" src="https://www.youtube.com/embed/ySN5Wnu88nE?si=yPNTbta0A8PvOk5g" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>

---
# Quelques liens utiles
## Maze solving
<iframe width="560" height="315" src="https://www.youtube.com/embed/rop0W4QDOUI?si=sRfZsMIKFk7zrSWq" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>