Εισαγωγή στην Θεωρία Υπολογισμού (ΗΥ311)
Μανόλης Βάβαλης
Ασχολούμαστε με τον σχεδιασμό, την ανάλυση και την χρήση κάθε τύπου μοντέλων στην περιοχή της επιστήμης υπολογιστών. Η αφαίρεση είναι το κεντρικό στοιχείο, η χρήση αφηρημένων εργαλείων είναι εκτεταμένη και η ανακάλυψη των πάσης φύσεως ορίων και των ουσιαστικών ιδιοτήτων των υπολογιστών είναι το κύριο ζητούμενο.
Ο όρος αφαίρεση (abstraction) αναφέρεται στη διάκριση µεταξύ των εξωτερικών ιδιοτήτων µιας οντότητας και των λεπτοµερειών της εσωτερικής της σύνθεσης.
Αφηρηµένα εργαλεία είναι τα συστατικά στοιχεία ενός συστήµατος, των οποίων αγνοούµε την εσωτερική τους σύνθεση.
Οι διαλέξεις του μαθήματος θα πραγματοποιούνται κάθε Δευτέρα 10-11 και κάθε Τρίτη και Τετάρτη 8-9 ενώ οι ασκήσεις/τεστς θα πραγματοποιούνται κάθε δεύτερη Δευτέρα 8-10.
ΛιγότεραΑσχολούμαστε με τον σχεδιασμό, την ανάλυση και την χρήση κάθε τύπου μοντέλων στην περιοχή της επιστήμης υπολογιστών. Η αφαίρεση είναι το κεντρικό στοιχείο, η χρήση αφηρημένων εργαλείων είναι εκτεταμένη και η ανακάλυψη των πάσης φύσεως ορίων και των ουσιαστικών ιδιοτήτων των υπολογιστών είναι το κύριο ζητούμενο.
Ο όρος αφαίρεση (abstraction) αναφέρεται στη διάκριση µεταξύ των εξωτερικών ιδιοτήτων µιας οντότητας και των λεπτοµερειών της εσωτερικής της σύνθεσης.
Αφηρηµένα εργαλεία είναι τα συστατικά στοιχεία ενός συστήµατος, των οποίων αγνοούµε την εσωτερική τους σύνθεση.
Οι διαλέξεις του μαθήματος θα πραγματοποιούνται κάθε Δευτέρα 10-11 και κάθε Τρίτη και Τετάρτη 8-9 ενώ οι ασκήσεις/τεστς θα πραγματοποιούνται κάθε δεύτερη Δευτέρα 8-10.
Ασχολούμαστε με τον σχεδιασμό, την ανάλυση και την χρήση κάθε τύπου μοντέλων στην περιοχή της επιστήμης υπολογιστών. Η αφαίρεση είναι το κεντρικό στοιχείο, η χρήση αφηρημένων εργαλείων είναι εκτεταμένη και η ανακάλυψη των πάσης φύσεως ορίων και των ουσιαστικών ιδιοτήτων των υπολογιστών είναι το κύριο ζητούμενο.
Ο όρος αφαίρεση (abstraction) αναφέρεται στη διάκριση µεταξύ των εξωτερικών ιδιοτήτων µιας οντότητας και των λεπτοµερειών της εσωτερικής της σύνθεσης.
Αφηρηµένα εργαλεία είναι τα συστατικά στοιχεία ενός συστήµατος, των οποίων αγνοούµε την εσωτερική τους σύνθεση.
Οι διαλέξεις του μαθήματος θα πραγματοποιούνται κάθε Δευτέρα 10-11 και κάθε Τρίτη και Τετάρτη 8-9 ενώ οι ασκήσεις/τεστς θα πραγματοποιούνται κάθε δεύτερη Δευτέρα 8-10.
Αυτόματα, υπολογισιμότητα, και πολυπλοκότητα, Μαθηματικές έννοιες και ορολογία
Πεπερασμένα αυτόματα, Ανταιτιοκρατία, Κανονικές εκφράσεις, Μη κανονικές γλώσσες
Ασυμφραστικές γραμματικές, Αυτόματα στοίβας, Μη ασυμφραστικές γλώσσες.
Μηχανές Turing, Παραλλαγές μηχανών Turing, Ο ορισμός του αλγορίθμου.
Διαγνώσιμες γλώσσες, Το πρόβλημα του τερματισμού.
Μέτρηση της πολυπλοκότητας, Η κλάση Ρ, Η κλάση ΝΡ.
Θεώρημα του Savitch, Η κλάση PSPACE.
