Εξειδικευμένα Θέματα Αλγορίθμων

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

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

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

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

• Βασικές έννοιες για τους πολυνηματικούς αλγόριθμους και τη δυναμική πολυνημάτωση. Η πολυνηματική εκδοχή του αλγόριθμου Merge Sort.
• Αποδοτικοί αλγόριθμοι για την επίλυση γραμμικών συστημάτων εξισώσεων μέσω πινάκων και για την αντιστροφή πινάκων..
• Εισαγωγή στο γραμμικό προγραμματισμό. Μορφές προβλημάτων γραμμικού προγραμματισμού και μετατροπές μεταξύ μορφών. Αναγωγή προβλημάτων σε γραμμικά προγράμματα. Ο αλγόριθμος Simplex. Η έννοια της δυϊκότητας στον γραμμικό προγραμματισμό.
• Παίγνια μηδενικού αθροίσματος. Ο διακριτός και ο ταχύς μετασχηματισμός Fourier..
• Στοιχειώδεις αριθμοθεωρητικοί αλγόριθμοι. Ο αλγόριθμος του μέγιστου κοινού διαιρέτη. Αριθμητική υπολοίπων. Επίλυση συστημάτων γραμμικών εξισώσεων υπολοίπων. Το κινεζικό θεώρημα του υπολοίπου. Το κρυπτοσύστημα δημόσιου κλειδιού RSA.
• Τυχαιοποιημένοι αλγόριθμοι. Τυχαίες μεταβλητές και μέσες τιμές. Τυχαιότητα και γραμμικός προγραμματισμός. Ο αλγόριθμος Metropolis και η Προσομοιωμένη Ανόπτηση.
• Εισαγωγή στους προσεγγιστικούς αλγόριθμους. Το πρόβλημα της κάλυψης κορυφών. Το πρόβλημα του πλανόδιου πωλητή. Το πρόβλημα της κάλυψης συνόλου. Ένας τυχαιοποιημένος προσεγγιστικός αλγόριθμος για το MAX 3-SAT.
• Η κλάση των προβλημάτων πολυωνυμικού χρόνου και η κλάση των προβλημάτων που επιδέχονται επαλήθευση σε πολυωνυμικό χρόνο. Η έννοια της αναγωγής και της NP-πληρότητας. Χαρακτηριστικά NP-πλήρη προβλήματα. Η κλάση πολυπλοκότητας PSPACE.

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