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 "existe un arbre couvrant du graphe G de profondeur k?" 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:
- chvatal.c : Graphe de Chvatal, 4-régulier, 12 sommets.
- golomb.c : Graphe de Golomb, planaire à 10 sommets.
- moser.c : Graphe de Moser, planaire à 7 sommets.
- hypercube8.c : Hypercube de dimension 8, 256 sommets, 8 régulier, biparti.
Autres
Voici quelques petits liens pour vous aider à réviser.
- L'argument diagonal de Cantor pour montrer que l'ensemble des réels n'est pas dénombrable: Vidéo
- Le problème de l'arrêt et le paradoxe de Turing: Vidéo
- Une vidépo sur la réduction SAT: Vidéo
Home