Was ist das beste Buch zum Studium der diskreten Mathematik?

Konkrete Mathematik: Eine Grundlage für Informatik, von Donald Knuth höchstpersönlich!

Diskrete mathematische Kenntnisse sind erforderlich, um die Korrektheit zu beweisen und die Komplexität von Algorithmen und Datenstrukturen abzuleiten. Sie werden diese in Algo/DS-Büchern lernen, aber Sie können die mathematischen Kenntnisse nur erlangen, indem Sie nur diskrete Mathematik üben.

Knuth Buch ist dafür sehr gut geeignet. Aber meiner Meinung nach werden Sie es nur brauchen, wenn Sie fortgeschrittene Beweise in DS/Algorithmen durchführen.

Für einen Anfänger wäre es großartig, „Grimaldi“ http://www.amazon.com/Discrete-Combinatorial-Mathematics-Applied-Introduction/dp/0201199122 durchzugehen und dann schnell zu Algorithmen überzugehen.

Andernfalls werden Sie weiterhin tief in die diskrete Mathematik einsteigen und nie zu Algorithmen/DS gelangen.

Denken Sie daran, dass Discrete Math Ihnen nicht beibringt, wie man Algorithmen oder Datenstrukturen entwirft. Das wird nur durch das Üben von Algorithmusproblemen @ topcoder, acm icpc , spoj usw. und das Lesen von Büchern über Algos/DS oder Kurse darüber erreicht.

Meine 2 Cent.

Ein sehr gutes Lehrbuch für diskrete Mathematik im Grundstudium ist das Buch von Kenneth Rosen mit dem Titel Discrete Mathematics and Its Applications .

Das Buch bietet Lösungen für die Hälfte der Probleme. Sie können auch den Lösungsleitfaden für Schüler kaufen . Ich besitze es nicht, aber ich würde vermuten, dass es entweder die Antworten auf die andere Hälfte der Fragen oder eine Schritt-für-Schritt-Anleitung zur Lösung der Probleme enthält (das Buch bietet nur endgültige Antworten mit minimalen Erklärungen dieser Antworten ).

Es wird für die Zweiviertelsequenz in Diskreter Mathematik verwendet, die von Informatik- und Software-Engineering-Hauptfächern sowie einer Reihe von Mathematikprogrammen an meiner Universität belegt wird. Ich habe dieses Buch auch nach dem Kurs aufbewahrt und benutze es derzeit, um meine diskreten Mathematikkenntnisse für meine Prüfung zum Certified Software Development Associate aufzufrischen.

Es gibt viele verschiedene Bereiche der diskreten Mathematik und viele gute Bücher.

Es gibt Graph Theory von Diestel, das als kostenlose PDF-Version unter verfügbar ist

diestel-graph-theory.com

Es gibt eine Generierungsfunktion von Wilf, kostenlose PDF-Version unter

math.upenn.edu/~wilf/DownldGF.html

Andere gute Bücher sind Enumerative Combinatorics 1 und 2 von Richard P. Stanley (ein Buch, das so umfangreich ist, dass es hilfreich ist, jeweils mindestens 1 Analyse- und Algebra-Kurs zu haben).

Davon abgesehen würde ich vorschlagen, für einführendere Darstellungen in Bezug auf die erwartete mathematische Reife zu googeln und verschiedene Vorlesungsunterlagen der Art "Einführung in die Kombinatorik" oder "Mathematik für Informatiker" anzusehen. Ich fand, dass die Notizen zu "Mathematik für Informatiker" des MIT OCW ziemlich nett waren, als ich sie mir vor einigen Jahren ansah.

ocw.mit.edu/courses/electrical-engineering-and-informatik...

hat einen Link zu den Vorlesungsunterlagen. Es gibt einige wirklich lustige Seiten darin. Einer meiner Favoriten "... jeder, der das sagt, liegt falsch, und Sie sollten sich über ihn lustig machen, bis er weint".

Wenn Sie noch tiefer in die diskrete Mathematik / Kombinatorik eintauchen möchten, lohnt es sich, ein bisschen mathematische Grundlagen in anderen Bereichen der Mathematik aufzubauen. Komplexe Analysis, reelle Analysis (mindestens auf der Ebene von Baby Rudin und vielleicht sogar bis zur Funktionsanalyse), vielleicht etwas Wahrscheinlichkeit bis zur Formulierung der Maßtheorie und zumindest ein bisschen abstrakte Algebra. Dann können Sie sich Dinge wie die Kombinatorik zufälliger Prozesse ansehen (großartig für die Analyse randomisierter Algorithmen) und coole Probleme wie Perkolation betrachten.

Es gibt wahrscheinlich noch andere Dinge, die ich vorschlagen sollte, aber der Punkt ist, dass diskrete Mathematik ohne so viel Hintergrund zugänglich ist, Sie aber auch dafür belohnt werden, dass Sie diesen mathematischen Hintergrund mit einigen erstaunlich schönen Dingen bereichern, die 1) großartig und unterhaltsam sind 2) nützlich sind.

Ich mag die Diskrete Mathematik von Norman Biggs sehr . Die zweite Auflage würde ich nicht empfehlen. Holen Sie sich lieber die Erstausgabe (die "überarbeitete" Erstausgabe, wenn Sie können). Der Text behauptet, in sich geschlossen zu sein (scheint mir so).

Da es online zu dieser Ausgabe des Textes nicht viele Informationen gibt (die Vorschau auf Amazon ist die zweite Ausgabe), hier eine Übersicht:

Teil 1: Zahlen und Zählen

1. Ganze Zahlen (Ordnung, Rekursion, Induktion, Teilbarkeit, ggT, ​​Faktorisierung)
2. Funktion und Zählen (Surjektionen, Injektionen, Bijektionen, Schubfachprinzip, Endlich vs. Unendlich)
3. Zählprinzipien (Eulersche Funktion, Additionsprinzip, Wörter, Permutationen)
4. Teilmengen und Designs (binomiales Theorem, Siebprinzip, Designs,$t$-Designs)
5. Partition (Äquivalenzbeziehungen, Verteilungen, Multinomialzahlen, Klassifikation von Permutationen)
6. Modulare Arithmetik (Kongruenzen,$\mathbb{Z}_m$, zyklische Konstruktionen, lateinische Quadrate)

Teil 2: Graphen und Algorithmen:

1. Algorithmen und Effizienz (Beweis der Korrektheit,$O$Notation, Vergleich, Sortierung)
2. Graphen (Isomorphie von Graphen, Valenz, Pfade, Zyklen, Bäume, Färbung, Greedy-Algorithmus)
3. Bäume, Sortieren, Suchen (Blätter zählen, Sortieralgorithmen, Bäume aufspannen, MST-Problem, Depth-First, Width-First, Shortest-Path-Problem)
4. Bipartite Graphen (Relationen, Kantenfärbungen, Matchings, Maximum Matchings, Transversalen)
5. Digraphen, Netzwerke, Flüsse (kritische Pfade, Flüsse und Schnitte, Max-Flow-Min-Cut-Theorem, Beschriftungsalgorithmus)
6. Rekursive Techniken (lineare Rekursion, rekursive Halbierung, rekursive Optimierung, dynamische Programmierung)

Teil 3: Algebraische Methoden:

1. Gruppen (Axiome, Isomorphismen, zyklische Gruppen, Untergruppen, Nebenklassen)
2. Gruppen von Permutationen (Definitionen, Bahnen, Stabilisatoren, Größe/Anzahl der Bahnen, Darstellung von Gruppen durch Permutationen)
3. Ringe, Körper, Polynome (Divisionsalgorithmus, Euklidischer Algorithmus, Faktorisierung)
4. Endliche Körper (Ordnung, Konstruktion, Primitiv-Elemente-Satz, endliche Geometrie, projektive Ebenen, Existenz)
5. Fehlerkorrektur (Wörter, Codes, Fehler, lineare Codes, zyklische Codes)
6. Erzeugende Funktionen (Potenzreihen, Partialbrüche, Binomialsatz, lineare Rekursion)
7. Partitionen einer positiven ganzen Zahl (konjugierte Partitionen, erzeugende Funktionen, mysteriöse Identität)
8. Symmetrie und Zählen (zyklische und Diedersymmetrie, 3D-Symmetrie, ungleiche Färbungen, Färbungen und erzeugende Funktionen, Satz von Polya)

Ich mag Discrete Mathematics von Ross und Wright sehr:

Mathematisches Denken: Problemlösung und Beweise.

John P. D’Angelo, Douglas B. West.

Erhältlich bei Amazon .

Dies soll eine Einführung in mathematische Beweise sein. Als solche ist sie nicht auf diskrete Mathematik beschränkt. Aber es macht einen sehr guten Job für die diskrete Mathematik. Sie würden auch einige Beweise in der realen Analyse sehen; Sie können sich jedoch nur auf den diskreten Teil konzentrieren und dies ignorieren.

Sehr hilfreich fand ich das Buch Elements of Discrete Mathematics von CL Liu .

Es ist auf einem sehr einfachen Niveau und eignet sich hervorragend, wenn Sie nach einer Einführung in die diskrete Mathematik suchen.

Die besten Bücher soweit ich weiß sind diese beiden:

Diskrete Mathematik von Norman L. Biggs

oder

Diskrete Mathematik und ihre Anwendungen von Kenneth H. Rosen

Das beste Buch zum Studium der Diskreten Mathematik ist " Diskrete Mathematik und Strukturen " von Satinder Bal Gupta . Es wird von University Science Press herausgegeben . Die Sprache des Buches ist sehr einfach. Es enthielt Hunderte von gelösten und ungelösten Problemen mit Hinweisen.

Grundlagen diskreter mathematischer Strukturen, 3. Auflage. Es ist gemäß dem ACM-Curriculum geschrieben, enthält viele Fragen auf GATE-Ebene und wurde von einem Informatikprofessor geschrieben.