Complexité et Calculabilité

Vous trouverez la page principale de cette UE sur la page d'Anca Muscholl qui donne le cours.

Le devoir à la maison

Il consiste à écrire un programme qui va convertir la question "le graphe G est il k-coloriable?" en une formule SAT et à la fournir à Glucose pour la résoudre. Vous trouverez ci dessous une liste de fonctions C qui vous permettront de tester votre programme. Toutes ces fonctions répondent au ".h" que voici.

Quelques graphes proposés par des camarades:

On vérifiera bien pour chaque graphe que le résultat fourni est SAT si le nombre de couleurs suffit et UNSAT si le nombre de couleurs est trop faible.

Autres

Voici quelques petits liens pour vous aider à réviser.



Home