ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ ΣΤΗ ΒΙΟΛΟΓΙΑ

Περιγραφή:
Σκοπός του μαθήματος είναι η παρουσίαση βασικών αλγορίθμων και μεθόδων σχεδίασης αλγορίθμων, η εμβάθυνση στην ανάλυση ενός αλγόριθμου και η εξοικείωση με τις έννοιες της ορθότητας και της υπολογιστικής πολυπλοκότητας, η παρουσίαση της κλάσης NP και τα υπολογιστικά δύσκολα προβλήματα, η παρουσίαση της μεθόδου της πολυωνυμικής αναγωγής, η παρουσίαση του προβλήματος Protein Folding η ανάλυσή του και η παρουσίαση NP-hardness αποτελεσμάτων και προσεγγιστικών αλγόριθμων και τέλος η γνωριμία με παράλληλους και κατανεμημένους αλγόριθμους.

Μετά την επιτυχή παρακολούθηση του μαθήματος οι φοιτητές θα μπορούν:

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

Βιβλιογραφία:
1. Εισαγωγή στους Αλγόριθμους (σε έναν τόμο), T. Cormen, C. Leiserson, R. Rivest, C. Stein, Πανεπιστημιακές Εκδόσεις Κρήτης, 2012
2. Σχεδιασμός Αλγορίθμων, J. Kleinberg, E. Tardos, Εκδόσεις Κλειδάριθμος ΕΠΕ, 2009 – Αλγόριθμοι, S. Dasgupta, C. Papadimitriou, U. Vazirani, Εκδόσεις Κλειδάριθμος ΕΠΕ, 2009
3. Αλγόριθμοι και Πολυπλοκότητα, Ε. Ζάχος, Σημειώσεις, Εθνικό Μετσόβιο Πολυτεχνείο, 2007
4. Αλγόριθμοι, Π. Μποζάνης, Εκδόσεις Α. Τζιολα & Υιοί Α. Ε., 2006.
5. Ανάλυση και σχεδίαση αλγορίθμων, L. Anany, Εκδόσεις Α. Τζιολα & Υιοί Α. Ε., 2008
6. The design and Analysis of Computer Algorithms, A. Aho, J. Hopcroft, J. Ullman. Addison-Wesley Publishing Company, 1974.
7. Computers and Intractability: A Guide to the Theory of NP-Completeness, M. Garey, D. Johnson. W. H. Freeman and Company, 1979
8. Θεωρία Γραφημάτων, Α. Παπαϊωάννου, Σημειώσεις, Εθνικό Μετσόβιο Πολυτεχνείο, 2010.
9. Θεωρία και Αλγόριθμοι Γράφων, Ι. Μανωλόπουλος, Α. Παπαδόπουλος, Κ. Τσίχλας, Εκδόσεις Νέων Τεχνολογιών Μον. ΕΠΕ, 2013.
10. Εισαγωγή στους γράφους, Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης, Γ. Σταματίου, Εκδόσεις Γ. Δαρδάνος – Κ. Δαρδάνος Ο. Ε., 1999.
11. Εισαγωγή στους Αλγόριθμους Βιοπληροφορικής, N. C. Jones, P. A. Pevzner, Εκδόσεις Κλειδάριθμος ΕΠΕ, 2010.
12. Ανάλυση Βιολογικών Αλληλουχιών, R. Durbin, S. R. Eddy, A. Krogh, Gr. Mitchison, Επιστ. Επιμ. Γ. Εμίρης, Εκδόσεις Πεδίο Α. Ε., 2015.
13. Αλγόριθμοι στη Δομική Βιοπληροφορική, Γ. Εμίρης, Σημειώσεις, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών, 2015