Algorithms and Complexity

Topic outline

• 

  Γενικά

  • Γενικές Ανακοινώσεις Forum

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

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

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

    
    

• 

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

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

  
  

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

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

  
  

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

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

  
  

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

  • Διονύσης Αρβανιτάκης
  • Σπύρος Δραγάζης
  • Κατερίνα Μάμαλη
  • Μάνος Παδουβάς
    
  • Ηλίας Παπανικολάου
  • Θοδωρής Τσιλιβής

  
  

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

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

  
  
• 

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

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

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

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

  
  
• 

  Υλικό

  
  

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

  • 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. 
  • Στην ιστοσελίδα του μαθήματος για το ακαδ. έτος 2020-2021, μπορείτε να βρείτε βιντεοσκοπημένες διαλέξεις και συνδέσμους για τις ιστοσελίδες του μαθήματος σε προηγούμενες χρονιές.
• 

  Διαλέξεις

  
  

  • Διάλεξη 7/10/2022: Εισαγωγή και διαδικαστικά. Εισαγωγικές έννοιες, ασυμπτωτική εκτίμηση υπολογιστικής πολυπλοκότητας.
  • Διάλεξη 10/10/2022: Ασυμπτωτικός Συμβολισμός (εκτενής επανάληψη). Αποδοτικοί αλγόριθμοι, fine-grained complexity (απλή αναφορά, δείτε διαφάνειες, διαφάνειες και survey, για περισσότερες πληροφορίες), beyond worst case analysis (απλή αναφορά, δείτε υλικό μαθήματος και survey, για περισσότερες πληροφορίες),
  • Διάλεξη 13/10/2022. Αλγόριθμοι Διαίρει-και-Βασίλευε: mergesort και μέτρηση αντιστροφών, master theorem (δείτε και αυτές τις σημειώσεις για την επίλυση αναδρομικών σχέσεων και το master theorem). Πλησιέστερο ζεύγος σημείων. 
    
  • Διάλεξη 17/10/2022. Πλησιέστερο ζεύγος σημείων. Κυρτό κάλυμμα (δείτε και αυτές τις σημειώσεις για αποδοτικούς αλγόριθμους που υπολογίζουν το κυρτό κάλυμμα).
  • Διάλεξη 20/10/2022. Quicksort. Επιλογή σε γραμμικό χρόνο. 
  • Διάλεξη 24/10/2022. Ντετερμινιστική επιλογή σε γραμμικό χρόνο. Ταξινόμηση σε γραμμικό χρόνο. 
  • Διάλεξη 27/10/2022. Αναζήτηση: Γραμμική αναζήτηση, δυαδική αναζήτηση, αναζήτηση με παρεμβολή. Σημειώσεις με την θεωρητική ανάλυση της αναζήτησης με παρεμβολή. Εφαρμογές δυαδικής αναζήτησης σε προβλήματα βελτιστοποίησης. Άπληστοι αλγόριθμοι. 
  • Διάλεξη 31/10/2022. Άπληστοι αλγόριθμοι. 
  • Διάλεξη 3/11/2022. Άπληστοι αλγόριθμοι. Δυναμικός προγραμματισμός. 
  • Διάλεξη 7/11/2022. Δυναμικός προγραμματισμός - παραδείγματα (σακίδιο, subset sum, coin change).
  • Διάλεξη 10/11/2022. Δυναμικός προγραμματισμός: χωρισμός ακολουθίας σε διαστήματα, μέγιστη κοινή υπακολουθία, edit distance, μέγιστη αύξουσα υπακολουθία). 
  • Διάλεξη 14/11/2022. Δυναμικός προγραμματισμός: πολλαπλασιασμός ακολουθίας πινάκων, αναδρομή με απομνημόνευση, travelling salesman problem.  
  • Διάλεξη 21/11/2022. String Matching.  Σημειώσεις του Jeff Erickson για string matching. 
    
  • Διάλεξη 24/11/2022: String Matching: υπολογισμός της Failure Function. Συντομότερα Μονοπάτια από μία αρχική κορυφή: αλγόριθμος Bellman-Ford. Συντομότερα μονοπάτια σε DAG, αλγόριθμος Dijkstra. 
  • Διάλεξη 28/11/2022:  Συντομότερα μονοπάτια για όλα τα ζεύγη κορυφών: αλγόριθμος Floyd-Warshall, αλγόριθμος Johnson. Ασκήσεις 
  • Διάλεξη 1/12/2022: Μέγιστη ροή και ελάχιστη τομή: υπολλειματικό δίκτυο, αλγόριθμος Ford-Fulkerson. Σημειώσεις του Jeff Erickson για υπολογισμό μέγιστης ροής και ελάχιστης τομής. 
  • Διάλεξη 5/12/2022: Μέγιστη ροή και ελάχιστη τομή: βελτιώσεις Edmonds-Karp, εφαρμογή στον υπολογισμό μέγιστου ταιριάσματος σε διμερή γραφή, μέγιστο ταίριασμα και ελάχιστο κάλυμμα κορυφών σε διμερή γραφήματα. Το πρόβλημα της ροής ελάχιστου κόστους. Σημειώσεις του Jeff Erickson για εφαρμογές των προβλημάτων μέγιστης ροής και ελάχιστης τομής. 
  • Διάλεξη 8/12/2022: Ροή ελάχιστου κόστους: αλγόριθμος απαλοιφής αρνητικών κύκλων, αλγόριθμος επαναλαμβανόμενων συντομότερων μονοπατιών.  Σημειώσεις του Jeff Erickson για το πρόβλημα της ροής ελάχιστου κόστους. 
  • Διάλεξη 12/12/2022: Πιθανοτικοί αλγόριθμοι: έλεγχος γινομένου πολυωνύμων και πινάκων, ελάχιστη τομή, 2-SAT (δείτε κάποιες σημειώσεις - set1 και set2 - για τον πιθανοτικό αλγόριθμο για το 2-SAT και κάποιες σημειώσεις για τον πιθανοτικό αλγόριθμο για το πρόβλημα της ελάχιστης τομής). 
  • Διάλεξη 15/12/2022: Μηχανές Turing και υπολογισιμότητα.
  • Διάλεξη 19/12/2022: Υπολογιστική πολυπλοκότητα. Αναγωγές.
  • Διάλεξη 22/12/2022: Μη ντετερμινισμός. Η κλάση NP. NP-πληρότητα: SAT, 3-SAT, MIS.
  • Διάλεξη 9/1/2023: NP-πληρότητα - παραδείγματα αναγωγών: 3-SAT(3), MAX 2-SAT, Vertex Cover, Clique, Set Cover, Subgraph Isomorphism.
  • Διάλεξη 12/1/2023: Πιθανοτικοί αλγόριθμοι: 2-SAT (σύντομη επανάληψη), 3-SAT (σημειώσεις), balls and bins και load balancing (σημειώσεις για το expected maximum load σε balls and bins, και προαιρετικό υλικό σχετικά με την εκθετική μείωση του expected maximum load με χρήση καλύτερου από δύο επιλογές και την εφαρμογή σε load balancing παράλληλων συστημάτων), συγκέντρωση γύρω από τη μέση τιμή, εφαρμογή στο πρόβλημα του set balancing. 
  • Διάλεξη 16/1/2023: Προσεγγιστικοί αλγόριθμοι: κλάσεις προσεγγισιμότητας, Vertex Cover (2-προσεγγιστικ΄΄ος αλγόριθμος, μόνο η εκδοχή χωρίς βάρη - unweighted VC), Set Cover (logn-προσεγγιστικός αλγόριθμος).
  • Διάλεξη 19/1/2023: Προσεγγιστικοί αλγόριθμοι: Set Cover (Hn-προσεγγιστικός αλγόριθμος), Maximum Coverage, TSP inapproximability, Metric TSP: 2-προσεγγιστικός αλγόριθμος και 3/2-προσεγγιστικός αλγόριθμος (απλή αναφορά).

  
  
• 

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

  • Διάλεξη 18/10/2022. Εισαγωγή στις δομές δεδομένων. Σωρός - Ουρές Προτεραιότητας - Heap Sort. Δομές union - find. (Διαφάνειες)
  • Διάλεξη 25/10/2022. Λεξικό. Δυαδικά Δέντρα Αναζήτησης. Hash Tables. (Διαφάνειες)
  • Διάλεξη 01/11/2022. Ολοκλήρωση Hash Tables. Γραφήματα. BFS και εφαρμογές. (Διαφάνειες)
  • Διάλεξη 22/11/2022: DFS και εφαρμογές: Σημεία Κοπής, Τοπολογική διάταξη (Διαφάνειες) 
  • Διάλεξη 29/11/2022: Ισχυρά Συνεκτικές Συνιστώσες, Ελάχιστo Συνδετικό Δέντρο, Prim, Kruskal, Borůvka (Διαφάνειες)
• 

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

  Not available