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

Η έννοια του αλγορίθμου και της πολυπλοκότητας. Μέθοδοι σχεδιασμού καλών αλγορίθμων: “διαίρει και κυρίευε”, δυναμικός προγραμματισμός, άπληστοι αλγόριθμοι. Εφαρμογές στη θεωρία γραφημάτων (αναζήτηση σε βάθος, αναζήτηση σε πλάτος, ελάχιστο δένδρο-σκελετός, διαδρομή ελαχίστου κόστους). Επεξεργασία δεδομένων (διάταξη και αναζήτηση). Αλγεβρικά προβλήματα (υπολογισμός πολυωνύμων, πολλαπλασιασμός πινάκων). Αλγόριθμοι πολυωνυμικού χρόνου και ΝΡ-πλήρη προβλήματα. Εύκολα και δύσκολα προβλήματα συνδυαστικής βελτιστοποίησης, προβλήματα απόφασης, οι κλάσεις P και NP, προβλήματα NP-complete και αναγωγές. Το πρόβλημα του σακιδίου (knapsack problem), το πρόβλημα του πλανόδιου πωλητή (TSP). Παράλληλοι και κατανεμημένοι αλγόριθμοι.

Εαρ. Εξάμηνο 2015 - 2016. Μάθημα επιλογής 3ου έτους.

Πρόγραμμα: Δευτέρα 14.00 - 16.00, Τετάρτη 15.00 - 17.00


Προαπαιτούμενες γνώσεις ή/και σχετικά μαθήματα: 

Διακριτά Μαθηματικά, Εισαγωγή στον Προγραμματισμό, Αντικειμενοστρεφής Προγραμματισμός, Δομές Δεδομένων, Θεωρία Γράφων, Θεωρία Υπολογισμού

Μαθησιακοί Στόχοι:

- Ανάλυση αλγορίθμων (ορθότητα και πολυπλοκότητα)

- Μέθοδοι σχεδίασης αλγορίθμων

- Υπολογιστικά ‘δύσκολα’ προβλήματα

- Παράλληλοι και κατανεμημένοι αλγόριθμοι

Μέθοδοι Διδασκαλίας:

Διαλέξεις θεωρίας (4 ώρες/εβδομάδα) και επιπλέον φροντιστηριακά μαθήματα με επίλυση ασκήσεων (2 ώρες/ 3 εβδομάδες).

Τρόπος Εξέτασης:

Μία σειρά ασκήσεων κάθε 3 εβδομάδες, ενδιάμεση γραπτή εξέταση (πρόοδος), τελικές γραπτές εξετάσεις.

Υλικό: Σημειώσεις


Ενημέρωση: 12-Οκτ-2023                                                                                                                            email: e<lastname>@dib.uth.gr