Cette page rassemble quelques solutions en Answer Set Programming (avec clingo) à une sélection de problèmes de logique originaires de sources diverses et variées.

Le grand pique-nique

When they started off on the great annual picnic every wagon in town was pressed into service, each one carrying the same number of people.

Half way to the picnic ground ten wagons broke down, so it was necessary for each of the remaining wagons to carry one more person.

…

Dans le précédent poste, nous avions résolu le problème de la couverture minimale avec l’Integer Programming. Dans ce billet, nous poursuivons notre exploration de ce problème en implémentant un programme logique Answer Set Programming avec clingo.

Reprenons le meme exemple:

% On commence par définir le graphe non orienté
% L'ensemble des sommets
noeud(a;b;c;d;e).
% L'ensemble des aretes
arete(a,c).
arete(a,d).
arete(a,e).
arete(c,b).
arete(d,e).

% Comme le graphe est non orienté, dès lors qu'une arete u,v existe, l'arete v,u est prise en compte.
arete(U,V) :- arete(V,U).

% Ici commence les choses intéressantes:

% Définition d'une couverture valide
:- couverture(V), - noeud(V).
% la couverture est un sous-ensemble des sommets

1 { couverture(U); couverture(V) } 2 :-
  arete(U, V).

cardinal(N) :- #count { V: couverture(V) } = N.
#minimize { N: cardinal(N) }.
#show couverture/1.

clingo version 5.8.0
Reading from /tmp/babel-lLz0Yh/clingo-zvg3tr
Solving...
Answer: 1 (Time: 0.001s)
couverture(c) couverture(d) couverture(e)
Optimization: 3
OPTIMUM FOUND

Models       : 1
  Optimum    : yes
Optimization : 3
Calls        : 1
Time         : 0.001s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.001s

Ce qui donne, en jaune sur le graphe ci-dessous, la couverture minimale:

Le problème de couverture par sommets (ou Vertex Cover en anglais) consiste, étant donné un graphe, à trouver un ensemble minimum de sommets de sorte que toutes les arêtes soient couvertes.

Formellement: soit \(G(V, E)\) un graphe, une couverture est un ensemble \(S\) tel que: \[ S \subseteq V \text{ tel que } \forall e = (u, v) \in E, u \in S, \text{ ou } v \in S \]

L’objectif est de miniser la taille de \(S\).

Après avoir enregistré des sons de chauve-souris, orthoptères ou d’oiseaux, il est souvent utile de jeter un oeil aux spectrogrammes des enregistrements, par exemple lors de l’analyse d’enregistrements réalisés dans le cadre du programme Vigie-Chiro.

Les logiciels recommandés dans les tutoriels Vigie-Chiro sont, pour certains, développés uniquement pour Windows. Dans cet article, nous apprendrons comment installer ces logiciels (Kaleidoscope, Syrinx, Batsound 4, 7-zip et Lupas-Rename) sur une machine Linux à l’aide de Wine.

Après avoir réalisé un piège photo avec un caméra déclenchée par un détecteur de mouvement infrarouge et Arduino, j’ai eu envie d’essayer de faire le même type de système avec un Raspberry Pi.

L’avantage de Raspberry Pi est que c’est un vrai ordinateur (pas un simple microcontrolleur comme l’ATMega de l’Arduino). De ce fait il a une plus grande capacité de calculs, et on peut se passer du PIR sensor en utilisant de l’analyse d’image pour détecter le mouvement.