Περιγραφή εβδομάδας

• Χειμερινό Εξάμηνο 2019-2020
  

  Χειμερινό Εξάμηνο 2019-2020

  Διδάσκοντες
  

  • Δημήτρης Φωτάκης, Αναπλ. Καθηγητής ( fotakis@cs.ntua.gr )
  • Δώρα Σούλιου, Ε.ΔΙ.Π ( dsouliou@mail.ntua.gr )

  
  

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

  • Μπορείτε να απευθύνετε τις ερωτήσεις σας στη διεύθυνση:  algo@corelab.ntua.gr
  • Ενημερωτικό φυλλάδιο του μαθήματος.

  
  

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

  • Αλβέρτος Καλαβάσης, Υ.Δ. (kalavasis@corelab.ntua.gr )
    
  • Λουκάς Κάβουρας, Υ.Δ. ( lkavouras@corelab.ntua.gr )
    
  • Παναγιώτης Πατσιλινάκος, Υ.Δ. ( patsilinak@corelab.ntua.gr )
    
  • Ελένη Ψαρουδάκη, Υ.Δ.( epsaroudaki@corelab.ntua.gr )

  
  

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

  
  

  • Παναγιώτης Κωστοπαναγιώτης
  • Κωνσταντίνα Μπαϊρακτάρη
  • Αργύρης Μουζάκης
  • Νικόλαος Μουζάκης
  • Αθανάσιος Πήττας
    
  • Χαρίλαος Πίπης  
  • Ιωάννης Φικιώρης
  • Δημήτριος Χρήστου

  
  

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

  • κάθε Δευτέρα 15:00-17:00 (Αμφιθέατρο 1, νέο κτήριο ΣΗΜΜΥ)
  • κάθε Πέμπτη 17:00-19:00 (Αμφιθέατρο 1, νέο κτήριο ΣΗΜΜΥ)

  
  

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

  
  

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

  • κάθε Πέμπτη 15:00-17:00 στο εργαστήριο 1.1.3 (CoReLab) ή στο γρ. 1.1.10, στο παλαιό κτήριο ΣΗΜΜΥ.

  
  

  • Ανακοινώσεις Φόρουμ
• Υλικό
  

  Υλικό

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

  • Προγραμματιστικές Ασκήσεις: Μια απλή συνάρτηση σε C για να διαβάζετε γρήγορα την είσοδο όταν αυτή αποτελείται από μη αρνητικούς ακέραιους και τα testcases είναι πολύ μεγάλα.
  • Σύντομη Εισαγωγή στη Θεωρία Γραφημάτων (σημειώσεις του Δ. Φωτάκη).
  • Συμπληρωματικές σημειώσεις του Δ. Φωτάκη. Καλύπτουν μόνο ένα μέρος της ύλης του μαθήματος.
  • Ένα ενδιαφέρον άρθρο από τον 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 
    

  
  

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

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

  
  

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

  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. J. Edmonds. How to Think About Algorithms. Cambridge University Press, 2008.
  5. J. Erickson. Algorithms, 1st edition, 2019. 
     
  6. G. Brassard, P. Bratley: Algorithmics: Theory and Practice, Prentice-Hall, 1988. 
  7. Sara Baase, Allen Van Gelder, Computer Algorithms: Introduction to Design and Analysis, 3rd edition, Addison Wesley Longman, 2000.
  8. Alfred V. Aho, John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Series in Computer Science and Information Processing, 1974.
  9. Dexter C. Kozen, The Design and Analysis of Algorithms, Springer, 1991.
  10. A. Levitin: Ανάλυση και Σχεδίαση Αλγορίθμων, Εκδόσεις Τζιόλα, 2007.
  11. G. J. E. Rawlings: Αλγόριθμοι: Ανάλυση και Σύγκριση, Εκδόσεις Κριτική, 2004.

  
  
• Διαλέξεις
  

  Διαλέξεις

  • Διάλεξη 3/10/2019: Εισαγωγή και διαδικαστικά. Εισαγωγικές έννοιες, ασυμπτωτική εκτίμηση υπολογιστικής πολυπλοκότητας.
  • Διάλεξη 7/10/2019: Ασυμπτωτικός Συμβολισμός (επανάληψη), αποδοτικοί αλγόριθμοι. Δομές δεδομένων, abstract data types, λεξικό, ουρές προτεραιότητας, σωρός (εκτενής επανάληψη).
  • Διάλεξη 14/10/2019: Σωρός, heapsort, κάτω φράγμα στη χρονική πολυπλοκότητα συγκριτικών αλγόριθμων ταξινόμησης (εκτενής επανάληψη). Ταξινόμηση σε γραμμικό χρόνo (links με σχετικό υλικό: 1, 2, 3, 4, 5). 
  • Διάλεξη 17/10/2019: Union - Find. Αλγόριθμοι Διαίρει-και-Βασίλευε: mergesort, master theorem.
  • Διάλεξη 21/10/2019: Πλησιέστερο ζεύγος σημείων. Quicksort, πιθανοτική Quicksort.
  • Διάλεξη 7/11/2019: Το πρόβλημα της επιλογής. Αναζήτηση: Γραμμική αναζήτηση, δυαδική αναζήτηση, αναζήτηση με παρεμβολή. Στα πλαίσια του μεταπτυχιακού μαθήματος, είδαμε ακόμη του πρόβλημα υπολογισμού ενός Κυρτού Καλύμματος (Convex Hull), με έμφαση στο Graham's Scan (δείτε π.χ., εδώ και εδώ) και δομές δεδομένων για Range Minimum Queries και Lowest Common Ancestor.
  • Διάλεξη 11/11/2019: Άπληστοι Αλγόριθμοι.
  • Διάλεξη 18/11/2019: Άπληστοι Αλγόριθμοι. Δυναμικός προγραμματισμός.
  • Διάλεξη 25/11/2019: Δυναμικός προγραμματισμός.
  • Διάλεξη 28/11/2019: Δυναμικός προγραμματισμός.
  • Διάλεξη 2/12/2019: Παραδείγματα και ασκήσεις σε δυναμικό προγραμματισμό.
  • Διάλεξη 9/12/2019: Αναζήτηση κατά Πλάτος και Αναζήτηση κατά Βάθος, υπολογισμός γεφυρών και σημείων κοπής.
  • Διάλεξη 12/12/2019: Αναζήτηση κατά Βάθος, τοπολογική ταξινόμηση, υπολογισμός ισχυρά συνεκτικών συνιστωσών. Ελάχιστο Συνδετικό Δέντρο: άπληστος αλγόριθμος, ορθότητα. Στα πλαίσια του μεταπτυχιακού μαθήματος, oλοκληρώσαμε τη διάλεξη για Range Minimum Queries και Lowest Common Ancestor και είδαμε την τεχνική του color coding για τον υπολογισμό απλού μονοπατιού μήκους k.
  • Διάλεξη 16/12/2019: Ελάχιστο Συνδετικό Δέντρο: αλγόριθμοι Kruskal, Prim και Boruvka, ασκήσεις.
  • Διάλεξη 19/12/2019: Ελάχιστο Συνδετικό Δέντρο: Ασκήσεις (bottleneck spanning tree, second best spanning tree). Συντομότερα μονοπάτια από μία αρχική κορυφή: βασικές έννοιες.
  • Διάλεξη 23/12/2019: Συντομότερα μονοπάτια από μία αρχική κορυφή: αλγόριθμος Bellman-Ford. Συντομότερα μονοπάτια σε DAG, αλγόριθμος Dijkstra. Ασκήσεις
  • Διάλεξη 9/1/2020: Συντομότερα μονοπάτια για όλα τα ζεύγη κορυφών: αλγόριθμος Floyd-Warshall, αλγόριθμος Johnson. Μέγιστη ροή - ελάχιστη τομή.
  • Διάλεξη 13/1/2020: Μέγιστη ροή - ελάχιστη τομή: Αλγόριθμος Ford-Fulkerson, βελτιώσεις Edmonds-Karp. Μηχανές Turing και Υπολογισιμότητα.
  • Διάλεξη 16/1/2020: Υπολογιστική Πολυπλοκότητα. Αναγωγές. Στα πλαίσια του μεταπτυχιακού μαθήματος, μιλήσαμε για Γραμμικό Προγραμματισμό, τη μέθοδο Simplex και τη δυϊκότητα στον Γραμμικό Προγραμματισμό (δείτε ακόμη αυτές τις διαφάνειες, που καλύπτουν ευρύτερη ύλη).
  • Διάλεξη 20/1/2020: Αναγωγές. Μη Ντετερμινισμός.
  • Διάλεξη 23/1/2020: Η κλάση NP. NP-Πληρότητα και NP-πλήρη προβλήματα.
  • Διάλεξη 27/1/2020: NP-Πλήρη Προβλήματα. Παραδείγματα Αναγωγών.
  • Διάλεξη 28/1/2020: Πιθανοτικοί Αλγόριθμοι.
  • Διάλεξη 30/1/2020: Περισσότερα παραδείγματα αναγωγών. Χωρική Πολυπλοκότητα.