Che cosa significa dire che un algoritmo è Suono e Completo?

Questi sono termini molto specifici relativi alla logica.

Ecco alcuni punti di partenza:

link

link

Fondamentalmente, la solidità (di un algoritmo) significa che l'algoritmo non produce risultati non veritieri. Se, ad esempio, ho un algoritmo di ordinamento che a volte non restituisce una lista ordinata, l'algoritmo non è valido.

La completezza, d'altra parte, significa che l'algoritmo affronta tutti i possibili input e non ne manca nessuno. Quindi, se il mio algoritmo di ordinamento non ha mai restituito un elenco non ordinato, ma semplicemente si è rifiutato di lavorare su elenchi che contenevano il numero 7, non sarebbe completo.

È completo e valido se funziona su tutti gli input (valido semanticamente nel mondo del programma) e ottiene sempre la risposta giusta.

Trovo la risposta di Erik Dietrich un po 'confusa. Quanto segue è meglio:

Un algoritmo è suono se, ogni volta che restituisce una risposta, quella risposta è vera. Un algoritmo è completo se garantisce di restituire una risposta corretta per qualsiasi input arbitrario (o, se non esiste una risposta, garantisce di restituire un errore).

Due punti importanti:

1. La solidità è una garanzia debole. Non promette che A terminerà.
2. La solidità e la completezza sono concetti correlati; infatti sono il logico vicolo l'uno dell'altro. Ad esempio, la solidità dice che se viene restituita una risposta, la risposta è vera. Completezza dice che una risposta è vera se viene restituita.

Consideriamo per esempio un algoritmo di ordinamento A che riceve come input un elenco di numeri. Diciamo che A è valido se ogni volta restituisce un risultato che risulta essere una lista ordinata. Allo stesso modo, diciamo che A è completo se garantisce di restituire una lista ordinata ogni volta che gli diamo un elenco di numeri.

Questi termini derivano dalla teoria del calcolo, quindi sono più significativi nel contesto della teoria della computazione che nel contesto dell'ingegneria del software

Nella maggior parte dei modelli standard di computazione, i problemi di calcolo sono rappresentati come lingue . Una lingua è un insieme di stringhe. Un algoritmo, quindi, è solo un sistema o una procedura che decide se una determinata stringa è un membro di una lingua (restituendo vero o falso). In termini di ingegneria del software, la teoria computazionale riguarda specificamente le funzioni che assomigliano a questo, assumendo che le stringhe siano immutabili:

boolean some_function(string argument){...}

Chiamiamo questa funzione completa se restituisce true per ogni argomento che è un membro della lingua. Lo chiamiamo suono se restituisce false per ogni argomento che non è un membro della lingua.

In altre parole, è completo se restituisce sempre true quando vogliamo che venga restituito true, e suona se restituisce sempre false quando vogliamo che restituisca false.

Come si traduce in altri tipi di funzione? A quanto pare, è quasi sempre possibile inserire una quantità arbitraria di dati in una stringa e ricostituirla all'interno della funzione. Quindi la restrizione sul tipo di argomento e sull'arit non è altro che una semplificazione teorica. La restrizione sul tipo di reso è più importante, tuttavia. I problemi che richiedono un risultato booleano sono chiamati problemi di decisione . La maggior parte della teoria del calcolo comporta problemi decisionali; gli insiemi P e NP sono limitati ai problemi decisionali (e NP, almeno, non potrebbe essere ragionevolmente definito senza questa restrizione). Il problema dell'arresto è un altro esempio di un problema decisionale molto studiato.

È mia opinione che questi termini non siano generalizzati al di fuori del dominio dei problemi decisionali, quindi la differenza tra loro non è veramente significativa quando si discute di una funzione generale.

Ci sono risposte molto migliori alla SO . Fondamentalmente, si fornisce una raccolta di dati e criteri per la ricerca. Algoritmo sonoro ti cattura solo il pesce che corrisponde ai criteri ma potrebbe perdere alcuni elementi di dati. Algoritmo completo produce un superset dei risultati richiesti, il che significa che ricevi un po 'di spazzatura in cima ai risultati richiesti. L'algoritmo audio è più conservativo.

Lo statistico probabilmente direbbe che l'algoritmo sonoro è distorto di errori di tipo I di rimorchio (non accetta i candidati corretti), mentre l'algoritmo completo è distorto verso errori di tipo II (per accettare i falsi candidati).