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