Διακριτά μαθηματικά

Abstract

Στο παρόν βιβλίο περιλαμβάνεται υλικό που υπερκαλύπτει ένα συνηθισμένο μάθημα "Διακριτών Μαθηματικών" όπως το επιλέγουν φοιτητές σε τμήματα Πληροφορικής κυρίως. Ξεκινά με τις βασικές έννοιες της Θεωρίας Συνόλων και της Λογικής, σε επίπεδο περισσότερο της γνώσης της γλώσσας και της ορολογίας στους δύο αυτούς τομείς (που επιτρέπει την ευκολότερη χρήση τους μετέπειτα στο μάθημα) και χωρίς ιδιαίτερη έμφαση σε δύσκολα θεωρήματα (θα δειχθεί όμως η έννοια του διαγώνιου επιχειρήματος που χρησιμεύει και στην έννοια της αριθμησιμότητας, αλλά και της υπολογισιμότητας). Ακολουθούν κάποιες βασικές έννοιες της Θεωρίας Αριθμών (διαιρετότητα, ανάλυση σε πρώτους, αλγόριθμος Ευκλείδη, υπολογισμοί με υπόλοιπα). Οι έννοιες και τεχνικές απαρίθμησης στη Συνδυαστική καταλαμβάνουν την πρώτη σημαντική ενότητα του μαθήματος και ακολουθούνται από την επόμενη ενότητα που είναι οι κεντρικές έννοιες της Θεωρίας Γραφημάτων (βαθμοί, συνεκτικότητα, χρωματισμοί, διμερή γραφήματα, ταιριάσματα σε διμερή γραφήματα και δυϊσμός, δέντρα, βασικοί αλγόριθμοι). Μετά την εισαγωγή στη συνδυαστική απαρίθμηση εισάγεται η έννοια της διακριτής Πιθανότητας, οι τυχαίες μεταβλητές και η μέση τιμή τους, που μας δίνουν τη δυνατότητα να δώσουμε πολλές εφαρμογές σε μη πιθανοθεωρητικά (και αλγοριθμικά) προβλήματα. Ως επιπλέον υλικό περιλαμβάνονται στοιχεία της θεωρίας τυπικών γλωσσών: κανονικές γλώσσες, αυτόματα ντετερμινιστικά και μη, αλγόριθμοι για αυτόματα). Το υλικό αυτό πρέπει να θεωρηθεί ως εκτός του βασικού μαθήματος Διακριτών Μαθηματικών και ως επιπλέον υλικό στο οποίο μπορεί να κινηθεί ο διδάσκων αν οι συνθήκες το επιτρέπουν ή ανάγκες το απαιτούν.

This book includes material that goes beyond a typical "Discrete Mathematics" course usually taken by Computer Science students. It begins with basic concepts of Set Theory and Logic, at a level that facilitates their later use in the course, without focusing on difficult theorems (though the diagonal argument is discussed for countability and computability). It then covers fundamental Number Theory concepts such as divisibility, prime factorization, the Euclidean algorithm, and modular arithmetic. The first major section focuses on enumeration techniques in Combinatorics, followed by core Graph Theory topics like degrees, connectivity, coloring, bipartite graphs, matchings and duality, trees, and basic algorithms. After combinatorics, it introduces discrete probability, random variables, and expected values, which support applications to non-probabilistic and algorithmic problems. Additional material includes formal language theory: regular languages, deterministic and non-deterministic automata, and automata algorithms. This extra content lies beyond the core Discrete Mathematics course and is used depending on teaching needs and available time.