Niveau: Supérieur
Examen Partiel : Algorithmique des Structure de Donnees Ecole normale superieure Departement d'informatique 5 Decembre 2011 Tous documents autorises. Ne paniquez pas. Il n'est pas indispensable d'ecrire du pseudo-code pour decrire un algorithme. L'important est de se faire comprendre. La rigueur des preuves sera evaluee. Il est possible d'admettre le resultat d'une question pour traiter les suivantes. Exercice 1 : Couverture Monotone minimale. On considere une grille n ? n dont les cases sont soit noires soit blanches. La grille est donnee par une matrice de booleens. Un chemin monotone dans la grille part d'une case noire, termine sur une case noire, et ne peut avancer que vers le bas ou vers la droite. Le but du probleme est de couvrir l'ensemble des cases marquees avec le moins possible de chemins monotones. La strategie generale est de ramener le probleme a une situation de flots maximaux. Comme c'est un peu complique, on va s'y prendre par etapes. D'abord, il est assez clair que la grille definit un reseau de transport de flot ou chaque case est reliee en a celle du bas et a celle de droite. (?) 1. Expliquez comment on peut forcer un flot a atteindre chacune des cases noires. Dessinez un flot maximal pour la grille d'exemple.
- probleme de flot maximum de cout minimum
- ordre de la partition
- lexbfs
- partition
- temps linaire
- flot