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