Εισαγωγή στα Διακριτά Μαθηματικά

Το παρόν βιβλίο, «Εισαγωγή στα Διακριτά Μαθηματικά», απευθύνεται κυρίως στους φοιτητές των τμημάτων Πληροφορικής, καθώς και άλλων τμημάτων, στα οποία διδάσκεται η Επιστήμη της Πληροφορικής, όπως και σε κάθε ενδιαφερόμενο για το αντικείμενο των Διακριτών Μαθηματικών.
Το βιβλίο είναι ο καρπός της διδασκαλίας μου στο Τμήμα Πληροφορικής του ΑΤΕΙ Θεσσαλονίκης, από την ίδρυσή του (1987) μέχρι το 2011.

Οι στόχοι του βιβλίου αποβλέπουν:
1. Στη διεύρυνση της μαθηματικής ωριμότητας των φοιτητών κατά τη διάρκεια της μελέτης μιας επιστημονικής περιοχής, η οποία είναι αρκετά διαφορετική από την παραδοσιακή κάλυψη στο βασικό Λογισμό.
2. Στη μελέτη μεθόδων και τεχνικών για να μπορεί ο φοιτητής να επιλύει προβλήματα που εμφανίζονται σε διάφορα πεδία στην επιστήμη των υπολογιστών.
3. Στην ανάπτυξη των ικανοτήτων των φοιτητών για τη δημιουργία και την επίλυση τέτοιων προβλημάτων, την ερμηνεία των λύσεών τους καθώς και τον τρόπο εφαρμογής τους.

Το βιβλίο περιλαμβάνει οκτώ κεφάλαια, τα οποία περιέχουν τα βασικά θέματα διδασκαλίας των Διακριτών Μαθηματικών που καλύπτουν το χρονικό διάστημα ενός εξαμήνου. Αυτά είναι:
• βασικά θέματα Άλγεβρας της Λογικής,
• εισαγωγή στη Θεωρία Συνόλων και στην Άλγεβρα Boole με αναφορά στα λογικά κυκλώματα και κυκλώματα διακοπτών,
• θέματα από τη Θεωρία Αριθμών,
• βασικοί κανόνες Απαρίθμησης με εισαγωγή στη Συνδυαστική Ανάλυση,
• Διακριτές Αριθμητικές Συναρτήσεις και Γεννήτριες Συναρτήσεων
• Αναδρομικές Σχέσεις,
• ευρεία εισαγωγή στη Θεωρία Γραφημάτων,
• στοιχεία από τα Δένδρα με περιγραφή των βασικών αλγορίθμων Dijkstra, Kruskal κ.λπ.

Σε κάθε κεφάλαιο υπάρχουν αρκετά λυμένα παραδείγματα. Επίσης κάθε κεφάλαιο συνοδεύεται από ικανό αριθμό άλυτων ασκήσεων. Συνολικά τα λυμένα παραδείγματα και οι άλυτες ασκήσεις είναι (περίπου) 350 και 220 αντίστοιχα.
Σημειώνεται ότι κάθε επιστημονικός όρος συνοδεύεται από την αντίστοιχη αγγλική έκφραση, έτσι ώστε ο αναγνώστης να έχει ευκολότερη πρόσβαση στη διεθνή βιβλιογραφία.

Περιεχόμενα

ΚΕΦΑΛΑΙΟ 1
Στοιχεία από την Άλγεβρα της Λογικής

1.1. Η Πρόταση – Λογικές Πράξεις

1. Η Πρόταση

2. Λογικές Πράξεις

3. Προτασιακές Παραστάσεις – Πολυώνυμα Boole

4. Ταυτολογία – Αντίφαση

5. Λογική ισοδυναμία

6. Λογική επαγωγή

Ασκήσεις

ΚΕΦΑΛΑΙΟ 2
Στοιχεία Θεωρίας Συνόλων και Άλγεβρας Boole

2.1. Στοιχεία θεωρίας συνόλων

1. Η Έννοια και η Παράσταση του Συνόλου

2. Πράξεις στα Σύνολα

3. Διατεταγμένα Ζεύγη – Καρτεσιανό Γινόμενο Συνόλων

4. Αντιστοιχίσεις – Συναρτήσεις

5. Ισοδύναμα Σύνολα – Αριθμήσιμα Σύνολα

6. Σχέσεις

7. Διατεταγμένα Σύνολα

2.2. Στοιχεία από την Άλγεβρα Boole

1. Δυαδικές Πράξεις

2. Άλγεβρα Boole

3. Λογικά Κυκλώματα – Κυκλώματα διακοπτών

Ασκήσεις

ΚΕΦΑΛΑΙΟ 3
Στοιχεία Θεωρίας Αριθμών

3.1. Η Μαθηματική Επαγωγή

3.2. Διαιρετότητα

3.3. Πρώτοι αριθμοί

3.4. Ισοδυναμία modulo m | Ισοϋπόλοιποι αριθμοί

3.5. Μέγιστος Κοινός Διαιρέτης – Ελάχιστο Κοινό Πολλαπλάσιο

1. Μέγιστος κοινός διαιρέτης | Ιδιότητες του ΜΚΔ | Μέθοδοι υπολογισμού του ΜΚΔ

2. Ελάχιστο κοινό πολλαπλάσιο

Ασκήσεις

ΚΕΦΑΛΑΙΟ 4
Συνδυαστική Aνάλυση

4.1. Βασικοί κανόνες απαρίθμησης

1. Κανόνας αθροίσματος

2. Κανόνας γινομένου

4.2. Διατάξεις – Μεταθέσεις – Συνδυασμοί

1. Διατάξεις – Μεταθέσεις

2. Συνδυασμοί

4.3. Κατανομή σφαιρών σε διακριτές υποδοχές

1. Κατανομή διακριτών σφαιρών

2. Κατανομή μη διακριτών σφαιρών

4.4. Διαμέριση συνόλων

4.5. Διωνυμικοί – Πολυωνυμικοί συντελεστές

1. Διωνυμικοί Συντελεστές

2. Πολυωνυμικοί συντελεστές

Ασκήσεις

ΚΕΦΑΛΑΙΟ 5
Γεννήτριες Συναρτήσεων

5.1. Αριθμητικές Συναρτήσεις

5.2. Συνήθεις Γεννήτριες Συναρτήσεων

1. Ιδιότητες των Γεννητριών Συναρτήσεων

5.3. Εκθετικές Γεννήτριες Συναρτήσεων

5.4. Εφαρμογές των Γεννητριών Συναρτήσεων

1. Συνήθεις Γεννήτριες Συναρτήσεων

2. Εκθετικές Γεννήτριες Συναρτήσεων

Ασκήσεις

ΚΕΦΑΛΑΙΟ 6
Αναδρομικές Σχέσεις

6.1. Ορισμός της Αναδρομικής Σχέσης

6.2. Γραμμικές Αναδρομικές Σχέσεις 1ης Τάξης με Σταθερούς Συντελεστές

6.3. Γραμμικές αναδρομικές σχέσεις 2ης και ανώτερης τάξης με σταθερούς συντελεστές

1. Η ομογενής λύση

2. Η Μερική Λύση

3. Η γενική (ολική) λύση

6.4. Λύση των γραμμικών αναδρομικών σχέσεων με τη χρήση γεννητριών συναρτήσεων

Ασκήσεις

ΚΕΦΑΛΑΙΟ 7
Θεωρία Γραφημάτων

7.1. Γενικοί ορισμοί

7.2. Ορισμός του γραφήματος

1. Μη Κατευθυνόμενα Γραφήματα

2. Κατευθυνόμενα Γραφήματα

7.3. Βαθμός κορυφής

7.4. Δρόμοι

7.5. Συνεκτικά γραφήματα

7.6. Υπογραφήματα

7.7. Ειδικά γραφήματα

7.8. Ισομορφισμός – ομοιομορφισμός στα γραφήματα

1. Γραφήματα με σήμανση

2. Ισομορφισμός

3. Ομοιομορφισμός

7.9. Γραφήματα Euler

7.10. Γραφήματα Hamilton

7.11. Επίπεδα γραφήματα

7.12. Γραφήματα και πίνακες

1. Οι πίνακες Γειτνίασης και Πρόσπτωσης

Ασκήσεις

ΚΕΦΑΛΑΙΟ 8
Στοιχεία από τα Δένδρα

8.1. Ορισμός του Δένδρου

8.2. Παράγοντα Δένδρα

8.3. Γραφήματα με Βάρος

1. Εύρεση του Ελάχιστου παράγοντος Δένδρου – Ο αλγόριθμος του Kruskal

2. Εύρεση της Ελάχιστης Διαδρομής – Ο αλγόριθμος του Dijkstra

8.4. Ριζωμένα Δένδρα

1. Διατεταγμένα ριζωμένα δένδρα

8.5. Δυαδικά Δένδρα

1. Δυαδική αναζήτηση

2. Δυαδικά δένδρα αναζήτησης

Ασκήσεις

Παράρτημα 1. Λύσεις – Απαντήσεις των ασκήσεων
Παράρτημα 2. Υπόδειγμα λύσης άσκησης γεννητριών συναρτήσεων (Κεφ. 5)
Παράρτημα 3. Η Απόδειξη του θεωρήματος 8.2

Βιβλιογραφία

Ευρετήριο Ελληνοαγγλικής Ορολογίας