Εισαγωγή στην Επιστήμη των Υπολογιστών (ΣΗΜΜΥ)
εαρινό εξάμηνο 2013-2014

Μέρος Α: Εισαγωγή σε Αλγόριθμους, Πολυπλοκότητα, Υπολογισιμότητα, Μοντέλα Προγραμματισμού

Για την σελίδα του Μέρους Β δείτε εδώ.

● Γενικά ● Ανακοινώσεις ● Υλικό μαθήματος ● Βιβλιογραφία ●

Γενικά

Διαλέξεις

  • Δευτέρα 15:15-17:00, αμφιθέατρα 1 και 2.
  • Παρασκευή 15:15-17:00, αμφιθέατρα 1 και 2.

Τρόπος βαθμολόγησης Α' μέρους

Νέος τρόπος βαθμολόγησης του Α' μέρους: Η βαθμολογία καθορίζεται από τον βαθμό στο γραπτό και στις δύο σειρές ασκήσεων (δεν θα δοθεί project για φέτος). Η κάθε σειρά ασκήσεων βαθμολογείται με άριστα το 0.5. Έστω Ασκ1, Ασκ2, οι αντίστοιχες βαθμολογίες και ΔιαγΑ η βαθμολογία του Α' μέρους στο γραπτό (άριστα για το ΔιαγΑ το 6.0).
ΒαθμόςΑ = min(6, ΔιαγΑ+Ασκ1+Ασκ2)
Ελάχιστη προϋπόθεση για προβιβάσιμο βαθμό: τουλάχιστον 2.0/6.0 για το Α' μέρος.

Διδάσκοντες (για το Μέρος Α)

  • Στάθης Ζάχος, Καθηγητής ()
  • Κωνσταντίνος Σαγώνας, Αναπλ. Καθηγητής ()
  • Άρης Παγουρτζής, Επικ. Καθηγητής ()

Βοηθοί διδασκαλίας

  • Δώρα Σούλιου, Ε.ΔΙ.Π. ()
  • Δημήτρης Σακαβάλας, Υ.Δ. ()

Ώρες γραφείου

Κάθε Τετάρτη 12:30-14:00 και Παρασκευή 12:30-14:00, στο Corelab (Κτ. Ηλεκτρολόγων, αίθ. 1.1.3) ή στο γραφείο του Α. Παγουρτζή (1.1.4).

Ανακοινώσεις

  • [30/03/15] Τα αποτελέσματα εξεταστικής περιόδου Φεβρουαρίου 2015 (εξέταση 11/02/2015).
  • [10/02/2015] Κατανομή αιθουσών εξέτασης (11/02/2015)
    Προσοχή: ισχύουν οι κανόνες της προηγούμενης εξέτασης (δείτε παρακάτω).
  • [03/02/2015] Την Παρασκευή 6 Φεβρουαρίου 2015 στις 17:30 θα γίνει στο Αμφιθέατρο ηλεκτρολόγων (στις σκάλες δίπλα από το CoReLab) φροντιστηριακό μάθημα στο κομμάτι του κ. Παγουρτζή.
  • [19/12/14] Τα αποτελέσματα της επαναληπτικής εξεταστικής περιόδου 2013-14 (εξέταση 3/10/2014).
  • [2/10/14] Κατανομή αιθουσών εξέτασης (3/10/2014)
    Προσοχή: ισχύουν οι κανόνες της προηγούμενης εξέτασης (δείτε παρακάτω).
  • [30/09/14] Τα αποτελέσματα της κανονικής εξεταστικής περιόδου 2013-14 (εξέταση 28/8/2014).
  • [27/08/14] Κατανομή αιθουσών εξέτασης: [εδώ]
    Προσοχή: η εξέταση γίνεται με κλειστά βιβλία και σημειώσεις. Δεν επιτρέπεται να έχετε στο έδρανο ή δίπλα σας τίποτε άλλο εκτός από στυλό, μολύβι και γόμα (ούτε κινητά ή άλλες συσκευές). Απαραίτητη η επίδειξη πάσου ή ταυτότητας.
  • [19/07/14] Διανομή σημειώσεων: κάθε Δευτέρα, Τετάρτη και Παρασκευή, ώρα 1μμ-2μμ (και μόνο), στο εργαστήριο CoReLab (1.1.3, παλ. κτήριο). Παρακαλούμε να μην προσέρχεστε σε άλλες ώρες.
  • [10/07/14] Η προθεσμία υποβολής της 2ης σειράς ασκήσεων παρατείνεται έως τις 15/7. Η εξέταση και των δύο σειρών θα πραγματοποιηθεί την Παρασκευή 18/7, ώρα 10πμ-2μμ, στο εργαστήριο Λογικής και Υπολογισμών. Θα βγει ανακοίνωση σχετικά με την επιλογή ώρας εξέτασης.
  • [25/06/14] Ενεργοποιήθηκε στο moodle του μαθήματος η σχετική ενότητα για υποβολή της 2ης σειράς ασκήσεων. Η προθεσμία υποβολής θα παραταθεί για εύλογο χρονικό διάστημα. Θα βγει νέα ανακοίνωση σχετικά.
  • [10/06/14] Αναρτήθηκε η δεύτερη σειρά ασκήσεων ( παρακάτω). Η υποβολή των απαντήσεων γίνεται αποκλειστικά στο moodle του μαθήματος.
  • [09/05/14] Αναρτήθηκε η πρώτη σειρά ασκήσεων ( παρακάτω). Για την υποβολή των απαντήσεων θα πρέπει να εγγραφείτε στο moodle του μαθήματος.
  • [28/04/14] Παρακαλούνται όλοι οι σπουδαστές να εγγραφούν στο μάθημα στο mycourses.ntua.gr.

Υλικό μαθήματος

Διαφάνειες διαλέξεων

Οι διαφάνειες ενημερώνονται κατά τη διάρκεια του εξαμήνου. Για παλαιότερες διαφάνειες μπορείτε να ανατρέχετε στη σελίδα του προηγούμενου έτους.

Αντιστοιχία διαφανειών - διαλέξεων: δείτε εδώ
  • Ενότητα 0: Εισαγωγή
    • Διαφάνειες [pdf]
  • Ενότητα 1: Αλγοριθμικές Τεχνικές - Αριθμητικοί Υπολογισμοί - Πολυπλοκότητα Αλγορίθμων
    • Διαφάνειες (νέα έκδοση: 5/5/2014) [pdf]
    • Συμπληρωματική μελέτη: i. από βιβλίο Foundations of Computer Science (Aho-Ullman) δείτε τα κεφ. 1, 2 και 3.
      ii. Από βιβλίο Algorithms (Dasgupta-Papadimitriou-Vazirani) δείτε τα κεφ. 1 (έως και 1.4) και κεφ. 2 (έως και 2.3).
    • Συμπληρωματική μελέτη: από βιβλίο Sipser δείτε το κεφ. 7.1.
  • 2η ενότητα - Αυτόματα, Γλώσσες, Γραμματικές
    • Διαφάνειες [pdf (νέα έκδοση: 12/5/2014)]
    • Συμπληρωματική μελέτη: από βιβλίο Foundations of Computer Science (Aho-Ullman) δείτε τα κεφ. 10 και 11.
    • Πολύ χρήσιμο εργαλείο για εξάσκηση στο σχεδιασμό και κατανόηση λειτουργίας των DFA, NFA και NFAε. (Ευχαριστίες στους δημιουργούς, σπουδαστές της ΣΗΜΜΥ, Μανόλη Ζαμπετάκη και Διονύση Ζήνδρο).
  • 3η ενότητα - Λογική, Μοντέλα Υπολογισμού, Κλάσεις Πολυπλοκότητας
    • Διαφάνειες [pdf]
    • Συμπληρωματική μελέτη: από βιβλίο Foundations of Computer Science (Aho-Ullman) δείτε τα κεφ. 12, και 14 (ενδιαφέρον και το κεφ. 13).
  • 4η ενότητα - Υπολογισιμότητα και Πολυπλοκότητα
    • Διαφάνειες [pdf]
    • Συμπληρωματική μελέτη: από βιβλίο Sipser δείτε τα κεφ. 3 (3.1 μόνο), 4 και 7 (7.2-7.4). Από βιβλίο Lewis-Papadimitriou δείτε τα κεφ. 4 (4.1 & 4.2), 5 (5.1-5.4, 5.7), 6 και 7 (7.1 μόνο)
  • 5η ενότητα - Γλώσσες Προγραμματισμού: Θεωρητικό Υπόβαθρο και Μοντέλα
  • 6η ενότητα - Γράφοι: Προβλήματα και Αλγόριθμοι
    • Διαφάνειες [pdf]

Ασκήσεις

  • 1η σειρά ασκήσεων: εδώ (προθεσμία παράδοσης: 27/5/2014).
  • 2η σειρά ασκήσεων: εδώ (προθεσμία παράδοσης: 26/6/2014 15/7/2014).

Βιβλιογραφία

  • Μ. Sipser: "Introduction to the Theory of Computation", 2nd edition, Course Technology, 2005. Κυκλοφορεί και σε μετάφραση ("Εισαγωγή στη Θεωρία Υπολογισμού") από τις Παν. Εκδόσεις Κρήτης.
  • H.R. Lewis and C.H. Papadimitriou: "Elements of the Theory of Computation", 2nd edition, Prentice Hall, 1997. Κυκλοφορεί και σε μετάφραση ("Στοιχεία Θεωρίας Υπολογισμού") από τις Εκδόσεις Κριτική.
  • Al Aho and Jeff Ullman: "Foundations of Computer Science", W.H.Freeman, 1992, free online.
  • S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani: "Algorithms", MacGraw-Hill, 2006 (μπορείτε να βρείτε draft έκδοση του βιβλίου αυτού εδώ).
  • D. Harel: "Algorithmics: The Spirit of Computing", Addison-Wesley, Reading, MA, 1st edition, 1987; 2nd edition, 1992. 3rd edition (with Y. Feldman), 2004.
  • D.C. Kozen: "Automata and Computability", Springer, 1997.
  • J.E. Hopcroft, R. Motwani and J.D. Ullman: "Introduction to Automata Theory, Languages and Computation", 3rd edition, Prentice Hall, 2007.
  • H.B. Enderton: "A Mathematical Introduction to Logic", Academic Press, 1st edition, 1972; 2nd edition, 2001.
  • A.V. Aho, J.E. Hopcroft, and J.D. Ullman: "The Design and Analysis of Computer Algorithms", Addison-Wesley Series in Computer Science andInformation Processing, 1974.
  • A. Levitin: "Ανάλυση και Σχεδίαση Αλγορίθμων", Εκδόσεις Τζιόλα, 2007.
  • K. Doets, and J. van Eijck: "The Haskell Road to Logic, Maths and Programming", College Publications, 2004.