Αλγόριθμοι και Πολυπλοκότητα (ΣΗΜΜΥ)
χειμερινό εξάμηνο 2009-2010

● Γενικά ● Ανακοινώσεις ● Υλικό ● Ασκήσεις ●

Γενικά

Διδάσκοντες

  • Στάθης Ζάχος, Καθηγητής ()
  • Δημήτρης Φωτάκης, Λέκτορας ()

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

  • Γεωργία Καούρη, Υ.Δ. ()

Διαλέξεις (θεωρία)

  • κάθε Δευτέρα 15:00-17:00 (Αμφιθέατρο 5, νέο κτήριο Ηλεκτρολόγων)
  • κάθε Πέμπτη 17:00-18:00 (Αίθουσα 06, νέο κτήριο Ηλεκτρολόγων)

Ασκήσεις

  • κάθε Πέμπτη 18:00-19:00 (Αίθουσα 06, νέο κτήριο Ηλεκτρολόγων)

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

  • κάθε Δευτέρα 12:00-14:00 στο εργαστήριο 1.1.30 (CoReLab) και στο γρ. 1.1.10 του κτηρίου Ηλεκτρολόγων
  • κάθε Πέμπτη 14:00-16:00 στο εργαστήριο 1.1.30 (CoReLab) και στο γρ. 1.1.10 του κτηρίου Ηλεκτρολόγων

Ενημερωτικό φυλλάδιο

Μπορείτε να βρείτε το ενημερωτικό φυλλάδιο του μαθήματος εδώ.

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

  1. Thomas Cormen, Charles Leiserson, Ronald Rivest and Cliff Stein: "Introduction to Algorithms", 2nd edition, MIT Press, 2001.
  2. J. Kleinberg, E. Tardos: "Algorithm Design", Addison-Wesley, 2005.
  3. S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani: "Algorithms", MacGraw-Hill, 2006 (Μπορείτε να βρείτε draft έκδοση του βιβλίου αυτού εδώ).
  4. G. Brassard, P. Bratley: "Algorithmics: Theory and Practice", Prentice-Hall.
  5. Sara Baase, Allen Van Gelder, "Computer Algorithms: Introduction to Design and Analysis", 3rd edition, Addison Wesley Longman, 2000.
  6. Alfred V. Aho, John E. Hopcroft, "The Design and Analysis of Computer Algorithms", Addison-Wesley Series in Computer Science and Information Processing, 1974.
  7. Dexter C. Kozen, "The Design and Analysis of Algorithms", Springer, 1991.
  8. A. Levitin: "Ανάλυση και Σχεδίαση Αλγορίθμων", Εκδόσεις Τζιόλα, 2007.
  9. G. J. E. Rawlings: "Αλγόριθμοι: Ανάλυση και Σύγκριση", Εκδόσεις Κριτική, 2004.

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

  • [4/10/2010] Βαθμολογία επαναληπτικής εξέτασης Σεπτεμβρίου 2010. Μπορείτε να δείτε τα γραπτά σας και να ρωτήσετε για την βαθμολογία σας την Πέμπτη 7 Οκτωβρίου, ώρα 15:00-16:00, στο CoReLab (1.1.30).
  • [2/3/2010] Βαθμολογία Φεβρουαρίου 2010.
  • [11/1/2010] ΠΡΟΣΟΧΗ: Έχει προγραμματιστεί διάλεξη αναπλήρωσης για την Τρίτη 12/1, ώρα 13:00 - 15:00, στην Αιθ. 02, του νέου κτηρίου Ηλεκτρολόγων.
  • [8/1/2010] Έχει "ανοίξει" η ενότητα του grader για την υποβολή και την ηλεκτρονική αξιολόγηση της 5ης προγραμματιστικής εργασίας. Για την υποβολή ισχύει ότι και για τις προηγούμενες εργασίες. Η προθεσμία για την υποβολή της εργασίας λήγει την Δευτέρα 18/1 (τα μεσάνυκτα). Όσοι αντιμετωπίσουν προβλήματα με τον grader ή χρησιμοποιούν Java, θα ανεβάσουν τις απαντήσεις τους στο moodle και θα τις επιδείξουν στο Corelab (1.1.30), την Τρίτη 19/1, 16:00-18:00. Καλή επιτυχία!
  • [7/1/2010] Στο moodle του μαθήματος, στην ενότητα Συζητήσεις, έχει ανακοινωθεί το link όπου υπάρχουν οι διαφάνειες του μαθήματος (powerpoint).
  • [14/12/2009] ΠΡΟΣΟΧΗ: Χρειάστηκε γίνει μια (αρκετά σημαντική) διόρθωση στα προγράμματα ελέγχου υποβολής στον grader για τους αλγόριθμους Dijkstra και Bellman-Ford. Έτσι όσοι έχετε ήδη υποβάλλει λύσεις για αυτούς τους αλγόριθμους (ακόμη και αν οι λύσεις σας εμφανίζονται ως σωστές και "active"), πρέπει οπωσδήποτε να τις υποβάλλετε εκ νέου πριν την λήξη της προθεσμίας.
  • [10/12/2009] Έχει "ανοίξει" η ενότητα του grader για την υποβολή και την ηλεκτρονική αξιολόγηση της 4ης προγραμματιστικής εργασίας. Για την υποβολή, θα χρησιμοποιήσετε τα login name και password που έχετε για το moodle του μαθήματος. Τα προγράμματά σας πρέπει να είναι σε C/C++, να διαβάζουν την είσοδο από το standard input, να τυπώνουν την έξοδο στο standard output, και να επιστρέφουν 0 όταν ολοκληρώνονται κανονικά. Για τα test cases υποβολής και αξιολόγησης, ισχύει ότι και για την 3η εργασία. Η προθεσμία για την υποβολή της εργασίας λήγει την Πέμπτη 17/12 (τα μεσάνυκτα). Όσοι αντιμετωπίσουν προβλήματα με τον grader ή χρησιμοποιούν Java, θα ανεβάσουν τις απαντήσεις τους στο moodle και θα τις επιδείξουν στο Corelab (1.1.30), την Παρασκευή 18/12, είτε 10:45-12:45 είτε 15:00-17:00. Καλή επιτυχία!
  • [10/12/2009] Λόγω των κινητοποιήσεων που αποφάσισε ο Φοιτητικός Σύλλογος, δίνεται νέα παράταση στην προθεσμία για την παράδοση της 4ης γραπτής εργασίας μέχρι την Δευτέρα 14/12. Στο μάθημα της Δευτέρας 14/12 θα καθορίσουμε ημέρες και ώρες για την αναπλήρωση των μαθημάτων που χάθηκαν εξ' αιτίας των κινητοποιήσεων.
  • [3/12/2009] Λόγω των κινητοποιήσεων που αποφάσισε ο Φοιτητικός Σύλλογος, δίνεται παράταση στην προθεσμία για την παράδοση της 4ης γραπτής εργασίας μέχρι την Πέμπτη 10/12. Επίσης, η επίδειξη της 3ης προγραμματιστικής εργασίας (μόνο για όσους αντιμετώπισαν προβλήματα με τον grader) θα γίνει στο Corelab (1.1.30), την Τρίτη 8/12, 16:00-18:00.
  • [25/11/2009] Υπάρχει δυνατότητα ηλεκτρονικής αξιολόγησης των απαντήσεων για την 3η προγραμματιστική εργασία (αντί της επίδειξης στο Corelab). Για να αξιολογηθείτε ηλεκτρονικά, θα υποβάλετε το source code των απαντήσεων στον grader (θερμές ευχαριστίες στον κ. Παπασπύρου για την πολύτιμη βοήθειά του!). Για την υποβολή, θα χρησιμοποιήσετε τα login name και password που έχετε για το moodle του μαθήματος. Τα προγράμματά σας πρέπει να είναι σε C/C++, να διαβάζουν την είσοδο από το standard input και να τυπώνουν την έξοδο στο standard output. Μια υποβολή θεωρείται επιτυχής (και συνεχίζει στο στάδιο της αξιολόγησης) αν "περάσει" επιτυχώς 3 επιλεγμένα test cases για το αντίστοιχο ερώτημα. Η αξιολόγηση γίνεται με αντίστοιχα (κοινά για όλους, αλλά διαφορετικά από αυτά που ελέγχονται κατά την υποβολή) test cases, μετά την λήξη της προθεσμίας. Για την καλύτερη εξοικείωσή σας με το σύστημα, δίνεται παράταση στην προθεσμία υποβολής της 3ης προγραμματιστικής εργασίας μέχρι την Τετάρτη 2/12 (τα μεσάνυκτα). Όσοι αντιμετωπίσουν προβλήματα με τον grader ή χρησιμοποιούν Java, θα ανεβάσουν τις απαντήσεις τους στο moodle και θα τις επιδείξουν στο Corelab (1.1.30), την Παρασκευή 4/12, είτε 10:45-12:45 είτε 15:00-17:00. Καλή επιτυχία!
  • [12/11/2009] Μπορείτε να πάρετε τις σημειώσεις του κ. Ζάχου από το Corelab (1.1.29, παλαιό κτ. ΗΜΜΥ) την Πέμπτη 12/11, ώρα 19:00-20:30, την Παρασκευή 13/11, ώρα 13:30-15:30, και την εβδομάδα 16-20/11, τις ημέρες και ώρες που εξετάζεται η 2η προγραμματιστική εργασία.
  • [12/11/2009] Για την υποβολή των προγραμματιστικών εργασιών, το moodle θα παραμένει "ανοικτό" μέχρι τις πρώτες πρωινές ώρες της ημέρας που ακολουθεί την λήξη της προθεσμίας (συνήθως η προθεσμία θα λήγει Δευτέρα, έτσι αναφερόμαστε στις πρώτες πρωινές ώρες της Τρίτης που ακολουθεί).
  • [5/11/2009] Κατά την υποβολή των προγραμματιστικών ασκήσεων στο moodle, πρέπει να "ανεβάζετε" τα αρχεία του κώδικα σας συμπιεσμένα (gzip, rar, zip, κλπ.). Αν τα αρχεία του κώδικα είναι text, κάποιοι χαρακτήρες αντικαθίστανται όταν "κατεβαίνουν" για την εξέταση στο εργαστήριο, με αποτέλεσμα ο κώδικας να μην μπορεί να μεταγλωττιστεί.
  • [22/10/2009] Το moodle του μαθήματος είναι ενεργό. Πρέπει να γραφτείτε όλοι μέχρι το Σάββατο 31/10, ώστε να γίνει η απαραίτητη προετοιμασία και να "ανεβάσετε" την 1η προγραμματιστική άσκηση την Δευτέρα 2/11. Από τα στοιχεία που θα δηλώσετε στο moodle πρέπει να προκύπτουν με σαφήνεια το Ονοματεπώνυμό σας και ο Αριθμός Μητρώου σας.
  • [20/10/2009] Αλλαγή αίθουσας: Από την Πέμπτη 22/10, οι διαλέξεις της Πέμπτης θα γίνονται στην αίθουσα 06, στο νέο κτήριο Ηλεκτρολόγων.
  • [19/10/2009] Ανακοινώθηκαν οι βαθμοί του μαθήματος για την επαναληπτική εξέταση. Μπορείτε να δείτε τους βαθμούς σας εδώ.
  • [23/09/2009] Η πρώτη διάλεξη του μαθήματος θα πραγματοποιηθεί την Πέμπτη 8 Οκτωβρίου στις 17:00 στο αμφιθέατρο Ηλεκτρολόγων.
  • [13/10/2009] Στις διαλέξεις της Πέμπτης 15/10 και Δευτέρας 19/10 θα δηλωθούν οι ομάδες για την επίδειξη των εργαστηριακών ασκήσεων.

Υλικό

Διαφάνειες μαθήματος

Σημειώσεις - Συμπληρωματικό Υλικό

Ασκήσεις

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

Εκφώνηση Ημερομηνία Παράδοσης Ενδεικτικές Λύσεις
Πρώτη σειρά

26/10/2009

 Λύσεις 1ης σειράς
Δεύτερη σειρά

9/11/2009

 Λύσεις 2ης σειράς
Τρίτη σειρά

23/11/2009

 Λύσεις 3ης σειράς
Τέταρτη σειρά

14/12/2009

 Λύσεις 4ης σειράς
Πέμπτη σειρά

12/2/2010

 Λύσεις 5ης σειράς
Οι ασκήσεις που σημειώνονται με αστερίσκο (*) είναι προαιρετικές.

Προγραμματιστικές ασκήσεις

Εκφώνηση Συμπληρωματικά Αρχεία Ημερομηνία Παράδοσης
Πρώτη σειρά

lab01.zip

2/11/2009
Δεύτερη σειρά

16/11/2009
Τρίτη σειρά

lab03.zip + sols.zip

2/12/2009
Τέταρτη σειρά

lab04.zip

17/12/2009
Πέμπτη σειρά

lab05.zip

18/1/2010

Παρατηρήσεις

  1. Στις γραπτές ασκήσεις να γράφετε ονοματεπώνυμο και αριθμό μητρώου. Τις παραδίδετε μόνο στην υπεύθυνη (Γεωργία Καούρη), κατά προτίμηση στο μάθημα της Δευτέρας. Η προθεσμία είναι αυστηρή και λήγει στις 18:00 της ημέρας παράδοσης. Εάν δοθεί παράταση θα ανακοινωθεί σε αυτή τη σελίδα και στο moodle.
  2. Δεν γίνεται δεκτή η παράδοση ασκήσεων μέσω e-mail.
  3. Συνεργασία επιτρέπεται και μάλιστα ενθαρρύνεται (εάν γίνεται σωστά), αλλά τελικά κάθε φοιτητής καλείται να διατυπώσει μόνος του τη λύση. Πανομοιότυπες διατυπώσεις θα εκλαμβάνονται ως αντιγραφή και δεν θα προσμετράται ο βαθμός τους, ενώ πιθανόν να υπάρξουν συνέπειες για όλες τις σειρές ασκήσεων.
  4. Για απορίες πάνω στις ασκήσεις και στη θεωρία μπορείτε να έρχεστε στο CoReLab (κτ. ΗΜΜΥ 1.1.30) στις ώρες γραφείου.

Τελευταία ανανέωση: 2 / 3 / 2010