Αλγόριθμοι και Στοιχεία Πολυπλοκότητας

Το μάθημα περιλαμβάνει την εισαγωγή αλλά και εμβάθυνση στην θεωρία των αλγορίθμων και παράλληλα εισαγωγή και χρήση βασικών στοιχείων πολυπλοκότητας.

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

• Αντικειμενικός στόχος είναι η εκμάθηση τεχνικών επίλυσης προβλημάτων και ο στοιχειώδης υπολογισμός της πολυπλοκότητάς τους. • Με την ολοκλήρωση του μαθήματος οι εκπαιδευόμενοι θα μπορούν 1. Να επιλύουν σύνθετα προβλήματα αλγοριθμικά, 2. Να υπολογίζουν την πολυπλοκότητά τους, 3. Να βελτιώνουν ήδη επιλυμένα προβλήματα, 4. Να χρησιμοποιούν γνωστές αλγοριθμικές τεχνικές, 5. Να επιλύουν προβλήματα που συσχετίζονται με δέντρα και γράφους.

Προαπαιτούμενες Γνώσεις

Χωρίς προαπαιτούμενα.

Περιεχόμενα

1. Ορισμοί και ορολογία, 2. Πολυπλοκότητα, 3. Βελτιωμένη μέθοδος υπολογισμού δισδιάστατων μέγιστων, 4. Αναδρομικοί αλγόριθμοι, 5. «Διαίρει και βασίλευε», 6. Δυναμικός προγραμματισμός, 7. Άπληστοι αλγόριθμοι, 8. Παράλληλοι αλγόριθμοι, 9. Δέντρα, 10. Γράφοι, 11. Κατακερματισμός, 12. Κλάσεις P και NP.