Εισαγωγή στην Επιστήμη των Υπολογιστών (ΣΗΜΜΥ)
εαρινό εξάμηνο 2011-2012
Μέρος Α: Εισαγωγή σε Αλγόριθμους, Πολυπλοκότητα, Υπολογισιμότητα, Μοντέλα Προγραμματισμού
Για την σελίδα του Μέρους Β δείτε εδώ.
Γενικά
Διαλέξεις
- Δευτέρα 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).
Επίσης, για διανομή του βιβλίου "Εισαγωγή στην Επιστήμη των Υπολογιστών (Στ. Ζάχος, Ν. Κοζύρης)":
- Δευτέρα 5:00-6:00
- Τετάρτη 3:00-5:00
- Πέμπτη 1:00-2:00 & 5:00-7:00
Ανακοινώσεις
- [09/05/12] Η προθεσμία για την υποβολή της πρώτης σειράς ασκήσεων παρατείνεται έως την Τετάρτη 16/5, ώρα 23:59. Η υποβολή θα γίνει στο moodle του μαθήματος. Συνιστάται να εγγραφείτε άμεσα, ώστε να επιλυθούν τυχόν προβλήματα έγκαιρα. Συνιστάται ακόμη κατά τη δημιουργία του λογαριασμού σας να συμπεριλάβετε τον Α.Μ. σας στα στοιχεία σας.
- [26/04/12] Αναρτήθηκε η πρώτη σειρά ασκήσεων (βλ. παρακάτω), και οι διαφάνειες ανά διάλεξη.
Υλικό μαθήματος
Διαφάνειες διαλέξεων
Αντιστοιχία διαφανειών - διαλέξεων: δείτε εδώ- Ενότητα 0 - Εισαγωγή
- Διαφάνειες [pdf]
- 1η ενότητα - Υπολογιστικά Προβλήματα, Υπολογισιμότητα και Πολυπλοκότητα
- Διαφάνειες [pdf]
- 2η ενότητα - Λογική, Μοντέλα Υπολογισμού, Κλάσεις Πολυπλοκότητας
- Διαφάνειες [pdf]
- 3η ενότητα - Αυτόματα, Γλώσσες, Γραμματικές
- Διαφάνειες (τελευταίες αλλαγές: 26/3/12) [pdf]
- 4η ενότητα - Αλγοριθμικές Τεχνικές - Αριθμητικοί Υπολογισμοί
- Διαφάνειες (τελευταίες αλλαγές: 27/4/12) [pdf]
- Συμπληρωματική μελέτη: από βιβλίο Algorithms (Dasgupta-Papadimitriou-Vazirani) δείτε τα κεφ. 1 (έως και 1.4) και κεφ. 2 (έως και 2.3).
- 5η ενότητα - Γράφοι: Προβλήματα και Αλγόριθμοι
- Διαφάνειες [pdf]
- 6η ενότητα - Γλώσσες Προγραμματισμού: Θεωρητικό Υπόβαθρο και Μοντέλα
- Διαφάνειες [pdf]
- Διαφάνειες (σε Α/Μ μορφή) [pdf]
- Από που να διαβάσετε για Haskell: http://learnyouhaskell.com
Διαβάστε τις ενότητες 1 έως 6 (μέχρι την ενότητα "Lambdas") εκτός της ενότητας 3.3 ("Typeclasses 101").
Συμπληρωματικά (καθώς και για Prolog) δείτε και το Αρχές Γλωσσών Προγραμματισμού (Σημειώσεις) (Χ. Νομικός, Παν. Ιωαννίνων). - Ωραία σελίδα σχετική με Haskell: http://www.willamette.edu/~fruehr/haskell/evolution.html.
Ασκήσεις
- 1η σειρά ασκήσεων: εδώ (προθεσμία παράδοσης: 11/5/2012).
Βιβλιογραφία
- Μ. 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.