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

.

Διακριτά μαθηματικά ονομάζεται η μελέτη μαθηματικών δομών που είναι θεμελιωδώς διακριτές αντί για συνεχείς. Σε αντίθεση με τους πραγματικούς αριθμούς που έχουν την ιδιότητα να "μεταβάλλονται ομαλά", τα αντικείμενα που μελετώνται στα διακριτά μαθηματικά - όπως οι ακέραιοι, οι γράφοι και οι προτάσεις της λογικής[1] – δεν μεταβάλλονται ομαλά κατά αυτόν τον τρόπο, αλλά έχουν ξεχωριστές, διακριτές τιμές.[2] Τα διακριτά μαθηματικά επομένως αποκλείουν θέματα των "συνεχών μαθηματικών", όπως ο απειροστικός λογισμός και η ανάλυση. Συχνά τα διακριτά αντικείμενα μπορούν να απαριθμηθούν με βάση τους ακέραιους. Τυπικότερα, τα διακριτά μαθηματικά έχουν χαρακτηριστεί ως ο κλάδος των μαθηματικών που ασχολείται με αριθμήσιμα σύνολα[3] (σύνολα που έχουν την ίδια πληθικότητα με τα υποσύνολα των φυσικών αριθμών, συμπεριλαμβανομένων των ρητών αριθμών αλλά όχι και των πραγματικών αριθμών). Όμως, δεν υπάρχει κάποιος ακριβής και καθολικά αποδεκτός ορισμός του όρου "διακριτά μαθηματικά."[4] Στην πράξη τα διακριτά μαθηματικά περιγράφονται λιγότερο από το τι περιέχουν και περισσότερο με βάση τι δεν περιέχουν: συνεχείς μεταβλητές και σχετικές με αυτές έννοιες.

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

Η έρευνα στα διακριτά μαθηματικά αναπτύχθηκε πολύ γρήγορα στο δεύτερο μισό του εικοστού αιώνα, εν μέρει λόγω της ανάπτυξης των ψηφιακών υπολογιστών, οι οποίοι λειτουργούν σε διακριτά βήματα και αποθηκεύουν τα δεδομένα τους σε διακριτά bits. Οι έννοιες και ο μαθηματικός συμβολισμός των διακριτών μαθηματικών χρησιμεύουν στη μελέτη και την περιγραφή αντικειμένων και προβλημάτων διάφορων κλάδων της επιστήμης υπολογιστών, όπως οι υπολογιστικοί αλγόριθμοι, οι γλώσσες προγραμματισμού, η κρυπτογραφία, η αυτοματοποιημένη απόδειξη θεωρημάτων και η ανάπτυξη λογισμικού. Από την άλλη πλευρά, υλοποιήσεις σε υπολογιστές εφαρμόζουν τις ιδέες των διακριτών μαθηματικών σε πραγματικά προβλήματα, όπως στην επιχειρησιακή έρευνα.

Αν και τα βασικά αντικείμενα που μελετώνται στα διακριτά μαθηματικά είναι διακριτά αντικείμενα, για την απόδειξη θεωρημάτων κάποιες φορές χρησιμοποιούνται συναρτήσεις και ιδιότητες των πραγματικών ή ακόμη και των μιγαδικών αριθμών.

Οι μεγάλες προκλήσεις, παρελθόν και παρόν
Ένα μεγάλο μέρος της θεωρίας γράφων αναπτύχθηκε κατά την προσπάθεια να αποδειχθεί το θεώρημα των τεσσάρων χρωμάτων. Μετά από πλήθος αποτυχημένων προσπαθειών, το θεώρημα τελικά αποδείχθηκε από τους Kenneth Appel και Wolfgang Haken το 1976.[5]

Η ιστορία των διακριτών μαθηματικών περιέχει αρκετά προβλήματα-προκλήσεις που εστίασαν σε συγκεκριμένες περιοχές του πεδίου. Στη θεωρία γράφων, σημαντική έρευνα ασχολήθηκε με προσπάθειες να αποδειχτεί το θεώρημα των τεσσάρων χρωμάτων, το οποίο αρχικά διατυπώθηκε το 1852, αλλά δεν αποδείχτηκε μέχρι το 1976 (από τον Kenneth Appel και τον Wolfgang Haken, χρησιμοποιώντας αρκετή υπολογιστική βοήθεια).[5]

Το 1900, ο Γερμανός μαθηματικός Ντάβιντ Χίλμπερτ πρότεινε μια σειρά ανοικτών ερωτημάτων ως τις σημαντικότερες προκλήσεις στα μαθηματικά για την εποχή του. Αυτή είναι τα λεγόμενα προβλήματα του Χίλμπερτ, πολλά από τα οποία έχουν μέχρι σήμερα επιλυθεί. Σε αυτά περιλαμβάνονται και προβλήματα από τα διακριτά μαθηματικά όπως το δεύτερο πρόβλημα το οποίο ρωτάει αν τα αξιώματα της αριθμητικής Πεάνο, αριθμητικής πάνω στους φυσικούς αριθμούς, είναι συνεπή. Ο επίσης Γερμανός Κουρτ Γκέντελ απέδειξε το 1931 με το δεύτερο θεώρημα μη-πληρότητας ότι αυτό δεν ισχύει. Ένα άλλο διάσημο πρόβλημα από τα διακριτά μαθηματικά είναι το δέκατο πρόβλημα του Χίλμπερτ το οποίο ζητούσε να βρεθεί μια γενική διαδικασία που θα μπορεί να ελέγχει αν μια οποιαδήποτε διοφαντική εξίσωση είναι επιλύσιμη. Διοφαντική εξίσωση λέγεται γενικώς ένα σύστημα πολυωνύμων με ακέραιους συντελεστές, ορισμένο στο σύνολο των ακεραίων. Το 1970 ο Yuri Matiyasevich απέδειξε ότι μια τέτοια διαδικασία δεν υπάρχει. Τα παραπάνω είναι ενδεικτικά της δυσκολίας και πολυπλοκότητας που μπορεί να συναντήσει κανείς προσπαθώντας να επιλύσει προβλήματα διακριτών μαθηματικών.

Η ανάγκη κρυπτανάλυσης των Γερμανικών κωδίκων κατά το Δεύτερο Παγκόσμιο Πόλεμο οδήγησε σε ανάπτυξη της κρυπτογραφίας και της θεωρητικής πληροφορικής, με τον πρώτο προγραμματιζόμενο ψηφιακό ηλεκτρονικό υπολογιστή να αναπτύσσεται στο Bletchley Park της Αγγλίας. Την ίδια περίοδο, οι στρατιωτικές ανάγκες οδήγησαν σε ανάπτυξη της επιχειρησιακής έρευνας. Η κρυπτογραφία παρέμεινε σημαντική κατά τον Ψυχρό Πόλεμο, με την εμφάνιση νέων τεχνικών, όπως η κρυπτογραφία δημόσιου κλειδιού. Η επιχειρησιακή έρευνα συνέχισε να είναι σημαντικό εργαλείο στις επιχειρήσεις και στη διαχείριση έργου (project management), με τη μέθοδο κρίσιμου δρόμου (critical path method), η οποία αναπτύχθηκε κατά τη δεκαετία του 1950. Η βιομηχανία των τηλεπικοινωνιών οδήγησε επίσης σε νέα αποτελέσματα στα διακριτά μαθηματικά, ειδικά στη θεωρία γράφων και στη θεωρία πληροφορίας. Η τυπική επαλήθευση προτάσεων της λογικής είναι απαραίτητη για την ανάπτυξη λογισμικού συστημάτων ύψιστης ασφάλειας, με αποτέλεσμα νέες τεχνικές στην αυτοματοποιημένη απόδειξη θεωρημάτων.

Η υπολογιστική γεωμετρία είναι σημαντικό κομμάτι των γραφικών υπολογιστών και χρησιμοποιείται στα σύγχρονα βιντεοπαιχνίδια και στα εργαλεία σχεδίασης με τη βοήθεια υπολογιστή (computer-aided design tools).

Αρκετά πεδία των διακριτών μαθηματικών, ειδικά η θεωρητική πληροφορική, η θεωρία γράφων και η συνδυαστική, είναι σημαντικά για την αντιμετώπιση δύσκολων προβλημάτων βιοπληροφορικής σχετικά με τη φυλογενετική ταξινόμηση.[6]

Σήμερα, ένα από τα πιο διάσημα ανοιχτά προβλήματα της θεωρητικής πληροφορικής είναι το πρόβλημα P = NP, που ασχολείται με τη σχέση μεταξύ των κλάσεων πολυπλοκότητας P και NP. Το Ινστιτούτο Μαθηματικών Clay έχει προσφέρει 1 εκατομμύριο δολάρια στις ΗΠΑ για την πρώτη σωστή απόδειξη, όπως και για άλλα έξι ανοιχτά μαθηματικά προβλήματα.[7]

Θέματα διακριτών μαθηματικών
Θεωρητική πληροφορική

Κύριο λήμμα: Θεωρητική πληροφορική

Η πολυπλοκότητα μελετά το χρόνο που χρειάζονται οι αλγόριθμοι, όπως αυτή η ρουτίνα ταξινόμησης (αλγόριθμος Quicksort).

Η θεωρητική πληροφορική περιλαμβάνει περιοχές των διακριτών μαθηματικών που έχουν σχέση με τους υπολογιστές. Βασίζεται σε σημαντικό βαθμό στη θεωρία γράφων και στη λογική. Περιλαμβάνει τη μελέτη των αλγορίθμων για τον υπολογισμό μαθηματικών αποτελεσμάτων. Η Θεωρία υπολογισμού μελετά τι μπορεί να υπολογιστεί θεωρητικά και είναι στενά συνδεδεμένη με τη λογική, ενώ η πολυπλοκότητα μελετά το χρόνο που χρειάζονται οι υπολογισμοί. Η θεωρία αυτομάτων και η θεωρία τυπικών γλωσσών έχουν στενή σχέση με τη θεωρία υπολογισμού. Τα δίκτυα Πέτρι και οι άλγεβρες διεργασιών χρησιμοποιούνται για τη μοντελοποίηση υπολογιστικών συστημάτων, ενώ μέθοδοι από τα διακριτά μαθηματικά χρησιμοποιούνται για την ανάλυση ηλεκτρονικών κυκλωμάτων VLSI. Η υπολογιστική γεωμετρία εφαρμόζει αλγόριθμους σε γεωμετρικά προβλήματα και η ανάλυση εικόνας μέσω υπολογιστή (computer image analysis) τους εφαρμόζει σε αναπαραστάσεις εικόνων. Η θεωρητική πληροφορική περιλαμβάνει επίσης τη μελέτη διάφορων υπολογιστικών θεμάτων με συνεχή χαρακτήρα.

Θεωρία πληροφορίας

Κύριο λήμμα: Θεωρία πληροφορίας

Οι κωδικοί ASCII της λέξης "Wikipedia", εδώ σε δυαδικό σύστημα, είναι ένας τρόπος αναπαράστασης της λέξης στη θεωρία πληροφορίας και στους αλγόριθμους επεξεργασίας πληροφορίας.

Η θεωρία πληροφορίας ασχολείται με τη μέτρηση της πληροφορίας. Σχετικό πεδίο είναι η θεωρία κωδικοποίησης, που χρησιμοποιείται για τη σχεδίαση αποδοτικών και αξιόπιστων μεθόδων μετάδοσης και αποθήκευσης δεδομένων. Η θεωρία πληροφορίας περιλαμβάνει επίσης θέματα σχετικά με τα αναλογικά σήματα και την αναλογική κωδικοποίηση.

Λογική

Κύριο λήμμα: Μαθηματική λογική

Η λογική είναι η μελέτη των αρχών της σωστής συλλογιστικής και της συνεπαγωγής, καθώς επίσης της συνέπειας, της ορθότητας και της πληρότητας. Για παράδειγμα, στα περισσότερα συστήματα της λογικής (αλλά όχι στην ιντουσιονιστική λογική) ο νόμος του Πιρς (((P→Q)→P)→P) είναι θεώρημα. Στην κλασική λογική μπορεί εύκολα να επαληθευτεί με έναν πίνακα αλήθειας. Η μελέτη των μαθηματικών αποδείξεων είναι ιδιαίτερα σημαντική στη λογική και έχει εφαρμογές στην αυτοματοποιημένη απόδειξη θεωρημάτων και στην τυπική επαλήθευση λογισμικού.

Οι λογικοί τύποι (logical formulas) είναι διακριτές δομές, όπως και οι αποδείξεις, που σχηματίζουν πεπερασμένα δένδρα[8] ή, γενικότερα, κατευθυνόμενους ακυκλικούς γράφους[9][10] (με κάθε βήμα της συνεπαγωγής να συνδυάζει έναν ή περισσότερους από τους κλάδους των υποθέσεων για να φτάσει σε ένα αποτέλεσμα). Η τιμή αλήθειας των λογικών τύπων συνήθως σχηματίζουν ένα πεπερασμένο σύνολο που περιορίζεται γενικά σε δύο τιμές: αληθές και ψευδές, αλλά η λογική μπορεί να έχει και συνεχείς τιμές, όπως η ασαφής λογική. Έχουν επίσης μελετηθεί έννοιες όπως τα άπειρα δένδρα αποδείξεων ή τα άπειρα δένδρα συνεπαγωγών,[11] για παράδειγμα στην infinitary λογική.

Θεωρία συνόλων

Κύριο λήμμα: Θεωρία συνόλων

Η θεωρία συνόλων είναι ο κλάδος των μαθηματικών που μελετά τα σύνολα, τα οποία είναι συλλογές από αντικείμενα όπως το {μπλε, άσπρο, κόκκινο} ή το (άπειρο) σύνολο όλων των πρώτων αριθμών. Τα μερικώς διατεταγμένα σύνολα και τα σύνολα με άλλες σχέσεις έχουν εφαρμογές σε πολλά πεδία.

Στα διακριτά μαθηματικά, τα μετρήσιμα σύνολα (συμπεριλαμβανομένων των πεπερασμένων συνόλων) είναι το βασικό αντικείμενο μελέτης. Η αρχή της θεωρίας συνόλων ως κλάδος των μαθηματικών συνήθως ορίζεται από το έργο του Γκέοργκ Καντόρ πάνω στη διάκριση μεταξύ διαφορετικών τύπων άπειρων συνόλων, με αφετηρία τη μελέτη των τριγωνομετρικών σειρών, ενώ η περαιτέρω ανάπτυξη της θεωρίας των άπειρων συνόλων είναι εκτός των σκοπών των διακριτών μαθηματικών. Πράγματι, η σύγχρονη έρευνα πάνω στη περιγραφική θεωρία συνόλων χρησιμοποιεί σε σημαντικό βαθμό τα κλασικά συνεχή μαθηματικά.

Συνδυαστική

Κύριο λήμμα: Συνδυαστική

Η συνδυαστική μελετά τον τρόπο με τον οποίο μπορούν να συνδυαστούν ή να διαταχτούν οι διακριτές δομές. Η απαριθμητική συνδυαστική ασχολείται κυρίως με τη μέτρηση του αριθμού συγκεκριμένων συνδυαστικών αντικειμένων όπως οι διατάξεις, οι συνδυασμοί, και η διαμέριση ενός συνόλου. Η αναλυτική συνδυαστική ασχολείται με την απαρίθμηση (δηλαδή τον προσδιορισμό του αριθμού) των συνδυαστικών δομών χρησιμοποιώντας εργαλεία της μιγαδικής ανάλυσης και της θεωρίας πιθανοτήτων. Σε αντίθεση με την απαριθμητική ανάλυση, η οποία χρησιμοποιεί συνδυαστικούς τύπους και ειδικές συναρτήσεις (generating functions) για να περιγράψει τα αποτελέσματα, η αναλυτική συνδυαστική προσπαθεί να βρει ασυμπτωτικούς τύπους.

Η θεωρία σχεδίασης μελετά τη συνδυαστική σχεδίαση, που ασχολείται με υποσύνολα με ιδιαίτερες ιδιότητες τομής. Η θεωρία διαμέρισης μελετά διάφορα απαριθμητικά και ασυμπτωτικά προβλήματα που σχετίζονται με τη διαμέριση ακεραίων και έχει στενή σχέση με τις σειρές q (q-series), τις ειδικές συναρτήσεις (special functions) και τις πολυωνυμικές ορθογώνιες ακολουθίες. Αρχικά αποτέλεσε τμήμα της θεωρίας αριθμών και της ανάλυσης αλλά σήμερα η θεωρία διαμέρισης θεωρείται είτε μέρος της συνδυαστικής, είτε ανεξάρτητο πεδίο.

Η θεωρία διάταξης μελετά τα μερικώς διατεταγμένα σύνολα, είτε είναι πεπερασμένα, είτε άπειρα.

Θεωρία γράφων

Κύριο λήμμα: Θεωρία γράφων

Η θεωρία γράφων έχει στενή σχέση με τη θεωρία ομάδων. Αυτός ο γράφος ενός κομμένου τετραέδρου έχει σχέση με την αντιμεταθετική ομάδα A4.

Η θεωρία γράφων, η οποία μελετά τους γράφους και τα δίκτυα, συχνά θεωρείται μέρος της συνδυαστικής, αλλά έχει αναπτυχθεί αρκετά και ξεχωριστά, με δικό της είδος προβλημάτων, ώστε να θεωρείται ξεχωριστό αντικείμενο.[12] Οι γράφοι αποτελούν ένα από τα σημαντικότερα αντικείμενα προς μελέτη στα διακριτά μαθηματικά γιατί είναι από τα πιο κοινά μοντέλα φυσικών και τεχνητών δομών. Μπορούν να μοντελοποιήσουν αρκετούς τύπους σχέσεων και δυναμικών διεργασιών σε φυσικά, βιολογικά και κοινωνικά συστήματα. Στην επιστήμη υπολογιστών, αναπαριστούν τα δίκτυα επικοινωνιών, την οργάνωση των δεδομένων, τις υπολογιστικές συσκευές, τη ροή των υπολογισμών κ.α.Στα μαθηματικά χρησιμοποιούνται στη γεωμετρία και σε συγκεκριμένες περιοχές της τοπολογίας, π.χ. στη θεωρία κόμβων. Η αλγεβρική θεωρία γράφων έχει στενές σχέσεις με τη θεωρία ομάδων. Υπάρχουν επίσης συνεχείς γράφοι, αλλά συνήθως το μεγαλύτερο μέρος της έρευνας στη θεωρία γράφων συμβαίνει στο πεδίο των διακριτών μαθηματικών.

Πιθανότητες

Κύριο λήμμα: Θεωρία διακριτών πιθανοτήτων

Η θεωρία διακριτών πιθανοτήτων ασχολείται με γεγονότα που συμβαίνουν σε μετρήσιμους δειγματικούς χώρους. Για παράδειγμα, οι μετρήσεις μέσω παρατήρησης όπως ο αριθμός των πτηνών σε ένα σμήνος είναι φυσικοί αριθμοί {0, 1, 2, ...}. Από την άλλη πλευρά, οι συνεχείς παρατηρήσεις, όπως το βάρος των πτηνών, αποτελούν πραγματικούς αριθμούς και συνήθως μοντελοποιούνται από μια συνεχή κατανομή πιθανότητας όπως η κανονική κατανομή. Οι κατανομές διακριτών πιθανοτήτων μπορούν να χρησιμοποιηθούν για να προσεγγίσουν τις συνεχείς και αντίστροφα. Σε πολύ περιορισμένες καταστάσεις, όπως η ρίψη ζαριών ή σε πειράματα με τράπουλες, ο υπολογισμός της πιθανότητας ενός γεγονότος βασίζεται στην απαριθμητική συνδυαστική.
Θεωρία αριθμών
Το σπιράλ του Ούλαμ για τους αριθμούς, με τις μαύρες κουκκίδες να δείχνουν τους πρώτους αριθμούς. Το διάγραμμα εμφανίζει κάποια επαναλαμβανόμενα μοτίβα στην κατανομή των πρώτων αριθμών.

Κύριο λήμμα: Θεωρία αριθμών

Η θεωρία αριθμών ασχολείται με τις γενικές ιδιότητες των αριθμών, και ιδιαίτερα των ακεραίων. Έχει εφαρμογή στην κρυπτογραφία, την κρυπτανάλυση και την κρυπτολογία, ειδικότερα όσον αφορά την αριθμητική με υπόλοιπο, τις διοφαντικές εξισώσεις, τη γραμμική και τετραγωνική σύγκλιση, τους πρώτους αριθμούς και τη δοκιμή για πρώτους αριθμούς (primality testing). Η γεωμετρία των αριθμών αποτελεί επίσης θέμα της θεωρίας αριθμών. Στην αναλυτική θεωρία αριθμών, χρησιμοποιούνται και τεχνικές από τα συνεχή μαθηματικά. Θέματα που επεκτείνονται πέρα από τα διακριτά αντικείμενα είναι οι υπερβατικοί αριθμοί, η διοφαντική προσέγγιση, η p-αδική ανάλυση και τα πεδία συναρτήσεων (function fields).
Άλγεβρα

Κύριο λήμμα: Αφηρημένη άλγεβρα

Οι αλγεβρικές δομές συναντώνται τόσο ως διακριτά, όσο και ως συνεχή παραδείγματα. Οι διακριτές άλγεβρες περιλαμβάνουν τις άλγεβρες Μπουλ που χρησιμοποιούνται στις λογικές πύλες και στον προγραμματισμό, τις σχεσιακές άλγεβρες που χρησιμοποιούνται στις βάσεις δεδομένων, τις διακριτές και πεπερασμένες εκδόσεις των ομάδων, των δακτυλίων και των πεδίων που χρησιμοποιούνται στην αλγεβρική θεωρία κωδικοποίησης, και τις διακριτές ημι-ομάδες και μονοειδή που εμφανίζονται στη θεωρία των τυπικών γλωσσών.
Λογισμός των πεπερασμένων διαφορών, διακριτός λογισμός ή διακριτή ανάλυση

Κύριο λήμμα: πεπερασμένη διαφορά

Μια συνάρτηση που ορίζεται σε ένα διάστημα των ακεραίων συνήθως ονομάζεται ακολουθία. Μια ακολουθία μπορεί να είναι μια πεπερασμένη ακολουθία από κάποια πηγή δεδομένων ή μια άπειρη ακολουθία από ένα διακριτό δυναμικό σύστημα. Μια τέτοια διακριτή συνάρτηση θα μπορούσε να οριστεί άμεσα από μια λίστα (αν έχει πεπερασμένο πεδίο τιμών) ή από έναν τύπο που ορίζει το γενικό όρο της, ή μέσω μιας σχέσης (recurrence relation) ή μιας εξίσωσης διαφορών. Οι εξισώσεις διαφορών μοιάζουν με τις διαφορικές εξισώσεις αλλά αντικαθιστούν την παράγωγο με τη διαφορά μεταξύ διπλανών όρων και μπορούν να χρησιμοποιηθούν για να προσεγγίσουν τις τιμές διαφορικών εξισώσεων ή (συχνότερα) ως ξεχωριστά αντικείμενα μελέτης. Πολλά ερωτήματα και μέθοδοι που σχετίζονται με τις διαφορικές εξισώσεις έχουν αντίστοιχα στις εξισώσεις διαφορών. Για παράδειγμα, όπου υπάρχουν ολοκληρωτικοί μετασχηματισμοί στην αρμονική ανάλυση, στη μελέτη συνεχών συναρτήσεων ή αναλογικών σημάτων, υπάρχουν διακριτοί μετασχηματισμοί για διακριτές συναρτήσεις ή ψηφιακά σήματα. Σε αναλογία με το διακριτό χώρο υπάρχουν γενικότεροι διακριτοί ή πεπερασμένοι μετρικοί χώροι και πεπερασμένοι τοπολογικοί χώροι.
Γεωμετρία
Η υπολογιστική γεωμετρία εφαρμόζει υπολογιστικούς αλγορίθμους σε αναπαραστάσεις γεωμετρικών αντικειμένων.

Κύρια λήμματα: διακριτή γεωμετρία και υπολογιστική γεωμετρία

Η διακριτή γεωμετρία και η συνδυαστική γεωμετρία ασχολούνται με τις συνδυαστικές ιδιότητες των διακριτών συλλογών από γεωμετρικά αντικείμενα. Ένα κλασικό θέμα της διακριτής γεωμετρίας είναι η πλακόστρωση του επιπέδου. Η υπολογιστική γεωμετρία εφαρμόζει αλγορίθμους σε γεωμετρικά προβλήματα.
Τοπολογία

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

Κύριο λήμμα: Επιχειρησιακή έρευνα

Τα γραφήματα PERT (Program Evaluation and Review Technique), όπως αυτό που απεικονίζεται, είναι μια τεχνική διοίκησης επιχειρήσεων βασισμένη στη θεωρία γράφων.

Η επιχειρησιακή έρευνα παρέχει τεχνικές επίλυσης πρακτικών προβλημάτων στο χώρο των επιχειρήσεων και σε άλλα πεδία εφαρμογών. Τέτοια προβλήματα είναι η κατανομή πόρων για μεγιστοποίηση κέρδους ή ο χρονοπρογραμματισμός των δραστηριοτήτων ενός εγχειρήματος με σκοπό την ελαχιστοποίηση του ρίσκου. Οι τεχνικές επιχειρησιακής έρευνας περιλαμβάνουν τον γραμμικό προγραμματισμό και άλλες περιοχές της βελτιστοποίησης, της θεωρίας ουρών αναμονής (queuing theory), της θεωρίας χρονοπρογραμματισμού και της θεωρίας δικτύων. Η επιχειρησιακή έρευνα συμπεριλαμβάνει επίσης συνεχείς περιοχές, όπως οι διεργασίες Μαρκόφ συνεχούς χρόνου, τα martingales συνεχούς χρόνου, η βελτιστοποίηση διεργασιών (process optimization), και η συνεχής και η υβριδική θεωρία ελέγχου.
Θεωρία παιγνίων, θεωρία αποφάσεων, θεωρία ωφελιμότητας, θεωρία κοινωνικής επιλογής
Συνεργασία Λιποταξία
Συνεργασία -1, -1 -10, 0
Λιποταξία 0, -10 -5, -5
Πίνακας οφέλους για το δίλημμα του φυλακισμένου, ένα συνηθισμένο παράδειγμα της θεωρίας παιγνίων. Ο ένας παίχτης επιλέγει μια σειρά, ο άλλος μια στήλη, και το ζεύγος που προκύπτει δίνει το όφελός τους.

Η θεωρία αποφάσεων ασχολείται με τις τιμές, τις αβεβαιότητες και άλλα προβλήματα που αφορούν μια απόφαση, το πόσο ορθολογική είναι αυτή, και τη βέλτιστη απόφαση που προκύπτει.

Η θεωρία ωφελιμότητας εξετάζει το μέτρο της σχετικής οικονομικής ικανοποίησης που προκύπτει από την κατανάλωση αγαθών και υπηρεσιών, καθώς και το πόσο επιθυμητή είναι αυτή.

Η θεωρία κοινωνικής επιλογής (social choice theory) εξετάζει τις ψηφοφορίες. Μια άλλη προσέγγιση στο ίδιο θέμα είναι η θεωρία κάλπης (ballot theory).

Η θεωρία παιγνίων ασχολείται με τις περιπτώσεις που η επιτυχία εξαρτάται από τις επιλογές των άλλων, με αποτέλεσμα η επιλογή της βέλτιστης πράξης να είναι πολύπλοκη. Υπάρχουν και συνεχή παιχνίδια, βλ. διαφορικό παίγνιο. Σχετικά θέματα της θεωρίας παιγνίων: θεωρία δημοπρασιών (auction theory), δίκαιο μοίρασμα (fair division).
Διακριτοποίηση

Η διακριτοποίηση ασχολείται με τη διαδικασία της μεταφοράς συνεχών μοντέλων και εξισώσεων στα διακριτά αντίστοιχά τους, συχνά για τη διευκόλυνση των υπολογισμών μέσω προσεγγιστικών μεθόδων. Σημαντικό παράδειγμα είναι η αριθμητική ανάλυση.
Διακριτά ανάλογα των συνεχών μαθηματικών

Υπάρχουν πολλές έννοιες των συνεχών μαθηματικών που έχουν διακριτές εκδόσεις, όπως ο διακριτός λογισμός, οι διακριτές πιθανοτικές κατανομές, οι διακριτοί μετασχηματισμοί Φουριέ, η διακριτή γεωμετρία, οι διακριτοί λογάριθμοι, η διακριτή διαφορική γεωμετρία, ο διαφορικός εξωτερικός λογισμός, η διακριτή θεωρία Μορς, οι εξισώσεις διαφορών, τα διακριτά δυναμικά συστήματα και τα διακριτά διανυσματικά μέτρα.

Στα εφαρμοσμένα μαθηματικά, η διακριτή μοντελοποίηση είναι το διακριτό ανάλογο της συνεχούς μοντελοποίησης. Στη διακριτή μοντελοποίηση, διακριτοί τύποι εφαρμόζονται σε δεδομένα. Μια συνηθισμένη μέθοδος που ακολουθείται σε αυτόν τον τύπο μοντελοποίησης είναι η χρήση σχέσεων (recurrence relations).
Υβριδικά διακριτά και συνεχή μαθηματικά

Ο λογισμός κλίμακας χρόνου ενοποιεί τη θεωρία των εξισώσεων διαφορών με αυτήν των διαφορικών εξισώσεων και έχει εφαρμογές σε πεδία που χρειάζονται ταυτόχρονη μοντελοποίηση διακριτών και συνεχών δεδομένων.
Αναφορές

Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall, 2008.
Weisstein, Eric W., "Discrete mathematics" από το MathWorld.
Norman L. Biggs, Discrete mathematics, Oxford University Press, 2002.
Brian Hopkins, Resources for Teaching Discrete Mathematics, Mathematical Association of America, 2008.
Wilson, Robin (2002). Four Colors Suffice. London: Penguin Books. ISBN 0-691-11533-8.
Trevor R. Hodkinson and John A. N. Parnell, Reconstructing the Tree of Life: Taxonomy and systematics of species rich taxa, CRC Press, 2007, ISBN 0849395798, p. 97.
«Millennium Prize Problems». 2000-05-24. Ανακτήθηκε στις 2008-01-12.
Sjerp Troelstra, Helmut Schwichtenberg, Basic Proof Theory, Cambridge University Press, 2000, ISBN 0521779111, p. 186.
Samuel R. Buss, Handbook of Proof Theory (Volume 137 of Studies in logic and the foundations of mathematics), Elsevier, 1998. ISBN 0444898409, p 13.
Stephan Schulz, "Learning Search Control Knowledge for Equational Theorem Proving," in KI 2001: Advances in Artificial Intelligence : Joint German/Austrian Conference on AI, Vienna, Austria, September 19-21, 2001 : Proceedings (Volume 2174 of Lecture notes in Artificial Intelligence), Franz Baader, Gerhard Brewka, and Thomas Eiter, eds., Springer, 2001, ISBN 3540426124, p. 325.
Cyclic proofs of program termination in separation logic, J Brotherston, R Bornat, C Calcagno, ACM SIGPLAN Notices, Volume 43 , Issue 1 (January 2008)

Graphs on Surfaces, Bojan Mohar and Carsten Thomassen, Johns Hopkins University press, 2001

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

Norman L. Biggs, Discrete Mathematics 2nd ed. Oxford University Press. ISBN 0-19-850717-8, και συμπληρωματική ιστοσελίδα με ερωτήσεις και λύσεις.
Ronald Graham, Ντόναλντ Κνουθ, Oren Patashnik, Concrete Mathematics
Richard Johnsonbaugh, Discrete Mathematics 6th ed. Macmillan. ISBN 0-13-045803-1, και συμπληρωματική ιστοσελίδα.
Klette, R., and A. Rosenfeld (2004). Digital Geometry. Morgan Kaufmann. ISBN 1-55860-861-3.
Jonathan Arbib & John Dwyer, Discrete Mathematics for Cryptography, 1st ed. ISBN 1-90-793401-4.
John Dwyer & Suzy Jagger, Discrete Mathematics for Business & Computing, 1st ed. 2010 ISBN 1-90-793400-6.
Ντόναλντ Κνουθ, The Art of Computer Programming
Kenneth H. Rosen, Handbook of Discrete and Combinatorial Mathematics CRC Press. ISBN 0-8493-0149-1.
Kenneth H. Rosen, Discrete Mathematics and Its Applications 6th ed. McGraw Hill. ISBN 0-07-288008-2, και συμπληρωματική ιστοσελίδα.
Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction 5th ed. Addison Wesley. ISBN 0-20-172634-3
Susanna S. Epp, Discrete Mathematics with Applications Brooks Cole. ISBN 978-0495391326
C.L. Liu, Elements of Discrete Math.
Jiří Matoušek & Jaroslav Nešetřil, Invitation to Discrete Mathematics, OUP.

Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License