Examples de codes correcteurs d'erreurs
Option Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'Orsay
Document disponible au format: PDF, Postscript, DVI, Text, LaTeX, LyX.
1 TP: Programmation Linéaire
Notes de cours: cf. http://nicolas.thiery.name/RO/Notes/ProgrammationLineaire.html
Exercice 1
En utilisant les commandes linopt::Transparent et linopt::Transparent::userstep
de MuPAD (ou leurs équivalents Maple: simplex[setup],
simplex[pivot]), appliquer pas-à-pas l'algorithme du simplexe
sur quelques uns des systèmes Chvatal7a, Chvatal7b, Chvatal7c, Chvatal26_21a
et Chvatal26_21c (cf. http://nicolas.thiery.name/RO/Notes/tableaux.mu)
Expérimentez avec les exemples 2 et 3 (systèmes Chvatal29 et Chvatal31)
illustrant les problèmes potentiels de cyclage.
Expérimentez avec le système de Klee Minty http://carbon.cudenver.edu/~hgreenbe/glossary/notes/Klee-Minty.pdf.
Exercice 2
On considère une formule booléenne, comme par exemple: (A∨ B)∧(¬(C∧ D)∨ A∨¬ D),
et on voudrait savoir si elle est satisfiable (c'est-à-dire si l'on
peut choisir des valeurs Vrai/Faux pour A, B, C, D telles que la formule
devienne vraie). Peut-on se ramener à la résolution d'un système d'inéquations
linéaires?
Exercice 3
Modélisation: on considère le problème (dit de flot) suivant:
On a un réseau de canalisations d'eau entre les noeuds a, b, ...,
i, où le nombre sur chaque arête indique le débit maximal pouvant
passer par cette canalisation. L'eau rentre par le sommet a et ressort
par le sommet i, sans perte ni création dans les noeuds intermédiaires.
Quel débit d'eau maximal peut on faire passer entre a et i?
Exercice 4
Un couplage d'un graphe est un ensemble d'arêtes de ce graphe deux
à deux disjointes. Chercher un couplage de taille maximale du graphe
biparti suivant:
Exercice 5
En se ramenant à la recherche d'un couplage dans un graphe biparti,
rechercher une couverture en chaîne de taille minimale dans l'ordre
partiel du cours.
Démontrer le théorème de Dilworth.
Examples de codes correcteurs d'erreurs
Option Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'Orsay
TP: Programmation Linéaire /
Option Algèbre et Calcul Formel /
Nicolas M. Thiéry
Dernière modification: Mer 25 Avr 2007 22:50:04