Χρησιμοποιούμε cookies για την ανάλυση της επισκεψιμότητάς μας. Αν συνεχίσετε να χρησιμοποιείτε την ιστοσελίδα μας, συναινείτε στη χρήση των cookies μας. Οκ Συμφωνώ!

ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ

Μαθησιακά Αποτελέσματα:

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




Γενικές Ικανότητες:

Οι ικανότητες που πρέπει να αποκτήσει ο πτυχιούχος και στις οποίες αποσκοπεί το μάθημα είναι:

  • Αυτόνομη εργασία.
  • Ομαδική εργασία.
  • Εργασία σε διεθνές περιβάλλον.
  • Εργασία σε διεπιστημονικό περιβάλλον.




Περιεχόμενο Μαθήματος:

  • Σύνολα, Σχέσεις και Γλώσσες
  • Πεπερασμένα αυτόματα (ντετερμινιστικά, μη-ντετερμινιστικά, πεπερασμένα αυτόματα και κανονικές γλώσσες)
  • Γλώσσες χωρίς συμφραζόμενα (γραμματικές, κανονικές γλώσσες, αυτόματα στοίβας, ιδιότητες, ντετερμινισμός και συντακτική ανάλυση)
  • Μηχανές Turing (ορισμός, υπολογισμοί με μηχανές Turing, συνδυασμοί και επεκτάσεις)
  • Μη Υπολογισιμότητα (πρόβλημα τερματισμού, Turing -αριθμησιμότητα, -αποδεκτικότητα και αποφασισιμότητα, μη επιλύσιμα προβλήματα, μ-αναδρομικές συναρτήσεις, μη επιλύσιμα προβλήματα γραμματικών)
  • Υπολογιστική πολυπλοκότητα (χρονικά φραγμένες μηχανές Turing, κλάσεις P και NP, το πρόβλημα του περιοδεύοντος πωλητή)
  • Προτασιακός Λογισμός (εισαγωγή, συντακτικό, τιμές αλήθειας, εγκυρότητα και ικανοποιησιμότητα)