LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » News » Studenti di dottorato

METIN Hakan

Dottore di ricerca
Gruppo di ricerca : MoVe
Data di partenza : 12/31/2019
https://pages.lip6.fr/Hakan.Metin
Relatore : Fabrice KORDON
Co-relazione : BAARIR Souheib

Exploitation des symétries dynamiques pour la résolution des problèmes SAT

Avec l’intégration toujours plus grande, des systèmes informatiques dans des applications critiques (métro, voitures, centrales-nucléaires, blocs opératoires, etc), assurer la correction des programmes devient une nécessité. Si l’utilisation systématique de tests permet d’améliorer grandement la qualité du code, elle ne peut réellement garantir leur correction. A l’inverse, les techniques dites de model-checking, qui vérifient la validité du workflow applicatif (modélisé par un graphe d’états) par rapport à une propriété donnée, permettent de garantir la correction des programmes. Ces techniques reposent, essentiellement, sur deux théories : celle basée sur les automates et celle fondée sur la satisfiabilité booléenne (SAT). Dans les deux théories l’ennemi commun est le problème bien connu de l’explosion combinatoire. En utilisant les automates, le problème se manifeste par une consommation mémoire démesurée, alors qu’en utilisant le SAT, le problème se manifeste sous la forme d’un temps de calcul extrêmement long. Cependant, certains systèmes exhibent des comportements symétriques, i.e., les compo- sants du système se comportent de façon identique à une permutation des identités près. Ces symétries se traduisent naturellement sur les problèmes SAT générés lors de la vérification : en effet, les permutations détectées au niveau du système se traduisent (de façon triviale) par des permutations, dont l’application laisse la formule SAT invariante. Ainsi, la prise en compte de symétries lors la résolution du problème est censée réduire considérablement le temps de calcul !
Difesa : 12/18/2019 - 14h - Campus Jussieu, Atrium, Salle RC 27
Membri della commissione :
Pascal Fontaine, Professeur, Université de Liège [rapporteur]
Laure Petrucci, Professeur, Université Paris 13 [rapporteur]
Jean-Michel Couvreur, Professeur, Université d'Orléans
Emmanuelle Encrenaz, Maître de conférences, Sorbonne Université
Bart Bogaerts, Assistant Professor, Vrije Universiteit Brussel
Souheib Baarir, Maître de conférences, Université Paris Nanterre
Fabrice Kordon, Professeur, Sorbonne Université

Pubblicazioni 2018-2019

 Mentions légales
Mappa del sito |