Θεωρία Υπολογισμού

Από Students support wiki

Μετάβαση σε: πλοήγηση, αναζήτηση
Θεωρία Υπολογισμού
Εξάμηνο 5ο Eξάμηνο
Κατηγορία Επιλογής
Διδάσκων/-οντες Χαράλαμπος Κωνσταντόπουλος
Σελίδα Μαθήματος GuNet2
Υπολογισμός βαθμού Γραπτή Εξέταση 100%


Πίνακας περιεχομένων

Περιγραφή

Σύνολα, Πράξεις με σύνολα, Νόμοι De Morgan, Αλφάβητα, συμβολοσειρές, πράξεις με συμβολοσειρές, γλώσσες, πράξεις με γλώσσες, Τεχνικές απόδειξης: Μαθηματική Επαγωγή, Αρχή Περιστεριώνα, Αρχή Διαγωνοποίησης, Κανονικά σύνολα, Πεπερασμένα αυτόματα: ντετερμινιστικά και μη ντετερμινιστικά, ισοδυναμία υπολογιστικών μοντέλων, Κανονικά σύνολα, κανονικές γλώσσες, ιδιότητες κλειστότητας, Κανονικές εκφράσεις, Ισοδυναμία κανονικών εκφράσεων και πεπερασμένων αυτομάτων, Γλώσσες που δεν είναι κανονικές, Pumping Lemma για κανονικές γλώσσες, Γραμματικές και γλώσσες χωρίς συμφραζόμενα, ιδιότητες κλειστότητας στην κλάση των γλωσσών χωρίς συμφραζόμενα, Αυτόματα στοίβας

Ισοδυναμία γραμματικών χωρίς συμφραζόμενα και αυτομάτων στοίβας, Σχέση κανονικών γλωσσών και γλωσσών χωρίς συμφραζόμενα, Συμπλήρωμα γλωσσών χωρίς συμφραζόμενα, Pumping Lemma για γλώσσες χωρίς συμφραζόμενα, Μηχανές Turing: εισαγωγή στο βασικό μοντέλο, ισοδυναμία παραλλαγών, Church Thesis.

Προαπαιτούμενες Γνώσεις

Η επιτυχής παρακολούθηση του μαθήματος προϋποθέτει καλή γνώση των μαθημάτων Διακριτά Μαθηματικά (2ο εξ.), Μεταγλωττιστές (3ο εξ.), Αλγόριθμοι (4ο εξ.).

Παρακολούθηση

Συνίσταται. Το μάθημα διεξάγεται 4 ώρες την εβδομάδα.

Ύλη

Από το βιβλίο «ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ» (SIPSER MICHAEL, ΠΑΝΕΠΙΣΤΗΜΙΑΚΕΣ ΕΚΔΟΣΕΙΣ ΚΡΗΤΗΣ), τα κεφάλαια: Εισαγωγή, 1,2,3,4,5 (εκτός 5.1.1) ,7, ειδικότερα:

Εξέταση

Η εξέταση γίνεται γραπτός με κλειστά βιβλία και σημειώσεις και αντιστοιχεί στο 100% του βαθμού.

Σημειώσεις

Παλαιότερα Θέματα

Προσωπικά εργαλεία
Περιοχές ονομάτων
Παραλλαγές
Ενέργειες
Πλοήγηση
Εργαλεία