22
Ho visto il riferimento alle prove di copia e incolla in alcuni testi di algoritmi. qual è l'idea principale di tali prove? e come faccio a usarli per dimostrare qualcosa?Che cos'è una prova di copia e incolla?
A
risposta
15
Il termine "taglia e incolla" si presenta negli algoritmi a volte quando si esegue la programmazione dinamica (e anche altre cose, ma è lì che l'ho visto per la prima volta). L'idea è che, per utilizzare la programmazione dinamica, il problema che si sta tentando di risolvere abbia probabilmente una sorta di ridondanza sottostante. Si utilizza una tabella o una tecnica simile per evitare di risolvere gli stessi problemi di ottimizzazione più e più volte. Naturalmente, prima di iniziare a provare a utilizzare la programmazione dinamica, sarebbe bello provare che il problema ha questa ridondanza, altrimenti non si otterrà nulla usando una tabella. Questa viene spesso definita proprietà "sottoproblema ottimale" (ad esempio, in CLRS).
La tecnica "taglia e incolla" è un modo per dimostrare che un problema ha questa proprietà. In particolare, vuoi dimostrare che quando trovi una soluzione ottimale a un problema, hai necessariamente utilizzato soluzioni ottimali per i sottoproblemi costituenti. La dimostrazione è per contraddizione. Supponiamo di aver trovato una soluzione ottimale a un problema utilizzando soluzioni subottimali a sottoproblemi. Quindi, se dovessi sostituire ("tagliare") quelle soluzioni subproblem subottimali con soluzioni di sottoproblem ottimali ("incollandole"), miglioreresti la soluzione ottimale. Ma poiché la tua soluzione era ottimale per ipotesi, hai una contraddizione. Ci sono altri passaggi coinvolti in tale prova, ma questa è la parte "taglia e incolla".
1
Cut-and-Paste è un modo utilizzato per la verifica dei concetti di teoria dei grafi, Idea è questa: si supponga di avere una soluzione per il problema A, si vuole dire qualche spigolo/nodo, dovrebbe essere disponibile in soluzione. Assumerai di avere una soluzione senza edge/node specificato, proverai a ricostruire una soluzione tagliando un edge/node e incollando edge/node specificato e affermerai che il nuovo vantaggio della soluzione è almeno uguale a quello della soluzione precedente.
Uno dei campioni più importanti sta dimostrando gli attributi MST (dimostrando che la scelta avida è abbastanza buona). vedi presentation on MST from CLRS book.
0
'taglia e incolla' tecnica può essere usata per provare entrambi correttezza delle algoritmo greedy (sia la struttura ottimale e proprietà avido scelta' e dinamico correttezza algoritmo di programmazione.
avido correttezza
La conferenza osserva Correctness of MST da MIT 2005 mostre classe algoritmo undergrad 'taglia-e-incolla' tecnica per dimostrare sia la struttura ottimale e proprietà avido scelta.
Questo dispense Correctness of MST da MIT 6.046J/18.410J molla 2015 uso 'taglia-e -paste 'tecnica per dimostrare gr eedy-scelta proprietà
Programmazione Dinamica Correttezza
Una spiegazione più autentico per 'taglia-e-incolla' è stata introdotta nel CLRS (3 ° Edtion) Capitolo 15.3 Elemento di programmazione dinamica a pagina 379
"4 . Dimostrate che le soluzioni ai sottoproblemi utilizzati all'interno della soluzione ottimale al problema devono essere ottimali utilizzando una tecnica "taglia e incolla" , facendo ciò supponendo che ciascuna delle soluzioni dei sottoproblemi non sia ottimale e quindi derivando una contraddizione. In particolare, "estrapolando" la soluzione di subproblem non ottimale e "incollando" quella ottimale, si dimostra che è possibile ottenere una soluzione migliore al problema originale, contraddicendo quindi la propria ipotesi di avere già una soluzione ottimale. Se c'è più di un sottoproblema, sono in genere così simili che l'argomento "copia e incolla" per uno può essere modificato per gli altri con poco sforzo."
0
Dimostrazione per contraddizione
P viene considerato falso, che è! P è vera.
è dimostrato che! P implica due affermazioni contraddittorie, Q e! Q.
Poiché Q e! Q non possono essere entrambi vere, l'ipotesi che P sia falsa deve essere errata e P deve essere vera
Perché il voto negativo e voti da chiudere? –
Non capisco perché questa non è una vera domanda. Ho incontrato prove di copia e incolla in più posizioni nei testi dell'algoritmo. In che modo questa domanda è diventata "" ambigua, vaga, incompleta, eccessivamente ampia o retorica e non si può ragionevolmente rispondere "" ?? @Cameron ha anche fornito una buona spiegazione sull'essenza di una tale dimostrazione alla programmazione dinamica. –