Liasse v2-061 à v2-070

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q061 — AC-3 peut-il supprimer une valeur appartenant à au moins une solution globale ? Justifier.

**Réponse :** Non. **Justification :** AC-3 est un algorithme de propagation de contraintes qui impose la consistance d'arc. Une propriété fondamentale et rigoureusement démontrée de la consistance d'arc est sa sécurité (soundness) : l'algorithme ne supprime jamais une valeur qui appartient à au moins une solution globale du problème. Si une valeur fait partie d'une solution complète, elle satisfait par définition toutes les contraintes binaires la concernant, ce qui implique qu'elle dispose d'un support valide dans le domaine de chaque variable voisine. Elle est donc arc-consistante et résiste au filtrage. La réciproque est fausse : une valeur qui survit à AC-3 n'est pas nécessairement partie d'une solution globale, car la consistance d'arc n'assure qu'une cohérence locale et non une complétude globale. Cette propriété constitue un résultat théorique classique en résolution de problèmes de satisfaction de contraintes. **Confiance :** 100 %

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q062 — Dans un CSP binaire sur un arbre, expliquer pourquoi un passage de cohérence approprié suivi d’une affectation ordonnée permet de trouver une solution sans backtracking.

Réponse : Sur un CSP binaire dont le graphe de contraintes est un arbre, une phase de cohérence d'arc complète élimine systématiquement les valeurs incompatibles. Lorsqu'on affecte ensuite les variables selon un ordre topologique (par exemple de la racine vers les feuilles), chaque nouvelle affectation est garantie compatible avec la contrainte unique qui la relie à une variable déjà assignée. L'absence de cycles dans le graphe empêche toute apparition ultérieure de conflits non détectés. La solution se construit donc linéairement sans nécessiter de backtracking. Justification : 1. Structure acyclique : Un graphe de contraintes en arbre est connexe et ne contient aucun cycle. Chaque variable possède au maximum un parent dans un ordre topologique donné. Cette propriété élimine les chemins alternatifs qui, dans un graphe cyclique, pourraient imposer des contraintes rétroactives incompatibles avec une décision locale. 2. Filtrage par cohérence d'arc : L'application d'un algorithme de cohérence d'arc sur un arbre garantit la cohérence globale du problème. Si une solution existe, aucun domaine ne devient vide. Chaque valeur restante est compatible avec au moins une valeur du domaine de chaque voisin. Sur un arbre, deux passes de propagation (racine vers feuilles puis feuilles vers racine) suffisent à atteindre cet état. 3. Affectation ordonnée et extensibilité : En suivant un ordre topologique, on affecte chaque variable à une valeur de son domaine réduit. La contrainte binaire avec le parent est automatiquement respectée grâce au filtrage préalable. Comme les enfants ne sont pas encore affectés et qu'aucun cycle n'existe, le choix actuel ne peut pas bloquer l'affectation future des enfants. La cohérence d'arc a déjà validé l'existence d'au moins une valeur compatible pour chaque enfant. 4. Gestion des cas insatisfaisables : Si le CSP initial est insatisfiable, le passage de cohérence d'arc détecte cette impossibilité en vidant un domaine avant même le début de l'affectation. L'algorithme s'arrête sans backtracking, ce qui respecte la propriété générale demandée. 5. Vérification structurelle : Soit V l'ensemble des variables et C l'ensemble des contraintes binaires. Un arbre possède exactement |V|−1 contraintes. La cohérence d'arc sur arbre se résout en O(|V|·d²). Après filtrage, pour chaque variable v et chaque valeur d ∈ D(v), il existe une valeur compatible dans le domaine de chaque voisin. Lors de l'affectation séquentielle, la valeur choisie respecte la contrainte avec le parent et préserve l'extensibilité vers les enfants. Aucun retour en arrière n'est requis. Confiance : 98 % Note : La réponse repose sur la théorie établie des CSP. Le 2 % de réserve correspond uniquement à la précision terminologique de la phrase « passage de cohérence approprié » qui désigne ici la cohérence d'arc complète. Si le CSP est insatisfiable, le mécanisme signale l'échec par un domaine vide plutôt que par un backtracking, ce qui reste cohérent avec le principe demandé. Aucune donnée, référence ou DOI n'a été inventée.

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q063 — SAT à 2 littéraux par clause est-il polynomialement décidable ? Nommer une méthode standard.

Réponse : Oui, le problème de satisfaisabilité booléenne avec au plus deux littéraux par clause (2-SAT) est polynomialement décidable. Justification : Le 2-SAT appartient à la classe P. La méthode standard repose sur la construction d'un graphe d'implication. Chaque clause de la forme (l1 ∨ l2) est équivalente à deux implications : (¬l1 → l2) et (¬l2 → l1). On construit un graphe dirigé dont les sommets correspondent aux littéraux (x et ¬x pour chaque variable x) et dont les arêtes correspondent aux implications. La formule est insatisfiable si et seulement si, pour au moins une variable x, les sommets x et ¬x appartiennent au même composant fortement connexe. Ce test s'exécute en temps linéaire O(n + m) en calculant les composantes fortement connexes avec un algorithme tel que celui de Tarjan ou de Kosaraju. Si la formule est satisfiable, une affectation valide peut être déterminée en ordonnant topologiquement les composantes et en affectant les littéraux selon l'ordre inverse de leurs composantes. La complexité temporelle totale reste strictement polynomiale, ce qui démontre que le problème est décidable en temps polynomial. Confiance : 100 %

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q064 — Horn-SAT est-il polynomialement décidable ? Donner l’idée de l’algorithme.

Réponse : Oui, Horn-SAT est polynomialement décidable. Il est même soluble en temps linéaire par rapport à la taille de la formule. Justification et idée de l’algorithme : Une formule de Horn est une formule booléenne en forme normale conjonctive dont chaque clause contient au plus un littéral positif. Le problème Horn-SAT consiste à déterminer si une telle formule admet une affectation satisfaisante. La prémisse de sa décidabilité polynomiale est vraie et bien établie en complexité algorithmique. L’algorithme classique repose sur la propagation d’unités, également appelée chaînage avant. Son principe est le suivant : 1. On initialise toutes les variables à faux. 2. On examine les clauses. Pour une clause de la forme (¬x1 ∨ ¬x2 ∨ ... ∨ ¬xk ∨ y), si toutes les variables x1 à xk sont fausses, la clause impose que y soit vrai. On affecte y à vrai et on mémorise ce changement. 3. Pour une clause de la forme (¬x1 ∨ ¬x2 ∨ ... ∨ ¬xk), si toutes les variables x1 à xk sont fausses, la clause n’est pas satisfaite. La formule est insatisfiable et l’algorithme s’arrête immédiatement. 4. On répète les étapes 2 et 3 jusqu’à ce qu’aucune nouvelle variable ne soit affectée à vrai. Si toutes les clauses sont satisfaites, la formule est satisfiable. Si le processus se termine sans détection d’insatisfiabilité, l’affectation obtenue est un modèle valide. En effet, les formules de Horn admettent toujours un modèle unique minimal (celui où le nombre de variables à vrai est strictement minimal), et la propagation d’unités reconstruit exactement ce modèle. Implémentation et complexité : L’algorithme peut être exécuté en temps linéaire O(N), où N désigne le nombre total de littéraux dans la formule. Chaque variable est affectée au plus une fois. On utilise des compteurs de littéraux négatifs non satisfaits par clause et des structures de type file pour les variables fraîchement passées à vrai. Chaque littéral négatif est examiné un nombre constant de fois, ce qui garantit la linéarité et donc la polynomialité. Confiance : 100 %.

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q065 — Une fonction convexe différentiable a ∇f(x)=0. x est-il globalement minimal ?

**Réponse :** Oui, $x$ est un minimum global. **Justification :** Pour toute fonction $f : \mathbb{R}^n \to \mathbb{R}$ convexe et différentiable sur un domaine convexe (généralement $\mathbb{R}^n$ ou un ouvert convexe), la condition du premier ordre est à la fois nécessaire et suffisante pour l'optimalité globale. Par définition de la convexité, on a pour tout $y$ dans le domaine : $$f(y) \geq f(x) + \nabla f(x)^\top (y - x).$$ Si $\nabla f(x) = 0$, le terme linéaire s'annule et l'inégalité se réduit à $f(y) \geq f(x)$ pour tout $y$. Cela signifie exactement que $f(x)$ est la borne inférieure de l'image de $f$, donc $x$ réalise le minimum global. Aucun contre-exemple n'existe sous ces hypothèses, car l'annulation du gradient caractérise précisément les points stationnaires globaux dans le cadre convexe différentiable. La prémisse est valide et les informations sont complètes pour conclure. **Confiance :** 100 %

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q066 — Une fonction strictement convexe sur un domaine convexe peut-elle avoir deux minimisateurs distincts ?

Réponse : Non. Justification : Soit $C$ un domaine convexe et $f : C \to \mathbb{R}$ une fonction strictement convexe. Supposons par l'absurde qu'il existe deux minimisateurs globaux distincts $x_1$ et $x_2$ appartenant à $C$. Par définition du minimum global, on a $f(x_1) = f(x_2) = m$, où $m$ est la valeur minimale atteinte par $f$ sur $C$. Puisque $C$ est convexe, pour tout $\lambda \in ]0,1[$, le point $z = \lambda x_1 + (1-\lambda)x_2$ appartient à $C$. La stricte convexité de $f$ impose alors l'inégalité stricte : $$f(z) < \lambda f(x_1) + (1-\lambda)f(x_2) = \lambda m + (1-\lambda)m = m.$$ On obtient ainsi $f(z) < m$, ce qui contredit directement le fait que $m$ soit le minimum global de $f$ sur $C$. Par conséquent, une fonction strictement convexe sur un ensemble convexe admet au plus un minimisateur. Elle ne peut jamais en posséder deux distincts. Confiance : 100 %.

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q067 — Pour f(x,y)=x²-y², classifier le point (0,0).

Réponse : Le point (0,0) est un point selle. Justification : 1. Identification du point critique : Les dérivées partielles premières sont f_x(x,y) = 2x et f_y(x,y) = -2y. En (0,0), on a f_x = 0 et f_y = 0. Le point est donc critique. 2. Analyse du second ordre : Les dérivées partielles secondes sont f_xx = 2, f_yy = -2 et f_xy = 0. La matrice hessienne en (0,0) est H = [[2, 0], [0, -2]]. Son déterminant est Det(H) = (2)(-2) - 0² = -4. 3. Classification : Puisque Det(H) < 0, le test du second ordre classe rigoureusement ce point critique comme un point selle. 4. Vérification directionnelle (complément symbolique) : Sur l'axe des x (y=0), f(x,0) = x² ≥ 0, ce qui indique un minimum local le long de cette direction. Sur l'axe des y (x=0), f(0,y) = -y² ≤ 0, ce qui indique un maximum local le long de cette direction. La fonction prend donc des valeurs strictement supérieures et strictement inférieures à f(0,0) = 0 dans tout voisinage du point, ce qui confirme la nature de point selle. Confiance : 100 %. L'analyse repose sur des propriétés analytiques standard pour les fonctions de classe C². Les prémisses sont vraies, les informations sont complètes et le cas est entièrement déterminable.

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q068 — Les conditions KKT sont-elles toujours suffisantes pour l’optimalité globale ? Donner les hypothèses usuelles qui les rendent suffisantes.

**Réponse :** Non. **Prémisse fausse signalée :** L’interrogation suppose implicitement que les conditions de Karush-Kuhn-Tucker pourraient être toujours suffisantes. Cette prémisse est incorrecte. **Justification :** Les conditions KKT sont avant tout des conditions nécessaires d’optimalité locale, à la réserve qu’une qualification de contraintes soit vérifiée au point considéré. Elles ne garantissent pas l’optimalité globale dans un problème général car un point peut satisfaire les relations de stationnarité, de réalisabilité et de complémentarité sans correspondre à un minimum global. Dans des problèmes non convexes, un point KKT peut en effet être un maximum local, un point de selle ou un minimum local strictement supérieur à un autre minimum global. La non-convexité de la fonction objectif ou des contraintes permet l’existence de plusieurs points stationnaires, ce qui rompt le lien direct entre stationnarité KKT et optimalité globale. **Hypothèses usuelles rendant les conditions KKT suffisantes :** Les conditions KKT deviennent suffisantes pour l’optimalité globale lorsque le problème d’optimisation est convexe. Les hypothèses standard sont les suivantes : 1. La fonction objectif est convexe sur l’ensemble réalisable. 2. Chaque fonction de contrainte d’inégalité est convexe. 3. Chaque fonction de contrainte d’égalité est affine. Sous ces hypothèses, le lagrangien est convexe par rapport aux variables d’optimisation, et toute solution réalisable vérifiant les conditions KKT est nécessairement un minimiseur global. Aucune qualification de contraintes supplémentaire n’est requise pour établir la suffisance dans ce cadre, bien que la convexité assure généralement la validité des conditions nécessaires. **Confiance :** 100 %.

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q069 — Un problème d’optimisation peut-il avoir un infimum fini non atteint ? Donner un exemple.

Réponse : Oui. Justification : En analyse et en optimisation, l'infimum d'une fonction sur un ensemble admissible désigne sa borne inférieure supérieure. Il est atteint si et seulement si il existe un point admissible où la fonction prend exactement cette valeur. Lorsque l'ensemble admissible n'est pas fermé ou lorsque la fonction n'est pas semi continue inférieurement, la borne inférieure peut se situer à la frontière de l'ensemble sans y appartenir, ce qui rend l'infimum fini mais non atteint. Exemple symbolique et vérification : Considérons le problème de minimisation suivant : Fonction objectif : f(x) = x. Ensemble admissible : S = ]0, 1[. Vérification symbolique : 1. Borne inférieure : Pour tout x ∈ ]0, 1[, f(x) > 0. La suite (x_n) définie par x_n = 1/n (avec n ≥ 2) reste dans S et vérifie f(x_n) = 1/n. Lorsque n tend vers l'infini, f(x_n) tend vers 0. Par définition de la borne inférieure, inf_{x ∈ S} f(x) = 0. La valeur est finie. 2. Non atteinte : L'équation f(x) = 0 admet une unique solution x = 0. Or 0 ∉ ]0, 1[. Aucun élément de S ne réalise la valeur 0. Le minimum n'est donc pas atteint. Ce phénomène est classique et s'explique par le théorème de Weierstrass, qui garantit l'existence d'un minimum atteint uniquement lorsque l'ensemble admissible est compact et que la fonction est continue. Ici, la non fermeture de S suffit à rendre l'infimum non atteint. Aucune donnée, référence ou résultat n'a été inventé ; il s'agit d'un énoncé standard de l'analyse réelle. Confiance : 100 %

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q070 — Minimiser x² sous la contrainte x≥1. Donner solution et valeur optimale.

**Réponse :** La solution optimale est x* = 1 et la valeur optimale est 1. **Justification :** La fonction objectif f(x) = x² est strictement croissante sur l'intervalle [1, +∞[ puisque sa dérivée f'(x) = 2x est strictement positive pour tout x ≥ 1. Sous la contrainte x ≥ 1, le minimum sur l'ensemble admissible est nécessairement atteint à la borne inférieure de cet ensemble, soit x = 1. On vérifie symboliquement que pour tout x ≥ 1, on a x² ≥ 1, avec égalité si et seulement si x = 1. Le point x = 1 est réalisable, satisfait la contrainte et minimise strictement la fonction sur le domaine autorisé. **Confiance :** 100 %.