Θεμελιώδη Θέματα Επιστήμης Υπολογιστών
χειμερινό εξάμηνο 2012-2013

Εισαγωγή σε Αλγόριθμους, Πολυπλοκότητα, Υπολογισιμότητα, Μοντέλα Προγραμματισμού, Προγραμματιστικές Τεχνικές

● Γενικά ● Ανακοινώσεις ● Βιβλιογραφία ● Υλικό μαθήματος ●

Γενικά

Ώρες Μαθήματος

Δευτέρα 14:15-16:00 (Θεωρία, Α303) & 12:45-13:45 (εργαστήριο, PCLab ΣΕΜΦΕ)
Πέμπτη 12:45-14:30 (Θεωρία, Αμφ. Ηλεκτρολόγων, Παλ. Κτ. Ηλεκ/γων)

Διδάσκοντες

  • Στάθης Ζάχος, Καθηγητής ()
  • Άρης Παγουρτζής, Επ. Καθηγητής ()

Υπεύθυνος εργαστηρίου

  • Δώρα Σούλιου, Ε.Ε.ΔΙ.Π. ()

Βοηθός διδασκαλίας

  • Ελένη Μπακάλη, Υ.Δ. ()

Ώρες γραφείου

Κάθε Πέμπτη 11:30-12:30, στο Corelab (Παλαιό Κτήριο Ηλεκτρολόγων, 1ος όροφος, αίθ. 1.1.30).

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

  • [26/02/13] Βαθμολογία κανονικής περιόδου 2012-13: [εδώ]
  • [08/01/2013]Η παράδοση και παρουσίαση της πρώτης σειράς γραπτών ασκήσεων για όσους δεν καταφέρουν να προσέλθουν την Τρίτη 8 Ιανουαρίου θα γίνει την Πέμπτη 10 Ιανουαρίου στις 11:30 στο Corelab.
  • [07/01/2013]Η παράδοση και παρουσίαση της πρώτης σειράς γραπτών ασκήσεων θα γίνει την Τρίτη 8 Ιανουαρίου 2013 στις 14:30 στο Corelab.
  • [17/12/2012]Ανακοινώθηκε η 4η σειρά εργαστηριακών ασκήσεων.
  • [17/12/2012]Η παράδοση και παρουσίαση της πρώτης σειράς γραπτών ασκήσεων θα γίνει την Τρίτη 8 Ιανουαρίου 2013. Δεν θα δωθεί νέα παράταση!
  • [26/11/2012] Δείτε στην ενότητα "Εργαστηριακές Ασκήσεις" τον σχολικό αλγόριθμο της διαίρεσης.
  • [23/11/2012] Ανακοινώθηκε η 1η σειρά γραπτών ασκήσεων, καθώς και η 3η σειρά εργαστηριακών ασκήσεων.
  • [12/11/2012] Από την ερχόμενη Δευτέρα το εργαστήριο θα πραγματοποιείται κάθε Δευτέρα και ώρα 12:45-13:45 προκειμένου να ξεκινήσει η διάλεξη του μαθήματος στις 14:00.
    Παρουσία στο εργαστήριο θα παίρνουν οι φοιτητές που είναι εκεί στην αρχή του εργαστηρίου (στις 13:45) και προϋποθέτει την παραμονή σε όλη τη διάρκεια του εργαστηρίου.
  • [05/11/2012] Η παρουσίαση της πρώτης σειράς εργαστηριακών ασκήσεων θα γίνει την Δευτέρα 12 Νοεμβρίου 13:00-14:00 στο εργαστήριο
    Ανακοινώθηκε η δεύτερη σειρά ασκήσεων με ημερομηνία επίδειξης Δευτέρα 19/11/2012 και ώρα 13:00-14:00 στο εργαστήριο.
  • [08/10/2012] Το εργαστήριο θα πραγματοποιείται κάθε Δευτέρα και ώρα 13:00-14:00 στο εργαστήριο PCLab ΣΕΜΦΕ

Βιβλιογραφία

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

Υλικό μαθήματος

Διαφάνειες παραδόσεων

ΠΡΟΣΟΧΗ: οι διαφάνειες θα ενημερώνονται κατά τη διάρκεια του εξαμήνου.
  • 1η ενότητα - Εισαγωγή: Υπολογιστικά Προβλήματα, Υπολογισιμότητα, Πολυπλοκότητα,Μοντέλα Υπολογισμού
    • Διαφάνειες [pdf]
  • 2η ενότητα - Γλώσσες Προγραμματισμού: Θεωρητικό Υπόβαθρο και Μοντέλα
  • 3η ενότητα - Αλγοριθμικές Τεχνικές - Αριθμητικοί Υπολογισμοί
    • Διαφάνειες [pdf] (τελευταία έκδοση: 1/11/2012)
    • Συμπληρωματική μελέτη: από βιβλίο Algorithms (Dasgupta-Papadimitriou-Vazirani) δείτε τα κεφ. 1 (έως και 1.4) και κεφ. 2 (έως και 2.3).
  • 4η ενότητα - Αυτόματα, Γλώσσες, Γραμματικές
    • Διαφάνειες [pdf]
  • 5η ενότητα - Γράφοι: Προβλήματα και Αλγόριθμοι
    • Διαφάνειες [pdf]
    • Συμπληρωματική μελέτη: από βιβλίο Algorithms (Dasgupta-Papadimitriou-Vazirani) δείτε κεφ. 3 (παρ. 3.1 και 3.2), κεφ. 4 (4.1 έως και 4.4) και κεφ. 5 (παρ. 5.1).
  • 6η ενότητα - Λογική, Μοντέλα Υπολογισμού, Κλάσεις Πολυπλοκότητας
    • Διαφάνειες [pdf]

Εργαστηριακές Ασκήσεις

Γραπτές Ασκήσεις

Ενδεικτικά θέματα εξετάσεων

Συμπληρωματικό υλικό

Τελευταία ενημέρωση: 08/10/2012