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

(INF148) -  ΦΟΥΣΤΟΥΚΟΥ ΕΥΓΕΝΙΑ

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

EAΡΙΝΟ ΕΞΑΜΗΝΟ 2024-25:

ΩΡΕΣ ΓΡΑΦΕΙΟΥ   ΔΕΥΤΕΡΑ 11:00-13:00 και ΠΕΜΠΤΗ 11:00-13:00

email: eugenie@aueb.gr

Θα γίνονται στο γραφειο μου Κοδριγκτώνος 12, 3ος οροφος.

 

ΩΡΕΣ ΦΡΟΝΤΙΣΤΗΡΙΟΥ (ένα δίωρο την εβδομάδα):

Παρασκευή 15:00-17:00 στο Αμφιθέατρο Β .

To φροντιστήριο γίνεται από τον Γιώργο Αμανατίδη g.d.amanatidis@aueb.gr - Ώρες Γραφείου: Πέμπτη: 10:00-12:00 και Παρασκευή: 12:00-13:00 και 14:00-15:00 Κοδριγκτώνος 12, 5ος οροφος.

 

ΠΕΡΙΕΧΟΜΕΝΟ ΜΑΘΗΜΑΤΟΣ

Πεπερασμένα αυτόματα     Αυτόματα στοίβας   Μηχανές Turing

Επιλύσιμα προβλήματα /  Μη επιλύσιμα προβλήματα

Αποδοτικά επιλύσιμα προβλήματα / Μη αποδοτικά επιλύσιμα προβλήματα. (κλάσεις P, NP, NP-complete προβλήματα).

 

ΒΙΒΛΙΑ

1) M. Sipser. Εισαγωγή στη Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης, 2019.

Πρόκειται για μετάφραση της τρίτης αγγλικής έκδοσης του 2013 (Μ. Sipser. Introduction to the Theory of Computation. Cengage Learning EMEA, 3rd edition 2013)

H παραπάνω τρίτη αγγλική έκδοση δεν διαφέρει ουσιωδώς (στα κεφάλεια που μας ενδιαφέρουν) από την δεύτερη αγγλική έκδοση του 2006 (Μ. Sipser. Introduction to the Theory of Computation. Course Technology, 2nd edition 2012).

2) H. Lewis, Χ. Παπαδημητρίου. Στοιχεία Θεωρίας Υπολογισμού, εκδόσεις Κριτική, 2005. Πρόκειται για μετάφραση της δεύτερης αγγλικής έκδοσης (H. Lewis and Ch. Papadimitriou. Elements of the Theory of Computation (2nd edition). Prentice-Hall, 1998).

 

YΛΗ  ΕΞΕΤΑΣΕΩΝ  

Η ύλη απο το βιβλίο στα ελληνικά του Sipser είναι τα κεφ. 0, κεφ. 1, απο το Κεφ.2 τα 2.1.1, 2.1.2, 2.1.3, 2.2.1, 2.2.2 και η  εκφώνηση του Θεωρήματος 2.12, τα κεφ. 3, κεφ. 4, κεφ. 5 (εκτός από το 5.1.1), και από το Κεφ 7. τα 7.1, 7.2, 7.3, 7.4.  Σημείωση:  στα Κεφάλαια 4.1.2  και  5.2. μπορείτε μόνο να διαβάσετε τις εκφωνήσεις των θεωρημάτων.

 

YΛΗ  ΕΞΕΤΑΣΕΩΝ   Απο βιβλίο στα ελληνικά των Lewis-Papadimitriou είναι τα κεφάλαια
1, 2, 3.3, 4 (εκτός απο 4.4 και 4.7), 5, 6 (εκτός από τα προβλήματα βελτιστοποίησης και τις διαμερίσεις ακεραίων  δηλ. εκτός απο σελ. 379-383),
7.1. και τα εξής θεωρήματα με τις αποδείξεις τους (Θ. 7.2.3., 7.3.1, 7.3.6, 7.3.7, 7.3.8 (δείτε και τα υπόλοιπα θεωρήματα των κεφ. 7.2 και 7.3 χωρίς τις αποδείξεις τους).
 

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

Παρασκευή, 23 Οκτωβρίου 2009