Quel thème en mathématiques discrètes est considéré comme une condition sine qua non pour le cours des structures de données?

Question

Je veux lire un livre sur les structures de données et algorithmes, mais je voudrais savoir s'il y a un sujet précis en mathématiques discrètes considéré comme très important en tant que condition préalable à la compréhension des documents présentés dans le livre de structure de données.

P.S Je suis programmeur autodidacte; Je ne l'ai pas suivi des cours de sciences informatiques.

Answer 1

« mathématiques discrètes » est plus un mot à la mode qui contient les bases d'une douzaine de sujets différents (logique, algorithmes, théorie du calcul, la théorie des nombres, la conception numérique, etc.) tous marginalement liés à la programmation. La lecture d'un livre de mathématiques discrètes serait à peu près la même chose que la lecture du premier chapitre ou deux des livres sur tous ces sujets.

La chose la plus essentielle est de comprendre la logique booléenne , que vous êtes probablement déjà assez bon si vous êtes autodidacte; algorithmes sont également très importants. La théorie des choses de calcul est assez intéressant, mais pas vraiment utile, sauf si vous êtes vraiment en algorithmes, ou si vous voulez écrire votre propre analyseur. La théorie des nombres est bon d'apprendre si vous voulez entrer dans la cryptographie.

Vous avez vraiment pas besoin de connaître l'une de ces choses à lire sur des structures de données.

Answer 2

L'induction mathématique est probablement la personne concept le plus important a encore mentionné. Il est essentiel de comprendre et de prouver les propriétés des algorithmes sur les arbres et d'autres structures de données définies inductivement.

BTW, le manuel classique sur ce sujet est Mathématiques Concrète: Fondation Informatique , par Ronald Graham, Donald Knuth, et Oren Patashnik.

Mais la vie est trop courte pour lire un manuel juste que vous pouvez lire si un manuel. Plongez. Si vous vous trouvez perdu, allez trouver l'arrière-plan dont vous avez besoin.

Answer 3

Allez-y et lisez les structures de données livre, vous serez très bien.

Answer 4

Certains sujets habituellement trouvés dans les livres de mathématiques discrètes d'introduction qui vous seront utiles dans un algorithmes / cours de structure de données sont:

1. Quelques probabilités statistiques de base /: utiles dans la compréhension et les algorithmes de hachage aléatoires
2. La plupart des livres de mathématiques discrètes ont un chapitre sur les graphiques et les concepts connexes, des choses comme le tri topologique, les relations, les commandes totales et partielles.
3. Définir la théorie et la logique formelle. Des outils essentiels dans le raisonnement sur l'exactitude et de la complexité des algorithmes

Il y a probablement quelques autres qui me échappent à ce moment. Cela fait un moment que je quitté le collège.

Cela dit, un bon livre structure de données / algorithme a souvent un ou deux chapitres d'introduction et sections dans la plupart des autres chapitres qui visent à amener le lecteur à la vitesse sur certains des sujets de mathématiques discrètes pertinentes. Mais l'OMI, il est préférable de connaître ce genre de choses juste pour avoir une compréhension plus approfondie, si vous avez le temps et l'inclinaison. Sinon, je ne pense pas que vous vous retrouvez coincé si vous avez un bon livre.

PS: Les sujets dont je parle sont de ces deux livres: « Mathématiques discrètes et combinatoires: Introduction appliquée » par Grimaldi « Mathématiques discrètes et ses applications » par Rosen ( « Math béton » est trop lourd à lire juste pour les structures de données)

Answer 5

Pour les structures de données et algorithmes Je pense que vous voulez la plupart du temps pour connaître le domaine de calcul liés à l'informatique des limites de la série. Ceci, à son tour, implique une certaine connaissance de l'algèbre.

Vous devez savoir comment calculer les limites de la série afin de pouvoir calculer la complexité de l'algorithme.

Answer 6

si vous êtes intéressé non seulement dans la structure de données, mais dans tous les domaines de l'informatique, les mathématiques discrètes comprennent l'algèbre de Boole et il est l'application qui est la base de l'architecture informatique et langage assembleur, mais je ne pense pas qu'il est lié aux structures de données et algorithmes