Υπολογιστική Πολυπλοκότητα
| Κωδικός | 323 |
|---|---|
| Εξάμηνο | Χειμερινό |
| Ώρες Διδασκαλίας - Ώρες Εργαστηρίου | 4 - 0 |
| Διδάσκοντες | Ευστάθιος Ζάχος, Αριστείδης Παγουρτζής |
Περιγραφή
Τεχνικές για ασυμπτωτική εκτίμηση υπολογιστικής πολυπλοκότητας, κριτήρια για επιλογή αλγορίθμων, πολυωνυμικοί αλγόριθμοι. Ουρές προτεραιότητας, σωρός, διαχείριση ξένων συνόλων, union – find. Επεξεργασία δεδομένων (ταξινόμηση, επιλογή, αναζήτηση). Μέθοδοι σχεδιασμού αποδοτικών αλγορίθμων: «διαίρει και βασίλευε», άπληστοι αλγόριθμοι, δυναμικός προγραμματισμός. Εφαρμογές σε προβλήματα γραφημάτων: αναζήτηση κατά βάθος, αναζήτηση κατά πλάτος, ελάχιστο συνδετικό δένδρο, συντομότερα μονοπάτια, μέγιστη ροή και ελάχιστη τομή. Πιθανοτικοί και προσεγγιστικοί αλγόριθμοι. Υπολογισιμότητα και πολυπλοκότητα. Κλάσεις υπολογιστικής πολυπλοκότητας και αναγωγές. Οι κλάσεις P και NP, NP-complete προβλήματα. Κλάσεις χωρικής πολυπλοκότητας. Μαντεία και ιεραρχίες.