Στόχος Μαθήματος

Ο στόχος του μαθήματος είναι να παρουσιάσει και να εξηγήσει αναλυτικά τη λειτουργία μερικών από τους πιο γνωστούς αλγόριθμους που χρησιμοποιούνται ευρέως για να επιλύσουν πληθώρα προβλημάτων που παρουσιάζουν μεγάλο πρακτικό ενδιαφέρον.

Περιγραφή Μαθήματος

Το μάθημα καλύπτει τα εξής θέματα:

• Η έννοια του αλγορίθμου και της πολυπλοκότητας. Οι βασικές έννοιες της ανάλυσης αλγορίθμων και το απαιτούμενο μαθηματικό υπόβαθρο.
• Τεχνικές επίλυσης αναδρομικών εξισώσεων και τεχνικές σχεδίασης αλγορίθμων. Η τεχνική «διαίρει και βασίλευε».
• Ο αλγόριθμος της γρήγορης ταξινόμησης και ο ελάχιστος χρόνος εκτέλεσης αλγορίθμων ταξινόμησης.
• Η τεχνική του δυναμικού προγραμματισμού, η ιδιότητα βέλτιστων επιμέρους δομών και το πρόβλημα του πολλαπλασιασμού ακολουθίας πινάκων.
• Το ακέραιο πρόβλημα του σακιδίου, το πρόβλημα της διαμέρισης και η άπληστη τεχνική. Δρομολόγηση εργασιών, απληστία και ρέστα, το κλασματικό πρόβλημα του σακιδίου.
• Θεωρία γραφημάτων και αναπαράσταση γραφημάτων. Αλγόριθμοι εξερεύνησης γραφημάτων: αναζήτηση πρώτα σε πλάτος, αναζήτηση πρώτα σε βάθος και τοπολογική ταξινόμηση.
• Ελάχιστα επικαλύπτοντα δένδρα. Άπληστος υπολογισμός ελάχιστου επικαλύπτοντος δέντρου.
• Συντομότερα μονοπάτια, συντομότερα μονοπάτια μοναδικής πηγής και συντομότερα μονοπάτια για όλα τα ζεύγη κορυφών.
• Οπισθοδρόμηση, διακλάδωση και φράξιμο.
• Βασικοί αλγόριθμοι συμβολοσειρών.
• Εισαγωγή στη Θεωρία Υπολογιστικής Πολυπλοκότητας.

Με την επιτυχή ολοκλήρωση του μαθήματος «Αλγόριθμοι» οι προπτυχιακοί φοιτητές είναι σε θέση:

• Να κατανοήσουν σε βάθος την έννοια του αλγόριθμου.
• Να εξοικειωθούν με το θεωρητικό υπόβαθρο και τις τεχνικές που χρησιμοποιούνται για την επίλυση αναδρομικών σχέσεων, για την ανάλυση αλγορίθμων και την εύρεσης της πολυπλοκότητάς τους.
• Να εξοικειωθούν με τις ιδιότητες και τον τρόπο χρήσης των πιο γνωστών αλγόριθμων για αναζήτηση, ταξινόμηση, επίλυση προβλημάτων πάνω σε γράφους, καθώς και δυναμικού προγραμματισμού.

Να κατανοήσουν εισαγωγικές έννοιες από τη Θεωρία Υπολογιστικής Πολυπλοκότητας.

Η έννοια του αλγορίθμου και της πολυπλοκότητας. Βασικές έννοιες της ανάλυσης αλγορίθμων. Μαθηματικό υπόβαθρο. Τεχνικές επίλυσης αναδρομικών εξισώσεων. Τεχνικές σχεδίασης αλγορίθμων. Η τεχνική «διαίρει και βασίλευε». Ο αλγόριθμος της συγχώνευσης. Ο αλγόριθμος της γρήγορης ταξινόμησης. Ελάχιστος χρόνος εκτέλεσης αλγορίθμων διάταξης. Πολλαπλασιασμός αριθμών και πινάκων. Η τεχνική του δυναμικού προγραμματισμού. Ιδιότητα βέλτιστων επιμέρους δομών. Το πρόβλημα του πολλαπλασιασμού ακολουθίας πινάκων. Το ακέραιο πρόβλημα του σακιδίου. Το πρόβλημα της διαμέρισης. Η άπληστη τεχνική. Δρομολόγηση εργασιών, απληστία και ρέστα, το κλασματικό πρόβλημα του σακιδίου. Θεωρία Γραφημάτων. Αναπαράσταση γραφημάτων, αλγόριθμοι εξερεύνησης γραφημάτων. Αναζήτηση πρώτα σε πλάτος, αναζήτηση πρώτα σε βάθος. Τοπολογική ταξινόμηση. Ελάχιστα επικαλύπτοντα δένδρα. Άπληστος υπολογισμός ελάχιστου επικαλύπτοντος δέντρου. Συντομότερα μονοπάτια. Συντομότερα μονοπάτια μοναδικής πηγής. Συντομότερα μονοπάτια για όλα τα ζεύγη κορυφών. Οπισθοδρόμηση. Διακλάδωση και Φράξιμο. Βασικοί αλγόριθμοι συμβολοσειρών. Εισαγωγή στη Θεωρία Υπολογιστικής Πολυπλοκότητας.

• “ΕΙΣΑΓΩΓΗ ΣΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ”, Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Εκδόσεις ΙΤΕ - Πανεπιστημιακές Εκδόσεις Κρήτης, ISBN 978-960-524-473-6, 2016
• “ΑΛΓΟΡΙΘΜΟΙ”, Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Εκδόσεις Κλειδάριθμος ΕΠΕ, ISBN 978-960-461-211-6, 2009
• “ΣΧΕΔΙΑΣΜΟΣ ΑΛΓΟΡΙΘΜΩΝ”, Jon Kleinberg, Eva Tardos, Εκδόσεις Κλειδάριθμος ΕΠΕ, ISBN 978-960-461-207-9, 2009
• “ΑΝΑΛΥΣΗ ΚΑΙ ΣΧΕΔΙΑΣΗ ΑΛΓΟΡΙΘΜΩΝ”, Neapolitan Richard, Εκδόσεις Broken Hill Publishers Ltd, ISBN 978-992-535-111-4, 2023 

Χρήση ηλεκτρονικών σημειώσεων.

Υποστήριξη μαθησιακής διαδικασίας μέσω της Πλατφόρμας Τηλεκπαίδευσης Ιονίου Πανεπιστημίου (https://opencourses.ionio.gr/courses/DDI189/) 

Γραπτή εξέταση (επίλυση προβλημάτων), 100% τελικής βαθμολογίας.

Οι όροι βαθμολόγησης αναφέρονται ρητά στην ιστοσελίδα του μαθήματος.