QCM : Recherche non informée en IA (10 questions)

Questions et réponses du QCM

1. Un robot doit résoudre un labyrinthe sans connaître à l’avance l’itinéraire gagnant. Que fait-il dans le cadre d’une recherche en IA ?

Il choisit une action sans rechercher de solution au problème.
Il explore des états et des actions possibles pour trouver une solution.
Il décrit la situation actuelle sans examiner les actions possibles.
Il exécute un itinéraire fixé avant de commencer le problème.

Il explore des états et des actions possibles pour trouver une solution.

Explication

La recherche en IA explore des états et des actions possibles afin de trouver une solution. Exécuter un itinéraire fixé confond recherche et plan préétabli, décrire la situation relève de la représentation d’un état, et choisir sans explorer omet le processus de recherche.

2. Dans un problème, deux chemins différents conduisent au même état. Quelle représentation peut montrer cet état plusieurs fois, une fois pour chaque chemin exploré ?

L’arbre de recherche, qui représente les chemins explorés.
Le modèle de transition, qui décrit l’état obtenu après une action.
Le graphe d’états, qui représente les états et leurs transitions.
L’espace d’états, qui rassemble les états possibles du problème.

L’arbre de recherche, qui représente les chemins explorés.

Explication

L’arbre de recherche représente les chemins explorés et peut contenir plusieurs occurrences d’un même état lorsque différents chemins y mènent. Le graphe d’états représente plutôt les états et transitions possibles; le modèle de transition décrit l’effet d’une action, et l’espace d’états rassemble les états possibles.

3. Un programme doit explorer les nœuds les plus récemment ajoutés à sa frontière. Quelle structure de données convient à cette stratégie ?

Une file FIFO, utilisée pour la recherche en largeur.
Une file FIFO, utilisée pour sélectionner le coût cumulé minimal.
Une file de priorité, utilisée pour la recherche à coût uniforme.
Une pile LIFO, utilisée pour la recherche en profondeur.

Une pile LIFO, utilisée pour la recherche en profondeur.

Explication

Une pile LIFO retire en premier le nœud ajouté le plus récemment, ce qui correspond à la recherche en profondeur. FIFO privilégie les nœuds les plus anciens, tandis qu’une file de priorité ordonne les nœuds selon leur coût pour la recherche à coût uniforme.

4. Dans un réseau de chemins, un algorithme garantit qu’il trouvera une solution si elle existe, mais ne garantit pas que son coût soit minimal. Quelle propriété possède-t-il ?

L’optimalité, sans garantie de complétude.
La complétude et l’optimalité simultanément.
Ni la complétude ni l’optimalité.
La complétude, sans garantie d’optimalité.

La complétude, sans garantie d’optimalité.

Explication

La complétude garantit qu’une solution sera trouvée lorsqu’elle existe, sous les hypothèses requises; l’optimalité garantit que la solution a un coût minimal. Ici, la garantie de trouver une solution établit la complétude, mais l’absence de garantie sur le coût exclut l’optimalité.

5. Que désigne la recherche en largeur dans un arbre ou un graphe de recherche ?

Une exploration des nœuds par niveaux, en ordre de profondeur croissante
Une exploration qui développe le nœud au coût cumulé le plus faible
Une exploration qui choisit les nœuds selon leur ordre alphabétique
Une exploration qui poursuit chaque branche aussi profondément que possible

Une exploration des nœuds par niveaux, en ordre de profondeur croissante

Explication

La recherche en largeur examine d’abord les nœuds les moins profonds, niveau par niveau. Le choix du nœud au coût cumulé minimal caractérise plutôt la recherche à coût uniforme.

6. Dans un graphe fini parcouru par DFS avec mémorisation des sommets visités, quelle est sa complexité temporelle ?

O(V)O(V), où VV désigne le nombre de sommets
O(bm)O(b^m), où bb désigne le branchement et mm la profondeur maximale
O(bd+1)O(b^{d+1}), où bb désigne le branchement et dd la profondeur de la solution la moins profonde
O(V+E)O(V+E), où VV désigne les sommets et EE les arêtes

$$O(V+E)$$, où $$V$$ désigne les sommets et $$E$$ les arêtes

Explication

Avec la mémorisation des sommets visités dans un graphe fini, DFS examine les sommets et les arêtes en temps O(V+E)O(V+E). La complexité O(bm)O(b^m) concerne l’analyse de DFS dans un arbre de recherche classique, et non le parcours du graphe fini décrit ici.

7. Quel rôle joue la file de priorité dans la recherche à coût uniforme ?

Développer en priorité le nœud ajouté le plus récemment
Retirer les nœuds dans l’ordre où ils ont été découverts
Sélectionner le nœud situé au niveau le moins profond
Sélectionner pour développement le nœud dont le coût cumulé est le plus faible

Sélectionner pour développement le nœud dont le coût cumulé est le plus faible

Explication

La file de priorité sert à choisir le nœud dont le coût cumulé depuis le départ est minimal. Une file FIFO, contrairement à cette structure, retire les nœuds selon leur ordre d’arrivée.

8. En quoi BFS et UCS diffèrent-ils lorsqu’ils recherchent un itinéraire dans un réseau où les liaisons ont des coûts différents ?

BFS privilégie le chemin avec le moins d’arêtes, tandis qu'UCS choisit la destination la plus proche en nombre de sauts.
BFS privilégie le chemin avec le moins d’arêtes, tandis qu'UCS privilégie celui dont le coût cumulé est minimal.
BFS explore les branches en profondeur, tandis qu'UCS privilégie le chemin avec le moins d’arêtes.
BFS privilégie le coût cumulé minimal, tandis qu'UCS privilégie le chemin avec le moins d’arêtes.

BFS privilégie le chemin avec le moins d’arêtes, tandis qu'UCS privilégie celui dont le coût cumulé est minimal.

Explication

BFS minimise le nombre d’arêtes, alors qu'UCS sélectionne les nœuds selon le coût cumulé, ce qui permet de tenir compte de coûts de liaison différents. L’idée qu'UCS minimise le nombre de sauts confond son critère avec celui de BFS.

9. Dans un problème de recherche en IA, quel élément décrit la situation pertinente à un instant donné ?

Le modèle de transition
L’action
Le coût du chemin
L’état

L’état

Explication

L’état représente la situation pertinente du problème à un instant donné. L’action désigne plutôt une opération qui permet de passer d’un état à un autre.

10. Si l’on remplace une file FIFO par une pile LIFO pour gérer la frontière, quelle conséquence cela a-t-il sur la stratégie de recherche ?

Les nœuds les plus récemment découverts sont développés en premier, ce qui favorise l’exploration en profondeur.
Les nœuds ayant le coût cumulé le plus faible sont développés en premier, ce qui favorise les chemins les moins coûteux.
Les nœuds déjà développés sont conservés dans la frontière, ce qui empêche les états répétés.
Les nœuds les moins profonds sont développés en premier, ce qui favorise l’exploration niveau par niveau.

Les nœuds les plus récemment découverts sont développés en premier, ce qui favorise l’exploration en profondeur.

Explication

Une pile LIFO retire en premier le dernier nœud ajouté, ce qui conduit à privilégier une exploration en profondeur. Le choix du coût cumulé minimal caractérise plutôt une file de priorité, et non une pile.

Révisez avec les flashcards

Mémorisez les réponses avec 10 flashcards sur Recherche non informée en IA.

Que cherche à trouver la recherche en IA en explorant des états et des actions possibles ?

Une solution à un problème.

Quels éléments comprend un problème de recherche classique ?

Un état initial, des actions, un modèle de transition, un test d’objectif et un coût du chemin.

Que contient la frontière dans un algorithme de recherche ?

Les nœuds découverts mais pas encore développés.

Voir les flashcards →

Approfondir avec la fiche

Consultez la fiche de révision complète sur Recherche non informée en IA.

Voir la fiche →

Cours similaires

Crée tes propres QCM

Importe ton cours et l'IA génère des QCM avec corrections en 30 secondes.

Générateur de QCM