Invariants et (mono)variants

Général

Résumé Chapitre entier

Points théoriques

Invariants Monovariants Variants

Exercices

Exercice 1 Exercice 2 Exercice 3 Exercice 4 Exercice 5

Exercice 3 (9 points) (Résolu 2807 fois - 33% de réussite au premier essai)
(Résolu 2807 fois -
33% de réussite au 1^er essai)

Considérons un problème où un processus consiste à répéter plusieurs fois une certaine transformation. On désire utiliser un monovariant pour prouver que le processus se terminera toujours après un nombre fini de transformations. Dans lesquelles des situations suivantes pourra-t-on toujours conclure ?

Cochez chaque proposition correcte.

Le monovariant prend ses valeurs dans $\mathbb{N}$, décroit strictement à chaque transformation et le processus se termine lorsqu'il vaut $0$

Le monovariant prend ses valeurs dans $\mathbb{Z}$, a une valeur initiale positive, décroit strictement à chaque transformation et le processus se termine lorsqu'il vaut $0$

Le monovariant prend ses valeurs dans $\mathbb{R}^+$, décroit strictement à chaque transformation et le processus se termine lorsqu'il vaut $0$

Le monovariant prend ses valeurs dans $\mathbb{Z}$, est diminué de $3$ à chaque transformation et le processus se termine dès qu'il est multiple de $100$

Pour pouvoir répondre aux exercices, vous devez être connecté.

Théorie > Combinatoire > Invariants et (mono)variants

Général

Points théoriques

Exercices

Exercice 3 (9 points) (Résolu 2807 fois - 33% de réussite au premier essai) (Résolu 2807 fois - 33% de réussite au 1er essai)

Exercice 3 (9 points) (Résolu 2807 fois - 33% de réussite au premier essai)
(Résolu 2807 fois -
33% de réussite au 1^er essai)