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