Python - Algoritmo di giustificazione

Per poter affermare che un algoritmo è efficiente, abbiamo bisogno di alcuni strumenti matematici come prova. Questi strumenti ci aiutano a fornire una spiegazione matematicamente soddisfacente sulle prestazioni e l'accuratezza degli algoritmi. Di seguito è riportato un elenco di alcuni di quegli strumenti matematici che possono essere utilizzati per giustificare un algoritmo rispetto a un altro.

• Direct Proof:

  È la verifica diretta della dichiarazione utilizzando i calcoli diretti. Ad esempio, la somma di due numeri pari è sempre un numero pari. In questo caso, aggiungi i due numeri che stai indagando e verifica il risultato come pari.

• Proof by induction:

  Qui iniziamo con un'istanza specifica di una verità e poi la generalizziamo a tutti i possibili valori che fanno parte della verità. L'approccio consiste nel prendere un caso di verità verificata, quindi provare che è vero anche per il caso successivo per la stessa condizione data. Ad esempio, tutti i numeri positivi della forma 2n-1 sono dispari. Lo dimostriamo per un certo valore di n, quindi lo dimostriamo per il valore successivo di n. Ciò stabilisce che l'affermazione è generalmente vera in base alla prova dell'induzione.

• Proof by contraposition:

  Questa dimostrazione si basa sulla condizione Se non A implica Non B allora A implica B. Un semplice esempio è se il quadrato di n è pari, allora n deve essere pari. Perché se il quadrato su n non è pari allora n non è pari.

• Proof by exhaustion:

  Questo è simile alla dimostrazione diretta, ma viene stabilito visitando ciascun caso separatamente e dimostrando ciascuno di essi. Un esempio di tale dimostrazione è il teorema dei quattro colori.