combine : une bibliothèque OCaml pour la combinatoire

Rémy El Sibaïe 1 Jean-Christophe Filliâtre 1, 2
2 TOCCATA - Certified Programs, Certified Tools, Certified Floating-Point Computations
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Résumé : Cet article présente combine1, une bibliothèque OCaml pour la combinatoire2. Elle fournit deux solutions algorithmiquement très différentes au problème de la couverture exacte d'une matrice (EMC) : les liens dansants de Knuth et une variante des diagrammes de décision binaire appelée ZDD. De très nombreux problèmes de combinatoire peuvent être ramenés au problème EMC. La bibliothèque combine l'illustre notamment sur l'exemple du pavage rectangulaire en dimension 2.
Type de document :
Communication dans un congrès
Damien Pous and Christine Tasson. JFLA - Journées francophones des langages applicatifs, Feb 2013, Aussois, France. 2013
Liste complète des métadonnées


https://hal.inria.fr/hal-00779431
Contributeur : Ist Inria Saclay <>
Soumis le : mardi 22 janvier 2013 - 11:13:47
Dernière modification le : jeudi 9 février 2017 - 15:56:48
Document(s) archivé(s) le : samedi 1 avril 2017 - 08:10:16

Fichier

jfla2013-05.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-00779431, version 1

Citation

Rémy El Sibaïe, Jean-Christophe Filliâtre. combine : une bibliothèque OCaml pour la combinatoire. Damien Pous and Christine Tasson. JFLA - Journées francophones des langages applicatifs, Feb 2013, Aussois, France. 2013. <hal-00779431>

Partager

Métriques

Consultations de
la notice

285

Téléchargements du document

194