Αρχική σελίδα | Επικοινωνία | Πίνακας πλοήγησης |

Παλαιότερα έτη

• 2014-2015
• 2013-2014
• 2012-2013
• 2011-2012
• 2010-2011

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

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

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

Γενικά

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

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

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

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

Διδάσκοντες

• Στάθης Ζάχος, Καθηγητής ()
• Πέτρος Ποτίκας, Ε.ΔΙ.Π. ()

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

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

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

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

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

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

• [20/10/2016] Αποτελέσματα επαναληπτικής εξέτασης: [εδώ]
• [22/7/2016] Αποτελέσματα επί πτυχίω εξέτασης: [εδώ]
• [17/3/2016] Αποτελέσματα κανονικής εξέτασης: [εδώ]
• [21/12/2015] Την Δευτέρα 11/1/2016 και ώρα 12:35 θα γίνει γραπτή εξέταση στο εργαστήριο. Η βαθμολογία της εξέτασης θα αντιπροσωπεύει το 50% της βαθμολογίας του εργαστηρίου.
• [21/12/2015] Αναρτήθηκε η 5η σειρά εργαστηριακών ασκήσεων. Ημερομηνία εξέτασης πέμπτης σειράς Δευτέρα 11/1/2016.
• [23/11/2015] Αναρτήθηκε η 4η σειρά εργαστηριακών ασκήσεων. Ημερομηνία εξέτασης τέταρτης σειράς Δευτέρα 21/12/2015.
• [23/11/2015] Αναρτήθηκε η 3η σειρά εργαστηριακών ασκήσεων. Ημερομηνία εξέτασης τρίτης σειράς Δευτέρα 7/12/2015.
• [09/11/2015] Αναρτήθηκε η 2η σειρά εργαστηριακών ασκήσεων. Ημερομηνία εξέτασης δεύτερης σειράς Δευτέρα 23/11/2015.
• [26/10/2015] Αναρτήθηκε η 1η σειρά εργαστηριακών ασκήσεων. Ημερομηνία εξέτασης πρώτης σειράς Δευτέρα 2/11/2015.

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

• Μ. 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η ενότητα - Γλώσσες Προγραμματισμού: Θεωρητικό Υπόβαθρο και Μοντέλα
  • Διαφάνειες [pdf]
  • Από που να διαβάσετε για Haskell: http://learnyouhaskell.com Διαβάστε τις ενότητες 1 έως 6 (μέχρι την ενότητα "Lambdas") εκτός της ενότητας 3.3 ("Typeclasses 101").
  • Συμπληρωματικά δείτε και το Αρχές Γλωσσών Προγραμματισμού (Σημειώσεις) (Χ. Νομικός, Παν. Ιωαννίνων).
• 2η ενότητα - Εισαγωγή: Υπολογιστικά Προβλήματα, Υπολογισιμότητα, Πολυπλοκότητα,Μοντέλα Υπολογισμού
  • Διαφάνειες [pdf]
  • Συμπληρωματική μελέτη: από βιβλίο Sipser, κεφ. 4, 7.
• 3η ενότητα - Αυτόματα, Γλώσσες, Γραμματικές
  • Διαφάνειες [pdf]
  • Συμπληρωματική μελέτη: από βιβλίο Sipser, κεφ. 1, 2.
• 4η ενότητα - Λογική, Μοντέλα Υπολογισμού, Κλάσεις Πολυπλοκότητας
  • Διαφάνειες [pdf]
  • Συμπληρωματική μελέτη: από βιβλίο Sipser, κεφ. 3.1, 7.2, 7.3.
• 5η ενότητα - Αλγοριθμικές Τεχνικές - Αριθμητικοί Υπολογισμοί
  • Διαφάνειες [pdf]
  • Συμπληρωματική μελέτη: από βιβλίο Sipser, κεφ. 7.1 και από βιβλίο Algorithms (Dasgupta-Papadimitriou-Vazirani) δείτε τα κεφ. 1 (έως και 1.4) και κεφ. 2 (έως και 2.3).
• 6η ενότητα - Γράφοι: Προβλήματα και Αλγόριθμοι
  • Διαφάνειες [pdf]
  • Συμπληρωματική μελέτη: από βιβλίο (Dasgupta-Papadimitriou-Vazirani) δείτε κεφ. 3 (παρ. 3.1 και 3.2), κεφ. 4 (4.1 έως και 4.4) και κεφ. 5 (παρ. 5.1).
  • NP-πληρότητα και παραδείγματα αναγωγών [pdf]

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

• 1η σειρά εργαστηριακών ασκήσεων. Ημερομηνία εξέτασης και παρουσίασης 2/11/2015.
• 2η σειρά εργαστηριακών ασκήσεων. Ημερομηνία εξέτασης και παρουσίασης 23/11/2015.
• Σχολικός Αλγόριθμος της Διαίρεσης.
• 3η σειρά εργαστηριακών ασκήσεων. Ημερομηνία εξέτασης και παρουσίασης 7/12/2015.
• 4η σειρά εργαστηριακών ασκήσεων. Ημερομηνία εξέτασης και παρουσίασης 21/12/2015.
• 5η σειρά εργαστηριακών ασκήσεων. Ημερομηνία εξέτασης και παρουσίασης 11/01/2016.

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

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

• Επαναληπτική εξέταση 2010-11.

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

• About Complexity Theory.
• Παράδειγμα μηχανής Turing & Turing machine Simulator.