Παρουσίαση/Προβολή

Εικόνα επιλογής

ΔΙΑΚΡΙΤΆ ΜΑΘΗΜΑΤΙΚΑ

(TP353) -  ΣΜΥΡΝΑΚΗΣ ΙΩΑΝΝΗΣ ΚΑΡΑΓΙΑΝΝΑΚΗΣ ΔΗΜΗΤΡΗΣ

Περιγραφή Μαθήματος

  • Στοιχεία από τη Θεωρία Συνόλων και τον Προτασιακό Λογισµό: Η έννοια του συνόλου. Το κενό σύνολο. Υποσύνολο. Ίσα σύνολα. Ένωση – Τοµή – ∆ιαφορά – Συµµετρική ∆ιαφορά συνόλων. ∆υναµοσύνολο. Πεπερασµένα – αριθµήσιµα – µη αριθµήσιµα σύνολα. Μαθηµατική επαγωγή. Αρχή του εγκλεισµού και του αποκλεισµού. Αληθής – Ψευδής Πρόταση. ∆ιάζευξη – Σύζευξη – Άρνηση µιας πρότασης. Συνδυασµός προτάσεων. Πίνακας Αληθείας.

 

  • Υπολογισιµότητα και Τυπικές γλώσσες: Παράδοξο του Russell. Υπολογισιµότητα. ∆ιατεταγµένα σύνολα. Γλώσσες. Γραµµατικές δοµής φράσεως.

 

  • Σχέσεις και Συναρτήσεις: ∆ιατεταγµένο ζεύγος. Καρτεσιανό γινόµενο. ∆ιµελής σχέση. Ιδιότητες διµελών σχέσεων. Σχέσεις ισοδυναµίας και µερικής διάταξης. Συναρτήσεις.

 

  • Γραφήµατα και επίπεδα γραφήµατα: Κατευθυνόµενο γράφηµα. Κορυφές – Ακµές. Βρόχος. Πολυσύνολα. Μη κατευθυνόµενο γράφηµα. Ισόµορφα γραφήµατα. Κατευθυνόµενο – µη κατευθυνόµενο πολυγράφηµα. Βεβα- ρηµένο γράφηµα. Μονοπάτι. Απλό µονοπάτι. Απλό - Στοιχειώδες κύκλωµα. Ελάχιστα µονοπάτια σε βεβαρηµένα γραφήµατα (µέθοδος Dijkstra). Συνεκτικό γράφηµα. Μονοπάτια και κυκλώµατα Euler. Μονοπάτια και κυκλώµατα Hamilton. Επίπεδα γραφήµατα.
  • ∆ένδρα: ∆ένδρο. Επικαλύπτον δένδρο. Βάρος επικαλύπτοντος δένδρου. Εύρεση ελάχιστου επικαλύπτοντος δένδρου σε συνεκτικό βεβαρηµένο γράφηµα.
  • Μηχανές πεπερασµένων καταστάσεων: Μηχανή επεξεργασίας πληρο- φοριών. Κατάσταση. Μηχανές πεπερασµένων καταστάσεων. Γλώσσες πεπερασµένων καταστάσεων. Μηχανές πεπερασµένων καταστάσεων ως αναγνωριστές γλώσσας. Αιτιοκρατικές και µη αιτιοκρατικές µηχανές πεπερασµένων καταστάσεων.
  • Ανάλυση αλγορίθµων: Αλγόριθµος. Χρονική πολυπλοκότητα ενός αλγόριθµου. Πρακτικώς επιλύσιµα και δυσεπίλυτα προβλήµατα

 

. ΒΙΒΛΙΟΓΡΑΦΙΑ 1. "Στοιχεία ∆ιακριτά Μαθηµατικά", C. Liu, Πανεπιστηµιακές Εκδόσεις Κρήτης, 1999, ISBN: 960-524-072-6

Ημερομηνία δημιουργίας

Πέμπτη 26 Μαΐου 2016