Αλγόριθμοι και Πολυπλοκότητα (Κ17)
Μισυρλής Νικόλαος
Περίγραμμα
Οργάνωση Μαθήματος
Το μάθημα είναι κορμού της πρώτης κατεύθυνσης (Θεωρητική Πληροφορική).
Οι διαλέξεις του μαθήματος γίνονται δύο δίωρα την εβδομάδα. Επίσης, υπάρχουν τέσσερα τμήματα φροντιστηρίων.
Στόχοι
Αναλύοντας τους αλγόριθμους στόχος μας είναι να διερευνήσουμε πως οι απαιτούμενοι για την εκτέλεσή τους πόροι, δηλαδή ο χρόνος και η μνήμη που χρησιμοποιούν, διακυμαίνονται με την αυξανόμενη διάσταση της εισόδου. Έτσι μπορούμε να αποτιμήσουμε την επίδοση ενός αλγορίθμου, να συγκρίνουμε δυο αλγόριθμους που επιλύουν το ίδιο πρόβλημα και να αναπτύξουμε έναν αποδοτικό αλγόριθμο για ένα πρόβλημα. Το ενδιαφέρον εστιάζεται στη κατανόηση ορισμένων βασικών τεχνικών σχεδίασης αλγορίθμων και στη διάκριση των προβλημάτων σε αυτά που θεωρούνται πρακτικώς επιλύσιμα και σε αυτά που θεωρούνται πρακτικώς δυσεπίλυτα.
Βοηθήματα
Οι διαλέξεις του μαθήματος είναι βιντεοσκοπημένες και βρίσκονται στο φάκελο Σύνδεσμοι.
Ένα από τα ακόλουθα βιβλία
Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, MIT-Press, 2001
Jon Kleinberg, Eva Tardos, Algorithm Design, Addison-Wesley, 2006
Σημειώσεις Μαθήματος (βλέπε Φάκελο Έγγραφα)
Διαφάνειες διαλέξεων (βλέπε Φάκελο Έγγραφα)
Υπάρχει και αρκετό υλικό από βιβλία,σημειώσεις, διαφάνειες και στον φάκελο Σύνδεσμοι
Ανθρώπινο Δυναμικό
Διδάσκων Καθηγητής: Νικόλαος Μισυρλής, Γραφείο Β24 , τηλ. 2107275103 (nmis@di.uoa.gr).
Φροντιστήρια ΕΔΙΠ: 1). Μ. Λουκά, Γραφείο A41, 2107275229 (mlouka@di.uoa.gr) και 2) Ο. Φουρτουνέλλη, Γραφείο A25, 2107275332 (folga@di.uoa.gr)
Aξιολόγηση / Βαθμολογία
Αξιολόγηση
Η επίδοση των φοιτητών θα αξιολογηθεί μέσα από ένα σύνολο εργασιών και εξετάσεων. Οι εργασίες θα περιλαμβάνουν θεωρητικές και προγραμματιστικές ασκήσεις. Επίσης θα διεξαχθούν μία ενδιάμεση και μία τελική εξέταση. Ο τελικός βαθμός θα υπολογιστεί ως ακολούθως:
· Τελική εξέταση 60%
· Ενδιάμεση εξέταση 25%
· Εργασίες 15%
Βαθμολογία
Πιό συγκεκριμμένα, η τελική βαθμολογία του μαθήματος προκύπτει με βάση τον ακόλουθο τύπο:
Αν ΒΓE >= 30 τότε
ΤΒ = [0.15 * ΒΥΕ + 0.25 * ΒΕΕ + 0.6 * ΒΓΕ]/10 (+ 0.01*ΒΠΑ)
διαφορετικά
ΤΒ = ΒΓΕ,
όπου ΤΒ=Τελικός βαθμός, ΒΥΕ= μέσος όρος βαθμών των υποχρεωτικών εργασιών, ΒΕΕ=βαθμός Ενδιάμεσης Εξέτασης, ΒΠΑ= μέσος όρος βαθμών των προαιρετικών εργασιών και ΒΓΕ= βαθμός γραπτής εξέτασης (Ιουνίου/Σεπτεμβρίου).
Δεν διατηρείται η βαθμολογία των ασκήσεων και της ενδιάμεσης εξέτασης στα επόμενα έτη. Για τον λόγο αυτό σε περίπτωση που δεν λάβετε προβιβάσιμο βαθμό τότε την επόμενη ακαδημαϊκή χρονιά θα πρέπει να συμμετέχετε και στις δύο εξέτάσεις (ενδιάμεση και τελική) και να παραδώσετε όλες τις τρέχουσες ασκήσεις.
Σημαντική Ενημέρωση
Είναι υποχρεωτικό να έχετε δηλώσει το μάθημα στην Γραμματεία το τρέχον ακαδημαϊκό έτος σε διαφορετική περίπτωση δεν είναι δυνατή η καταχώρηση της βαθμολογίας σας.
Ασκήσεις
Οι ασκήσεις υποβάλλονται ηλεκτρονικά (pdf) εντός των προθεσμιών στην η-τάξη. Παράταση των καταληκτικών ημερομηνιών δεν θα δίνεται καθόσον προκαλούν πολλαπλά προβλήματα σε όλο το σύστημα αξιολόγησης. Οι εκπρόθεσμες ασκήσεις θα μπορούν να υποβληθούν μόνον εντός των επόμενων δύο ημερών μετά την καταληκτική ημερομηνία. Ωστόσο η βαθμολογία τους θα είναι μειωμένη κατά το 50%.
Οριστικοποίηση Τελικής Βαθμολογίας
Η βαθμολογία είναι ένα θέμα που τελειώνει οριστικά με την ανακοίνωση των τελικών αποτελεσμάτων. Πιο συγκεκριμένα οποιοδήποτε θέμα αφορά διόρθωση βαθμολογίας ασκήσεων και γραπτών εξετάσεων διευθετείται μόνον την ημερομηνία που δείχνονται οι κόλλες μετά την εξέταση του μαθήματος (θα υπάρξει σχετική ανακοίνωση μετά την εξέταση). Η διαδικασία αυτή διενεργείται μόνον με τη φυσική παρουσία του ενδιαφερόμενου φοιτητή. Μετά την παρέλευση της συγκεκριμένης ημερομηνίας η βαθμολογία οριστικοποιείται, καταχωρείται άμεσα στο σύστημα (mystudies) και δεν είναι δυνατή καμία τροποποίησή της. Ηλεκτρονικά μηνύματα και τηλεφωνικές κλήσεις δεν λαμβάνονται υπόψη.
Για τον λόγο αυτό να ελέγξετε με προσοχή τη βαθμολογία (κυρίως των ασκήσεών σας) και σε περίπτωση που διαπιστώσετε κάποιο λάθος ή παράλειψη θα πρέπει να επισημανθεί την ανωτέρω ημερομηνία προκειμένου να διορθωθεί. Διευκρινίζεται ότι σε περίπτωση που δεν προβείτε στην ανωτέρω ενέργεια και παρέλθει η ανωτέρω ημερομηνία, τότε η βαθμολογία σας οριστικοποιείται και παραμένει ως έχει για μελλοντική χρήση.
Ώρες υποδοχής φοιτητών:
Καθηγητής Ν. Μισυρλής : Γραφείο Β24, Τετάρτη 1-3, Παρασκευή 3-4, ή μετά από συνεννόηση.
ΕΔΙΠ Μ. Λουκά: Γραφείο Α41, Τρίτη 2:00-3:00, Πέμπτη 11:00-12:00 ή μετά από συνεννόηση.
ΕΔΙΠ Ο. Φουρτουνέλλη: Γραφείο Α19, Τρίτη 3:00-4:00 ή μετά από συνεννόηση.
Περιεχόμενο Μαθήματος
Εισαγωγή: Ανάλυση Αλγορίθμων, Ασυμπτωτική Πολυπλοκότητα. Αναδρομή. Διαίρει και Βασίλευε: Ταξινόμηση με συγχώνευση (merge sort), Δυαδική Αναζήτηση, Η ακολουθία Fibonacci, Γρήγορη ταξινόμηση (Quicksort). Θεώρημα κυριαρχίας (the master theorem). Αναδρομικές Γραμμικές εξισώσεις. Σωροί: Εισαγωγή, Διαγραφή, Κατασκευή, ταξινόμηση με σωρό (heapsort). Μετασχηματισμός κλειδιού (hashing). Γραφήματα: Παράσταση, Πράξεις. Αλγόριθμοι Γραφημάτων : Eξερεύνηση κατά πλάτος (Breadth First Search), Eξερεύνηση κατά βάθος (Depth First Search), Συνεκτικότητα, Τοπολογική Ταξινόμηση, Πράξεις με ασύνδετα σύνολα. Aπληστοι (greedy) αλγόριθμοι: συντομότερα μονοπάτια σε γραφήματα (αλγόριθμοι Dijkstra, Bellman-Ford), Δέντρα Επικάλυψης Ελάχιστου Κόστους (αλγόριθμοι Prim, Kruskal), το συνεχές πρόβλημα του σακιδίου (knapsack problem), το διακριτό πρόβλημα του σακιδίου, Κώδικες Huffman. Δυναμικός προγραμματισμός: Εισαγωγή, Χρονοδρομολόγηση γραμμής παραγωγής, Αλυσιδωτός πολλαπλασιασμός πινάκων, Μέγιστη Κοινή Υπακολουθία, το Πρόβλημα του Σακιδίου. Εξαντλητική αναζήτηση: το πρόβλημα των βασιλισσών. Οι κλάσεις P και NP. Προβλήματα απόφασης. Προβλήματα NP-complete και NP-hard. Αναγωγές.
Βιβλιογραφία
[1] Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, MIT-Press, 2001
[2] S. Dasgupta, C. H. Papadimitriou & U. V. Vazirani, Algorithms, McGraw-Hill, 2008
[3] Jon Kleinberg, Eva Tardos, Algorithm Design, Addison-Wesley, 2006
[4] R. Sedgewick, Algorithms in C, Addison-Wesley, 2nd ed., 1998.
Για επιπλέον υλικό όπως διαφάνειες διαλέξεων άλλων καθηγητών, σημειώσεις, η-βιβλία και ιστοσελίδες σχετικά με το μάθημα επισκεφτείτε τους Συνδέσμους.
Το μάθημα είναι κορμού της πρώτης κατεύθυνσης (Θεωρητική Πληροφορική).
Οι διαλέξεις του μαθήματος γίνονται δύο δίωρα την εβδομάδα. Επίσης, υπάρχουν τέσσερα τμήματα φροντιστηρίων.
Αναλύοντας τους αλγόριθμους στόχος μας είναι να διερευνήσουμε πως οι απαιτούμενοι για την εκτέλεσή τους πόροι, δηλαδή ο χρόνος και η μνήμη που χρησιμοποιούν, διακυμαίνονται με την αυξανόμενη διάσταση της εισόδου. Έτσι μπορούμε να αποτιμήσουμε την επίδοση ενός αλγορίθμου, να συγκρίνουμε δυο αλγόριθμους που επιλύουν το ίδιο πρόβλημα και να αναπτύξουμε έναν αποδοτικό αλγόριθμο για ένα πρόβλημα. Το ενδιαφέρον εστιάζεται στη κατανόηση ορισμένων βασικών τεχνικών σχεδίασης αλγορίθμων και στη διάκριση των προβλημάτων σε αυτά που θεωρούνται πρακτικώς επιλύσιμα και σε αυτά που θεωρούνται πρακτικώς δυσεπίλυτα.
Οι διαλέξεις του μαθήματος είναι βιντεοσκοπημένες και βρίσκονται στο φάκελο Σύνδεσμοι.
Ένα από τα ακόλουθα βιβλία
Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, MIT-Press, 2001
Jon Kleinberg, Eva Tardos, Algorithm Design, Addison-Wesley, 2006
Σημειώσεις Μαθήματος (βλέπε Φάκελο Έγγραφα)
Διαφάνειες διαλέξεων (βλέπε Φάκελο Έγγραφα)
Υπάρχει και αρκετό υλικό από βιβλία,σημειώσεις, διαφάνειες και στον φάκελο Σύνδεσμοι
Διδάσκων Καθηγητής: Νικόλαος Μισυρλής, Γραφείο Β24 , τηλ. 2107275103 (nmis@di.uoa.gr).
Φροντιστήρια ΕΔΙΠ: 1). Μ. Λουκά, Γραφείο A41, 2107275229 (mlouka@di.uoa.gr) και 2) Ο. Φουρτουνέλλη, Γραφείο A25, 2107275332 (folga@di.uoa.gr)
Αξιολόγηση
Η επίδοση των φοιτητών θα αξιολογηθεί μέσα από ένα σύνολο εργασιών και εξετάσεων. Οι εργασίες θα περιλαμβάνουν θεωρητικές και προγραμματιστικές ασκήσεις. Επίσης θα διεξαχθούν μία ενδιάμεση και μία τελική εξέταση. Ο τελικός βαθμός θα υπολογιστεί ως ακολούθως:
· Τελική εξέταση 60%
· Ενδιάμεση εξέταση 25%
· Εργασίες 15%
Βαθμολογία
Πιό συγκεκριμμένα, η τελική βαθμολογία του μαθήματος προκύπτει με βάση τον ακόλουθο τύπο:
Αν ΒΓE >= 30 τότε
ΤΒ = [0.15 * ΒΥΕ + 0.25 * ΒΕΕ + 0.6 * ΒΓΕ]/10 (+ 0.01*ΒΠΑ)
διαφορετικά
ΤΒ = ΒΓΕ,
όπου ΤΒ=Τελικός βαθμός, ΒΥΕ= μέσος όρος βαθμών των υποχρεωτικών εργασιών, ΒΕΕ=βαθμός Ενδιάμεσης Εξέτασης, ΒΠΑ= μέσος όρος βαθμών των προαιρετικών εργασιών και ΒΓΕ= βαθμός γραπτής εξέτασης (Ιουνίου/Σεπτεμβρίου).
Δεν διατηρείται η βαθμολογία των ασκήσεων και της ενδιάμεσης εξέτασης στα επόμενα έτη. Για τον λόγο αυτό σε περίπτωση που δεν λάβετε προβιβάσιμο βαθμό τότε την επόμενη ακαδημαϊκή χρονιά θα πρέπει να συμμετέχετε και στις δύο εξέτάσεις (ενδιάμεση και τελική) και να παραδώσετε όλες τις τρέχουσες ασκήσεις.
Σημαντική Ενημέρωση
Είναι υποχρεωτικό να έχετε δηλώσει το μάθημα στην Γραμματεία το τρέχον ακαδημαϊκό έτος σε διαφορετική περίπτωση δεν είναι δυνατή η καταχώρηση της βαθμολογίας σας.
Ασκήσεις
Οι ασκήσεις υποβάλλονται ηλεκτρονικά (pdf) εντός των προθεσμιών στην η-τάξη. Παράταση των καταληκτικών ημερομηνιών δεν θα δίνεται καθόσον προκαλούν πολλαπλά προβλήματα σε όλο το σύστημα αξιολόγησης. Οι εκπρόθεσμες ασκήσεις θα μπορούν να υποβληθούν μόνον εντός των επόμενων δύο ημερών μετά την καταληκτική ημερομηνία. Ωστόσο η βαθμολογία τους θα είναι μειωμένη κατά το 50%.
Οριστικοποίηση Τελικής Βαθμολογίας
Η βαθμολογία είναι ένα θέμα που τελειώνει οριστικά με την ανακοίνωση των τελικών αποτελεσμάτων. Πιο συγκεκριμένα οποιοδήποτε θέμα αφορά διόρθωση βαθμολογίας ασκήσεων και γραπτών εξετάσεων διευθετείται μόνον την ημερομηνία που δείχνονται οι κόλλες μετά την εξέταση του μαθήματος (θα υπάρξει σχετική ανακοίνωση μετά την εξέταση). Η διαδικασία αυτή διενεργείται μόνον με τη φυσική παρουσία του ενδιαφερόμενου φοιτητή. Μετά την παρέλευση της συγκεκριμένης ημερομηνίας η βαθμολογία οριστικοποιείται, καταχωρείται άμεσα στο σύστημα (mystudies) και δεν είναι δυνατή καμία τροποποίησή της. Ηλεκτρονικά μηνύματα και τηλεφωνικές κλήσεις δεν λαμβάνονται υπόψη.
Για τον λόγο αυτό να ελέγξετε με προσοχή τη βαθμολογία (κυρίως των ασκήσεών σας) και σε περίπτωση που διαπιστώσετε κάποιο λάθος ή παράλειψη θα πρέπει να επισημανθεί την ανωτέρω ημερομηνία προκειμένου να διορθωθεί. Διευκρινίζεται ότι σε περίπτωση που δεν προβείτε στην ανωτέρω ενέργεια και παρέλθει η ανωτέρω ημερομηνία, τότε η βαθμολογία σας οριστικοποιείται και παραμένει ως έχει για μελλοντική χρήση.
Καθηγητής Ν. Μισυρλής : Γραφείο Β24, Τετάρτη 1-3, Παρασκευή 3-4, ή μετά από συνεννόηση.
ΕΔΙΠ Μ. Λουκά: Γραφείο Α41, Τρίτη 2:00-3:00, Πέμπτη 11:00-12:00 ή μετά από συνεννόηση.
ΕΔΙΠ Ο. Φουρτουνέλλη: Γραφείο Α19, Τρίτη 3:00-4:00 ή μετά από συνεννόηση.
Εισαγωγή: Ανάλυση Αλγορίθμων, Ασυμπτωτική Πολυπλοκότητα. Αναδρομή. Διαίρει και Βασίλευε: Ταξινόμηση με συγχώνευση (merge sort), Δυαδική Αναζήτηση, Η ακολουθία Fibonacci, Γρήγορη ταξινόμηση (Quicksort). Θεώρημα κυριαρχίας (the master theorem). Αναδρομικές Γραμμικές εξισώσεις. Σωροί: Εισαγωγή, Διαγραφή, Κατασκευή, ταξινόμηση με σωρό (heapsort). Μετασχηματισμός κλειδιού (hashing). Γραφήματα: Παράσταση, Πράξεις. Αλγόριθμοι Γραφημάτων : Eξερεύνηση κατά πλάτος (Breadth First Search), Eξερεύνηση κατά βάθος (Depth First Search), Συνεκτικότητα, Τοπολογική Ταξινόμηση, Πράξεις με ασύνδετα σύνολα. Aπληστοι (greedy) αλγόριθμοι: συντομότερα μονοπάτια σε γραφήματα (αλγόριθμοι Dijkstra, Bellman-Ford), Δέντρα Επικάλυψης Ελάχιστου Κόστους (αλγόριθμοι Prim, Kruskal), το συνεχές πρόβλημα του σακιδίου (knapsack problem), το διακριτό πρόβλημα του σακιδίου, Κώδικες Huffman. Δυναμικός προγραμματισμός: Εισαγωγή, Χρονοδρομολόγηση γραμμής παραγωγής, Αλυσιδωτός πολλαπλασιασμός πινάκων, Μέγιστη Κοινή Υπακολουθία, το Πρόβλημα του Σακιδίου. Εξαντλητική αναζήτηση: το πρόβλημα των βασιλισσών. Οι κλάσεις P και NP. Προβλήματα απόφασης. Προβλήματα NP-complete και NP-hard. Αναγωγές.
[1] Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, MIT-Press, 2001
[2] S. Dasgupta, C. H. Papadimitriou & U. V. Vazirani, Algorithms, McGraw-Hill, 2008
[3] Jon Kleinberg, Eva Tardos, Algorithm Design, Addison-Wesley, 2006
[4] R. Sedgewick, Algorithms in C, Addison-Wesley, 2nd ed., 1998.
Για επιπλέον υλικό όπως διαφάνειες διαλέξεων άλλων καθηγητών, σημειώσεις, η-βιβλία και ιστοσελίδες σχετικά με το μάθημα επισκεφτείτε τους Συνδέσμους.
