Pourquoi est-ce une preuve par contradiction pour cet algorithme? N'est-ce pas une preuve directe à la place?
-
05-11-2019 - |
Question
Première diapositive: trouver max (a)
- // Entrée: A [1..N] - un tableau d'entiers
- // Sortie: un élément m de a tel que m> = a [j], pour tous les 1 <= j <= a.Length
- max = a [j == 1
- pour j = 2 à A.Length
- Si max <a [j
- max = a [j
- retourner max
Deuxième diapositive: preuve par contradiction
Preuve: Supposons que l'algorithme soit incorrect. Ensuite, pour une entrée A, soit:
- Max n'est pas un élément de a ou
- A a un élément a [j] tel que max <a [j
Max est initialisé et affecté aux éléments de a - donc (1) est impossible.
Après l'itération J-Th de la boucle pour (lignes 4 - 6), max> = a [j]. Des lignes 5,6 Max n'augmente que. Par conséquent, lors de la fin, max> = a [j] qui contredit (2).
Fin des diapositives
Cet algorithme (première diapositive) trouve l'élément maximum dans le tableau. Il s'agit d'une preuve par contradiction. Cet algorithme n'est-il pas déjà prouvé quand il arrive max> = a [j] dans la dernière ligne de la deuxième diapositive. Est qui contredit (2) Même nécessaire? Parce que dans la deuxième diapositive, vous avez montré que Max est dans le tableau, puis Vous avez atteint l'état d'un maxium m: un élément m de a tel que m> = a [j] pour tous les 1 <= j <= a.Length.
Cela semble être deux preuves en un. Et comme il me semble que la preuve directe se produit d'abord, la preuve par contradiction est redondante et donc pas nécessaire. Est-ce que j'ai râté quelque chose? Est-ce seulement une preuve par contradiction? Ou est-ce une preuve directe à la place?
L'image ci-dessous n'est que les diapositives 1 et 2 que j'ai transcrites ci-dessus. De l'Université de York.
Pas de solution correcte