Υπολογιστική Πολυπλοκότητα


Κωδικός 323
Εξάμηνο Χειμερινό
Ώρες Διδασκαλίας - Ώρες Εργαστηρίου 4 - 0
Διδάσκοντες Ευστάθιος Ζάχος, Αριστείδης Παγουρτζής

Περιγραφή

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