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