Section outline

  • Γενικά

    Collapse all Expand all

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

    • Δημήτρης Φωτάκης, Καθηγητής ( )
    • Δώρα Σούλιου, Ε.ΔΙ.Π ( )

     

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

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

     

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

    • Σωτήρης Κανελλόπουλος, Υ.Δ. ( )
    • Μαρίνα Κονταλέξη, Υ.Δ. ( )
    • Χρήστος Περγαμηνέλης, Υ.Δ. ( )
    • Θάνος Τόλιας, Υ.Δ. ( )

     

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

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

     

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

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

     

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

    • Δημήτρης Φωτάκης: Πέμπτη 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, στο παλαιό κτήριο της ΣΗΜΜΥ, γίνονται πρόσθετες διαλέξεις για τους μεταπτυχιακούς φοιτητές. Σχετικά με το περιεχόμενο και το πρόγραμμα των διαλέξεων, δείτε τη σελίδα του μεταπτυχιακού μαθήματος. 

  • Υλικό

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

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

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

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

    • 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.

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

  • Διαλέξεις

    • Διάλεξη 29/9/2025 : Εισαγωγή και διαδικαστικά. Εισαγωγικές έννοιες, ασυμπτωτική εκτίμηση υπολογιστικής πολυπλοκότητας. 
    • Διάλεξη 2/10/2025 :  Ασυμπτωτικός συμβολισμός (γρήγορη επανάληψη). Σύντομη αναφορά και επανάληψη βασικών εννοιών δομών δεδομένων: λεξικό - balanced binary search trees και hashing, ουρές προτεραιότητας - σωροί.   
    • Διάλεξη 6/10/2025 : Γρήγορη επανάληψη βασικών εννοιών δομών δεδομένων: prefix-sums και binary indexed trees (δείτε ακόμη αυτές τις σημειώσεις), min-range queries, lowest common ancestor.   
    • Διάλεξη 9/10/2025 : Lowest common ancestor, αναγωγές μεταξύ min-range queries και lowest common ancestor, union-find, tries. Αλγόριθμοι Διαίρει-και-Βασίλευε: μέτρηση αντιστροφών (δείτε την αντίστοιχη άσκηση στην 1η σειρά λυμένων ασκήσεων).
    • Διάλεξη 13/10/2025 . Αλγόριθμοι Διαίρει-και-Βασίλευε: mergesort, master theorem (δείτε και αυτές τις σημειώσεις για την επίλυση αναδρομικών σχέσεων και το master theorem), πλησιέστερο ζεύγος σημείων (δείτε και αυτές τις διαφάνειες για γενίκευση της ανάλυσης σε d διαστάσεις και πιθανοτικό αλγόριθμου με γραμμική εξάρτηση στο πλήθος των σημείων).
    • Διάλεξη 16/10/2025. Πλησιέστερο ζεύγος σημείων (επανάληψη, συζήτηση). Quicksort. Επιλογή σε γραμμικό χρόνο.
    • Διάλεξη 20/10/2025 . Ντετερμινιστική επιλογή σε γραμμικό χρόνο. Ταξινόμηση σε γραμμικό χρόνο. Υπολογισμός κυρτού καλύματος (δείτε και αυτές τις σημειώσεις για αποδοτικούς αλγόριθμους που υπολογίζουν το κυρτό κάλυμμα).
    • Διάλεξη 23/10/2025. Κυρτό κάλυμα. Αναζήτηση: Γραμμική αναζήτηση, δυαδική αναζήτηση, αναζήτηση με παρεμβολή. Σημειώσεις για το πρόβλημα αναδιοργάνωσης μιας γραμμικής λίστας (List Update) και την ανάλυση του Move-to-Front. Σημειώσεις με την θεωρητική ανάλυση της αναζήτησης με παρεμβολή. 
    • Διάλεξη 27/10/2025. Εφαρμογές δυαδικής αναζήτησης σε προβλήματα βελτιστοποίησης. Άπληστοι αλγόριθμοι.
    • Διάλεξη 30/10/2025. Άπληστοι αλγόριθμοι: επιλογή διαστημάτων, χρωματισμός διαστημάτων, coin change.
    • Διάλεξη 4/11/2025. Άπληστοι αλγόριθμοι: ελαχιστοποίηση συνολικού χρόνου ολοκλήρωσης (χωρίς και με βάρη), κλασματικό πρόβλημα σακιδίου. Δυναμικός προγραμματισμός. 
    • Διάλεξη 10/11/2025. Δυναμικός προγραμματισμός: διακριτό πρόβλημα σακιδίου.
    • Διάλεξη 11/11/2025. Δυναμικός προγραμματισμός: subset sum, coin change, επιλογή διαστημάτων με βάρη. 
    • Διάλεξη 13/11/2025. Δυναμικός προγραμματισμός: επιλογή διαστημάτων με βάρη, αναδρομή με απομνημόνευση, μέγιστο ανεξάρτητο σύνολο στη γραμμή, σε δέντρα και σε πλέγμα σταθερού πλάτους. 
    • Διάλεξη 18/11/2025 . Δυναμικός προγραμματισμός: πολλαπλασιασμός ακολουθίας πινάκων (παράδειγμα κώδικα python για το πρόβλημα πολλαπλασιασμού ακολουθίας πινάκων), χωρισμός ακολουθίας σε διαστήματα, πρόβλημα πλανόδιου πωλητή (TSP).
    • Διάλεξη 20/11/2025. Δυναμικός προγραμματισμός: πρόβλημα πλανόδιου πωλητή (TSP). Συντομότερα μονοπάτια από μία αρχική κορυφή: βασικές έννοιες, ιδιότητα βέλτιστων επιμέρους λύσεων, βασικό αλγοριθμικό σχήμα.  
    • Διάλεξη 24/11/2025. Συντομότερα μονοπάτια από μία αρχική κορυφή: βασικό αλγοριθμικό σχήμα, δυναμικός προγραμματισμός - αλγόριθμος Bellman-Ford, συντομότερα μονοπάτια σε DAG, αλγόριθμος Dijkstra. Συντομότερα μονοπάτια για όλα τα ζεύγη κορυφών: αλγόριθμος Floyd-Warshall. 
    • Διάλεξη 27/11/2025. Συντομότερα μονοπάτια για όλα τα ζεύγη κορυφών: αλγόριθμος Floyd-Warshall, αλγόριθμος Johnson. Μέγιστη ροή και ελάχιστη τομή: υπολλειματικό δίκτυο, αλγόριθμος Ford-Fulkerson.
    • Διάλεξη 1/12/2025. Μέγιστη ροή και ελάχιστη τομή: αλγόριθμος Ford-Fulkerson, βελτιώσεις Edmonds-Karp, εφαρμογή στον υπολογισμό μέγιστου ταιριάσματος σε διμερή γραφή. Διαφάνειες Kleinberg-Tardos και σημειώσεις του Jeff Erickson για υπολογισμό μέγιστης ροής και ελάχιστης τομής. 
    • Διάλεξη 4/12/2025. Πιθανοτικοί αλγόριθμοι: έλεγχος γινομένου πολυωνύμων και πινάκων, ελάχιστη τομή, 2-SAT (δείτε κάποιες σημειώσεις - set1 και set2 - για τον πιθανοτικό αλγόριθμο για το 2-SAT και κάποιες σημειώσεις για τον πιθανοτικό αλγόριθμο για το πρόβλημα της ελάχιστης τομής).
    • Διάλεξη 8/12/2025. Πιθανοτικοί αλγόριθμοι: 2-SAT (σύντομη επανάληψη), 3-SAT (σημειώσεις). String Matching: αλγόριθμος Karp Rabin. Σημειώσεις του Jeff Erickson για string matching. 
    • Διάλεξη 11/12/2025. String Matching: αλγόριθμος KMP. υπολογισμός της Failure Function.
    • Διάλεξη 15/12/2025 : Σύντομη εισαγωγή στην υπολογισιμότητα. Υπολογιστικά προβλήματα και τυπικές γλώσσες. Η έννοια του αλγορίθμου. Μηχανές Turing. Αποκρίσιμες και ημι-αποκρίσιμες γλώσσες. Η θέση Church-Turing. Μη υπολογισιμότητα. Το πρόβλημα τερματισμού (Halting Problem) και η μέθοδος της διαγωνιοποίησης. Δείτε και σημειώσεις του Jeff Erickson για μη υπολογισιμότητα (έως και ενότητα 7.10).
    • Διάλεξη 18/12/2025 : Υπολογιστική πολυπλοκότητα. Χρονική πολυπλοκότητα ντετερμινιστικής μηχανής Turing. Οι κλάσεις πολυπλοκότητας P και EXP. Αναγωγές (πολυωνυμικού χρόνου). Δύσκολα και πλήρη προβλήματα για κλάσεις πολυπλοκότητας. Η αναγωγή του Hamilton Cycle στο TSP.
    • Διάλεξη 22/12/2025 : Απλά παραδείγματα αναγωγών: πολυωνυμική ισοδυναμία Vertex Cover, Independent Set και Clique. Πολυωνυμικός αλγόριθμος για 2-SAT (αναγωγή σε Non-Reachability).
      Μη-ντετερμινισμός. Η κλάση NP. Περιγραφή της NP μέσω συνοπτικών πιστοποιητικών. NP-πλήρη προβλήματα. Η κλάση co-NP. Σημειώσεις Jeff Erickson για μη-ντετερμινισμό και για NP-πληρότητα.
    • Διάλεξη 8/1/2026 : Το Θεώρημα του Cook: NP-πληρότητα του SAT. NP-πληρότητα των 3-SAT, Max 2-SAT, Independent Set, Integer Programming, Set Cover, Subgraph Isomorphism, 3-Colorability, 3-Dimensional Matching (απλή αναφορά).

  • Διαλέξεις και Σημειώσεις για Δομές Δεδομένων και Βασικούς Αλγόριθμους

    Βιντεοσκοπημένες Διαλέξεις "Προγραμματιστικών Τεχνικών"

    Βιντεοσκοπημένες Διαλέξεις "Αλγόριθμοι και Πολυπλοκότητα". 

    Σημειώσεις και Διαφάνειες 

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

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

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

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

    • 1η σειρά προγραμματιστικών ασκήσεων (αρχεία εισόδου). Προθεσμία υποβολής: 24/11/2025. 
    • 2η σειρά προγραμματιστικών ασκήσεων (αρχεία εισόδου). Προθεσμία υποβολής (εκτιμώμενη): 22/12/2025.  
    • 3η σειρά προγραμματιστικών ασκήσεων (αρχεία εισόδου). Προθεσμία υποβολής (εκτιμώμενη): 20/01/2026.