Εισαγωγή στην Επιστήμη των Υπολογιστών (ΣΗΜΜΥ)
εαρινό εξάμηνο 2012-2013
Μέρος Α: Εισαγωγή σε Αλγόριθμους, Πολυπλοκότητα, Υπολογισιμότητα, Μοντέλα Προγραμματισμού
Για την σελίδα του Μέρους Β δείτε εδώ.
Γενικά
Διαλέξεις
- Δευτέρα 15:15-17:00, αμφιθέατρα 1 και 2.
- Παρασκευή 16:15-18:00, αμφιθέατρα 1 και 2.
Διδάσκοντες (για το Μέρος Α)
- Στάθης Ζάχος, Καθηγητής ()
- Κωνσταντίνος Σαγώνας, Αναπλ. Καθηγητής ()
- Άρης Παγουρτζής, Επικ. Καθηγητής ()
Βοηθοί διδασκαλίας
- Δώρα Σούλιου, Ε.Ε.ΔΙ.Π. ()
- Δημήτρης Σακαβάλας, Υ.Δ. ()
Ώρες γραφείου
Κάθε Τετάρτη 12:00-13:30 και Παρασκευή 12:00-13:30, στο Corelab (Κτ. Ηλεκτρολόγων, αίθ. 1.1.3) ή στο γραφείο του Α. Παγουρτζή (1.1.4).
Ανακοινώσεις
- [13/05/13] Η προθεσμία υποβολής της 1ης σειράς ασκήσεων παρατείνεται έως 15/5.
- [12/05/13] Για την βαθμολογία της έκτακτης εξεταστικής (Μαρτίου 2013) δείτε τις Ανακοινώσεις στην σελίδα του έτους 2011-12.
- [19/04/13] Αναρτήθηκε η πρώτη σειρά ασκήσεων (βλ. παρακάτω).
- [08/03/13] Παρακαλούνται όλοι οι σπουδαστές να εγγραφούν στο μάθημα στο mycourses.ntua.gr.
Υλικό μαθήματος
Διαφάνειες διαλέξεων
Οι διαφάνειες ενημερώνονται κατά τη διάρκεια του εξαμήνου. Για παλαιότερες διαφάνειες μπορείτε να ανατρέχετε στη σελίδα του προηγούμενου έτους.Αντιστοιχία διαφανειών - διαλέξεων: δείτε εδώ
- Ενότητα 0 - Εισαγωγή
- Διαφάνειες [pdf]
- 1η ενότητα - Αυτόματα, Γλώσσες, Γραμματικές
- Διαφάνειες (τελευταίες αλλαγές: 8/3/13) [pdf]
- Πολύ χρήσιμο εργαλείο για εξάσκηση στο σχεδιασμό και κατανόηση λειτουργίας των DFA, NFA και NFAε. (Ευχαριστίες στους δημιουργούς, σπουδαστές της ΣΗΜΜΥ, Μανόλη Ζαμπετάκη και Διονύση Ζήνδρο).
- 2η ενότητα - Υπολογιστικά Προβλήματα, Υπολογισιμότητα και Πολυπλοκότητα
- Διαφάνειες [pdf]
- 3η ενότητα - Λογική, Μοντέλα Υπολογισμού, Κλάσεις Πολυπλοκότητας
- Διαφάνειες [pdf]
- 4η ενότητα - Αλγοριθμικές Τεχνικές - Αριθμητικοί Υπολογισμοί
- Διαφάνειες (νέα έκδοση) [pdf]
- Συμπληρωματική μελέτη: από βιβλίο Algorithms (Dasgupta-Papadimitriou-Vazirani) δείτε τα κεφ. 1 (έως και 1.4) και κεφ. 2 (έως και 2.3).
- 5η ενότητα - Γλώσσες Προγραμματισμού: Θεωρητικό Υπόβαθρο και Μοντέλα
- Διαφάνειες (νέα έκδοση) [pdf]
- Διαφάνειες (νέα έκδοση, σε Α/Μ μορφή) [pdf]
- Από που να διαβάσετε για Haskell: http://learnyouhaskell.com
Διαβάστε τις ενότητες 1 έως 6 (μέχρι την ενότητα "Lambdas") εκτός της ενότητας 3.3 ("Typeclasses 101").
Συμπληρωματικά (καθώς και για Prolog) δείτε και το Αρχές Γλωσσών Προγραμματισμού (Σημειώσεις) (Χ. Νομικός, Παν. Ιωαννίνων). - Ωραία σελίδα σχετική με Haskell: http://www.willamette.edu/~fruehr/haskell/evolution.html.
- 6η ενότητα - Γράφοι: Προβλήματα και Αλγόριθμοι
- Διαφάνειες [pdf]
Ασκήσεις
- 1η σειρά ασκήσεων: εδώ (προθεσμία παράδοσης: 13/5/2013).
Βιβλιογραφία
- Μ. Sipser: "Introduction to the Theory of Computation", 2nd edition, Course Technology, 2005. Κυκλοφορεί και σε μετάφραση ("Εισαγωγή στη Θεωρία Υπολογισμού") από τις Παν. Εκδόσεις Κρήτης.
- H.R. Lewis and C.H. Papadimitriou: "Elements of the Theory of Computation", 2nd edition, Prentice Hall, 1997. Κυκλοφορεί και σε μετάφραση ("Στοιχεία Θεωρίας Υπολογισμού") από τις Εκδόσεις Κριτική.
- D. Harel: "Algorithmics: The Spirit of Computing", Addison-Wesley, Reading, MA, 1st edition, 1987; 2nd edition, 1992. 3rd edition (with Y. Feldman), 2004.
- D.C. Kozen: "Automata and Computability", Springer, 1997.
- J.E. Hopcroft, R. Motwani and J.D. Ullman: "Introduction to Automata Theory, Languages and Computation", 3rd edition, Prentice Hall, 2007.
- H.B. Enderton: "A Mathematical Introduction to Logic", Academic Press, 1st edition, 1972; 2nd edition, 2001.
- S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani: "Algorithms", MacGraw-Hill, 2006 (μπορείτε να βρείτε draft έκδοση του βιβλίου αυτού εδώ).
- A.V. Aho, J.E. Hopcroft, and J.D. Ullman: "The Design and Analysis ofComputer Algorithms", Addison-Wesley Series in Computer Science andInformation Processing, 1974.
- A. Levitin: "Ανάλυση και Σχεδίαση Αλγορίθμων", Εκδόσεις Τζιόλα, 2007.
- K. Doets, and J. van Eijck: "The Haskell Road to Logic, Maths and Programming", College Publications, 2004.