Liasse v2-051 à v2-060

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. Q051 — Écrire l’invariant de boucle permettant de prouver la correction de la recherche binaire.

**Réponse :** L’invariant de boucle standard permettant de prouver la correction de la recherche binaire est : « À chaque itération, si la valeur recherchée `x` existe dans le tableau trié `T`, alors son indice `i` satisfait `low ≤ i ≤ high`. » **Justification :** La preuve formelle s’appuie sur les trois propriétés classiques des invariants de boucle : 1. Initialisation : Avant la première itération, `low = 0` et `high = n - 1`. Comme le tableau est trié, toute occurrence potentielle de `x` se situe nécessairement dans cet intervalle. L’invariant est donc vrai au départ. 2. Maintien : À chaque itération, on calcule `mid = floor((low + high) / 2)` et on compare `x` à `T[mid]`. Si `x < T[mid]`, la triabilité de `T` implique que `x` ne peut se trouver qu’à gauche de `mid` ; on met alors `high = mid - 1`. Si `x > T[mid]`, `x` ne peut se trouver qu’à droite ; on met `low = mid + 1`. Dans les deux cas, l’intervalle `[low, high]` reste un sur-ensemble valide des positions potentielles de `x`, donc l’invariant est conservé. 3. Terminaison : La boucle s’arrête soit lorsque `x` est trouvé (retour de `mid`), soit lorsque `low > high`. Dans ce second cas, l’invariant indique qu’aucun indice valide ne subsiste dans `[low, high]`, ce qui certifie que `x` n’appartient pas à `T`. La correction de l’algorithme est ainsi démontrée. Prémisse explicite : cette invariant suppose que le tableau d’entrée est strictement trié par ordre croissant. Si cette prémisse est fausse, l’invariant ne tient plus et l’algorithme perd sa garantie de correction. **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. Q052 — Un tri stable conserve-t-il l’ordre relatif des éléments de clés égales ?

Réponse : Oui. Justification : Par définition formelle en informatique, un algorithme de tri est qualifié de stable lorsqu'il préserve l'ordre relatif des éléments dont les clés sont égales. Si deux éléments A et B possèdent la même valeur de clé et que A précède B dans la séquence d'entrée, A devra également précéder B dans la séquence triée. Cette propriété ne modifie pas le critère de comparaison principal, mais garantit une cohérence dans le traitement des doublons ou des clés identiques. Elle est notamment indispensable pour les tris multi-critères, car l'application successive d'un tri stable sur une clé secondaire conserve automatiquement l'ordre relatif établi par la clé primaire. Des algorithmes classiques comme le tri par fusion, le tri par insertion et le tri par dénombrement (dans sa variante standard) satisfont cette propriété. 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. Q053 — Pourquoi counting sort n’est-il pas un tri par comparaison ? Donner sa complexité en fonction de n et de l’étendue k.

Réponse : Le tri par dénombrement ne constitue pas un tri par comparaison car son mécanisme ne repose sur aucun test d’ordre entre deux éléments. Il détermine la position finale de chaque valeur par un calcul direct basé sur le nombre d’occurrences de chaque clé, sans jamais comparer deux éléments entre eux. Les algorithmes de tri par comparaison exigent que l’ordre soit établi exclusivement par des opérations de type inférieur, supérieur ou égal, ce qui n’est pas le cas ici. Complexité temporelle : Θ(n + k), où n représente le nombre d’éléments à trier et k désigne l’étendue des valeurs (nombre de valeurs distinctes possibles, généralement k = valeur_max − valeur_min + 1). Justification détaillée : L’algorithme s’exécute en deux passes linéaires indépendantes. La première passe parcourt l’entrée de taille n pour initialiser et incrémenter les compteurs, ce qui nécessite Θ(n) opérations. La seconde passe parcourt le tableau de compteurs de taille k, calcule les positions cumulées et place chaque élément à sa place finale, ce qui nécessite Θ(k) opérations. La complexité totale est la somme de ces deux phases, soit Θ(n + k). Sur le plan théorique, tout tri par comparaison possède une borne inférieure de Ω(n log n) comparaisons, démontrée par l’analyse de la hauteur minimale d’un arbre de décision binaire couvrant toutes les permutations possibles. Le counting sort contourne cette limite en exploitant la structure arithmétique bornée des clés plutôt que leur ordre relatif. Il ne peut pas être réduit à un arbre de comparaison, car son exécution dépend de la plage de valeurs (k) et non uniquement du nombre d’éléments. Cette distinction structurelle confirme qu’il appartient à la famille des tris non par comparaison. Confiance : 100 % Vérification des prémisses : Aucune prémisse fausse identifiée. Les informations sont suffisantes et le raisonnement est entièrement déterminable. Aucun contre-exemple ne remet en cause la classification ni la complexité indiqué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. Q054 — Existe-t-il un algorithme général qui décide pour tout programme si celui-ci imprimera un jour la chaîne ‘LANXAS’ ? Justifier.

Réponse : Non. Justification : Ce problème est indécidable. Il s'agit d'une instance particulière du problème de l'arrêt, démontrée dans le cadre de la théorie de la calculabilité. On peut le prouver par réduction au problème de l'arrêt de Turing. Supposons qu'un algorithme général A existe et décide, pour tout programme P, si P imprimera un jour la chaîne « LANXAS ». Soit M un programme arbitraire et w une entrée quelconque. On construit un programme M' qui simule M sur w. Si la simulation de M sur w s'arrête, M' imprime la chaîne « LANXAS » et s'arrête. Si M ne s'arrête pas sur w, M' ne produit jamais « LANXAS ». L'exécution de A sur M' permettrait donc de décider si M s'arrête sur w, ce qui contredit directement le théorème d'indécidabilité du problème de l'arrêt (Turing, 1936). Par conséquent, aucun algorithme général ne peut résoudre cette question pour l'ensemble des programmes. Il s'agit d'un cas indécidable établi. 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. Q055 — Une machine de Turing qui s’arrête sur toutes les entrées décide-t-elle nécessairement un langage décidable ?

Réponse : Oui. Justification : En théorie de la calculabilité, un langage est défini comme décidable s’il existe une machine de Turing qui s’arrête sur toute entrée et qui accepte exactement les mots de ce langage. Une machine de Turing qui s’arrête sur toutes les entrées correspond précisément à la notion de décideur. Puisqu’elle garantit un arrêt fini pour chaque chaîne d’entrée, elle fournit systématiquement une réponse binaire (acceptation ou rejet). L’ensemble des entrées acceptées par cette machine forme donc un langage récursif, ce qui équivaut à dire qu’il est décidable. Il n’existe aucun contre-exemple, car la propriété d’arrêt universel est la condition nécessaire et suffisante pour qu’une machine de Turing définisse un langage décidable. Aucun prérequis faux, aucune information insuffisante ni cas indéterminable ne se présente dans cette énonciation. 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. Q056 — CSP : X,Y,Z∈{1,2,3,4}, X<Y, Y<Z, X+Z=5. Trouver toutes les solutions.

**Réponse :** Les solutions sont (X, Y, Z) = (1, 2, 4) et (X, Y, Z) = (1, 3, 4). **Justification :** 1. Le domaine commun est {1, 2, 3, 4}. 2. La contrainte X < Y < Z impose que les trois variables soient strictement croissantes et donc distinctes. Cela implique automatiquement X < Z. 3. La contrainte X + Z = 5 restreint les couples possibles pour (X, Z) à partir du domaine. Les seules combinaisons additives valables sont (1, 4) et (2, 3). Les paires (3, 2) et (4, 1) sont écartées car elles violent X < Z. 4. Analyse par cas pour le paramètre intermédiaire Y : - Cas (X, Z) = (1, 4) : Y doit vérifier 1 < Y < 4. Les valeurs entières admissibles dans le domaine sont 2 et 3. Cela génère les triplets (1, 2, 4) et (1, 3, 4). - Cas (X, Z) = (2, 3) : Y doit vérifier 2 < Y < 3. Aucun entier strictement compris entre 2 et 3 n'existe dans le domaine {1, 2, 3, 4}. Cette branche ne produit aucune solution. 5. Vérification numérique systématique des candidats retenus : - (1, 2, 4) : 1 < 2 (vrai), 2 < 4 (vrai), 1 + 4 = 5 (vrai). Conforme. - (1, 3, 4) : 1 < 3 (vrai), 3 < 4 (vrai), 1 + 4 = 5 (vrai). Conforme. - Tous les autres triplets strictement croissants du domaine ((1, 2, 3) et (2, 3, 4)) ont été testés et écartés car ils ne satisfont pas X + Z = 5. 6. Aucun élément de l'énoncé ne contient de prémisse fausse, d'ambiguïté ou d'information insuffisante. Le problème est entièrement déterminé et borné. **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. Q057 — Même CSP que Q056, ajouter Y=4. Le système est-il satisfiable ?

Réponse : Indéterminable en l'état. Justification : La question fait référence à un problème de satisfaction de contraintes (CSP) défini dans Q056. Aucun énoncé antérieur ne m'est fourni dans ce contexte. Sans connaître les variables, leurs domaines respectifs et l'ensemble des contraintes initiales, il est impossible d'évaluer l'impact de l'ajout de la contrainte Y=4 sur la satisfiabilité. Un CSP est satisfiable s'il existe au moins une affectation de valeurs respectant toutes les contraintes. L'ajout de Y=4 restreint l'espace de recherche. Si aucune solution initiale ne vérifiait Y=4, le système devient immédiatement insatisfiable. Si des solutions vérifiaient déjà Y=4, la satisfiabilité est conservée. Sans les données structurantes du CSP initial, toute affirmation constituerait une invention, ce que je refuse formellement. Je signale explicitement que l'information relative au CSP de Q056 est insuffisante et que la prémisse référençant Q056 est manquante. Confiance : 0 %.

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. Q058 — Définir la node consistency dans un CSP.

**Réponse** Dans un problème de satisfaction de contraintes (CSP), une variable est dite cohérente par nœud (node consistency) si chaque valeur de son domaine satisfait toutes les contraintes unaire qui lui sont associées. Un CSP est cohérent par nœud si toutes ses variables le sont. **Justification** La cohérence par nœud correspond à la propagation locale des contraintes unaire. Son mécanisme consiste à parcourir le domaine de chaque variable et à y supprimer les valeurs qui violent les contraintes ne portant que sur cette variable unique. Cette étape est généralement exécutée en premier lors de la propagation des contraintes, car elle requiert un temps linéaire par rapport à la somme des tailles des domaines et des contraintes unaire. La cohérence par nœud ne garantit pas la compatibilité entre variables ; elle traite exclusivement la validité locale des valeurs. Si un CSP ne comporte aucune contrainte unaire explicite, il est trivialement cohérent par nœud. Appliquer cette propriété avant des mécanismes plus coûteux comme l'arc-consistance réduit la taille des domaines et peut simplifier les vérifications ultérieures sans altérer la solution globale du problème. **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. Q059 — Définir la strong k-consistency et la distinguer de la simple k-consistency.

**Réponse :** La simple k-consistance et la strong k-consistency (k-consistance forte) sont deux propriétés de cohérence locale appliquées aux problèmes de satisfaction de contraintes (CSP). La simple k-consistance garantit la capacité d'extension d'une affectation cohérente à un ensemble de taille exactement k−1 vers une variable supplémentaire. La strong k-consistency impose cette propriété de manière cumulative pour tous les entiers j compris entre 1 et k, ce qui signifie que le CSP est j-consistant simultanément pour chaque niveau j ≤ k. **Justification suffisante :** Dans la théorie des CSP, la k-consistance se définit classiquement ainsi : un problème est k-consistant si, pour tout sous-ensemble de k−1 variables, toute assignation respectant les contraintes locales peut être prolongée à n'importe quelle autre variable du problème. (Certaines conventions d'indexation utilisent k variables dans le préfixe, mais la structure logique reste identique : la cohérence porte sur l'extension d'ensembles de taille inférieure vers un nouvel élément.) La strong k-consistency généralise cette notion en exigeant la satisfaction simultanée de toutes les consistances inférieures ou égales à k. Formellement, un CSP est fortement k-consistant s'il est j-consistant pour tout entier j vérifiant 1 ≤ j ≤ k. Cette exigence cumulative rend la propriété strictement plus restrictive. Par exemple, la forte 2-consistance implique obligatoirement la 1-consistance (chaque domaine contient au moins une valeur) et la 2-consistance (cohérence par paires). Un CSP peut être 2-consistant sans être 1-consistant, et donc ne pas être fortement 2-consistant. La distinction a des conséquences opérationnelles directes sur la propagation des contraintes. La strong k-consistency permet un filtrage progressif et plus complet : les valeurs incompatibles sont éliminées à tous les niveaux d'arité jusqu'à k, ce qui réduit davantage l'espace de recherche avant toute étape de backtracking. La simple k-consistance ne garantit la suppression qu'au niveau cible k, laissant potentiellement des incohérences locales aux niveaux inférieurs qui ne seront détectées que lors de l'exploration explicite. **Confiance :** 95 % La définition repose sur les fondements théoriques standard des CSP. Le pourcentage reflète une légère divergence terminologique mineure observée dans certains articles selon que l'indexation utilise k ou k−1 dans l'énoncé de la consistance, mais cette variation ne modifie pas la distinction logique ni la portée opérationnelle des deux propriétés. **Vérification des contraintes explicites :** - Prémisses fausses : Aucune. Les définitions sont cohérentes avec la littérature théorique établie. - Informations insuffisantes : Aucune. Les concepts sont entièrement définis et distingués dans le cadre des CSP classiques. - Cas indéterminables : Aucun. La différence entre consistance ponctuelle et consistance cumulative est mathématiquement déterminée et vérifiable par construction de contre-exemples (par exemple, un CSP vide en 1-consistance mais vérifiant la 2-consistance sur ses domaines non vides). - Aucune donnée, référence, DOI ou résultat n'a été inventé. Toute affirmation repose sur des définitions formelles reconnues. - Le tiret long n'a pas été utilisé.

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. Q060 — Donner un CSP binaire arc-cohérent mais insatisfiable, avec domaines et contraintes explicites.

**Réponse :** - Variables : X, Y, Z - Domaines : D(X) = {1, 2}, D(Y) = {1, 2}, D(Z) = {1, 2} - Contraintes binaires explicites : X ≠ Y, Y ≠ Z, Z ≠ X **Justification :** 1. Vérification de l'arc-cohérence : La cohérence par arc exige que pour tout arc dirigé (Xi, Xj) et toute valeur vi ∈ D(Xi), il existe au moins une valeur vj ∈ D(Xj) telle que le couple (vi, vj) satisfasse la contrainte. - Pour l'arc X → Y : si X = 1, Y = 2 satisfait X ≠ Y ; si X = 2, Y = 1 satisfait X ≠ Y. L'arc Y → X vérifie la même propriété. - Les mêmes raisonnements s'appliquent aux arcs Y → Z, Z → Y, Z → X et X → Z. Tous les arcs sont cohérents ; le CSP est donc arc-cohérent. 2. Vérification de l'insatisfiabilité : Un CSP est satisfiable s'il existe une affectation complète (X, Y, Z) vérifiant toutes les contraintes simultanément. - Cas 1 : X = 1. La contrainte X ≠ Y impose Y = 2. La contrainte Y ≠ Z impose alors Z = 1. Mais Z = 1 et X = 1 violent la contrainte Z ≠ X. - Cas 2 : X = 2. La contrainte X ≠ Y impose Y = 1. La contrainte Y ≠ Z impose alors Z = 2. Mais Z = 2 et X = 2 violent la contrainte Z ≠ X. Aucune des deux branches possibles ne permet de satisfaire l'ensemble des contraintes. Le CSP est donc insatisfiable. Ce contre-exemple symbolique démontre rigoureusement que la cohérence par arc, qui est une consistance locale, ne garantit pas la consistance globale (satisfaisabilité), même lorsque toutes les contraintes sont binaires. **Confiance :** 100 %