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

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

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

Γενικά

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

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

Δευτέρα 14:15-16:00 (Θεωρία, Α303) & 12:45-13:45 (εργαστήριο, PCLab ΣΕΜΦΕ)
Πέμπτη 12:45-14:30 (Θεωρία, Αμφ. Ηλεκτρολόγων, Παλ. Κτ. Ηλεκ/γων)

Διδάσκοντες

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

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

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

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

  • Αντώνης Αντωνόπουλος, Υ.Δ.

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

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

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

  • [29/5/2014] Αποτελέσματα επαναληπτικής εξέτασης: [εδώ]
  • [29/5/2014] Αποτελέσματα κανονικής εξέτασης: [εδώ]
  • [14/3/2014] Αλλαγή ημερομηνίας εξέτασης: Η ημερομηνία εξέτασης του μαθήματος μεταφέρεται στις 10/4/2014, ώρα 6μμ-9μμ. Η εξέταση θα γίνει στην αίθουσα 1.1.29 του παλ. κτ. Ηλεκτρολόγων
  • [3/3/2014] Υπενθύμιση: θα πραγματοποιηθεί έκτακτο μάθημα στις 4/3, ώρα 3μμ-5μμ. Θα συζητηθούν λύσεις της 1ης σειράς γραπτών ασκήσεων καθώς και υποδείξεις για τη 2η σειρά.
  • [27/2/2014] Αναρτήθηκε η 2η σειρά γραπτών ασκήσεων.
  • [26/2/2014] Βαθμολογία Προόδου Εργαστηρίου
  • [10/2/2014] Την Δευτέρα 17/2/2014 και ώρα 13:00-14:00 θα γίνει γραπτή εξέταση στο εργαστήριο. Η βαθμολογία της εξέτασης θα αντιπροσωπεύει το 50% της βαθμολογίας του εργαστηρίου.
  • [27/1/2014] Αναρτήθηκε η 1η σειρά γραπτών ασκήσεων.
  • [25/1/2014] Την Δευτέρα 27/1/2014 θα γίνουν 2 βάρδιες εργαστηρίων 12:00-13:00 και 13:00/-14:00. Προσπαθήστε όσοι μπορείτε να έρθετε στην πρώτη βάρδια.
  • [13/1/2014] Την Δευτέρα 20/1/2014 στις 12:30 στο PCLAB του ΣΕΜΦΕ θα γίνει μία σύντομη επανάληψη των 2 πρώτων εργαστηριακών μαθημάτων για όσους απουσίαζαν ή έχουν απορίες.
    Ανακοινώθηκε η δεύτερη σειρά ασκήσεων.
  • [22/12/2013] Αύριο Δευτέρα 23 Δεκεμβρίου 2013 θα γίνει θεωρητικό μάθημα 13:15-16:00 στην αίθουσα 1.1.31, στα Παλιά Κτίρια ΗΜΜΥ.
  • [18/12/2013] Αύριο Πέμπτη 19 Δεκεμβρίου 2013 το μάθημα θα γίνει στο PClab ΣΕΜΦΕ 12:45-14:30

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

  • Μ. 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 έκδοση του βιβλίου αυτού εδώ).
  • 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] (τελευταία έκδοση: 9/1/2014)
    • Συμπληρωματική μελέτη: από βιβλίο Sipser, κεφ. 4, 7.
  • 3η ενότητα - Αλγοριθμικές Τεχνικές - Αριθμητικοί Υπολογισμοί
    • Διαφάνειες [pdf] (τελευταία έκδοση: 23/12/2013)
    • Συμπληρωματική μελέτη: από βιβλίο 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).

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

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

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

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