Προχωρημένα Θέματα Αλγορίθμων (ΤΒ1)

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

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

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

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

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

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

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

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

• “ΕΙΣΑΓΩΓΗ ΣΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ”, Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Εκδόσεις ΙΤΕ - Πανεπιστημιακές Εκδόσεις Κρήτης, ISBN 978-960-524-473-6, 2016
• “ΣΧΕΔΙΑΣΜΟΣ ΑΛΓΟΡΙΘΜΩΝ”, 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/DDI210/) 

Ατομική Γραπτή Εργασία και Παρουσίαση.

Η επιτυχής εκπόνηση και παρουσίαση της γραπτής εργασίας απαλλάσσει από την υποχρέωση της τελικής γραπτής εξέτασης και συμβάλλει στο 100% της βαθμολογίας.

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