Η έννοια του αλγορίθμου και της πολυπλοκότητας. Μέθοδοι σχεδιασμού καλών αλγορίθμων: “διαίρει και κυρίευε”, δυναμικός προγραμματισμός, άπληστοι αλγόριθμοι. Εφαρμογές στη θεωρία γραφημάτων (αναζήτηση σε βάθος, αναζήτηση σε πλάτος, ελάχιστο δένδρο-σκελετός, διαδρομή ελαχίστου κόστους). Επεξεργασία δεδομένων (διάταξη και αναζήτηση). Αλγόριθμοι πολυωνυμικού χρόνου και ΝΡ-πλήρη προβλήματα. Εύκολα και δύσκολα προβλήματα συνδυαστικής βελτιστοποίησης, προβλήματα απόφασης, οι κλάσεις P και NP, προβλήματα NP-complete και αναγωγές. Το πρόβλημα Protein folding, το μοντέλο Hydrophobic-Polar, Levinthal paradox, NP-hardness αποτελέσματα και προσεγγιστικοί αλγόριθμοι. Παράλληλοι και κατανεμημένοι αλγόριθμοι.
Χειμ. Εξάμηνο 2019-2020. Μεταπτυχιακό μάθημα.
Πρόγραμμα: Τρίτη 15.00-18.00, Εργ. 3
Προαπαιτούμενες γνώσεις ή/και σχετικά μαθήματα:
Διακριτά Μαθηματικά, Αλγόριθμοι και Πολυπλοκότητα, Θεωρία Γράφων, Θεωρία Υπολογισμού, Υπολογιστική Βιολογία