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

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

Γενικά

Διδάσκοντες

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

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

  • Χάρης Αγγελιδάκης, Υ.Δ. ()
  • Σωτήρης Δήμος, Υ.Δ. ()
  • Θανάσης Λιανέας, Υ.Δ. ()

Βοηθοί Εργαστηρίου

  • Μάνος Κουκουτός
  • Θεόδωρος Λυκούρης
  • Βασίλης Νάκος
  • Πέτρος Πανταβός
  • Λυδία Πολύζου
  • Γιάννης Χατζημίχος

Βοηθός Γραπτών Ασκήσεων

  • Μάρκος Επιτρόπου

Διαλέξεις

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

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

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

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

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

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

  1. Thomas Cormen, Charles Leiserson, Ronald Rivest and Cliff Stein: "Introduction to Algorithms", 3rd edition, MIT Press, 2009.
  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.

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

  • [15/3/2012] Βαθμολογία εξεταστικής περιόδου Φεβρουαρίου. Μπορείτε να δείτε τα γραπτά σας την Πέμπτη 22 Μαρτίου, ώρα 17:00 - 19:00, στο Corelab (1.1.3).
  • [15/2/2012] Δίνεται παράταση στην προθεσμία για την υποβολή της 4ης γραπτής και της 4ης προγραμματιστικής εργασίας. Συγκεκριμένα, η 4η γραπτή εργασία μπορεί να παραδωθεί μέχρι και την Δευτέρα 20/2, και η 4η προγραμματιστική εργασία μπορεί να υποβληθεί στον grader μέχρι και την Δευτέρα 12/3.
  • [13/2/2012] Την Τρίτη 14/2, ώρα 17:00 - 19:00, στην αίθουσα 007, θα γίνει διάλεξη αναπλήρωσης.
  • [2/2/2012] Το μάθημα της Δευτέρας 6/2 θα διαρκέσει λίγο περισσότερο. Στον επιπλέον χρόνο, θα συζητήσουμε τις λύσεις των ασκήσεων της 3ης γραπτής εργασίας.
  • [15/12/2011] Σημειώσεις: Οι σημειώσεις του κ. Ζάχου θα μοιράζονται στο Corelab (1.1.3, παλαιό κτ. ΗΜΜΥ), την Πέμπτη 15/12, 19:00-20:30, τη Δευτέρα 19/12, 17:00-18:00, και την Πέμπτη 22/12, 19:00-20:30.
  • [2/12/2011] Λόγω των κινητοποιήσεων της Πέμπτης 1/12, δίνεται παράταση στην προθεσμία για την υποβολή της 1ης γραπτής και της 1ης προγραμματιστικής εργασίας. Συγκεκριμένα, η 1η γραπτή εργασία μπορεί να παραδωθεί μέχρι και την Πέμπτη 8/12, και η 1η προγραμματιστική εργασία μπορεί να υποβληθεί στον grader μέχρι και την Πέμπτη 15/12.
  • [2/12/2011] Έχει "ανοίξει" ο grader για την υποβολή της 1ης προγραμματιστικής άσκησης. Για την υποβολή, πρέπει να χρησιμοποιείται τα login name και password που έχετε για το moodle του μαθήματος (και όχι άλλα accounts που πιθανώς έχετε ήδη στον grader), ώστε να μην υπάρξουν προβλήματα με τη βαθμολογία σας. Καλή επιτυχία!
  • [15/11/2011] Ανακοινώθηκαν οι βαθμοί του μαθήματος για την επαναληπτική εξέταση. Μπορείτε να δείτε τα γραπτά σας ή να ρωτήσετε σχετικά με την βαθμολογία σας την Δευτέρα 21/11, ώρα 17:15 - 18:15, στο Corelab (αίθουσα 1.1.3, στο παλαιό κτήριο Ηλεκτρολόγων).
  • [14/11/2011] Το moodle του μαθήματος είναι ενεργό. Πρέπει να γραφτείτε όλοι μέχρι την Δευτέρα 21/11, ώστε να γίνει η απαραίτητη προετοιμασία για την ανακοίνωση της 1ης προγραμματιστικής άσκησης την Δευτέρα 28/11. Από τα στοιχεία που θα δηλώσετε στο moodle πρέπει να προκύπτουν με σαφήνεια το Ονοματεπώνυμό σας και ο Αριθμός Μητρώου σας. Τα login name και password που θα δηλώσετε στο moodle θα χρησιμοποιούνται και για την πρόσβαση / υποβολή των προγραμματιστικών ασκήσεων στον grader.
  • [7/11/2011] Η πρώτη διάλεξη θα γίνει την Δευτέρα 7 Νοεμβρίου στις 15:00.

Υλικό

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

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

Προτεινόμενες Ασκήσεις (με τις λύσεις τους)

  • 1η σειρά: Ασυμπτωτικός συμβολισμός, αναδρομικές σχέσεις, ταξινόμηση.
  • 2η σειρά: Άπληστοι αλγόριθμοι, δυναμικός προγραμματισμός.
  • 3η σειρά: Αλγόριθμοι γραφημάτων, Ελάχιστο Συνδετικό Δέντρο.
  • 4η σειρά: Συντομότερα Μονοπάτια, Μέγιστη Ροή, Αναγωγές.

Ασκήσεις

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

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

8/12/2011

Διαφάνειες
Δεύτερη σειρά

10/1/2012

Διαφάνειες
Τρίτη σειρά

31/1/2012

Διαφάνειες
Τέταρτη σειρά

20/2/2012

Διαφάνειες

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

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

lab01.zip

15/12/2011
Δεύτερη σειρά

lab02.zip

15/1/2012
Τρίτη σειρά

lab03.zip

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

lab04.zip

12/3/2012

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

  • Οι προγραμματιστικές ασκήσεις υποβάλλονται (source code) στον grader, και αξιολογούνται ηλεκτρονικά. Η προθεσμία υποβολής λήγει τα μεσάνυχτα της ημέρας παράδοσης. Για την υποβολή, θα χρησιμοποιήσετε τα login name και password που έχετε για το moodle του μαθήματος. Τα προγράμματά σας πρέπει να είναι σε C/C++, να διαβάζουν την είσοδο από το standard input, και να τυπώνουν την έξοδο στο standard output. Μια υποβολή θεωρείται επιτυχής (και συνεχίζει στο στάδιο της αξιολόγησης) αν "περάσει" επιτυχώς τα επιλεγμένα test cases για το αντίστοιχο ερώτημα. Η αξιολόγηση γίνεται με αντίστοιχα (κοινά για όλους, αλλά διαφορετικά από αυτά που ελέγχονται κατά την υποβολή) test cases, μετά την λήξη της προθεσμίας. Με κάθε άσκηση, θα δίνεται και ένας αριθμός test cases (με τις απαντήσεις τους), που μπορείτε να χρησιμοποιήσετε για προκαταρκτικό έλεγχο των λύσεων σας.
  • Στις γραπτές ασκήσεις να γράφετε ονοματεπώνυμο και αριθμό μητρώου. Είτε τις παραδίδετε στους βοηθούς διδασκαλίας, κατά προτίμηση στο μάθημα της Δευτέρας, είτε τις αναρτάτε στο moodle. Η προθεσμία λήγει στις 19:00 της ημέρας παράδοσης. Εάν δοθεί παράταση θα ανακοινωθεί σε αυτή τη σελίδα και στο moodle.
  • Δεν γίνεται δεκτή η παράδοση ασκήσεων με e-mail.
  • Συνεργασία επιτρέπεται και μάλιστα ενθαρρύνεται (εάν γίνεται σωστά), αλλά τελικά κάθε φοιτητής πρέπει να διατυπώσει μόνος του τη λύση. Πανομοιότυπες διατυπώσεις θα εκλαμβάνονται ως αντιγραφή και δεν θα προσμετράται ο βαθμός τους, ενώ πιθανόν να υπάρξουν συνέπειες για όλες τις σειρές ασκήσεων.
  • Για απορίες πάνω στις ασκήσεις και στη θεωρία μπορείτε να έρχεστε στο CoReLab (κτ. ΗΜΜΥ 1.1.3) στις ώρες γραφείου.

Τελευταία ανανέωση: 15 / 3 / 2012