Θεμελιώδη Θέματα Επιστήμης Υπολογιστών
χειμερινό εξάμηνο 2010-2011
Εισαγωγή σε Αλγόριθμους, Πολυπλοκότητα, Υπολογισιμότητα, Μοντέλα Προγραμματισμού
Γενικά
Ώρες Μαθήματος
Δευτέρα 14:15-16:00 (Θεωρία, Α303) & 16:00-17:00 (εργαστήριο, PCLab ΣΕΜΦΕ)
Πέμπτη 12:45-14:30 (Θεωρία, Α303)
Διδάσκοντες
- Στάθης Ζάχος, Καθηγητής ()
- Άρης Παγουρτζής, Επ. Καθηγητής ()
Υπεύθυνος εργαστηρίου
- Δώρα Σούλιου, Ε.Ε.ΔΙ.Π.
Βοηθός διδασκαλίας
- Θανάσης Λιανέας, Υ.Δ. ()
Ώρες γραφείου
Κάθε Δευτέρα 13:00-14:00 και Πέμπτη 15:00-16:00, στο Corelab (Κτ. Ηλεκτρολόγων, αίθ. 1.1.30).
Ανακοινώσεις
- [16/01/11] Ανακοινώθηκε η τέταρτη σειρά ασκήσεων.
- [17/12/10] Ανακοινώθηκε η τρίτη σειρά ασκήσεων.
- [20/10/10] Ανακοινώθηκε η πρώτη σειρά ασκήσεων.
Βιβλιογραφία
Προτεινόμενη βιβλιογραφία
- Μ. 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.
Κυκλοφορεί μεταφρασμένο στα Ελληνικά από τις εκδόσεις Κριτική. - Martin Davis, Μηχανές της Λογικής: Οι Μαθηματικοί και οι Απαρχές του Υπολογιστή.
Τίτλος πρωτοτύπου: Engines of Logic: Mathematicians and the Origin of the Computer
Υλικό μαθήματος
Διαφάνειες παραδόσεων
- 1η ενότητα - Εισαγωγή: Υπολογιστικά Προβλήματα, Υπολογισιμότητα, Πολυπλοκότητα,Μοντέλα Υπολογισμού
- Διαφάνειες [pdf]
- 2η ενότητα - Γλώσσες Προγραμματισμού: Θεωρητικό Υπόβαθρο και Μοντέλα
- Διαφάνειες [pdf] (μόνο οι διαφάνειες 30-57)
- Από που να διαβάσετε για Haskell: http://learnyouhaskell.com
Διαβάστε τις ενότητες 1 έως 6 (μέχρι την ενότητα "Lambdas") εκτός της ενότητας 3.3 ("Typeclasses 101").
Συμπληρωματικά δείτε και το Αρχές Γλωσσών Προγραμματισμού (Σημειώσεις) (Χ. Νομικός, Παν. Ιωαννίνων).
- 3η ενότητα - Αλγοριθμικές Τεχνικές - Αριθμητικοί Υπολογισμοί
- Διαφάνειες [pdf]
- 4η ενότητα - Αυτόματα, Γλώσσες, Γραμματικές
- Διαφάνειες [pdf]
- 5η ενότητα - Γράφοι: Προβλήματα και Αλγόριθμοι
- Διαφάνειες [pdf]
- 6η ενότητα - Λογική, Μοντέλα Υπολογισμού, Κλάσεις Πολυπλοκότητας
- Διαφάνειες [pdf]
Ασκήσεις
Λυμένες ασκήσεις
- Παλιότερα θέματα εξετάσεων και λύσεις σε αυτόματα/τυπικές γλώσσες/λογική: [set1], [set2], [set3]
- Σχετικές ασκήσεις και λύσεις από το μάθημα "Εισαγωγή στην Επιστήμη των Υπολογιστών (ΣΗΜΜΥ)": [εδώ (δείτε στο τέλος της σελίδας)]