Περιεχόμενα

• Ακρωνύμια
• Πρόλογος
• 1. Βασικές έννοιες από τη Θεωρία Συνόλων και τον Προτασιακό Λογισμό
  • 1.1 Εισαγωγή
  • 1.2 Σύνολα
  • 1.3 Σχέσεις
  • 1.4 Συναρτήσεις
  • 1.5 Πράξεις σε σύνολα
  • 1.6 Γενικευμένες πράξεις συνόλων
  • 1.7 Σχέσεις ισοδυναμίας
  • 1.8 Πληθάριθμος. Αριθμήσιμα και μη άπειρα σύνολα.
  • 1.9 Μαθηματική Επαγωγή
    • 1.9.1 Η μέθοδος στην απλή της μορφή
      • 1.9.1.1 Όλες οι προηγούμενες περιπτώσεις ως επαγωγική υπόθεση
    • 1.9.2 Προχωρημένη χρήση της επαγωγής
      • 1.9.2.1 <<Μπρος-πίσω>> επαγωγή
      • 1.9.2.2 Πολλαπλή επαγωγή
      • 1.9.2.3 Ενισχύοντας την πρόταση που θέλουμε να δείξουμε
    • 1.9.3 Εφαρμογή: Το θεώρημα του Γάμου (Hall)
  • 1.10 Προτασιακός Λογισμός
    • 1.10.0.1 Σύζευξη
    • 1.10.0.2 Διάζευξη
    • 1.10.0.3 Άρνηση
    • 1.10.0.4 Συνεπαγωγή
    • 1.10.0.5 Ταυτολογίες και αντιφάσεις
  • 1.11 Επαναληπτικές Ασκήσεις Κεφαλαίου
  • 1.12 Video Κεφαλαίου
  
  
• 2. Θεωρία Αριθμών
  • 2.1 Διαιρετότητα, ισοϋπόλοιποι αριθμοί
  • 2.2 Μέγιστος κοινός διαιρέτης, ελάχιστο κοινό πολλαπλάσιο, αλγόριθμος του Ευκλείδη
  • 2.3 Πρώτοι αριθμοί
  
  
• 3. Βασικές αρχές απαρίθμησης
  • 3.1 Αρχή πολλαπλασιασμού ανεξάρτητων επιλογών
    • 3.1.1 Πλήθος υποσυνόλων ενός πεπερασμένου συνόλου
    • 3.1.2 Πλήθος συναρτήσεων από σύνολο $A$ σε σύνολο $B$
  • 3.2 Αρχή πολλαπλασιασμού ημι-ανεξάρτητων επιλογών
    • 3.2.1 Πλήθος διατεταγμένων επιλογών. Μεταθέσεις συνόλου
    • 3.2.2 Μη διατεταγμένες επιλογές. Συνδυασμοί
  • 3.3 Επαναληπτικές ασκήσεις Κεφαλαίου
  • 3.4 Video Κεφαλαίου
  
  
• 4. Προχωρημένη απαρίθμηση
  • 4.1 Διαμερίσεις και συνδυασμοί με επανάθεση
  • 4.2 Πολυωνυμικοί συντελεστές
  • 4.3 Το Διωνυμικό Θεώρημα
  • 4.4 Συνδυαστικές αποδείξεις ταυτοτήτων
  • 4.5 Επαναληπτικές ασκήσεις Κεφαλαίου
  • 4.6 Video Κεφαλαίου
  
  
• 5. Εισαγωγή στη θεωρία γραφημάτων
  • 5.1 Απλά γραφήματα
  • 5.2 Μερικά ειδικά γραφήματα
  • 5.3 Υπογραφήματα και ισομορφία
    • 5.3.1 Υπογραφήματα
    • 5.3.2 Ισομορφία γραφημάτων
  • 5.4 Συνεκτικότητα και αποστάσεις πάνω σε γραφήματα
  • 5.5 Δέντρα και δάση
  • 5.6 Γενικεύσεις της έννοιας του γραφήματος
  • 5.7 Ο αλγόριθμος του Kruskal για ελάχιστα δέντρα που παράγουν σε γραφήματα με βάρη
  • 5.8 Ο αλγόριθμος Floyd-Warshall για εύρεση αποστάσεων πάνω σε γραφήματα
  
  
• 6. Διμερή γραφήματα και ταιριάσματα
  • 6.1 Διμερή γραφήματα
  • 6.2 Ταιριάσματα σε διμερή γραφήματα
  • 6.3 Μέγιστα ταιριάσματα
  • 6.4 Μονοπάτια και κυκλώματα Euler και Hamilton
    • 6.4.1 Γενικά
    • 6.4.2 Συνθήκες για κύκλωμα/μονοπάτι Euler
  • 6.5 Χρωματισμοί
    • 6.5.1 Γενικά
    • 6.5.2 Εκτιμήσεις για τον χρωματικό αριθμό
  
  
• 7. Τυπικές γλώσσες και αυτόματα
  • 7.1 Αλφάβητα, λέξεις και γλώσσες
  • 7.2 Ντετερμινιστικά Αυτόματα
  • 7.3 Μη ντετερμινιστικά αυτόματα
  • 7.4 Ισοδυναμία NFA και DFA.
  • 7.5 NFA με ε-κινήσεις
  • 7.6 Ισοδυναμία ε-NFA και NFA
  • 7.7 Κανονικές εκφράσεις και οι γλώσσες τους
  • 7.8 Κανονικότητα γλωσσών των αυτομάτων
  • 7.9 Κλειστότητα κανονικών γλωσσών κάτω από απλές πράξεις
  • 7.10 Το Λήμμα Άντλησης και μη κανονικές γλώσσες
  
  
• 8. Αλγόριθμοι για αυτόματα
  • 8.1 Πότε ένα DFA αναγνωρίζει κενή ή άπειρη γλώσσα
  • 8.2 Σχέσεις ισοδυναμίας για γλώσσες και αυτόματα. Θεώρημα Myhill-Nerode
  • 8.3 Ελαχιστοποίηση DFA
  
  
• 9. Context free γραμματικές και γλώσσες
  • 9.1 Ένας τρόπος περιγραφής απλών αριθμητικών εκφράσεων
  • 9.2 Ορισμός context free γραμματικών και των γλωσσών τους
  • 9.3 Ένα ενδιαφέρον παράδειγμα με πλήρη απόδειξη
  • 9.4 Οι κανονικές γλώσσες είναι και context free
  • 9.5 Το αυτόματο με στοίβα (Push Down Automaton)
  • 9.6 Παραδείγματα PDA
  • 9.7 Το Λήμμα Άντλησης για context free γλώσσες, και η εφαρμογή του
  
  
• 10. Υπολογισιμότητα
  • 10.1 Υπολογίσιμες συναρτήσεις και αναδρομικά σύνολα
  • 10.2 Μη υπολογίσιμες συναρτήσεις
  • 10.3 Το Halting Problem. Άλλα μη αποφασίσιμα προβλήματα στα Μαθηματικά.
  • 10.4 Αναδρομικά απαριθμήσιμα (α.α.) σύνολα.
  
  
• 11. Εισαγωγή στη διακριτή πιθανότητα
  • 11.1 Πειράματα
    • 11.1.1 Ρίψη νομίσματος
    • 11.1.2 Ρίψη ζαριού
    • 11.1.3 Ζεύγος νομισμάτων
    • 11.1.4 Αριθμός παιδιών
    • 11.1.5 Χρόνος αναμονής
    • 11.1.6 Ύψος και βάρος
  • 11.2 Δειγματικοί χώροι, ενδεχόμενα, η πιθανότητά τους
    • 11.2.1 Υπεραριθμήσιμοι δειγματικοί χώροι
    • 11.2.2 Ενδεχόμενα με πιθανότητα 0
  • 11.3 Υπό συνθήκη πιθανότητα
  • 11.4 Ανεξαρτησία ενδεχομένων
  • 11.5 Video Κεφαλαίου
  
  
• 12. Τυχαίες μεταβλητές και μέση τιμή
  • 12.1 Τυχαίες μεταβλητές και η κατανομή τους
  • 12.2 Μέση τιμή μιας ΤΜ
  • 12.3 Διασπορά μιας ΤΜ και ανισότητες απόκλισης
  • 12.4 Γεννήτριες συναρτήσεις
  • 12.5 Video Κεφαλαίου
  
  
• Index