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

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

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

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

Γενικά

Διαλέξεις

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

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

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

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

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

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

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

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

  • [09/08/14] Τα αποτελέσματα της επί πτυχίω Εξεταστικής Ιουλίου 2014.
  • [19/07/14] Έκτακτο φροντιστηριακό μάθημα για θέματα Α' μέρους, Δευτέρα 21/7, ώρα 18:00-19:30, στο Αμφ. Ηλεκτρολόγων (παλ. κτήριο). Απευθύνεται κυρίως (αλλά όχι αποκλειστικά) σε όσους θα συμμετάσχουν στην επί πτυχίω εξεταστική.
  • [08/06/14] Τα αποτελέσματα της Εξεταστικής Μαρτίου 2014.
  • [18/03/14] Κατανομή αιθουσών εξέτασης: [εδώ]
    Προσοχή: η εξέταση γίνεται με κλειστά βιβλία και σημειώσεις. Δεν επιτρέπεται να έχετε στο έδρανο ή δίπλα σας τίποτε άλλο εκτός από στυλό, μολύβι και γόμα (ούτε κινητά ή άλλες συσκευές). Απαραίτητη η επίδειξη πάσου ή ταυτότητας.
  • [28/02/14] Τα αποτελέσματα της Επί Πτυχίω Εξεταστικής 2014.
  • [22/08/13] Για απορίες σχετικά με το γραπτό σας μπορείτε να έρθετε στις 29/8, ώρα 14:00-16:00, στο CoReLab (1.1.3, παλ. κτ. Ηλεκτρολόγων).
  • [26/7/2013] Τα αποτελέσματα της Κανονικής Εξέτασης 2013 είναι διαθέσιμα εδώ. Καλά αποτελέσματα και καλό καλοκαίρι!
  • [25/06/13] Κατανομή αιθουσών εξέτασης: [εδώ]
    Προσοχή: η εξέταση γίνεται με κλειστά βιβλία και σημειώσεις. Δεν επιτρέπεται να έχετε στο έδρανο τίποτε άλλο εκτός από στυλό, μολύβι και γόμα (ούτε κινητά ή άλλες συσκευές). Απαραίτητη η επίδειξη πάσου ή ταυτότητας.
  • [13/06/13] Η δυνατότητα υποβολής της 2ης σειράς ασκήσεων και της εργασίας παρατείνεται εως τις 18 Ιουνίου, ώρα 23:59. Καμμία επιπλέον παράταση δεν θα δοθεί. Η παρουσίαση των εμπρόθεσμων λύσεων θα γίνει αμέσως μετά το τέλος της εξεταστικής (συγκεκριμένα στις 12/7 αν δεν υπάρξουν στο μεταξύ αλλαγές στο πρόγραμμα).
  • [29/05/13] Αναρτήθηκε η δεύτερη σειρά ασκήσεων (βλ. εδώ). και τα προτεινόμενα θέματα για το project (βλ. εδώ).
    Διευκρινίζεται ότι η βαθμολογία στις σειρές ασκήσεων καθώς και στην εργασία θα ληφθούν υπ'όψιν μόνο εφ'όσον βελτιώνουν τη συνολική επίδοση στο Α' μέρος.
  • [24/05/13] Η διανομή των σημειώσεων συνεχίζεται στο CoReLab (Παλιά Κτίρια ΗΜΜΥ, Αιθ. 1.1.3), Δευτέρα, Πέμπτη και Παρασκευή 2:00-7:00.
  • [13/05/13] Η προθεσμία υποβολής της 1ης σειράς ασκήσεων παρατείνεται έως 15/5.
  • [12/05/13] Για την βαθμολογία της έκτακτης εξεταστικής (Μαρτίου 2013) δείτε τις Ανακοινώσεις στην σελίδα του έτους 2011-12.
  • [19/04/13] Αναρτήθηκε η πρώτη σειρά ασκήσεων (βλ. παρακάτω).
  • [08/03/13] Παρακαλούνται όλοι οι σπουδαστές να εγγραφούν στο μάθημα στο mycourses.ntua.gr.

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

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

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

Αντιστοιχία διαφανειών - διαλέξεων: δείτε εδώ
  • Ενότητα 0 - Εισαγωγή
    • Διαφάνειες [pdf]
  • 1η ενότητα - Αυτόματα, Γλώσσες, Γραμματικές
    • Διαφάνειες (τελευταίες αλλαγές: 8/3/13) [pdf]
    • Πολύ χρήσιμο εργαλείο για εξάσκηση στο σχεδιασμό και κατανόηση λειτουργίας των DFA, NFA και NFAε. (Ευχαριστίες στους δημιουργούς, σπουδαστές της ΣΗΜΜΥ, Μανόλη Ζαμπετάκη και Διονύση Ζήνδρο).
  • 2η ενότητα - Υπολογιστικά Προβλήματα, Υπολογισιμότητα και Πολυπλοκότητα
    • Διαφάνειες [pdf]
  • 3η ενότητα - Λογική, Μοντέλα Υπολογισμού, Κλάσεις Πολυπλοκότητας
    • Διαφάνειες [pdf]
  • 4η ενότητα - Αλγοριθμικές Τεχνικές - Αριθμητικοί Υπολογισμοί
    • Διαφάνειες (νέα έκδοση) [pdf]
    • Συμπληρωματική μελέτη: από βιβλίο Algorithms (Dasgupta-Papadimitriou-Vazirani) δείτε τα κεφ. 1 (έως και 1.4) και κεφ. 2 (έως και 2.3).
  • 5η ενότητα - Γλώσσες Προγραμματισμού: Θεωρητικό Υπόβαθρο και Μοντέλα
  • 6η ενότητα - Γράφοι: Προβλήματα και Αλγόριθμοι
    • Διαφάνειες [pdf]

Εργασία (project)

  • Προτεινόμενα θέματα και οδηγίες για την εκπόνηση εργασίας (προθεσμία ανάληψης: 5/6/2013, προθεσμία υποβολής: 15/6/2013).

Ασκήσεις

  • 1η σειρά ασκήσεων: εδώ (προθεσμία παράδοσης: 13/5/2013).
  • 2η σειρά ασκήσεων: εδώ (προθεσμία παράδοσης: 14/6/2013).

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

  • Μ. 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. Κυκλοφορεί και σε μετάφραση ("Στοιχεία Θεωρίας Υπολογισμού") από τις Εκδόσεις Κριτική.
  • 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.
  • S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani: "Algorithms", MacGraw-Hill, 2006 (μπορείτε να βρείτε draft έκδοση του βιβλίου αυτού εδώ).
  • A.V. Aho, J.E. Hopcroft, and J.D. Ullman: "The Design and Analysis ofComputer 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.

Τελευταία ενημέρωση: 28/02/2014