Ειδικά Θέματα Αλγορίθμων (3632)
Evangelos Markakis
Το μάθημα αποτελεί συνέχεια του μαθήματος των Αλγορίθμων και επικεντρώνεται:
α) στη σχεδίαση και ανάλυση πολυωνυμικών αλγορίθμων για προβλήματα συγκεκριμένων περιοχών, και
β) στην έννοια των δύσκολων προβλημάτων και στις μεθόδους σχεδιασμού αλγορίθμων για αυτά.
Σκοπός του μαθήματος είναι η σε βάθος μελέτη τεχνικών σχεδίασης αλγορίθμων και ανάλυσης της πολυπλοκότητάς τους και η απόκτηση από τους φοιτητές γνώσεων, οι οποίες, για μεγάλο αριθμό προβλημάτων από διαφορετικές περιοχές εφαρμογών, θα τους επιτρέπουν να:
- κατανοήσουν το βαθμό δυσκολίας τους
- σχεδιάσουν και να αναλύσουν αποδοτικούς αλγορίθμους
- χρησιμοποιήσουν τις κατάλληλες μαθηματικές μεθόδους.
Η διδασκαλία του μαθήματος για το ακαδημαϊκό έτος 2023-2024 θα γίνεται κάθε
Δευτέρα 11:00-13:00, στην Τ102 και
Παρασκευή 11:00-13:00 στην Τ102
Λιγότερα
Το μάθημα αποτελεί συνέχεια του μαθήματος των Αλγορίθμων και επικεντρώνεται:
α) στη σχεδίαση και ανάλυση πολυωνυμικών αλγορίθμων για προβλήματα συγκεκριμένων περιοχών, και
β) στην έννοια των δύσκολων προβλημάτων και στις μεθόδους σχεδιασμού αλγορίθμων για αυτά.
Σκοπός του μαθήματος είναι η σε βάθος μελέτη τεχνικών σχεδίασης αλγορίθμων και ανάλυσης της πολυπλοκότητάς τους και η απόκτηση από τους φοιτητές γνώσεων, οι οποίες, για μεγάλο αριθμό προβλημάτων από διαφορετικές περιοχές εφαρμογών, θα τους επιτρέπουν να:
- κατανοήσουν το βαθμό δυσκολίας τους
- σχεδιάσουν και να αναλύσουν αποδοτικούς αλγορίθμους
- χρησιμοποιήσουν τις κατάλληλες μαθηματικές μεθόδους.
Η διδασκαλία του μαθήματος για το ακαδημαϊκό έτος 2023-2024 θα γίνεται κάθε
Δευτέρα 11:00-13:00, στην Τ102 και
Παρασκευή 11:00-13:00 στην Τ102
Το μάθημα αποτελεί συνέχεια του μαθήματος των Αλγορίθμων και επικεντρώνεται:
α) στη σχεδίαση και ανάλυση πολυωνυμικών αλγορίθμων για προβλήματα συγκεκριμένων περιοχών, και
β) στην έννοια των δύσκολων προβλημάτων και στις μεθόδους σχεδιασμού αλγορίθμων για αυτά.
Σκοπός του μαθήματος είναι η σε βάθος μελέτη τεχνικών σχεδίασης αλγορίθμων και ανάλυσης της πολυπλοκότητάς τους και η απόκτηση από τους φοιτητές γνώσεων, οι οποίες, για μεγάλο αριθμό προβλημάτων από διαφορετικές περιοχές εφαρμογών, θα τους επιτρέπουν να:
- κατανοήσουν το βαθμό δυσκολίας τους
- σχεδιάσουν και να αναλύσουν αποδοτικούς αλγορίθμους
- χρησιμοποιήσουν τις κατάλληλες μαθηματικές μεθόδους.
Η διδασκαλία του μαθήματος για το ακαδημαϊκό έτος 2023-2024 θα γίνεται κάθε
Δευτέρα 11:00-13:00, στην Τ102 και
Παρασκευή 11:00-13:00 στην Τ102
Πληροφορίες
Περιεχόμενο Μαθήματος
Το μάθημα αυτό είναι συνέχεια του υποχρεωτικού μαθήματος Αλγόριθμοι.
Στο μάθημα αυτό σας δίνεται η δυνατότητα να εμβαθύνετε, να συζητήσετε και να δημιουργήσετε σε θέματα αλγοριθμικά.
Στόχος είναι να εμπλουτίσετε και να εμπεδώσετε τις αλγοριθμικές σας γνώσεις σε θέματα που έχουν μεγάλη εφαρμογή στην πράξη όπως αλγόριθμοι κρυπτογραφίας, ο δυναμικός προγραμματισμός και η αναγνώριση και αντιμετώπιση δύσκολων (ΝΡ-πλήρων) προβλημάτων.
Η ύλη μπορεί να μεταβληθεί, αν οι φοιτητές προτείνουν αλγοριθμικά θέματα που τους ενδιαφέρουν. Το αρχικό πρόγραμμα είναι το εξής:
Αρχικά συζητάμε αλγορίθμους που δεν περιλαμβάνονται στο υποχρεωτικό μάθημα, όπως αλγορίθμους αριθμοθεωρίας και συμπληρώνουμε τις γνώσεις σας στην αλγοριθμική μέθοδο του Δυναμικού προγραμματισμού με αντιπροσωπευτικά παραδείγματα, εμβαθύνοντας στη μέθοδο αυτή. Στη συνέχεια εξετάζουμε σε βάθος την θεωρία της ΝP-πληρότητας με κάποιες αναγωγές και μελετάμε προσεγγιστικούς και τυχαιοκρατικούς αλγορίθμους, καθώς και άλλους τρόπους αντιμετώπισης προβλημάτων για τα οποία δεν γνωρίζουμε γρήγορους (πολυωνυμικούς) αλγορίθμους. Επίσης, μελετάμε αλγόριθμους για την εύρεση μέγιστης ροής σε γράφους δικτύων καθώς και για την έρευση μέγιστου ταιριάσματος σε διμερείς γράφους. Τέλος μελετάμε σε βάθος αλγόριθμους βασισμένους στην μοντελοποίηση προβλημάτων με χρήση (ακέραιου) γραμμικού προγραμματισμού.
Μπορείτε να διαβάσετε την ύλη των διαλέξεων από οποιαδήποτε πηγή επιθυμείτε. Δεν σκοπεύω να σας προτείνω σελίδες από συγγράμματα.
Τρόποι αξιολόγησης / εξέτασης
Θα δοθούν δύο ατομικά σετ ασκήσεων, τα οποία αποτελούν το 15% του τελικού βαθμού του μαθήματος.
Στα μέσα του εξαμήνου θα γίνει πρόοδος, η οποία αποτελεί το 20% του τελικού βαθμού στο μάθημα. Το ποσοστό της προόδου μετράει μόνο θετικά (υπολογίζεται μόνο αν ο βαθμός είναι μεγαλύτερος από τον τελικό βαθμό στο μάθημα).
Tο ποσοστό προόδου υπολογίζεται αν ο φοιτητής πάρει τουλάχιστον 3,5/10 στο τελικό διαγώνισμα.
Βοηθήματα
Για διανομή προτείνονται τα εξής δύο βιβλία, εκ των οποίων επιλέγετε το ένα:
- S. Dasgupta, C.H. Papadimitriou και U.V. Vazirani, Αλγόριθμοι, Κλειδάριθμος 2009. Μπορείτε επίσης να χρησιμοποιείτε το αγγλικό πρωτότυπο Algorithms, by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest και Clifford Stein Εισαγωγή στους Αλγορίθμους, Τόμος ΙΙ, Πανεπιστημιακές Εκδόσεις Κρήτης
Διδάσκοντες - Ώρες Γραφείου
Γεώργιος Ζώης,
email: georzois@aueb.gr
Διεύθυνση: Ευελπίδων 47Α & Λευκάδος 33, 8ος Όροφος, γραφείο 801
Ώρες Γραφείου: Τρίτη 11:00-12:00, Παρασκευή 16:00-17:00
Φροντιστήρια
Παναγιώτης Τσαμόπουλος
email: tsamopoulos@aueb.gr
Διεύθυνση: Πατησίων 76, 10434, Πτέρυγα Αντωνιάδου, 4ος Όροφος, Εργαστήριο Α46.
Ώρες Γραφείου: ΤΒΑ
Το μάθημα αυτό είναι συνέχεια του υποχρεωτικού μαθήματος Αλγόριθμοι.
Στο μάθημα αυτό σας δίνεται η δυνατότητα να εμβαθύνετε, να συζητήσετε και να δημιουργήσετε σε θέματα αλγοριθμικά.
Στόχος είναι να εμπλουτίσετε και να εμπεδώσετε τις αλγοριθμικές σας γνώσεις σε θέματα που έχουν μεγάλη εφαρμογή στην πράξη όπως αλγόριθμοι κρυπτογραφίας, ο δυναμικός προγραμματισμός και η αναγνώριση και αντιμετώπιση δύσκολων (ΝΡ-πλήρων) προβλημάτων.
Η ύλη μπορεί να μεταβληθεί, αν οι φοιτητές προτείνουν αλγοριθμικά θέματα που τους ενδιαφέρουν. Το αρχικό πρόγραμμα είναι το εξής:
Αρχικά συζητάμε αλγορίθμους που δεν περιλαμβάνονται στο υποχρεωτικό μάθημα, όπως αλγορίθμους αριθμοθεωρίας και συμπληρώνουμε τις γνώσεις σας στην αλγοριθμική μέθοδο του Δυναμικού προγραμματισμού με αντιπροσωπευτικά παραδείγματα, εμβαθύνοντας στη μέθοδο αυτή. Στη συνέχεια εξετάζουμε σε βάθος την θεωρία της ΝP-πληρότητας με κάποιες αναγωγές και μελετάμε προσεγγιστικούς και τυχαιοκρατικούς αλγορίθμους, καθώς και άλλους τρόπους αντιμετώπισης προβλημάτων για τα οποία δεν γνωρίζουμε γρήγορους (πολυωνυμικούς) αλγορίθμους. Επίσης, μελετάμε αλγόριθμους για την εύρεση μέγιστης ροής σε γράφους δικτύων καθώς και για την έρευση μέγιστου ταιριάσματος σε διμερείς γράφους. Τέλος μελετάμε σε βάθος αλγόριθμους βασισμένους στην μοντελοποίηση προβλημάτων με χρήση (ακέραιου) γραμμικού προγραμματισμού.
Μπορείτε να διαβάσετε την ύλη των διαλέξεων από οποιαδήποτε πηγή επιθυμείτε. Δεν σκοπεύω να σας προτείνω σελίδες από συγγράμματα.
Θα δοθούν δύο ατομικά σετ ασκήσεων, τα οποία αποτελούν το 15% του τελικού βαθμού του μαθήματος.
Στα μέσα του εξαμήνου θα γίνει πρόοδος, η οποία αποτελεί το 20% του τελικού βαθμού στο μάθημα. Το ποσοστό της προόδου μετράει μόνο θετικά (υπολογίζεται μόνο αν ο βαθμός είναι μεγαλύτερος από τον τελικό βαθμό στο μάθημα).
Tο ποσοστό προόδου υπολογίζεται αν ο φοιτητής πάρει τουλάχιστον 3,5/10 στο τελικό διαγώνισμα.
Για διανομή προτείνονται τα εξής δύο βιβλία, εκ των οποίων επιλέγετε το ένα:
- S. Dasgupta, C.H. Papadimitriou και U.V. Vazirani, Αλγόριθμοι, Κλειδάριθμος 2009. Μπορείτε επίσης να χρησιμοποιείτε το αγγλικό πρωτότυπο Algorithms, by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest και Clifford Stein Εισαγωγή στους Αλγορίθμους, Τόμος ΙΙ, Πανεπιστημιακές Εκδόσεις Κρήτης
Γεώργιος Ζώης,
email: georzois@aueb.gr
Διεύθυνση: Ευελπίδων 47Α & Λευκάδος 33, 8ος Όροφος, γραφείο 801
Ώρες Γραφείου: Τρίτη 11:00-12:00, Παρασκευή 16:00-17:00
Φροντιστήρια
Παναγιώτης Τσαμόπουλος
email: tsamopoulos@aueb.gr
Διεύθυνση: Πατησίων 76, 10434, Πτέρυγα Αντωνιάδου, 4ος Όροφος, Εργαστήριο Α46.
Ώρες Γραφείου: ΤΒΑ
