Section outline
-
-
Εδώ αναρτώνται οι γενικές ανακοινώσεις από τους διδάσκοντες προς τους εγγεγραμμένους φοιτητές, οι οποίοι τις λαμβάνουν και στην ηλεκτρονική τους διεύθυνση.
-
Σε αυτό το forum, μπορεί οποιοσδήποτε εγγεγραμμένος φοιτητής να αναρτά ερωτήσεις σχετικές με το μάθημα και να λαμβάνει απαντήσεις από τους διδάσκοντες. Οι ερωτήσεις και οι απαντήσεις θα είναι διαθέσιμες σε όλους τους φοιτητές.
Οι φοιτητές μπορούν να δηλώσουν με την εγγραφή τους αν θέλουν να ενημερώνονται για τις αναρτώμενες ερωταπαντήσεις.
-
-
- Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)
- Δώρα Σούλιου, Ε.ΔΙ.Π ( )
- Παναγιώτης Γροντάς (pgrontas@mail.ntua.gr), Μεταδιδάκτορας
Επικοινωνία και Πληροφορίες
- Μπορείτε να απευθύνετε τις ερωτήσεις σας στη διεύθυνση: .
Βοηθοί Διδασκαλίας
- Σωτήρης Κανελλόπουλος, Υ.Δ. ( sotkanel@yahoo.gr )
- Μαρίνα Κονταλέξη, Υ.Δ. ( )
- Χρήστος Περγαμηνέλης Υ.Δ. ( chrispergaminelis@gmail.com )
- Θάνος Τόλιας, Υ.Δ. ( )
Ώρες Γραφείου Διδασκόντων
- Άρης Παγουρτζής: Πέμπτη 13:00 - 14:00, στο γραφείο 1.1.16, (Παλιό) Κτίριο Ηλεκτρολόγων.
- Δώρα Σούλιου: Παρασκευή 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, στο παλαιό κτήριο της ΣΗΜΜΥ, γίνονται πρόσθετες διαλέξεις για τους μεταπτυχιακούς φοιτητές. Σχετικά με το περιεχόμενο και το πρόγραμμα των διαλέξεων, δείτε τη σελίδα του μεταπτυχιακού μαθήματος.
-
Σημειώσεις - Συμπληρωματικό Υλικό
- Συμπληρωματικές σημειώσεις του Σ. Ζάχου.
- Συμπληρωματικές σημειώσεις του Δ. Φωτάκη. Καλύπτουν μόνο ένα μέρος της ύλης του μαθήματος.
- Σύντομη Εισαγωγή στη Θεωρία Γραφημάτων (σημειώσεις του Δ. Φωτάκη).
- Σύντομη Εισαγωγή στις Συναρτήσεις Κατακερματισμού (σημειώσεις Σ. Ζάχου και Α. Παγουρτζή).
- Ένα ενδιαφέρον άρθρο από τον Bernard Chazelle: The Algorithm: Idiom of Modern Science.
- Ένα ενδιαφέρον άρθρο για τον Donald Knuth: The Yoda of Silicon Valley.
- Ένα ενδιαφέρον άρθρο από τον Jeff Ullman σχετικά με την θεωρητική και την πειραματική αξιολόγηση των αλγορίθμων: Experiments as Research Validation – Have We Gone too Far?
- Ένα εξαιρετικά ενδιαφέρον άρθρο του Alexander Schrijver με ιστορικά στοιχεία για την έρευνα στην περιοχή της συνδυαστικής βελτιστοποίησης.
- Μια ενδιαφέρουσα παρουσίαση για το πως αρχικοποιούμε έναν πίνακα σε σταθερό χρόνο.
- Ένα survey για priority algorithms, ένα θεωρητικό πλαίσιο εργασίας για την μελέτη των δυνατοτήτων και των περιορισμών των άπληστων αλγόριθμων.
- Προγραμματιστικές Ασκήσεις: Μια απλή συνάρτηση σε C για να διαβάζετε γρήγορα την είσοδο όταν αυτή αποτελείται από μη αρνητικούς ακέραιους και τα testcases είναι πολύ μεγάλα.
- Προγραμματιστικές Ασκήσεις: Σημειώσεις (με παραδείγματα) για την ιδέας της convex hull βελτιστοποίησηςσε συγκεκριμένες μορφές δυναμικού προγραμματισμού (δείτε ακόμη και αυτές τις διαφάνειες).
- Ένα review από τους Andrew Goldberg και Robert Tarjan των γνωστών αποδοτικών αλγόριθμων για το πρόβλημα της Μέγιστης Ροής. Το review είναι εξαιρετικά ενδιαφέρον, το ίδιο και το video για τη σημασία και τις εφαρμογές του προβλήματος.
Προτεινόμενες Ασκήσεις (με τις λύσεις τους) και Παραδείγματα
- 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, το ακαδ. έτος 2023-2024, και το ακαδ. έτος 2025-2026.
-
- Διάλεξη 28/9/2026 : Εισαγωγή και διαδικαστικά. Εισαγωγικές έννοιες, προβλήματα απόφασης, και βελτιστοποίησης, εύρεσης και καταμέτρησης.
- Διάλεξη 1/10/2026 : Εκτίμηση πολυπλοκότητας, ασυμπτωτικός συμβολισμός.
- Διάλεξη 5/10/2026 : Ασυμπτωτικός συμβολισμός (σύντομη επανάληψη, παραδείγματα). Το πρόβλημα union-find. Union by rank. Path compression.
- Διάλεξη 8/10/2026 : Απόδειξη Hopcroft - Ulmann για πολυπλοκότητα Ο(mlog*n) για m finds και n unions. ADT Λεξικού. Hash tables. Cuckoo hashing. Bloom filters.
- Διάλεξη 12/10/2026 : Εμβάθυνση σε hash functions. Universal hash families. Δείτε σχετικές διαφάνειες του Uri Zwick.
- Διάλεξη 15/10/2026: Hashing με open addressing: απόδειξη του παράγοντα φόρτου για uniform probing, γραμμική και τετραγωνική διερεύνηση, διπλός κατακερματισμός. Ουρές προτεραιότητας, σωροί: εισαγωγή, διαγραφή, γραμμική κατασκευή σωρού.
- Διάλεξη 19/10/2026: Σωροί: σύντομη επανάληψη και Heapsort. Η μέθοδος Διαίρει και Βασίλευε (Divide and Conquer): Mergesort και Master Theorem.
-
Βιντεοσκοπημένες Διαλέξεις "Προγραμματιστικών Τεχνικών"
- Γραφήματα, αναπαράσταση γραφημάτων, εξερεύνηση γραφημάτων, εξερεύνηση κατά πλάτος (BFS), εξερεύνηση κατά βάθος (DFS).
- Εφαρμογές εξερεύνησης κατά πλάτος και εξερεύνησης κατά βάθος: τοπολογική ταξινόμηση, υπολογισμός ισχυρά συνεκτικών συνιστωσών, εντοπισμός γεφυρών και σημείων κοπής, κύκλοι Euler.
- Βασικές δομές δεδομένων, union-find, ουρές προτεραιότητας και σωροί (heaps), κατακερματισμός (hashing).
- Βασικές δομές δεδομένων, δυαδικά δέντρα, ιδιότητες, διάσχιση δέντρων, δυαδικά δέντρα αναζήτησης, αναζήτηση, εισαγωγή και διαγραφή στοιχείων σε δυαδικά δέντρα αναζήτησης.
- Ζυγισμένα δυαδικά δέντρα αναζήτησης, AVL δέντρα, επαναζυγιστικές πράξεις σε AVL δέντρα.
- Δέντρα αναζήτησης με μεγαλύτερο βαθμό διακλάδωσης, B-δέντρα.
Πρόσθετες σημειώσεις και Διαφάνειες
- Πίνακες κατακερματισμού (hashing), τεχνικές κατακερματισμού, cuckoo hashing.
- Δυαδικά δέντρα αναζήτησης που βελτιστοποιούνται με βάση τη σειρά λειτουργιών που εκτελούνται (στατική και δυναμική βελτιστότητα), splay trees.
- Binary indexed trees και range sum queries.
- Range min queries.
- Αποθήκευση συμβολοσειρών, tries.
- Αναζήτηση κατά Πλάτος (BFS) και Αναζήτηση κατά Βάθος (DFS), εφαρμογές.
-
- Θα ανακοινωθούν τρεις (3) σειρές γραπτών ασκήσεων και δύο (2) σειρές προγραμματιστικών ασκήσεων.
- Οι γραπτές ασκήσεις υποβάλλονται στη σελίδα του μαθήματος, στο helios. Δεν γίνεται δεκτή η παράδοση ασκήσεων με e-mail.
- Οι προγραμματιστικές ασκήσεις υποβάλλονται (source code) στον grader, και αξιολογούνται ηλεκτρονικά. Για την υποβολή, θα χρησιμοποιήσετε το login name με το οποίο έχετε κάνει enroll στο μάθημα. Τα προγράμματά σας πρέπει να είναι σε C/C++, να διαβάζουν την είσοδο από το standard input και να τυπώνουν την έξοδο στο standard output. Μια υποβολή θεωρείται επιτυχής (και συνεχίζει στο στάδιο της αξιολόγησης) αν "περάσει" επιτυχώς τα επιλεγμένα test cases για το αντίστοιχο ερώτημα. Η αξιολόγηση γίνεται με αντίστοιχα (κοινά για όλους, αλλά διαφορετικά από αυτά που ελέγχονται κατά την υποβολή) test cases, μετά την λήξη της προθεσμίας. Με κάθε άσκηση, θα δίνεται και ένας αριθμός test cases (με τις απαντήσεις τους), τα οποία μπορείτε να χρησιμοποιήσετε για προκαταρκτικό έλεγχο των λύσεων σας.
- Συνεργασία επιτρέπεται και μάλιστα ενθαρρύνεται (εάν γίνεται σωστά, π.χ. αφού αφιερώσετε ικανό χρόνο ατομικής προσπάθειας), αλλά τελικά κάθε φοιτητής πρέπει να διατυπώσει μόνος του τη λύση. Πανομοιότυπες διατυπώσεις θα εκλαμβάνονται ως αντιγραφή και δεν θα προσμετράται ο βαθμός τους, ενώ πιθανόν να υπάρξουν συνέπειες για όλες τις σειρές ασκήσεων.
Εκφωνήσεις Γραπτών Ασκήσεων
- 1η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 11/11/2026.