Εισαγωγή στην Επιστήμη των Υπολογιστών (ΣΗΜΜΥ)
εαρινό εξάμηνο 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 μονάδες.
- Γραπτό: 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η ενότητα - Γλώσσες Προγραμματισμού: Θεωρητικό Υπόβαθρο και Μοντέλα
- Διαφάνειες [pdf]
- Διαφάνειες (σε Α/Μ μορφή) [pdf]
- Από που να διαβάσετε για Haskell: http://learnyouhaskell.com
Διαβάστε τις ενότητες 1 έως 6 (μέχρι την ενότητα "Lambdas") εκτός της ενότητας 3.3 ("Typeclasses 101").
Συμπληρωματικά (καθώς και για Prolog) δείτε και το Αρχές Γλωσσών Προγραμματισμού (Σημειώσεις) (Χ. Νομικός, Παν. Ιωαννίνων). - Ωραία σελίδα σχετική με Haskell: http://www.willamette.edu/~fruehr/haskell/evolution.html.
Εργασία (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.