Glossaire IA
Le dictionnaire complet de l'Intelligence Artificielle
Solveur SAT
Algorithme déterminant si une formule booléenne propositionnelle possède une assignation de variables la rendant vraie. Fondamental pour la résolution de problèmes de décision en synthèse de programmes.
Solveur SMT
Extension des solveurs SAT intégrant des théories mathématiques comme l'arithmétique, les tableaux et les types de données. Permet de résoudre des contraintes plus complexes dans la synthèse de programmes.
Contraintes logiques
Formules mathématiques exprimant les propriétés et comportements que doit respecter le programme généré. Servent de pont entre les spécifications utilisateur et la recherche automatique de solutions.
Synthèse dirigée par contraintes
Paradigme où les spécifications sont transformées en un système de contraintes résolu par des solveurs automatiques. Génère des programmes garantissant formellement le respect des exigences.
Encodage problème
Processus de traduction des spécifications de haut niveau en formules logiques compréhensibles par les solveurs. Détermine l'efficacité de la phase de résolution de contraintes.
Inductive Synthesis
Technique inférant automatiquement des programmes à partir d'exemples d'entrées-sorties désirés. Combine apprentissage inductif et résolution de contraintes pour généraliser les comportements.
SKETCH
Langage de programmation permettant de spécifier des programmes partiels avec trous à compléter automatiquement. Utilise des solveurs SMT pour trouver les valeurs optimales des trous.
SyGuS
Syntax-Guided Synthesis, standard formalisant les problèmes de synthèse avec grammaire de solutions spécifiée. Permet de contrôler la structure et la complexité des programmes générés.
Abstraction-réfinissement
Stratégie itérative simplifiant initialement le problème puis raffinant progressivement les contraintes. Équilibre efficacité et précision dans la synthèse de programmes complexes.
Apprentissage par contraintes
Méthode hybride combinant techniques d'apprentissage automatique et résolution de contraintes logiques. Accélère la synthèse en guidant intelligemment l'espace de recherche.
Vérification conditionnelle
Processus formel validant que le programme synthétisé satisfait l'ensemble des spécifications initiales. Essentiel pour garantir la correction des programmes générés automatiquement.
Algorithme DPLL
Davis-Putnam-Logemann-Loveland, algorithme fondamental pour la satisfaction de formules booléennes. Base de nombreux solveurs SAT modernes utilisés en synthèse de programmes.
Théorie des combinaisons
Mécanisme permettant aux solveurs SMT de gérer simultanément plusieurs théories mathématiques hétérogènes. Indispensable pour modéliser des problèmes de synthèse réalistes.
SAT modulo théories
Formalisme unifiant logique propositionnelle et théories mathématiques dans un cadre de résolution unique. Permet de traiter des contraintes complexes en synthèse de programmes.
Contraintes de symétrie
Propriétés formelles éliminant les solutions équivalentes pour réduire l'espace de recherche. Accélèrent significativement la synthèse en évitant l'exploration redondante.
Synthèse incrémentale
Approche constructivant progressivement le programme en ajoutant des fonctionnalités et contraintes itérativement. Permet de gérer la complexité par décomposition du problème.
Modèles de Hoare
Triplets {Précondition} Programme {Postcondition} formels pour la vérification et synthèse de programmes corrects. Fondement théorique garantissant la validité des programmes générés.