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

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


Χειμ. Εξάμηνο 2019-2020. Μεταπτυχιακό μάθημα.


Πρόγραμμα: Τρίτη 15.00-18.00, Εργ. 3


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

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





Ενημέρωση: 21-Σεπ-2021                                                                                                                            email: e<lastname>@dib.uth.gr