Αλγόριθμοι και Πολυπλοκότητα

Section outline

• Επιλογή ενότητας Γενικά

  Γενικά

  Σύμπτυξη όλων Ανάπτυξη όλων

  • Επιλογή δραστηριότητας Γενικές Ανακοινώσεις

    

    Γενικές Ανακοινώσεις Φόρουμ

    Εδώ αναρτώνται οι γενικές ανακοινώσεις από τους διδάσκοντες προς τους εγγεγραμμένους φοιτητές, οι οποίοι τις λαμβάνουν και στην ηλεκτρονική τους διεύθυνση.
    
    
  • Επιλογή δραστηριότητας Forum Ερωτήσεων/Απαντήσεων

    

    Forum Ερωτήσεων/Απαντήσεων Φόρουμ

    Σε αυτό το forum, μπορεί οποιοσδήποτε εγγεγραμμένος φοιτητής να αναρτά ερωτήσεις σχετικές με το μάθημα και να λαμβάνει απαντήσεις από τους διδάσκοντες. Οι ερωτήσεις και οι απαντήσεις θα είναι διαθέσιμες σε όλους τους φοιτητές. 

    Οι φοιτητές μπορούν να δηλώσουν με την εγγραφή τους αν θέλουν να ενημερώνονται για τις αναρτώμενες ερωταπαντήσεις.

    
    

• Επιλογή ενότητας Διδάσκοντες - Βοηθοί Διδασκαλίας

  Διδάσκοντες - Βοηθοί Διδασκαλίας

  • Αριστείδης Παγουρτζής, Καθηγητής ()
  • Δημήτρης Φωτάκης, Καθηγητής ()
  • Δώρα Σούλιου, Ε.ΔΙ.Π ()
  • Παναγιώτης Γροντάς, Μεταδιδάκτορας ()

  
  

  Επικοινωνία και Πληροφορίες

  • Μπορείτε να απευθύνετε τις ερωτήσεις σας στη διεύθυνση: . 

  
  

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

  • Σωτήρης Κανελλόπουλος, Υ.Δ. ()
  • Δημήτρης Κελέσης, Υ.Δ. ()
  • Σταύρος Πετσαλάκης, Υ.Δ. ()
  • Μαριάννα Σπυράκου, Υ.Δ. ()
  • Θάνος Τόλιας, Υ.Δ. ()
  • Αποστόλης Τσορβαντζής, Υ.Δ. ()

  
  

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

  • Βασίλης Βαρσαμής
  • Γιώργος Γκρίνιας
  • Βάλια Ευθυμίου
  • Αλέξανδρος Κουριδάκης

  
  

  Βοηθοί Προγραμματιστικών Ασκήσεων

  • Θα ανακοινωθούν.

  
  

  Ώρες Γραφείου Διδασκόντων

  • Αριστείδης Παγουρτζής: Παρασκευή 13:00-14:00, στο γραφείο 1.1.6, (Παλιό) Κτίριο Ηλεκτρολόγων.
  • Δημήτρης Φωτάκης: Πέμπτη 16:00 - 17:00, στο γραφείο 1.1.10, (Παλιό) Κτίριο Ηλεκτρολόγων.
  • Δώρα Σούλιου: Παρασκευή 13:00 - 14:00, στο γραφείο 1.1.30, (Παλιό) Κτίριο Ηλεκτρολόγων.
  • Παναγιώτης Γροντάς: θα ανακοινωθούν.

  
  
• Επιλογή ενότητας Πρόγραμμα Διαλέξεων

  Πρόγραμμα Διαλέξεων

  
  Οι διαλέξεις του μαθήματος γίνονται κάθε Δευτέρα 15:00 - 17:00 και κάθε Πέμπτη 17:00 - 19:00, στο Αμφ. 1, στο νέο κτήριο της ΣΗΜΜΥ. 

  Επιπλέον διαλέξεις και διαλέξεις αναπλήρωσης γίνονται Τρίτη 15:30 - 17:30, στο Αμφ. 4, στο νέο κτήριο της ΣΗΜΜΥ, σύμφωνα με πρόγραμμα που θα ανακοινωθεί (και θα ενημερώνεται κατά τη διάρκεια του εξαμήνου). 

  Κάθε Πέμπτη, 19:00 - 20:00, στην αίθουσα 1.1.31, στο παλαιό κτήριο της ΣΗΜΜΥ, γίνονται πρόσθετες διαλέξεις για τους μεταπτυχιακούς φοιτητές. Σχετικά με το περιεχόμενο και το πρόγραμμα των διαλέξεων, δείτε τη σελίδα του μεταπτυχιακού μαθήματος. 
  

  
  
• Επιλογή ενότητας Υλικό

  Υλικό

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

  • Συμπληρωματικές σημειώσεις του Σ. Ζάχου.
  • Συμπληρωματικές σημειώσεις του Δ. Φωτάκη. Καλύπτουν μόνο ένα μέρος της ύλης του μαθήματος.
  • Σύντομη Εισαγωγή στη Θεωρία Γραφημάτων (σημειώσεις του Δ. Φωτάκη).
  • Προγραμματιστικές Ασκήσεις: Μια απλή συνάρτηση σε C για να διαβάζετε γρήγορα την είσοδο όταν αυτή αποτελείται από μη αρνητικούς ακέραιους και τα testcases είναι πολύ μεγάλα.
  • Προγραμματιστικές Ασκήσεις: Σημειώσεις (με παραδείγματα) για την ιδέας της convex hull βελτιστοποίησηςσε συγκεκριμένες μορφές δυναμικού προγραμματισμού (δείτε ακόμη και αυτές τις διαφάνειες). 
  • Ένα survey για priority algorithms, ένα θεωρητικό πλαίσιο εργασίας για την μελέτη των δυνατοτήτων και των περιορισμών των άπληστων αλγόριθμων.  
  • Ένα ενδιαφέρον άρθρο από τον Bernard Chazelle: The Algorithm: Idiom of Modern Science.
  • Ένα ενδιαφέρον άρθρο από τον Jeff Ullman σχετικά με την θεωρητική και την πειραματική αξιολόγηση των αλγορίθμων: Experiments as Research Validation – Have We Gone too Far?
  • Ένα review από τους Andrew Goldberg και Robert Tarjan των γνωστών αποδοτικών αλγόριθμων για το πρόβλημα της Μέγιστης Ροής. Το review είναι εξαιρετικά ενδιαφέρον, το ίδιο και το video για τη σημασία και τις εφαρμογές του προβλήματος.
  • Ένα ενδιαφέρον άρθρο για τον Donald Knuth: The Yoda of Silicon Valley.
  • Ένα εξαιρετικά ενδιαφέρον άρθρο του Alexander Schrijver με ιστορικά στοιχεία για την έρευνα στην περιοχή της συνδυαστικής βελτιστοποίησης. 
  • Μια ενδιαφέρουσα παρουσίαση για το πως αρχικοποιούμε έναν πίνακα σε σταθερό χρόνο.

  
  

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

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

  
  

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

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

  
  

  Βιντεοσκοπημένες Διαλέξεις - Ιστοσελίδες Παλαιότερων Ετών

  • Ιστοσελίδα του μαθήματος για το ακαδ. έτος 2021-2022 και το ακαδ. έτος 2022-2023.
  • Στην ιστοσελίδα του μαθήματος για το ακαδ. έτος 2020-2021, μπορείτε να βρείτε βιντεοσκοπημένες διαλέξεις και συνδέσμους για τις ιστοσελίδες του μαθήματος σε προηγούμενες χρονιές.
• Επιλογή ενότητας Διαλέξεις

  Διαλέξεις

  
  

  • Διάλεξη 2/10/2023: Εισαγωγή και διαδικαστικά. Εισαγωγικές έννοιες, ασυμπτωτική εκτίμηση υπολογιστικής πολυπλοκότητας. 
  • Διάλεξη 5/10/2023:  Ασυμπτωτικός Συμβολισμός (γρήγορη επανάληψη). Αποδοτικοί αλγόριθμοι, fine-grained complexity (απλή αναφορά, δείτε ακόμη ένα survey και ένα σχετικό μάθημα για περισσότερες πληροφορίες), beyond worst case analysis (απλή αναφορά, δείτε ακόμη ένα πρόσφατο βιβλίο και ένα σχετικό μάθημα για περισσότερες πληροφορίες). Αλγόριθμοι Διαίρει-και-Βασίλευε: mergesort, master theorem (δείτε και αυτές τις σημειώσεις για την επίλυση αναδρομικών σχέσεων και το master theorem). 
  • Διάλεξη 12/10/2023. Αλγόριθμοι Διαίρει-και-Βασίλευε: πλησιέστερο ζεύγος σημείων, μέτρηση αντιστροφών (γρήγορη αναφορά, δείτε την αντίστοιχη άσκηση στην 1η σειρά λυμένων ασκήσεων), σύντομη επανάληψη στο master theorem, κυρτό κάλυμμα. 
    
  • Διάλεξη 17/10/2023. Κυρτό κάλυμμα (δείτε και αυτές τις σημειώσεις για αποδοτικούς αλγόριθμους που υπολογίζουν το κυρτό κάλυμμα). Quicksort.
  • Διάλεξη 19/10/2023. Quicksort. Επιλογή σε γραμμικό χρόνο. Ντετερμινιστική επιλογή σε γραμμικό χρόνο.
  • Διάλεξη 23/10/2023. Ταξινόμηση σε γραμμικό χρόνο. Αναζήτηση: Γραμμική αναζήτηση, δυαδική αναζήτηση, αναζήτηση με παρεμβολή. Σημειώσεις για το πρόβλημα αναδιοργάνωσης μιας γραμμικής λίστας (List Update) και την ανάλυση του Move-to-Front. Σημειώσεις με την θεωρητική ανάλυση της αναζήτησης με παρεμβολή. 
  • Διάλεξη 26/10/2023. Εφαρμογές δυαδικής αναζήτησης σε προβλήματα βελτιστοποίησης. Άπληστοι αλγόριθμοι. 
  • Διάλεξη 30/10/2023. Άπληστοι αλγόριθμοι: επιλογή διαστημάτων, χρωματισμός διαστημάτων, αθροίσματα με ελάχιστο πλήθος προσθετέων.
  • Διάλεξη 2/11/2023. Άπληστοι αλγόριθμοι: ελαχιστοποίηση συνολικού χρόνου ολοκλήρωσης (χωρίς και με βάρη), σακίδιο. Δυναμικός προγραμματισμός. 
  • Διάλεξη 6/11/2023. Δυναμικός προγραμματισμός: σακίδιο, subset sum, coin change, πολλαπλασιασμός ακολουθίας πινάκων. 
  • Διάλεξη 9/11/2023. Δυναμικός προγραμματισμός: πολλαπλασιασμός ακολουθίας πινάκων, αναδρομή με απομνημόνευση, μέγιστο ανεξάρτητο σύνολο στη γραμμή και σε δέντρα, επιλογή διαστημάτων με βάρη, χωρισμός ακολουθίας σε διαστήματα. 
  • Διάλεξη 13/11/2023. Δυναμικός προγραμματισμός: μέγιστη κοινή υπακολουθία, edit distance, μέγιστη αύξουσα υπακολουθία.  
  • Διάλεξη 20/11/2023. Δυναμικός προγραμματισμός: travelling salesman problem.  String Matching.  Σημειώσεις του Jeff Erickson για string matching. 
    
  • Διάλεξη 23/11/2023: String Matching: υπολογισμός της Failure Function. Συντομότερα Μονοπάτια από μία αρχική κορυφή: αλγόριθμος Bellman-Ford.  
  • Διάλεξη 27/11/2023:  Συντομότερα μονοπάτια σε DAG, αλγόριθμος Dijkstra.
  • Διάλεξη 30/11/2023: Συντομότερα μονοπάτια για όλα τα ζεύγη κορυφών: αλγόριθμος Floyd-Warshall, αλγόριθμος Johnson. Ασκήσεις.
  • Διάλεξη 4/12/2023: Μέγιστη ροή και ελάχιστη τομή: υπολλειματικό δίκτυο, αλγόριθμος Ford-Fulkerson, βελτιώσεις Edmonds-Karp. Διαφάνειες Kleinberg-Tardos και σημειώσεις του Jeff Erickson για υπολογισμό μέγιστης ροής και ελάχιστης τομής. 
  • Διάλεξη 7/12/2023: Μέγιστη ροή και ελάχιστη τομή:  εφαρμογή στον υπολογισμό μέγιστου ταιριάσματος σε διμερή γραφή, μέγιστο ταίριασμα και ελάχιστο κάλυμμα κορυφών σε διμερή γραφήματα. Το πρόβλημα της ροής ελάχιστου κόστους. Σημειώσεις του Jeff Erickson για εφαρμογές των προβλημάτων μέγιστης ροής και ελάχιστης τομής. 
  • Διάλεξη 11/12/2023: Ροή ελάχιστου κόστους: αλγόριθμος απαλοιφής αρνητικών κύκλων, αλγόριθμος επαναλαμβανόμενων συντομότερων μονοπατιών.  Σημειώσεις του Jeff Erickson για το πρόβλημα της ροής ελάχιστου κόστους. 
  • Διάλεξη 14/12/2023: Μηχανές Turing και υπολογισιμότητα.
    
  • Διάλεξη 18/12/2023: Υπολογιστική πολυπλοκότητα. Αναγωγές.
  • Διάλεξη 21/12/2023: Μη ντετερμινισμός. Η κλάση NP. NP-πληρότητα.
  • Διάλεξη 8/1/2024: NP-πληρότητα: SAT (Θεώρημα Cook), 3-SAT, MAX 2-SAT, MIS, VC, CLIQUE, SET COVER.
  • Πρόσθετη μελέτη: NP-πληρότητα: 3-COLORING, 3DM, Knapsack.  Προσεγγιστικοί αλγόριθμοι: κλάσεις προσεγγισιμότητας, Vertex Cover (unweighted), Set Cover (logn- και Hn-προσεγγιστικός αλγόριθμος), Maximum Coverage, TSP inapproximability, Metric TSP: 2-προσεγγιστικός αλγόριθμος και 3/2-προσεγγιστικός αλγόριθμος (χωρίς απόδειξη).

  
  
• Επιλογή ενότητας Συμπληρωματικές Διαλέξεις

  Συμπληρωματικές Διαλέξεις

  Ενδεικτικό πρόγραμμα συμπληρωματικών διαλέξεων

  • Διάλεξη 24/10/2023. Εισαγωγή στις δομές δεδομένων. Σωρός - Ουρές Προτεραιότητας - Heap Sort. Δομές union - find. Slides
    
  • Διάλεξη 31/10/2023. Λεξικό. Δυαδικά Δέντρα Αναζήτησης. Hash Tables. Slides
  • Διάλεξη 07/11/2023. Εισαγωγή Γραφήματα. BFS, DFS και βασικές εφαρμογές. Slides (μέχρι δ. 38)
  • Διάλεξη 14/11/2023: Ελάχιστo Συνδετικό Δέντρο, Αλγόριθμοι Prim, Kruskal, Borůvka. Ολοκλήρωση εφαρμογών DFS. Slides.
• Επιλογή ενότητας Γραπτές Ασκήσεις - Προγραμματιστικές Ασκήσεις

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

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

  Εκφωνήσεις Γραπτών Ασκήσεων

  • 1η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 13/11/2023. 
  • 2η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 28/12/2023. 
  • 3η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 6/2/2024.  
    

  Εκφωνήσεις Προγραμματιστικών Ασκήσεων

  • 1η σειρά προγραμματιστικών ασκήσεων (αρχεία εισόδου). Προθεσμία υποβολής: 20/11/2023. 
  • 2η σειρά προγραμματιστικών ασκήσεων (αρχεία εισόδου). Προθεσμία υποβολής: 8/1/2024.  
    
  • 3η σειρά προγραμματιστικών ασκήσεων (αρχεία εισόδου). Προθεσμία υποβολής: 29/2/2024.