Εισαγωγή στην Επιστήμη των Υπολογιστών (ΣΗΜΜΥ)
εαρινό εξάμηνο 2010-2011

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

Για την σελίδα του Μέρους Β δείτε εδώ.

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

Γενικά

Διαλέξεις

  • Δευτέρα 15:15-17:00, αμφιθέατρα 1 και 2.
  • Παρασκευή 16:15-18:00, αμφιθέατρα 1 και 2.

Τρόπος βαθμολόγησης

Για εισαχθέντες το 2009 ("νέους"):
  • Γραπτό: 9 μονάδες συνολικά (5.5 μονάδες για μέρος Α, 3.5 μονάδες για μέρος Β). Ελάχιστη βαθμολογία γραπτού: 3 μονάδες (1.8 μονάδες για μέρος Α, 1.2 μονάδες για μέρος Β).
  • Ασκήσεις + project: 2.6 μονάδες συνολικά (0.6 μονάδες για ασκήσεις Α' μέρους, 1 μονάδα για εργασία/project Α' μέρους, 1 μονάδα για άσκηση/project B' μέρους).
  • Ελάχιστη συνολική βαθμολογία (από όλα τα παραπάνω: γραπτό, ασκήσεις, project): 5 μονάδες.
Για εισαχθέντες πριν το 2009 ("παλιούς"):
  • Γραπτό: 6 μονάδες για μέρος Α, 4 μονάδες για μέρος Β. Ελάχιστη βαθμολογία: 4.5 μονάδες (συνολικά).
  • Οι "παλιοί" σπουδαστές μπορούν να επιλέξουν να βαθμολογηθούν με το σύστημα των "νέων" (αρκεί η σχετική δήλωση στο γραπτό τους).

Διδάσκοντες (για το Μέρος Α)

  • Στάθης Ζάχος, Καθηγητής ()
  • Κωνσταντίνος Σαγώνας, Αναπλ. Καθηγητής ()
  • Άρης Παγουρτζής, Επικ. Καθηγητής ()

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

  • Δώρα Σουλίου, Ε.Ε.ΔΙ.Π.
  • Θανάσης Λιανέας, Υ.Δ. ()

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

Κάθε Τετάρτη 12:00-13:30 και Παρασκευή 12:00-13:30, στο Corelab (Κτ. Ηλεκτρολόγων, αίθ. 1.1.3) ή στο γραφείο του Α. Παγουρτζή (1.1.4).

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

  • [19/01/12] Η χαριστική εξέταση του μαθήματος θα γίνει στις 25/1/12, ώρα 12-3μμ, στην αίθουσα 1.1.29 (παλιό κτ. Ηλεκ/γων). Η συμμετοχή στην εξέταση αυτή αποκλείει τη συμμετοχή σε άλλη χαριστική εξέταση για το μάθημα αυτό.
  • [15/12/11] Ημερομηνία επίδειξης γραπτών: 21/12/2011, ώρα 2-4μμ, παλιό corelab (1.1.30).
  • [09/12/11] Αποτελέσματα επαναληπτικής εξέτασης: [εδώ]
  • [02/11/11] Κατανομή αιθουσών εξέτασης 3/11: [εδώ]
  • [21/07/11]Αποτελέσματα κανονικής εξέτασης: [εδώ]
  • [11/07/11] Κατανομή αιθουσών εξέτασης: [εδώ]
    Οδηγίες εξέτασης: Η εξέταση γίνεται με κλειστά βιβλία και σημειώσεις. Δεν επιτρέπεται η χρήση βοηθημάτων, κινητών τηλεφώνων, αριθμομηχανών, ή άλλων ηλεκτρονικών συσκευών. Επιτρέπεται η χρήση μολυβιού. Αλλαγή αίθουσας δεν επιτρέπεται χωρίς συνεννόηση με διδάσκοντα που βεβαιώνεται με την υπογραφή του στο γραπτό. Ελάχιστος χρόνος παραμονής στην αίθουσα: 1 ώρα.
  • [08/07/11] Αναρτήθηκαν οι απαντήσεις για την 2η σειρά ασκήσεων.
  • [07/07/11] Αναρτήθηκαν οι απαντήσεις για την 1η σειρά ασκήσεων.
  • [19/06/11] Η προθεσμία για την υποβολή της 2ης σειράς ασκήσεων παρατείνεται έως την Τρίτη 21/6, ώρα 23:59.
  • [10/06/11] Η προθεσμία για την υποβολή της εργασίας παρατείνεται έως την Κυριακή 12/6, ώρα 23:59.
  • [06/06/11] Αναρτήθηκε η δεύτερη σειρά ασκήσεων (βλ. παρακάτω).
  • [16/05/11] Η δήλωση εργασίας θα γίνει στο moodle του μαθήματος (περισσότερες οδηγίες εκεί). Η σχετική προθεσμία παρατείνεται έως την Τρίτη 17/5, ώρα 23:59.
  • [01/05/11] Η προθεσμία για την υποβολή των απαντήσεων παρατείνεται έως την Τετάρτη 4/5, ώρα 23:59. Είναι απαραίτητη η εγγραφή στο moodle έως Δευτέρα 2/5, ώρα 23:59. Την Δευτέρα 2/5, μετά το μάθημα (δηλ. στις 5μμ), στο Αμφ. 1, θα συζητήσουμε τυχόν απορίες για την 1η σειρά ασκήσεων.
  • [23/04/11] Αναρτήθηκαν προτεινόμενα θέματα και οδηγίες για την εργασία (project) (βλ. παρακάτω).
  • [15/04/11] Το moodle του μαθήματος είναι ενεργό. Πρέπει να γραφτείτε όλοι μέχρι την Τρίτη 26/04, ώστε να γίνει η απαραίτητη προετοιμασία για να μπορείτε να ανεβάσετε τις ασκήσεις σας. Από τα στοιχεία που θα δηλώσετε στο moodle πρέπει να προκύπτουν με σαφήνεια το Ονοματεπώνυμό σας και ο Αριθμός Μητρώου σας.
  • [15/04/11] Το τεύχος σημειώσεων του μαθήματος θα μοιραστεί σήμερα στο Νέο Κτήριο, μπροστά από το Αμφ. 1, ώρες 14:45-16:00. Η διανομή θα συνεχιστεί και Μ. Δευτέρα, Μ. Τρίτη, ώρες 12:00-14:00 στο εργαστήριο CoReLab (1.1.30 & 1.1.3, παλιό κτ. Ηλεκτρολόγων), και μετά το Πάσχα σε ώρες γραφείου.
  • [13/04/11] Το μάθημα της Πέμπτης 14/4 θα γίνει στο Νέο Κτήριο. Προς το παρόν διατίθενται οι αίθουσες 03 και 07, ενώ γίνεται προσπάθεια για να έχουμε κάποιο αμφιθέατρο (1 ή 2). Για την τελική απόφαση θα ενημερωθείτε λίγο πριν την έναρξη του μαθήματος.
  • [08/04/11] Το μάθημα της Δευτέρας 11/4 αναβάλλεται για την Πέμπτη 14/4 λόγω της προγραμματισμένης εκδήλωσης του Τομέα Τεχνολογίας Πληροφορικής και Υπολογιστών, στην οποία είναι προσκεκλημένοι όλοι οι σπουδαστές της Σχολής. Το μάθημα της Πέμπτης 14/4 θα είναι 3ωρο (15:00-18:00) - τα αμφιθέατρα στα οποία θα πραγματοποιηθεί θα ανακοινωθούν σύντομα.
  • [06/04/11] Αναρτήθηκε η πρώτη σειρά ασκήσεων (βλ. παρακάτω).

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

Διαφάνειες διαλέξεων

      Αντιστοιχία διαφανειών - διαλέξεων: εδώ
  • Ενότητα 0 - Εισαγωγή
    • Διαφάνειες [pdf]
  • 1η ενότητα - Υπολογιστικά Προβλήματα, Υπολογισιμότητα και Πολυπλοκότητα
    • Διαφάνειες [pdf]
  • 2η ενότητα - Λογική, Μοντέλα Υπολογισμού, Κλάσεις Πολυπλοκότητας
    • Διαφάνειες [pdf]
  • 3η ενότητα - Αυτόματα, Γλώσσες, Γραμματικές
    • Διαφάνειες [pdf]
  • 4η ενότητα - Αλγοριθμικές Τεχνικές - Αριθμητικοί Υπολογισμοί
    • Διαφάνειες [pdf]
  • 5η ενότητα - Γράφοι: Προβλήματα και Αλγόριθμοι
    • Διαφάνειες [pdf]
  • 6η ενότητα - Γλώσσες Προγραμματισμού: Θεωρητικό Υπόβαθρο και Μοντέλα

Εργασία (project)

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

Ασκήσεις

  • 1η σειρά ασκήσεων: εδώ (προθεσμία παράδοσης: 2/5/2011).
  • Απαντήσεις 1ης σειράς: εδώ.
  • 2η σειρά ασκήσεων: εδώ (προθεσμία παράδοσης: 19/6/2011).
  • Απαντήσεις 2ης σειράς: εδώ.

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

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

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