ΠΑΝΕΠΙΣΤΗΜΙΟ ΚΥΠΡΟΥ Τμήμα Πληροφορικής

 

ΕΠΛ 336: Αλγόριθμοι και Πολυπλοκότητα

 

Περιεχόμενο Μαθήματος

     

Ενότητα

Θέματα

1

Εισαγωγή: Αλγόριθμος, Ανάλυση και Πολυπλοκότητα, Τάξη Αλγορίθμου και Προβλήματος,Σχεδιασμός αλγορίθμων  

2

Αλγόριθμοι Οπισθοδρόμησης: Τεχνική Σχεδιασμού Οπισθοδρόμησης, Πρόβλημα του Ευσταθούς Ταιριάσματος, Αλγόριθμος των Gale-Shapley

 

3

Αλγόριθμοι τύπου Διαίρει και Βασίλευε.

Μέρος Α’: Τεχνική Σχεδιασμού Διαίρει-Βασίλευε, Αλγόριθμος του Strassen για Πολλαπλασιασμό Πινάκων, Αλγόριθμος για Πολλαπλασιασμό Ακεραίων, Αλγόριθμος Επιλογής

 

Μέρος Β’: Γεωμετρικοί Αλγόριθμοι – Αλγόριθμος Υπολογισμού Κυρτού Περιβλήματος και Αλγόριθμος Εύρεσης Πλησιέστερου Ζεύγους Σημείων

 

Μέρος Γ’: Ταχύς Μετασχηματισμός Fourier – Συνέλιξη Διανυσμάτων και Πολλαπλασιασμός Πολυωνύμων, Μιγαδικές Ρίζες της Μονάδας, Αλγόριθμος Υπολογισμού Συνέλιξης με τη Χρήση Ταχύ Μετασχηματισμού Fourier

4

Άπληστοι Αλγόριθμοι: Τεχνική Σχεδιασμού Απληστίας, Τεχνικές Απόδειξης Βέλτιστης Λύσης, Αλγόριθμοι για Χρονοπρογραμματισμό Διαστημάτων (με ένα πόρο, με πολλούς πόρους, με προθεσμίες)

 

5

Δυναμικός Προγραμματισμός: Τεχνική Σχεδιασμού Δυναμικού Προγραμματισμού, Αλγόριθμος για Πολλαπλασιασμό Αλυσίδας Πινάκων, Αλγόριθμος Σύγκρισης DNA δύο  Οργανισμών

6

Δίκτυα Ροής: Πρόβλημα Μέγιστης Ροής, Αλγόριθμος Ford-Fulkerson και FF κατα Edmonds-Karp, Θεώρημα Μέγιστης Ροής και Ελάχιστης Αποκοπής

 

  Εφαρμογή: Διμερή Ταιριάσματα

7

Παραμετρικοί Αλγόριθμοι: Παραμετρικό Πρόβλημα, Παραμετρικός Αλγόριθμος, Πρόβλημα Κάλυψης Κορυφών, Πρόβλημα Ανεξαρτήτου Συνόλου σε Δένδρα

8

Τυχαιοποιημένοι Αλγόριθμοι: Τυχαιοποίηση, Κατηγορίες Τυχαιοποιημένων Αλγορίθμων, Βασικές Τεχνικές Σχεδίασης, Πρόβλημα Επαλήθευσης Γινομένου Πινάκων, Πρόβλημα Ελέγχου Πολυωνυμικών Ταυτοτήτων, Πρόβλημα Καθολικής Ελάχιστης Αποκοπής

   

Αρχική