IFT-2003 / Automne 2026 / Techniques de recherche (2/2)

Mini-test — Techniques de recherche (2/2)

Exercices d’entraînement créés pour le portail. Aucun questionnaire officiel. Banque v3.

12 questions. Un point par réponse automatique correcte; aucun crédit partiel. Les autoévaluations sont comptées séparément. Les corrigés apparaissent après chaque réponse; ce mini-test sert à apprendre.

Toute la banque

Aucune tentative commencée.

1. h compte les tuiles bien placées. Quel sens indique une amélioration ?

Compréhension · version 1

Hypothèses et règle de réponse

Exercice original du portail, distinct des évaluations officielles. Les données nécessaires à l’application sont fournies dans l’énoncé ou le passage précisément référencé.
Logique classique du premier ordre pour les preuves; les exemples Prolog sont analysés, sans interpréteur exécuté.

Une réponse exacte selon les données; aucune approximation ou convention implicite supplémentaire.

Corrigé — question 1

Le sens dépend de la définition : bien placées → croissant; mal placées ou coût restant → décroissant.

Variantes : Une réponse exacte selon les données; aucune approximation ou convention implicite supplémentaire.

Revoir la matière — 2.2 Sens de l’heuristique

2. Dans f=(1-w)g+wh, que produit w=0,5 ?

Compréhension · version 2

Hypothèses et règle de réponse

Exercice original du portail, distinct des évaluations officielles. Les données nécessaires à l’application sont fournies dans l’énoncé ou le passage précisément référencé.
Logique classique du premier ordre pour les preuves; les exemples Prolog sont analysés, sans interpréteur exécuté.

Une réponse exacte selon les données; aucune approximation ou convention implicite supplémentaire.

Corrigé — question 2

w=0 donne g (Dijkstra), w=1 donne h (meilleur d’abord). Un facteur positif commun préserve l’ordre, pas la valeur numérique.

Variantes : Une réponse exacte selon les données; aucune approximation ou convention implicite supplémentaire.

Revoir la matière — 5.4 Variante pondérée

3. Arcs S→A(3),S→B(1),B→A(1),A→G(3). h(S)=5,h(A)=0,h(B)=4,h(G)=0. A* retire d’abord A (f=3), puis B (f=5). Si A fermé est ignoré définitivement, quel coût sera rendu pour G ?

Application · version 1

Hypothèses et règle de réponse

Exercice original de transfert, distinct des évaluations officielles. Toutes les données du problème figurent dans l’énoncé.

Une réponse exacte sous les conventions de l’énoncé.

Corrigé — question 3

h est admissible : distances réelles S=5,A=3,B=4,G=0. Elle est incohérente sur B→A : 4>1+0. Ignorer l’amélioration de A laisse G à 6. Rouvrir A avec g=2 permet G à 5. Cet exemple précise la limite de la procédure du support.

Variantes : Une réponse exacte sous les conventions de l’énoncé.

Revoir la matière — 5.2 Admissibilité et optimalité

4. Distances exactes au but : d(A)=4,d(B)=2,d(G)=0. Quelle heuristique est admissible sur CES trois états ?

Application · version 1

Hypothèses et règle de réponse

Exercice original de transfert, distinct des évaluations officielles. Toutes les données du problème figurent dans l’énoncé.

Une réponse exacte sous les conventions de l’énoncé.

Corrigé — question 4

L’admissibilité exige h(n)≤d(n) partout. Le deuxième choix surestime A; le troisième surestime B. Ce tableau seul ne permet pas de vérifier la cohérence, qui dépend aussi des arcs.

Variantes : Une réponse exacte sous les conventions de l’énoncé.

Revoir la matière — 5.2 Admissibilité et optimalité

5. Dans f=(1-w)g+wh, que donnent les deux extrêmes w=0 et w=1 ?

Application · version 1

Hypothèses et règle de réponse

Exercice original de transfert, distinct des évaluations officielles. Toutes les données du problème figurent dans l’énoncé.

Une réponse exacte sous les conventions de l’énoncé.

Corrigé — question 5

Les coefficients sélectionnent g ou h aux extrêmes. À w=0,5, on obtient (g+h)/2 : même ordre que A* si le départage est identique, mais valeurs divisées par deux.

Variantes : Une réponse exacte sous les conventions de l’énoncé.

Revoir la matière — 5.4 Variante pondérée

6. Un nœud MAX est exploré avec β=5 hérité d’un ancêtre MIN. Son premier enfant vaut 6. Quelle décision est justifiée ?

Application · version 1

Hypothèses et règle de réponse

Exercice original de transfert, distinct des évaluations officielles. Toutes les données du problème figurent dans l’énoncé.

Une réponse exacte sous les conventions de l’énoncé.

Corrigé — question 6

Chez MAX, α devient au moins 6 et α≥β. La valeur exacte du sous-arbre peut rester inconnue, mais il ne sera pas préféré par l’ancêtre MIN disposant de 5.

Variantes : Une réponse exacte sous les conventions de l’énoncé.

Revoir la matière — 9.1 Bornes Revoir la matière — 9.2 Règles du cours

7. Un nœud MIN reçoit α=4. Après un enfant de valeur 3, on coupe. Que sait-on de la valeur exacte v du nœud ?

Application · version 1

Hypothèses et règle de réponse

Exercice original de transfert, distinct des évaluations officielles. Toutes les données du problème figurent dans l’énoncé.

Une réponse exacte sous les conventions de l’énoncé.

Corrigé — question 7

Une coupure peut fournir une borne plutôt que la valeur exacte de chaque nœud interne. La décision et la valeur racine Minimax sont conservées; le pire cas peut ne rien élaguer.

Variantes : Une réponse exacte sous les conventions de l’énoncé.

Revoir la matière — 9.1 Bornes Revoir la matière — 9.2 Règles du cours Revoir la matière — 9.4 Propriétés

8. Contrôle de coût des villes, arcs dirigés : v0→v3(2), v0→v2(4), v0→v1(3), v3→v2(1), v3→v4(1), v2→v4(3), v1→v5(7), v4→v6(4), v5→v6(4). h(v0..v6)=(9,2,2,5,2,3,0). Quel est le coût MINIMAL de v0 à v6, calculé sur les coûts d’arcs, sans additionner les heuristiques ? Entier, tolérance 0.

Application · version 1

Hypothèses et règle de réponse

Révision locale personnelle : données du maître et, pour les figures historiques, transcription contrôlée des PDF officiels locaux; aucune tentative d’évaluation officielle.
Toute convention ajoutée au support est annoncée dans l’énoncé. Les graphiques source ne sont pas reconstitués à partir de la seule trace.

Entier exact, unité et tolérance indiquées.

Corrigé — question 8

v0→v3→v4→v6 coûte 2+1+4=7. Le 14 du tableau est une accumulation erronée de priorités f; le coût g ne cumule que les arcs.

Variantes : Entier exact, unité et tolérance indiquées.

Revoir la matière — 5.3 Exemple des villes

9. Arbre historique P, enfants gauche→droite : P→Q,R,S; Q→T,U; R→V,W; S→X,Y; T→Z,A; U→B; V→C; W→D. h : P=10, Q=9, R=7, S=8, T=8, U=7, V=10, W=9, X=5, Y=0, Z=6, A=7, B=0, C=5, D=7. But h=0 au retrait, sans revisite. Tracer Hill-Climbing escarpé et meilleur d’abord; pour ce dernier, écrire OUVERTS après P,R,S et distinguer chemin/trace. Pour comparer A* sur ce même arbre, ajouter la convention explicite coût 1 par arc (les coûts ne sont pas donnés dans cet exercice officiel); donner ses priorités et contrôler l’admissibilité.

Application · version 1

Hypothèses et règle de réponse

Révision locale personnelle : données du maître et, pour les figures historiques, transcription contrôlée des PDF officiels locaux; aucune tentative d’évaluation officielle.
Toute convention ajoutée au support est annoncée dans l’énoncé. Les graphiques source ne sont pas reconstitués à partir de la seule trace.

Renommages uniformes et démonstrations équivalentes acceptés si toutes les étapes demandées sont justifiées.

Corrigé — question 9

Ce sont les valeurs et liens du PDF, désormais tous fournis. Le résultat du maître est vérifié par une simulation déterministe.

HC escarpé : P(10)→R(7), puis échec car V(10) et W(9) sont moins bons.
Meilleur d’abord après P : [R7,S8,Q9]; après R : [S8,Q9,W9,V10] (égalité gauche→droite); après S : [Y0,X5,Q9,W9,V10].
Retraits P,R,S,Y; succès. Parents de Y : Y←S←P, donc chemin P→S→Y, sans R.
La frontière conserve Q/S quand R est choisi. HC abandonne ces alternatives et ne peut reprendre S.
Avec les coûts unitaires ajoutés : A* retire aussi P,R,S,Y. Depuis P : R(g1,f8),S(g1,f9),Q(g1,f10); depuis S : Y(g2,f2),X(g2,f7). Chemin P→S→Y, coût2. h(P)=10>distance2 : l’heuristique de cet exercice de classement n’est pas admissible pour cette adaptation en coût.

Variantes : Renommages uniformes et démonstrations équivalentes acceptés si toutes les étapes demandées sont justifiées.

Revoir la matière — 10.1 Recherche heuristique

10. Labyrinthe historique, données complètes : Lignes y=0..5 de haut en bas, colonnes x=0..3 de gauche à droite : [A,B,C,D]; [Entrée,#,E,#]; [F,#,G,#]; [H,#,I,Sortie]; [J,#,K,L]; [M,N,O,P]. # est bloqué; N nomme la case non nommée du PDF. Chaque voisin orthogonal libre coûte 1. Départ Entrée=(0,1), but Sortie=(3,3). h=|3−x|+|3−y| (Manhattan, malgré le terme « vol d’oiseau » du PDF). A*, but au retrait, sans revisite, voisins haut,bas,droite,gauche; départage f puis h puis ordre d’insertion. Donner frontière et parents, trace, chemin/coût; justifier h, son admissibilité et sa cohérence; diagnostiquer le tableau officiel.

Application · version 1

Hypothèses et règle de réponse

Révision locale personnelle : données du maître et, pour les figures historiques, transcription contrôlée des PDF officiels locaux; aucune tentative d’évaluation officielle.
Toute convention ajoutée au support est annoncée dans l’énoncé. Les graphiques source ne sont pas reconstitués à partir de la seule trace.

Renommages uniformes et démonstrations équivalentes acceptés si toutes les étapes demandées sont justifiées.

Corrigé — question 10

Les coordonnées et les cases interdites viennent du dessin PDF. L’expression numérique 3 horizontalement +2 verticalement est Manhattan, et non une distance euclidienne.

Retraits Entrée,F,H,J,A,B,C,E,G,I,Sortie. Le départage f/h/ordre annoncé reproduit cet ordre; d’autres départages peuvent changer la trace sans changer le coût.
F : g1,h4,f5; H : g2,h3,f5; J : g3,h4,f7. A reste ouvert g1,h6,f7; M est ajouté après J en g4,h5,f9.
A→B→C donne g1,2,3; depuis C : E et D en g4,h3,f7. E→G→I donne g4,5,6 et h3,2,1.
Depuis I : Sortie g7,h0,f7 et K g7,h2,f9; M reste ouvert, D aussi, J reste fermé.
Chemin Entrée→A→B→C→E→G→I→Sortie, coût 7. Dijkstra confirme le minimum; Manhattan est admissible/cohérente sur les arcs unitaires.
Le tableau du solutionnaire omet M dans les lignes ultérieures et réintroduit J déjà fermé. Le portail conserve la frontière complète et ne répète pas ces erreurs.

Variantes : Renommages uniformes et démonstrations équivalentes acceptés si toutes les étapes demandées sont justifiées.

Revoir la matière — 10. Exercices et résultats Revoir la matière — 10.1 Recherche heuristique

11. Arbre historique E..J. A→B,C,D; B→E,F; C→G,H; D→I,J; E→K,L; F→M; G→P,Q; H→R,S; I→T,U; J→W,X. Les autres nœuds sont des feuilles. Valeurs terminales du point de vue de MAX : K=3, L=2, M=5, P=0, Q=2, R=7, S=8, T=2, U=1, W=4, X=5. Racine A MAX; B,C,D MIN; E,F,G,H,I,J MAX. Dessiner l’arbre, propager TOUTES les valeurs puis effectuer Alpha-Bêta gauche→droite, avec feuilles visitées, bornes et sous-arbres coupés.

Application · version 1

Hypothèses et règle de réponse

Révision locale personnelle : données du maître et, pour les figures historiques, transcription contrôlée des PDF officiels locaux; aucune tentative d’évaluation officielle.
Toute convention ajoutée au support est annoncée dans l’énoncé. Les graphiques source ne sont pas reconstitués à partir de la seule trace.

Renommages uniformes et démonstrations équivalentes acceptés si toutes les étapes demandées sont justifiées.

Corrigé — question 11

Les vraies feuilles du PDF sont fournies. H et J sont élagués dans ce parcours précis; les valeurs exactes 8 et 5 sont issues du calcul Minimax complet, pas des feuilles lues par Alpha-Bêta.

Valeurs MAX : E=max(3,2)=3,F=5,G=max(0,2)=2,H=max(7,8)=8,I=max(2,1)=2,J=max(4,5)=5.
Valeurs MIN : B=min(3,5)=3,C=min(2,8)=2,D=min(2,5)=2. A=max(3,2,2)=3; choisir B.
Alpha-Bêta visite K3,L2,M5 puis P0,Q2 : G rend 2, donc C coupe H (R7,S8) car β=2≤α=3.
I visite T2,U1 et rend 2 : D coupe J (W4,X5) pour la même raison. Feuilles visitées K,L,M,P,Q,T,U : 7 sur 11.
F ne possède qu’une feuille M; ne pas inventer un second enfant. Les minima et maxima restent alternés; la valeur racine 3 est inchangée.

Variantes : Renommages uniformes et démonstrations équivalentes acceptés si toutes les étapes demandées sont justifiées.

Revoir la matière — 10.2 Jeux avec adversaires

12. A* : g(n)=6 et h(n)=4. Quelle priorité f(n) ? (entier, tolérance 0)

Application · version 1

Hypothèses et règle de réponse

Exercice original du portail, distinct des évaluations officielles. Les données nécessaires à l’application sont fournies dans l’énoncé ou le passage précisément référencé.
Logique classique du premier ordre pour les preuves; les exemples Prolog sont analysés, sans interpréteur exécuté.

Une réponse exacte selon les données; aucune approximation ou convention implicite supplémentaire.

Corrigé — question 12

f=g+h=10. g est parcouru, h estime le reste; les deux doivent employer une échelle compatible.

Variantes : Une réponse exacte selon les données; aucune approximation ou convention implicite supplémentaire.

Revoir la matière — 5. A*

Récupérer manuellement les données locales

Copier séparément les données ci-dessous dans des fichiers texte avant de fermer la page ou de modifier le stockage. Une valeur illisible ou incompatible reste en place. Aucun effacement ni rétablissement écrasant n’est effectué automatiquement. L’export/import JSON est disponible sur la page Progression du cours. Cette récupération séparée reste utile pour une valeur brute ou un conflit.

Clé de ce cours : . Format v1 porté par cette clé; dates UTC et identifiants durables.

État valide en mémoire (JSON) Valeur brute lue dans le stockage (copier même si illisible) Données en conflit à conserver séparément (JSON)

Si l’accès est refusé, la valeur persistée peut rester inaccessible. Réautoriser le stockage dans le navigateur puis rouvrir ce cours permet de la relire. Une réinitialisation exige une décision explicite après récupération; aucune commande de suppression n’est proposée ici. Les données restent sur cette origine et cet appareil, sans transfert automatique.