Discrete Mathematics

Abstract

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

This book will include material that goes beyond a typical "Discrete Mathematics" course as mostly taken by students in Computer Science departments. It will start with the basic concepts of Set Theory and Logic, to a level which will allow their easier use later in the course)and without particular emphasis on difficult theorems (but the diagonal argument that serves both the concept of countability and computability will be discussed). Some basic concepts of Number Theory will follow (divisibility, analysis into primes, Euclidean algorithm, calculations with remainders). Concepts and techniques of enumeration in Combinatorics occupy the first important section of the course and are followed by the next section which are the central concepts of Graph theory (degrees, connectivity, colorings, bipartite graphs, matchings in bipartite graphs and duality, trees, basic algorithms).After the introduction to combinatorial enumeration, the concept of discrete probability, random variables and their mean value are introduced which enable us to give many applications to non-probabilistic (and algorithmic) problems. Additional material includes elements of the theory of formal languages: regular languages, deterministic and non-deterministic automata, algorithms for automata. This material must be considered as outside the basic course of Discrete Mathematics and as additional material to which the teacher can move if circumstances allow it or needs require it.