Come si "capisce" quando si tratta di prove?

Question

Quando iniziamo a entrare nella progettazione dell'algoritmo e in argomenti più discreti di informatica, finiamo per dover provare le cose tutto il tempo. Ogni volta che ho visto qualcuno chiedere come diventare veramente bravo a prove, la risposta comune (e forse pigra) è "pratica".

La pratica va bene se si hanno le nozioni di base, ma come si entra nel set mentale per prove matematiche? Quando è scattato l'induzione? Quali sono le risorse migliori per insegnare questi argomenti? Quali argomenti di base dovrebbero essere ricercati prima di dedicarsi alla prova scritta?

Answer 1

Non sono pigri, la pratica è l'unico modo. Prendi lezioni in cui devi fare prove e cerca online le note di classe e i vecchi test con le risposte di altre università che superano le prove.

Answer 2

Non ne ho idea. Probabilmente allo stesso modo in cui sei bravo a comporre musica.

Quando provo a dimostrare che non sto seguendo una strategia fissa, penso solo al problema. Poi [tempo indefinito] più tardi, la mia mente restituisce un risultato e salgo su per scriverlo.

Ma la pratica aiuta sicuramente. Quando ho iniziato a provare dichiarazioni estremamente semplici, come le leggi di DeMorgan, ero completamente senza speranza. Così mi sono seduto e ho fatto la cinquantina di problemi di esempio opzionali su un foglio di lavoro che ci è stato dato. Ora è naturale provare qualcosa.

Answer 3

Inizierò la mia risposta ammettendo che, come studente di CS, ho avuto un momento davvero difficile cogliere un modo formale di pensare, e non è mai facile, a meno che non si abbia un talento per questo.

Temo che non ci sia una risposta migliore di pratica e studio.

Un modo formale di approccio matematico e algoritmico e problemi di visione è un'abilità che richiede innanzitutto una comprensione molto profonda delle materie trattate. Secondo, richiede una buona conoscenza delle prove esistenti. Cerca di immaginare te stesso come alcuni dei grandi scienziati che hanno elaborato gli algoritmi che stai studiando. Comprendi come avresti provato ad affrontare quel problema specifico. Poi vedi come hanno dimostrato la correttezza del loro algoritmo.

Posso solo raccomandare il miglior libro di testo in questo argomento che è Intro to Algorithms by CLRS. Se lo attraversi dall'inizio alla fine, incluso ogni esercizio, lo sarà migliorare le tue abilità.

Answer 4

Si entra nella mente per fare prove matematiche diventando un matematico. Non intendo l'ultima affermazione in modo tautologico, ma mi rendo conto che una dimostrazione matematica, come pubblicata in un diario matematico, è qualcosa di un artefatto retorico; cioè, è una prova perché un corpo di matematici concorda che è una prova. Idealmente, gli argomenti nella dimostrazione potrebbero essere tutti ridotti alla logica simbolica, ma questo non è il modo in cui viene fatto nella pratica. Il completo fallimento delle dimostrazioni generate dal computer a fare matematica preziosa fornisce alcune prove a riguardo.

Mi metto nella mente facendo prove e accettandole da altri matematici. Sono d'accordo con gli altri che la "pratica" è essenziale. Non fai prove a meno che non provi, provi e provi. Spesso la luce si alza lentamente.

Le migliori risorse sono, naturalmente, altri matematici e prove di lettura. Ci sono pochissimi, se ce ne sono, che possono fare vere dimostrazioni matematiche senza far parte della comunità matematica.

Answer 5

Ho paura che "pratica" sia davvero la migliore risposta qui.

È molto simile alla programmazione: una volta capito, è possibile trovare schemi che risolvono i problemi in modo particolare e creare un'immagine del design di alto livello di nuovi sistemi che non sono mai stati implementati in precedenza. Tuttavia, i programmatori neofiti non sono a conoscenza dei modelli: attaccano il codice finché non inciampano accidentalmente su una soluzione che sembra "funzionare".

Quando ti viene dato un problema da dimostrare, di solito puoi identificare le proprietà ("Ho un insieme di oggetti distinti?", "Sto generando permute?", "Sto cercando di minimizzare/massimizzare qualche valore ?", eccetera). Presto o tardi, le prove si raggrupperanno in un gruppo vagamente simile, dove le tecniche utilizzate per risolvere un problema possono facilmente applicarsi a nuove varianti.

Letture consigliate:

• The Algorithm Design Manual da Steven Skiena.

Answer 6

La pratica è davvero l'unico modo, ma può essere aiutato anche da leggendo le prove. Non toccherò sulla pratica perché gli altri rispondenti hanno coperto tutto ciò a cui riesco a pensare, quindi parlerò solo di ciò che intendo leggendo.

Ai libri di testo piace molto scrivere le prove "importanti". È molto bello, perché spesso dimostrano affermazioni molto potenti e sono davvero fantasiosi. Ma proprio come non dovresti imparare ad essere una ginnasta di livello mondiale dal primo giorno emulando un olimpionico (come in, probabilmente ti romperesti la spina dorsale), non dovresti leggere nessuna prova veramente grande (all'inizio). Ciò che ho trovato è stato utile leggendo le bozze più piccole, di solito dai compiti a casa tornati (presumo che tu sia uno studente) o occasionalmente un libro di testo che sogna.

Il motivo per cui penso che la lettura di bozze è utile è perché ci sono una piccola serie di "trucchi" o "idee" che costituiscono enormi pezzi di prove scolastici, e anche quelli più avanzati. qualità struttura dei dati e relazioni di ricorrenza di solito comportano pensando correlate a prova per induzione, prove che coinvolgono computabilità con macchine a stati finiti a volte usano il principio pigeonhole, e più raramente l'idea di diagonalizzazione (molto frequente, non ti preoccupare esso). E, naturalmente, quasi ogni altra prova utilizza prova per contraddizione. Sono sicuro che ci sono altri strumenti utili che mi sono sfuggiti di mente, ma spero che tu abbia l'idea.

Capire quando, come e perché si affronta un problema con un metodo particolare o un altro è ciò che richiede pratica ed esperienza. Suggerisco di leggere le prove oltre alla pratica perché spesso può mostrarti modi creativi di usare un metodo di prova che hai già incontrato.

Come nota finale, cerca di ricordare quando hai imparato a programmare. Come sei migliorato? Dimostrare cose e programmare cose non sono troppo dissimili, secondo me. :)

Answer 7

La pratica e lo studio hanno perfettamente senso, concordato. Alcuni trucchi, che ho trovato utili:

1. Prendere appunti su tutto ciò che si studia (ho provato solo a leggere libri - un sacco di materiale appena passato).
2. In aggiunta al punto precedente: fare tutte le prove (o la maggior parte) da soli, utilizzare le note di libri/lezioni come guida; molte prove contengono frasi come "possiamo vedere ora, che XXX". E XXX non è sempre una conclusione banale.
3. Fare esercizi; per esempio, nel libro CLRS ci sono dozzine di esercizi. Esercizi sono un buon modo per ottenere le idee dietro gli algoritmi/prove corrette.
4. Se si desidera comprendere meglio i componenti interni dell'algoritmo, prendere in considerazione la partecipazione a concorsi di programmazione online come UVa's.