Δες Ανακοίνωσεις !

Γενικά

Υποχρεωτικό Μάθημα στο Προπτυχιακό Επίπεδο, το οποίο πιστώνεται με 8 Μονάδες ECTS.

Συμβόλαιο Μαθήματος

Διδάσκων

    Παπαδοπούλου Βίκη, Επισκέπτρια Λέκτορας

• Γραφείο: Β120, Κτίριο FST 01         
• Τηλέφωνο: (22) 892744          
• Ηλεκτρονικό Ταχυδρομείο: viki@ucy.ac.cy
• Ώρες Γραφείου:  Τετάρτη & Πέμπτη, 15:30--17:00,  ή με ραντεβού (το οποίο μπορεί να διευθετηθεί μέσω ηλεκτρονικού ταχυδρομείου).

Διαλέξεις και Φροντιστήριο   

• Τρίτη & Παρασκευή: 12:00--13:30 (διαλέξεις, A Ακροατήριο)
• Τρίτη & Παρασκευή: 13:30--15:00 (διαλέξεις, Β Ακροατήριο)
• Τρίτη: 16:30--17:30 (φροντιστήριo, A Ακροατήριο)
• Παρασκευή: 17:00--18:00 (φροντιστήριο, Β Ακροατήριο)

Διδακτικός Βοηθός

    Λουκία Παπακωνσταντίνου

• email: cs01pl@cs.ucy.ac.cy

• Ώρες γραφείου: 15:30-16:30, γραφείο 214, Τρίτη και Παρασκευή.

Προαπαιτούμενα

• ΜΑΣ004--Εισαγωγικά Μαθηματικά

• ΕΠΛ111--Διακριτές Δομές στην Πληροφορική και Υπολογισμό

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

Τυπικά μοντέλα υπολογισμού βασισμένα σε μηχανές, γραμματικές και γλώσσες: πεπερασμένα αυτόματα έναντι κανονικών γλωσσών, αυτόματα με στοίβα έναντι γλωσσών ανεξαρτήτων από συμφραζόμενα, μηχανές Turing έναντι γενικών γραμματικών. Μοντέλα υπολογισμού ισοδύναμα προς τη μηχανή Turing και το αίτημα του Church. Υπολογισιμότητα και Μη Υπολογισιμότητα. Εισαγωγή στη Θεωρία της Υπολογιστικής Πολυπλοκότητας, με έμφαση στη θεωρία της NP-πληρότητας.

Γραπτά Βοηθήματα

• Μ. Μαυρονικόλας, Θεωρία Υπολογισμού, προσχέδιο βιβλίου,  Δεκέμβριος 2006

• H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation,  Second Edition, Prentice-Hall, 1998.

• H. R. Lewis και Χ. Χ. Παπαδημητρίου, Στοιχεία Θεωρίας Υπολογισμού, Εκδόσεις Κριτική, Επιστημονική Βιβλιοθήκη, 2005. (ελληνική μετάφραση του προηγούμενου βιβλίου)

Συμπληρωματικά Βοηθήματα

• J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2nd Ed. (2000).

Αξιολόγηση

• Τελική εξέταση: 60%

• Ενδιάμεση εξέταση: 20%

• Κατ' οίκον εργασία: 16%

• Συμμετοχή στην τάξη και παρακολούθηση: 4%

Για την εξασφάλιση προβιβάσιμου βαθμού στο μάθημα (δηλαδή, βαθμού τουλάχιστον πέντε), είναι απαραίτητο όπως ένας τουλάχιστον από τους βαθμούς στον ενδιάμεσο και τον τελικό διαγωνισμό είναι τουλάχιστον 40%. Σε αντίθετη περίπτωση, ο τελικός βαθμός του μαθήματος θα είναι ο μέσος όρος των δύο βαθμών στην ενδιάμεση και την τελική εξέταση. Η τελική και η ενδιάμεση εξέταση θα διεξαχθούν αμφότερες με ανοικτά βιβλία και σημειώσεις. Αμφότερες οι εξετάσεις δυνατό να περιλαμβάνουν παραλλαγές προβλημάτων που περιλήφθηκαν σε σειρές ασκήσεων, ή παρουσιάστηκαν στις διαλέξεις ή το φροντιστήριο.

Η ενδιάμεση εξέταση θα πραγματοποιηθεί 6 Μαρτίου, 2007.

Προηγούμενες Διδασκαλίες Μαθήματος

Το μάθημα διδασκόταν από τον Αναπληρωτή Καθηγητή κ.  Μάριο Μαυρονικόλα

• 2006

• 2005