Εισαγωγή στην Επιστήμη των Υπολογιστών (ΣΗΜΜΥ)
εαρινό εξάμηνο 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
στο CoReLab, (Παλιά) Κτίρια Ηλεκτρολόγων, αιθ. 1.1.3.

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

  • [12/05/13] Βαθμολογία έκτακτης εξεταστικής Μαρτίου 2013: [εδώ]
  • [30/11/12] Η επίδειξη γραπτών της επαναληπτικής εξέτασης θα πραγματοποιηθεί στο CoReLab, στις 5/12/2012, ώρα 12-2. Δικαίωμα προσέλευσης έχουν μόνο όσοι στείλουν email έως 30/11, ώρα 23:59.
  • [14/11/12] Βαθμολογία επαναληπτικής περιόδου: [εδώ]
  • [12/09/12] Κατανομή αιθουσών εξέτασης: [εδώ]
    Προσοχή: η εξέταση γίνεται με κλειστά βιβλία και σημειώσεις. Δεν επιτρέπεται να έχετε στο έδρανο κινητό, αριθμομηχανή, ή άλλες συσκευές. Απαραίτητη η επίδειξη πάσου ή ταυτότητας.
  • [11/09/12] Η εξέταση της 13/9 θα πραγματοποιηθεί κανονικά.
  • [18/08/12] Μπορείτε να δείτε το γραπτό σας στις 24/8, ώρα 14:30-16:30, στο παλιό corelab (1.1.31, παλ. κτ. Ηλεκτρολόγων).
  • [02/08/12] Βαθμολογία κανονικής περιόδου: [εδώ]
  • [12/07/12] Κατανομή αιθουσών εξέτασης: [εδώ]
    Προσοχή: η εξέταση γίνεται με κλειστά βιβλία και σημειώσεις. Δεν επιτρέπεται να έχετε στο έδρανο τίποτε άλλο εκτός από στυλό, μολύβι και γόμα (ούτε κινητά ή άλλες συσκευές). Απαραίτητη η επίδειξη πάσου ή ταυτότητας.
  • [12/07/12] Για διευκόλυνσή σας έχουν "ξεκλειδωθεί" οι απαντήσεις στις σειρές ασκήσεων των 2 προηγουμένων ετών. Επίσης στις 'Ανακοινώσεις' του έτους 2008-09 υπάρχουν κάποιες λύσεις παλιών θεμάτων.
  • [15/06/12] Η προθεσμία υποβολής του project παρατείνεται έως τη Δευτέρα 18/6, ώρα 23:59.
  • [25/05/12] Αναρτήθηκαν τα προτεινόμενα θέματα για το project (βλ. παρακάτω).
  • [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η ενότητα - Γλώσσες Προγραμματισμού: Θεωρητικό Υπόβαθρο και Μοντέλα

Εργασία (project)

  • Προτεινόμενα θέματα και οδηγίες για την εκπόνηση εργασίας (προθεσμία ανάληψης: 1/6/2012, προθεσμία υποβολής: 15/6/2012).

Ασκήσεις

  • 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.

Τελευταία ενημέρωση: 12/05/2013