Αλγόριθμοι

Το μάθημα επιδιώκει την εμπέδωση από την πλευρά των φοιτητριών και φοιτητών της έννοιας των αλγορίθμων, καθώς και των σημαντικότερων τεχνικών με τις οποίες γίνεται η ανάλυση των αλγορίθμων ως προς την πολυπλοκότητά τους.

          Με την επιτυχή ολοκλήρωση των σπουδών στο μάθημα οι φοιτήτριες και φοιτητές θα είναι σε θέση:

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

Το μάθημα απευθύνεται σε φοιτήτριες και φοιτητές του δεύτερου έτους σπουδών. Καλύπτει τα εξής θέματα:

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

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