Topic outline

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

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

  Διδάσκοντες
  

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

  
  Πρόσθετες διαλέξεις για μεταπτυχιακούς (σελίδα μεταπτυχιακού μαθήματος):

  • Στάθης Ζάχος, Καθηγητής ( zachos@cs.ntua.gr )
  • Θανάσης Λιανέας, postdoc ( kaiserg7@hotmail.com )
  • Αντώνης Αντωνόπουλος, Υ/Δ (aanton@corelab.ntua.gr)
    

  
  

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

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

  
  

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

  • Στρατής Σκουλάκης, Υ.Δ. ( sskoul@corelab.ntua.gr )
    
  • Λουκάς Κάβουρας, Υ.Δ. ( kavouras@corelab.ntua.gr )
    
  • Παναγιώτης Πατσιλινάκος, Υ.Δ. ( patsilinak@corelab.ntua.gr )
    
  • Ελένη Ψαρουδάκη, Υ.Δ.( psaroudaki@corelab.ntua.gr )

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

  • Εμμανουήλ Βάρδας
    
  • Γρηγόρης Βελέγκας
  • Νίκος Ζαρίφης
    
  • Βαρδής Κανδήρος
  • Παναγιώτης Κωστοπαναγιώτης
  • Κυριάκος Λωτίδης
  • Στέλιος Τριανταφύλλου

  
  

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

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

  
  

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

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

  • Ανακοινώσεις Forum
• Υλικό
  

  Υλικό

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

  • Σύντομη Εισαγωγή στη Θεωρία Γραφημάτων (σημειώσεις του Δ. Φωτάκη).
  • Συμπληρωματικές σημειώσεις του Δ. Φωτάκη. Καλύπτουν μόνο ένα μέρος της ύλης του μαθήματος.
  • Εξαιρετικές σημειώσεις του Jeff Erickson σε δυναμικό προγραμματισμό (με πολλά παραδείγματα και πολλές ασκήσεις).
  • Ένα ενδιαφέρον άρθρο από τον 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 για τη σημασία και τις εφαρμογές του προβλήματος.
  • Ένα ενδιαφέρον άρθρο: The Yoda of Silicon Valley (Donald Knuth)
    

  
  

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

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

  
  

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

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

  
  
• Διαλέξεις
  

  Διαλέξεις

  • Διάλεξη 1/10/2018: Εισαγωγή και Διαδικαστικά. Εισαγωγικές Έννοιες.
  • Διάλεξη 4/10/2018: Ασυμπτωτικός Συμβολισμός.
  • Διάλεξη 8/10/2018: Δομές Δεδομένων. Ουρές Προτεραιότητας: Σωρός. Κάτω Φράγμα στη χρονική πολυπλοκότητα συγκριτικών αλγόριθμων ταξινόμησης. 
    
  • Διάλεξη 12/10/2018: Ταξινόμηση σε γραμμικό χρόνο (κάποια links με σχετικό υλικό: 1, 2, 3, 4). Union - Find.
    
  • Διάλεξη 15/10/2018: Αλγόριθμοι Διαίρει-και-Βασίλευε: mergesort, master theorem, πολλαπλασιασμός αριθμών και πινάκων, πλησιέστερο ζεύγος σημείων. 
    
  • Διάλεξη 18/10/2018: Αλγόριθμοι διαίρει-και-βασίλευε: πλησιέστερο ζεύγος σημείων, ύψωση σε δύναμη. Quicksort, πιθανοτική Quicksort.
  • Διάλεξη 22/10/2018: Το πρόβλημα της επιλογής. 
  • Διάλεξη 25/10/2018: Το πρόβλημα της επιλογής. Αναζήτηση: Γραμμική αναζήτηση, δυαδική αναζήτηση, αναζήτηση με παρεμβολή. Άπληστοι Αλγόριθμοι.
  • Διάλεξη 1/11/2018: Άπληστοι Αλγόριθμοι. 
  • Διάλεξη 5/11/2018: Άπληστοι Αλγόριθμοι. Δυναμικός προγραμματισμός. 
  • Διάλεξη 6/11/2018: Δυναμικός προγραμματισμός.
  • Διάλεξη 8/11/2018: Παραδείγματα και ασκήσεις σε δυναμικό προγραμματισμό.
  • Διάλεξη 12/11/2018: Ασκήσεις σε άπληστους αλγόριθμους και δυναμικό προγραμματισμό. Συζήτηση λύσεων 1ης σειράς ασκήσεων.
  • Διάλεξη 19/11/2018: Αναζήτηση κατά Πλάτος και Αναζήτηση κατά Βάθος, εφαρμογές. 
  • Διάλεξη 22/11/2018: Ελάχιστο Συνδετικό Δέντρο: άπληστος αλγόριθμος, αλγόριθμοι Kruskal, Prim και Boruvka.
  • Διάλεξη 26/11/2018: Ελάχιστο Συνδετικό Δέντρο: ασκήσεις.
  • Διάλεξη 27/11/2018: Συντομότερα μονοπάτια από μία αρχική κορυφή: βασικές έννοιες, αλγόριθμος Bellman-Ford.
  • Διάλεξη 29/11/2018: Συντομότερα μονοπάτια σε DAG, αλγόριθμος Dijkstra. 
  • Διάλεξη 3/12/2018: Συντομότερα μονοπάτια για όλα τα ζεύγη κορυφών: αλγόριθμος Floyd-Warshall, αλγόριθμος Johnson.
  • Διάλεξη 10/12/2018: Μέγιστη ροή - ελάχιστη τομή. Αλγόριθμος Ford-Fulkerson, βελτιώσεις Edmonds-Karp.
    
  • Διάλεξη 13/12/2018: Μηχανές Turing και Υπολογισιμότητα.
  • Διάλεξη 17/12/2018: Υπολογιστική Πολυπλοκότητα.
  • Διάλεξη 20/12/2018: Αναγωγές. Μη Ντετερμινισμός. Η κλάση NP.
  • Διάλεξη 7/1/2019: NP-Πληρότητα.
    
  • Διάλεξη 10/1/2019: NP-Πλήρη Προβλήματα. Παραδείγματα Αναγωγών.
  • Διάλεξη 14/1/2019: Περισσότερα παραδείγματα Αναγωγών.