Προσεγγιστικοί Αλγόριθμοι

Τύπος
Κατ' επιλογήν υποχρεωτικό
Ομάδα
Α
Περιγραφή μαθήματος

Άπληστοι προσεγγιστικοί αλγόριθμοι. Τυχαιοκρατική στρογγυλοποίηση. Η μέθοδος του πρωτεύοντος-δυϊκού. Επαναληπτική στρογγυλοποίηση. Γεωμετρικές εμβαπτίσεις. Εφαρμογές σε προβλήματα όπως: Set Cover, Steiner Tree, Sparsest Cut. Ημιορισμένος Προγραμματισμός.

Αλγόριθμοι στη Δομική Βιοπληροφορική

Τύπος
Επιλογής
Περιγραφή μαθήματος

Γονιδίωμα και πρωτεΐνες, πρωτοταγής, δευτεροταγής και τριτοταγής μοριακή δομή. Πειραματικά δεδομένα NMR και κρυσταλλογραφίας ακτίνων Χ. Σύγκριση και στοίχιση ακολουθιών, στοίχιση με κενά. Δυναμικός προγραμματισμός. Αναζήτηση και χώρος μοριακών διαμορφώσεων (C-space). Γεωμετρία των αποστάσεων. Κινηματική των μορίων, Ευκλείδειοι μετασχηματισμοί Ομοιότητες και αναγνώριση μοριακών δομών, πρόσδεση (docking) μορίου σε υποδοχέα: μοριακές επιφάνειες (α-σχήματα, τριγωνοποίηση Delaunay), δομές γεωμετρικών δεδομένων, γεωμετρικός κατακερματισμός Εξόρυξη δεδομένων, αναζήτηση και συσταδοποίηση μοριακών δεδομένων.

Αλγόριθμοι

Τύπος
Υποχρεωτικό
Περιγραφή μαθήματος

Τεχνικές για ασυμπτωτική εκτίμηση υπολογιστικής πολυπλοκότητας, κριτήρια για επιλογή αλγορίθμων, πολυωνυμικοί αλγόριθμοι. Ουρές προτεραιότητας, σωροί, διαχείριση ξένων συνόλων, union-find. Επεξεργασία δεδομένων (ταξινόμηση, επιλογή, αναζήτηση). Μέθοδοι σχεδιασμού αποδοτικών αλγορίθμων: «διαίρει και βασίλευε», άπληστοι αλγόριθμοι, δυναμικός προγραμματισμός. Εφαρμογές σε προβλήματα γραφημάτων: αναζήτηση κατά βάθος, αναζήτηση κατά πλάτος, ελάχιστο συνδετικό δένδρο, συντομότερα μονοπάτια, μέγιστη ροή και ελάχιστη τομή. Πιθανοτικοί και προσεγγιστικοί αλγόριθμοι. Υπολογισιμότητα και πολυπλοκότητα. Κλάσεις υπολογιστικής πολυπλοκότητας και αναγωγές. Οι κλάσεις P και NP, NP-πλήρη προβλήματα. Κλάσεις χωρικής πολυπλοκότητας. Μαντεία και ιεραρχίες.

ΑΛΜΑ

Το ΑΛΜΑ είναι ένα Μεταπτυχιακό Πρόγραμμα Ειδίκευσης στις περιοχές των Αλγορίθμων, της Λογικής, και των Διακριτών Μαθηματικών. Το πρόγραμμα συνδιοργανώνεται από το Τμήμα Πληροφορικής και Τηλεπικοινωνιών και από το Τμήμα Μαθηματικών, του Εθνικού και Καποδιστριακού Πανεπιστημίου Αθηνών, καθώς επίσης και από τη Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών και τη Σχολή Εφαρμοσμένων Μαθηματικών και Φυσικών Επιστημών, του Εθνικού Μετσόβιου Πολυτεχνείου.