Θεμελιώδη Θέματα Επιστήμης Υπολογιστών
χειμερινό εξάμηνο 2014-2015

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

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

Γενικά

Το μάθημα προσφέρεται στο πρόγραμμα της Σχολής Εφαρμοσμένων Μαθηματικών και Φυσικών Επιστημών ΕΜΠ, στο 5ο εξάμηνο.

Ώρες Μαθήματος

Δευτέρα 12:00-13:00 13:00-14:00 (εργαστήριο) & 14:15-16:00 (θεωρία)
Πέμπτη 12:45-14:30 (θεωρία)

  • Θεωρία: αίθουσα 1.1.31 Παλ. Κτ. Ηλεκ/γων
  • Εργαστήριο: PCLab ΣΕΜΦΕ

Διδάσκοντες

  • Στάθης Ζάχος, Καθηγητής ()
  • Άρης Παγουρτζής, Επ. Καθηγητής ()

Υπεύθυνος εργαστηρίου

  • Δώρα Σούλιου, Ε.Ε.ΔΙ.Π. ()

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

  • Αλέξανδρος Αγγελόπουλος, Υ.Δ. ()

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

Κάθε Πέμπτη 15:00-16:00, στο Corelab (Παλαιό Κτήριο Ηλεκτρολόγων, 1ος όροφος, αίθ. 1.1.30).

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

  • [26/11/2015] Αποτελέσματα επαναληπτικής εξέτασης: [εδώ]
  • [19/08/2015] Αποτελέσματα εξέτασης επί πτυχίω: [εδώ]
  • [02/03/2015] Αποτελέσματα κανονικής εξέτασης: [εδώ]
  • [15/02/2015] Η αυριανή εξέταση θα αρχίσει στις 8:45. Η παρουσίαση των λύσεων των γραπτών ασκήσεων θα γίνει αύριο, αμέσως μετά την εξέταση. Οι απαντήσεις υποβάλλονται με email στον διδάσκοντα, έως τις 23:59 απόψε.
  • [3/2/2015] Την Παρασκευή 6/2 και ώρα 17:30 θα γίνει φροντηστηριακό μάθημα με λύση αποριών & παλιών θεμάτων, στο Αμφιθέατρο Ηλεκτρολόγων (δίπλα στο CoReLab).
  • [24/01/2015] Η παρουσίαση-εξέταση της τελευταίας σειράς εργαστηριακών ασκήσεων θα γίνει στο γραφείο 1.1.30 (παλαιό Corelab) για τους φοιτητές και των δύο τμημάτων την Πέμπτη 29 Ιανουαρίου 2015 στις 14:30
  • [15/01/2015] Αναρτήθηκε η σειρά γραπτών ασκήσεων.
  • [13/01/2015] Η εργαστηριακή εξέταση του μαθήματος θα γίνει για τους φοιτητές και των δύο τμημάτων την Δευτέρα 19/01/2015 στις 12:00-13:00 (στο εργαστήριο PCLab ΣΕΜΦΕ)
  • [13/01/2015] Αναρτήθηκε η 5η σειρά εργαστηριακών ασκήσεων. Ημερομηνία εξέτασης πέμπτης σειράς Δευτέρα 26/1/2015.
  • [15/12/2014] Αναρτήθηκε η 4η σειρά εργαστηριακών ασκήσεων. Ημερομηνία εξέτασης τέταρτης σειράς Δευτέρα 12/1/2015.
  • [5/12/2014] Αναρτήθηκε η 3η σειρά εργαστηριακών ασκήσεων. Ημερομηνία εξέτασης τρίτης σειράς Δευτέρα 22/12/2014.
  • [3/11/2014] Αναρτήθηκε η 2η σειρά εργαστηριακών ασκήσεων. Ημερομηνία εξέτασης πρώτης και δεύτερης σειράς Δευτέρα 24/11/2014.
  • [30/10/2014] Η αναπλήρωση του μαθήματος της 27/10/2014 θα γίνει την Παρασκευή 7/11/2014, 15:00-17:00 (αίθουσα 1.1.31).
  • [26/10/2014] Αύριο, Δευτέρα 27/10/2014 δεν θα γίνει μάθημα, ούτε εργαστήριο, λόγω της ημιαργίας. Θα υπάρξει επόμενη ανακοίνωση για την αναπλήρωση του μαθήματος.
  • [20/10/2014] Αύριο, Τρίτη 21/10/2014 και ώρα 12:30-14:00 θα γίνει η αναπλήρωση του σημερινού μαθήματος (αίθουσα 1.1.31).

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

    • Μ. Sipser. Introduction to the Theory of Computation. Course Technology, 2005.
      Κυκλοφορεί μεταφρασμένο στα Ελληνικά από τις Πανεπιστημιακές Εκδόσεις Κρήτης.
    • H. Lewis and Ch. Papadimitriou. Elements of the Theory of Computation (2nd edition). Prentice-Hall, 1998.
      Κυκλοφορεί μεταφρασμένο στα Ελληνικά από τις εκδόσεις Κριτική.
    • S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. Algorithms, MacGraw-Hill, 2006 (μπορείτε να βρείτε draft έκδοση του βιβλίου αυτού με αναζήτηση στο internet).
    • Martin Davis. Μηχανές της Λογικής: Οι Μαθηματικοί και οι Απαρχές του Υπολογιστή>.
      Τίτλος πρωτοτύπου: Engines of Logic: Mathematicians and the Origin of the Computer
    • Ε. Ζάχος, Θεμελιώδη Θέματα Επιστήμης Υπολογιστών, Σημειώσεις, ΕΜΠ, 2011.
    • K. Doets, and J. van Eijck: The Haskell Road to Logic, Maths and Programming, College Publications, 2004.

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

    Διαφάνειες παραδόσεων

      ΠΡΟΣΟΧΗ: Η διδαχθείσα ύλη είναι αυτή που περιέχεται στις διαφάνειες:
    • Εισαγωγή
      • Διαφάνειες [pdf]
      • Συμπληρωματική μελέτη: από βιβλίο Sipser, κεφ. 0.
    • 1η ενότητα - Γλώσσες Προγραμματισμού: Θεωρητικό Υπόβαθρο και Μοντέλα
    • 2η ενότητα - Εισαγωγή: Υπολογιστικά Προβλήματα, Υπολογισιμότητα, Πολυπλοκότητα,Μοντέλα Υπολογισμού
      • Διαφάνειες [pdf]
      • Συμπληρωματική μελέτη: από βιβλίο Sipser, κεφ. 4, 7.
    • 3η ενότητα - Αλγοριθμικές Τεχνικές - Αριθμητικοί Υπολογισμοί
      • Διαφάνειες [pdf]
      • Συμπληρωματική μελέτη: από βιβλίο Sipser, κεφ. 7.1 και από βιβλίο Algorithms (Dasgupta-Papadimitriou-Vazirani) δείτε τα κεφ. 1 (έως και 1.4) και κεφ. 2 (έως και 2.3).
    • 4η ενότητα - Αυτόματα, Γλώσσες, Γραμματικές
      • Διαφάνειες [pdf]
      • Συμπληρωματική μελέτη: από βιβλίο Sipser, κεφ. 1, 2.
    • 5η ενότητα - Λογική, Μοντέλα Υπολογισμού, Κλάσεις Πολυπλοκότητας
      • Διαφάνειες [pdf]
      • Συμπληρωματική μελέτη: από βιβλίο Sipser, κεφ. 3.1, 7.2, 7.3.
    • 6η ενότητα - Γράφοι: Προβλήματα και Αλγόριθμοι
      • Διαφάνειες [pdf]
      • Συμπληρωματική μελέτη: από βιβλίο Algorithms (Dasgupta-Papadimitriou-Vazirani) δείτε κεφ. 3 (παρ. 3.1 και 3.2), κεφ. 4 (4.1 έως και 4.4) και κεφ. 5 (παρ. 5.1).
      • NP-πληρότητα και παραδείγματα αναγωγών [pdf]

    Εργαστηριακές Ασκήσεις

    Γραπτές Ασκήσεις

    Ενδεικτικά θέματα εξετάσεων

    Συμπληρωματικό υλικό