Quale argomento in Matematica Discreta è considerato come un prerequisito per il corso strutture di dati?

Question

Voglio leggere un libro su strutture dati e algoritmi, ma mi piacerebbe sapere se c'è qualche argomento specifico in matematica discreta considerata molto importante come prerequisito per la comprensione dei materiali presentati in struttura di dati libro.

P.S Sono programmatore autodidatta; Non ho preso alcun corso di informatica.

Answer 1

"matematica discreta" è più uno slogan che contiene i principi fondamentali da una dozzina di diversi argomenti (logica, algoritmi, teoria della computazione, teoria dei numeri, digital design, ecc) tutto marginalmente legati alla programmazione. La lettura di un libro di matematica discreta sarebbe più o meno come la lettura del primo capitolo o due di libri su tutti questi argomenti.

La cosa più importante da capire è la logica booleana , che si è probabilmente già abbastanza bravo, se sei autodidatta; algoritmi sono molto importanti. La teoria della computazione roba è abbastanza interessante, ma non molto utile se non sei davvero in algoritmi, o volete scrivere il proprio parser. teoria dei numeri è bene imparare se si vuole entrare in crittografia.

Non si ha realmente bisogno di sapere qualsiasi di queste cose leggere di strutture di dati.

Answer 2

Induzione matematica è probabilmente il concetto più importante nessuno ha ancora citato. È essenziale per la comprensione e dimostrare le proprietà di algoritmi su alberi e altre strutture di dati definiti induttivamente.

A proposito, il classico libro di testo su questo argomento è Concrete Mathematics: A Foundation for Computer Science , da Ronald Graham, Donald Knuth, e Oren Patashnik.

Ma la vita è troppo breve per leggere un libro di testo solo così si può leggere un libro di testo. Dive in. Se vi trovate perso, andare a trovare lo sfondo è necessario.

Answer 3

andare avanti e leggere il libro strutture di dati, andrà tutto bene.

Answer 4

Alcuni argomenti di solito si trovano in introduttivi libri di matematica discreta che vengono in aiuto in un corso di algoritmi / struttura dati sono:

1. Alcuni di base di probabilità / statistiche: utile per la comprensione di hashing e algoritmi randomizzati
2. La maggior parte dei libri di matematica discreta hanno un capitolo sui grafici e concetti correlati, cose come ordinamento topologico, le relazioni, parziale e ordini totali.
3. Imposta la teoria e la logica formale:. Strumenti essenziali nel ragionamento circa la correttezza e la complessità degli algoritmi

Ci sono probabilmente pochi altri che mi sfuggono in questo momento. E 'stato un po' da quando ho lasciato il college.

Detto questo, un buon libro di dati-struttura / algoritmo ha spesso uno o due capitoli introduttivi e sezioni in maggior parte degli altri capitoli che hanno lo scopo di portare il lettore fino a velocità su alcune delle rilevanti argomenti di matematica discreta. Ma IMO, è meglio sapere queste cose solo per avere una conoscenza più approfondita, se avete tempo e voglia. In caso contrario, non credo che vi troverete bloccato se si dispone di un buon libro.

PS: Gli argomenti che ho citato sono da questi due libri: "discrete e combinatoria Matematica: An Introduction Applicata" di Grimaldi "Matematica Discreta e le sue applicazioni" di Rosen ( "Concrete Math" è troppo pesante da leggere solo per strutture di dati)

Answer 5

Per le strutture e gli algoritmi di dati Penso che la maggior parte vuole di conoscere il territorio del calcolo relativo al calcolo dei limiti di serie. Questo, a sua volta, comporta una certa conoscenza di Algebra.

Hai bisogno di sapere come calcolare i limiti della serie in modo da essere in grado di calcolare l'algoritmo di complessità.

Answer 6

se siete interessati, non solo nella struttura dati, ma in tutti i campi di informatica, matematica discreta includono algebra booleana ed è un'applicazione che è alla base della architettura del computer e il linguaggio assembly, ma io non credo che è legato alle strutture di dati e algoritmi