Θεμελιώδη Θέματα Επιστήμης Υπολογιστών
χειμερινό εξάμηνο 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).

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

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

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

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