Αλγόριθμοι
Μανωλόπουλος Ιωάννης, Γούναρης Αναστάσιος
"Sorting quicksort anim" by en:User:RolandH. Licensed under CC BY-SA 3.0 via Commons - https://commons.wikimedia.org/wiki/File:Sorting_quicksort_anim.gif#/media/File:Sorting_quicksort_anim.gif
Στόχος του μαθήματος είναι η γνωριμία των φοιτητών με βασικά ζητήματα σχετικά με τη σχεδίαση και την ανάλυση αλγορίθμων. Αρχικά, παρουσιάζονται βασικές έννοιες σχετικές με το περιεχόμενο του μαθήματος και γίνεται εισαγωγή σε ένα σύνολο βασικών τεχνικών σχεδίασης. Στο υπόλοιπο μέρος του μαθήματος, περιγράφονται ζητήματα σχετικά με συμβιβασμούς χώρου και χρόνου, δυναμικό προγραμματισμό, άπληστους αλγορίθμους και επαναληπτική βελτίωση. Τέλος, αναλύονται θέματα σχετικά με περιορισμούς της αλγοριθμικής δύναμης και μεθόδους αντιμετώπισης. Επίσης, στο μάθημα αυτό πραγματοποιείται μελέτη μεγάλης ποικιλίας προβλημάτων ταξινόμησης, αναζήτησης, γράφων, ταύτισης προτύπου, συνδυαστικής και αριθμητικών και γεωμετρικών προβλημάτων.
Λιγότερα
"Sorting quicksort anim" by en:User:RolandH. Licensed under CC BY-SA 3.0 via Commons - https://commons.wikimedia.org/wiki/File:Sorting_quicksort_anim.gif#/media/File:Sorting_quicksort_anim.gif
Στόχος του μαθήματος είναι η γνωριμία των φοιτητών με βασικά ζητήματα σχετικά με τη σχεδίαση και την ανάλυση αλγορίθμων. Αρχικά, παρουσιάζονται βασικές έννοιες σχετικές με το περιεχόμενο του μαθήματος και γίνεται εισαγωγή σε ένα σύνολο βασικών τεχνικών σχεδίασης. Στο υπόλοιπο μέρος του μαθήματος, περιγράφονται ζητήματα σχετικά με συμβιβασμούς χώρου και χρόνου, δυναμικό προγραμματισμό, άπληστους αλγορίθμους και επαναληπτική βελτίωση. Τέλος, αναλύονται θέματα σχετικά με περιορισμούς της αλγοριθμικής δύναμης και μεθόδους αντιμετώπισης. Επίσης, στο μάθημα αυτό πραγματοποιείται μελέτη μεγάλης ποικιλίας προβλημάτων ταξινόμησης, αναζήτησης, γράφων, ταύτισης προτύπου, συνδυαστικής και αριθμητικών και γεωμετρικών προβλημάτων.
"Sorting quicksort anim" by en:User:RolandH. Licensed under CC BY-SA 3.0 via Commons - https://commons.wikimedia.org/wiki/File:Sorting_quicksort_anim.gif#/media/File:Sorting_quicksort_anim.gif
Στόχος του μαθήματος είναι η γνωριμία των φοιτητών με βασικά ζητήματα σχετικά με τη σχεδίαση και την ανάλυση αλγορίθμων. Αρχικά, παρουσιάζονται βασικές έννοιες σχετικές με το περιεχόμενο του μαθήματος και γίνεται εισαγωγή σε ένα σύνολο βασικών τεχνικών σχεδίασης. Στο υπόλοιπο μέρος του μαθήματος, περιγράφονται ζητήματα σχετικά με συμβιβασμούς χώρου και χρόνου, δυναμικό προγραμματισμό, άπληστους αλγορίθμους και επαναληπτική βελτίωση. Τέλος, αναλύονται θέματα σχετικά με περιορισμούς της αλγοριθμικής δύναμης και μεθόδους αντιμετώπισης. Επίσης, στο μάθημα αυτό πραγματοποιείται μελέτη μεγάλης ποικιλίας προβλημάτων ταξινόμησης, αναζήτησης, γράφων, ταύτισης προτύπου, συνδυαστικής και αριθμητικών και γεωμετρικών προβλημάτων.
Περίγραμμα
Διδάσκοντες
Διδάσκοντες: Ιωάννης Μανωλόπουλος, Καθηγητής
Yannis Manolopoulos is Professor with the Department of Informatics of the Aristotle University of Thessaloniki. He has been with the University of Toronto, the University of Maryland at College Park and the University of Cyprus. He has also served as Rector of the University of Western Macedonia in Greece, Head of his own department, and Vice-Chair of the Greek Computer Society. His research interest focuses in Data Management. He has co-authored 5 monographs and 8 textbooks in Greek, as well as >300 journal and conference papers. He has received >9000 citations from >1300 distinct academic institutions (h-index=44). He has also received 3 best paper awards from SIGMOD, ECML/PKDD and MEDES conferences and has been invited as keynote speaker in 10 international events. He has served as main co-organizer of several major conferences.
Αναστάσιος Γούναρης, Επίκουρος Καθηγητής
Anastasios Gounaris is an Assistant Professor at the Dept. of Informatics of the Aristotle University of Thessaloniki. Prior to that, he was a visiting lecturer at the University of Cyprus and a research associate member of the Information Management Group of the School of Computer Science of the University of Manchester and of CERTH. He is a member of Delab. He graduated with a PhD from the School of Computer Science of the University of Manchester in 2005. He also graduated from the Dept. of Electrical and Computer Engineering of Thessaloniki, Greece in 1999 (BSc), and from the Dept. of Computation, UMIST, Manchester, UK, in 2002 (MPhil). His main research interests are in the area of autonomic, adaptive and wide-area data management, distributed DBMSs, massive parallelism, data mining and resource scheduling.
Συνεργάτης Ανάπτυξης Περιεχομένου: Ανδρέας Κοσματόπουλος
Περιεχόμενο μαθήματος
- Εισαγωγή
- Ανάλυση Αλγορίθμων
- Ωμή Βία
- Διαίρει και Βασίλευε
- Μείωσε και Βασίλευε
- Μετασχημάτισε και Κυριάρχησε
- Χωρικοί – Χρονικοί Συμβιβασμοί
- Δυναμικός Προγραμματισμός
- Άπληστοι Αλγόριθμοι
- Επαναληπτική Βελτίωση
- Περιορισμοί της Αλγοριθμικής Ισχύος
- Αντιμετώπιση Περιορισμών Αλγοριθμικής Ισχύος
Μαθησιακοί στόχοι
Κατάρτιση σε μεθόδους σχεδίασης αλγορίθμων, εξοικείωση με τις βασικές στρατηγικές επίλυσης προβλημάτων και κατανόηση των ιδιαίτερων χαρακτηριστικών τους και εισαγωγικών στοιχείων της ανάλυσης αλγορίθμων. Απόκτηση ικανότητας εφαρμογής αλγορίθμων σε γνωστούς τύπους προβλημάτων, ικανότητας σχεδιασμού αλγορίθμων και επίλυσης νέων προβλημάτων, και βασικών γνώσεων ανάλυσης αλγορίθμων.
Μέθοδοι διδασκαλίας
Πρόσωπο με πρόσωπο, διδασκαλία καθ’ έδρας.
Μέθοδοι αξιολόγησης
Γραπτές εξετάσεις και εργασίες. Η ακριβής διαδικασία και βαρύτητα ανακοινώνεται στην ιστοσελίδα.
Μέθοδοι Αξιολόγησης Φοιτητών
Γραπτή Εξέταση με Ερωτήσεις Σύντομης Απάντησης
Γραπτή Εργασία
Γραπτή Εξέταση με Επίλυση Προβλημάτων
Προαπαιτούμενα
Δεν υπάρχουν.
Ομάδα στόχος
Οι φοιτητές του τμήματος Πληροφορικής ενδιαφερόμενοι για τη θεματική περιοχή της σχεδίασης και ανάλυσης αλγορίθμων.
Προτεινόμενα συγγράμματα
Το μάθημα βασίζεται στο βιβλίο “Introduction to the Design and Analysis of Algorithms” (Anany Levitin), Addison Wesley 2003, μτφρ. Εκδόσεις Τζιόλα 2008, ISBN:960-418-143-2
Βιβλιογραφία
- Παναγιώτης Μποζάνης: "Αλγόριθμοι - Σχεδιασμός και Ανάλυση", Εκδόσεις Τζιόλα, 2003.
- Jon Kleinberg and Eva Tardos: "Algorithm Design", Addison Wesley, 2005 (μεταφρασμένο από τις Εκδόσεις Κλειδάριθμος).
- Steven Skienna: "The Algorithm Design Manual" Springer, 2nd edition, 2007.
- Thomas Cormen, Charles Leiserson and Ronald Rivest: "Introduction to Algorithms", 1st edition, MIT Press, 1990 (μεταφρασμένο από τις Πανεπιστημιακές Εκδόσεις Κρήτης).
- Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani: Algorithms (μεταφρασμένο από τις Εκδόσεις Κλειδάριθμος).
- Ιωάννης Μανωλόπουλος και Κωνσταντίνος Ζαχαρής: "Η Τέχνη της Αλγοριθμικής Επίλυσης Προβλημάτων", Εκδόσεις Σαββάλα, 2002.
- Gregory Rawlings: "Αλγόριθμοι - Ανάλυση και Σύγκριση", Εκδόσεις Κριτική, 2004.
- Gilles Brassard and Paul Bratley: "Algorithmics - Theory and practice", 1st edition, Prentice Hall, 1988.
- Robert Sedgewick: "Algorithms in C, Part 5 - Graph Algorithms", 3rd edition, Addison Wesley, 2002.
- Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran: "Computer Algorithms", Computer Science Press, 1998.
- Robert Sedgewick and Philippe Flajolet: "An Introduction to the Analysis of Algorithms", Addisson Wesley, 1996.
- Michael Goodrich and Roberto Tamassia: "Algorithm Design Foundations, Analysis, and Internet Examples" John Wiley, 2002.
Διδάσκοντες: Ιωάννης Μανωλόπουλος, Καθηγητής
Yannis Manolopoulos is Professor with the Department of Informatics of the Aristotle University of Thessaloniki. He has been with the University of Toronto, the University of Maryland at College Park and the University of Cyprus. He has also served as Rector of the University of Western Macedonia in Greece, Head of his own department, and Vice-Chair of the Greek Computer Society. His research interest focuses in Data Management. He has co-authored 5 monographs and 8 textbooks in Greek, as well as >300 journal and conference papers. He has received >9000 citations from >1300 distinct academic institutions (h-index=44). He has also received 3 best paper awards from SIGMOD, ECML/PKDD and MEDES conferences and has been invited as keynote speaker in 10 international events. He has served as main co-organizer of several major conferences.
Αναστάσιος Γούναρης, Επίκουρος Καθηγητής
Anastasios Gounaris is an Assistant Professor at the Dept. of Informatics of the Aristotle University of Thessaloniki. Prior to that, he was a visiting lecturer at the University of Cyprus and a research associate member of the Information Management Group of the School of Computer Science of the University of Manchester and of CERTH. He is a member of Delab. He graduated with a PhD from the School of Computer Science of the University of Manchester in 2005. He also graduated from the Dept. of Electrical and Computer Engineering of Thessaloniki, Greece in 1999 (BSc), and from the Dept. of Computation, UMIST, Manchester, UK, in 2002 (MPhil). His main research interests are in the area of autonomic, adaptive and wide-area data management, distributed DBMSs, massive parallelism, data mining and resource scheduling.
Συνεργάτης Ανάπτυξης Περιεχομένου: Ανδρέας Κοσματόπουλος
- Εισαγωγή
- Ανάλυση Αλγορίθμων
- Ωμή Βία
- Διαίρει και Βασίλευε
- Μείωσε και Βασίλευε
- Μετασχημάτισε και Κυριάρχησε
- Χωρικοί – Χρονικοί Συμβιβασμοί
- Δυναμικός Προγραμματισμός
- Άπληστοι Αλγόριθμοι
- Επαναληπτική Βελτίωση
- Περιορισμοί της Αλγοριθμικής Ισχύος
- Αντιμετώπιση Περιορισμών Αλγοριθμικής Ισχύος
Κατάρτιση σε μεθόδους σχεδίασης αλγορίθμων, εξοικείωση με τις βασικές στρατηγικές επίλυσης προβλημάτων και κατανόηση των ιδιαίτερων χαρακτηριστικών τους και εισαγωγικών στοιχείων της ανάλυσης αλγορίθμων. Απόκτηση ικανότητας εφαρμογής αλγορίθμων σε γνωστούς τύπους προβλημάτων, ικανότητας σχεδιασμού αλγορίθμων και επίλυσης νέων προβλημάτων, και βασικών γνώσεων ανάλυσης αλγορίθμων.
Πρόσωπο με πρόσωπο, διδασκαλία καθ’ έδρας.
Γραπτές εξετάσεις και εργασίες. Η ακριβής διαδικασία και βαρύτητα ανακοινώνεται στην ιστοσελίδα.
Μέθοδοι Αξιολόγησης Φοιτητών
Γραπτή Εξέταση με Ερωτήσεις Σύντομης Απάντησης
Γραπτή Εργασία
Γραπτή Εξέταση με Επίλυση Προβλημάτων
Δεν υπάρχουν.
Οι φοιτητές του τμήματος Πληροφορικής ενδιαφερόμενοι για τη θεματική περιοχή της σχεδίασης και ανάλυσης αλγορίθμων.
Το μάθημα βασίζεται στο βιβλίο “Introduction to the Design and Analysis of Algorithms” (Anany Levitin), Addison Wesley 2003, μτφρ. Εκδόσεις Τζιόλα 2008, ISBN:960-418-143-2
- Παναγιώτης Μποζάνης: "Αλγόριθμοι - Σχεδιασμός και Ανάλυση", Εκδόσεις Τζιόλα, 2003.
- Jon Kleinberg and Eva Tardos: "Algorithm Design", Addison Wesley, 2005 (μεταφρασμένο από τις Εκδόσεις Κλειδάριθμος).
- Steven Skienna: "The Algorithm Design Manual" Springer, 2nd edition, 2007.
- Thomas Cormen, Charles Leiserson and Ronald Rivest: "Introduction to Algorithms", 1st edition, MIT Press, 1990 (μεταφρασμένο από τις Πανεπιστημιακές Εκδόσεις Κρήτης).
- Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani: Algorithms (μεταφρασμένο από τις Εκδόσεις Κλειδάριθμος).
- Ιωάννης Μανωλόπουλος και Κωνσταντίνος Ζαχαρής: "Η Τέχνη της Αλγοριθμικής Επίλυσης Προβλημάτων", Εκδόσεις Σαββάλα, 2002.
- Gregory Rawlings: "Αλγόριθμοι - Ανάλυση και Σύγκριση", Εκδόσεις Κριτική, 2004.
- Gilles Brassard and Paul Bratley: "Algorithmics - Theory and practice", 1st edition, Prentice Hall, 1988.
- Robert Sedgewick: "Algorithms in C, Part 5 - Graph Algorithms", 3rd edition, Addison Wesley, 2002.
- Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran: "Computer Algorithms", Computer Science Press, 1998.
- Robert Sedgewick and Philippe Flajolet: "An Introduction to the Analysis of Algorithms", Addisson Wesley, 1996.
- Michael Goodrich and Roberto Tamassia: "Algorithm Design Foundations, Analysis, and Internet Examples" John Wiley, 2002.
Στη συγκεκριμένη ενότητα πραγματοποιείται μια πρώτη γνωριμία με το μάθημα. Δίνεται το κίνητρο της ενασχόλησης με τα περιεχόμενα του μαθήματος και παρέχονται βασικές έννοιες και ορισμοί.
Λέξεις Κλειδιά: Αλγόριθμος, ταξινόμηση, ταξινόμηση με επιλογή, μέγιστος κοινός διαιρέτης
Στη συγκεκριμένη ενότητα παρουσιάζονται έννοιες σχετικά με την ανάλυση των αλγορίθμων όπως η χρονική αποδοτικότητα, οι τάξεις μεγέθους και οι ασυμπτωτικοί συμβολισμοί Ο, Ω, Θ.
Λέξεις Κλειδιά: Ανάλυση αλγορίθμων, αποδοτικότητα, καλύτερη περίπτωση, μέση περίπτωση, χειρότερη περίπτωση, τάξη μεγέθους, ασυμπτωτική κλάση, πύργοι του Ανόι, Fibonacci
Η συγκεκριμένη ενότητα παρέχει βασικές έννοιες και παραδείγματα σχετικά με την τεχνική σχεδίασης «Ωμή Βία». Επίσης, παρουσιάζονται αλγόριθμοι «Ωμής Βίας» για ορισμένα κλασικά προβλήματα (π.χ. ταύτιση προτύπου, κυρτού περιβλήματος κ.α.)
Λέξεις Κλειδιά: Ωμή βία, bubble sort, εξαντλητική αναζήτηση
Σε αυτήν την ενότητα παρουσιάζονται βασικές έννοιες και παραδείγματα σχετικά με την τεχνική σχεδίασης «Διαίρει και Βασίλευε». Συγκεκριμένα, αναλύονται δύο σημαντικοί αλγόριθμοι ταξινόμησης, ο αλγόριθμος της ταξινόμησης με συγχώνευση και ο αλγόριθμος της γρήγορης ταξινόμησης. Επίσης παρουσιάζεται ο πολλαπλασιασμός πινάκων αλά Strassen και ο αλγόριθμος Quickhull για το πρόβλημα του κυρτού περιβλήματος.
Λέξεις Κλειδιά: Διαίρει και Βασίλευε, αναδρομή, ταξινόμηση με συγχώνευση, γρήγορη ταξινόμηση, Strassen, Quickhull
Στην ενότητα αυτή αναπτύσσονται βασικές έννοιες και παραδείγματα σχετικά με την τεχνική σχεδίασης «Μείωσε και Βασίλευε». Συγκεκριμένα, περιγράφονται ο αλγόριθμος της ταξινόμησης με εισαγωγή και οι μέθοδοι διάσχισης γράφων DFS και BFS. Επίσης, αναφέρονται ζητήματα σχετικά με τη δημιουργία μεταθέσεων, το πρόβλημα εύρεσης μέσου και την αναζήτηση παρεμβολής.
Λέξεις Κλειδιά: Μείωσε και Βασίλευε, ταξινόμηση με εισαγωγή, αναζήτηση κατά βάθος, DFS, αναζήτηση κατά πλάτος, BFS, τοπολογική ταξινόμηση, δημιουργία μεταθέσεων, αναζήτηση παρεμβολής
Η συγκεκριμένη ενότητα περιγράφει βασικές έννοιες και παραδείγματα σχετικά με την τεχνική σχεδίασης «Μετασχημάτισε και Κυριάρχησε». Συγκεκριμένα, γίνεται αναφορά στο πρόβλημα της επιλογής και στη Gaussian απαλοιφή, αναλύονται τα ισοζυγισμένα δένδρα AVL ενώ τέλος περιγράφεται η ταξινόμηση με τη χρήση σωρού.
Λέξεις Κλειδιά: Μετασχημάτισε και Κυριάρχησε, προταξινόμηση, Gaussian απαλοιφή, Δένδρα AVL, σωρός, ταξινόμηση με σωρό
Η ενότητα αυτή αναλύει μεθόδους οι οποίες βασίζονται στη χρήση επιπλέον χώρου με σκοπό τη μείωση του συνολικού χρόνου εκτέλεσής τους. Οι τρεις κύριες έννοιες που παρουσιάζονται στην ενότητα είναι η ταξινόμηση με απαρίθμηση, η ταύτιση προτύπου με τους αλγορίθμους Horspool και Boyer-Moore και ο κατακερματισμός.
Λέξεις Κλειδιά: Συμβιβασμοί, ταξινόμηση με απαρίθμηση, ταύτιση προτύπου, ολίσθηση, Horspool, Boyer-Moore, ανοικτός κατακερματισμός, κλειστός κατακερματισμός
Σε αυτή την ενότητα παρουσιάζονται έννοιες σχετικά με τον Δυναμικό Προγραμματισμό καθώς και οι αλγόριθμοι Warshall, Floyd που βασίζονται στη λογική του Δυναμικού Προγραμματισμού. Επίσης, παρουσιάζονται έννοιες σχετικά με βέλτιστα δυαδικά δέντρα αναζήτησης καθώς και με το πρόβλημα του σάκου (knapsack).
Λέξεις Κλειδιά: Δυναμικός προγραμματισμός, διωνυμικοί συντελεστές, Warshall, Floyd, βέλτιστα δυαδικά δέντρα αναζήτησης, πρόβλημα του σάκου
Στην παρούσα ενότητα αναλύονται οι άπληστοι αλγόριθμοι και δίνονται συγκεκριμένα παραδείγματά τους, όπως οι αλγόριθμοι Prim, Kruskal και Dijkstra που αφορούν γραφήματα.
Λέξεις Κλειδιά: Άπληστος αλγόριθμος, απληστία, ζευγνύον δένδρο, Prim, Kruskal, Dijkstra, Huffman
Το περιεχόμενο της συγκεκριμένης ενότητας αφορά την επαναληπτική βελτίωση η οποία είναι μια τεχνική σχεδίασης αλγορίθμων για προβλήματα βελτιστοποίησης. Συγκεκριμένα, παρουσιάζεται η μέθοδος Simplex καθώς και το πρόβλημα του ευσταθούς γάμου.
Λέξεις Κλειδιά: Επαναληπτική βελτίωση, simplex, ευσταθής γάμος
Σε αυτή την ενότητα γίνεται μια παρουσίαση εννοιών σχετικά με τους περιορισμούς της αλγοριθμικής ισχύος. Συγκεκριμένα, αναπτύσσονται τα κατώτερα φράγματα και οι κλάσεις P και NP
Λέξεις Κλειδιά: Περιορισμοί αλγοριθμικής ισχύος, κατώτερο φράγμα, δένδρα απόφασης, κλάση P, κλάση NP, CNF, NP-complete
Στη συγκεκριμένη ενότητα παρουσιάζονται η τεχνική της ανάτρεξης και η τεχνική της φραγής-και-διακλάδωσης οι οποίες αποτελούν δύο στρατηγικές αντιμετώπισης περιορισμών αλγοριθμικής ισχύος. Επίσης, περιγράφεται το πρόβλημα των n βασιλισσών, το πρόβλημα του Χαμιλτονιανού κυκλώματος καθώς και το πρόβλημα της ανάθεσης.
Λέξεις Κλειδιά: Αντιμετώπιση περιορισμών αλγοριθμικής ισχύος, ανάτρεξη, διακλάδωση και φραγή
Ανοικτό Ακαδ. Μάθημα
Αρ. Επισκέψεων : 5538
Αρ. Προβολών : 29769
