Πτυχιακές εργασίες

Φοιτητές και φοιτήτριες που έχω επιβλέψει ή επιβλέπω εμφανίζονται εδώ.

Για προπτυχιακούς φοιτητές που ενδιαφέρονται να κάνουν πτυχιακή εργασία μαζί μου:

Ενδιαφέρομαι περισσότερο για την κατασκευή και την ανάλυση αλγόριθμων (δηλαδή την απόδειξη της ορθότητας του αλγόριθμου και την απόδειξη φραγμάτων υπολογιστικής πολυπλοκότητας), και την σχεδίαση και ανάλυση προσεγγιστικών αλγόριθμων (δηλαδή την απόδειξη του παράγοντα προσεγγισιμότητας), χρησιμοποιώντας μαθηματικά.

Από τα μαθήματα που έχετε παρακολουθήσει στο τμήμα μας τα πιο σχετκά με τα ενδιαφέροντά μου είναι: Διακριτά Μαθηματικά, Δομές Δεδομένων,   Αλγόριθμοι και Πολυπλοκότητα, Θεωρία Γράφων, Θεωρία Υπολογισμού. Θα πρέπει να τα έχετε πάει αρκετά καλά σε αυτά τα μαθήματα για να μπορείτε να εργαστείτε με άνεση σε κάποιο θέμα πτυχιακής εργασίας μαζί μου. Συχνά οι πτυχιακές εργασίες μπορεί να περιλαμβάνουν και την υλοποίηση ενός αλγόριθμου σε κάποια γλώσσα προγραμματισμού (και σε αυτήν την περίπτωση θα πρέπει να τα έχετε πάει καλά στα μαθήματα προγραμματισμού και να μπορείτε να προγραμματίζετε άνετα σε κάποια γλώσσα). Επιμένω όμως στο να έχετε μια καλή κατανόηση των θεμάτων με τα οποία ασχολούνται τα παραπάνω μαθήματα.

Για να πάρετε μια ιδέα των θεμάτων στα οποία θα μπορούσαμε να δουλέψουμε, δείτε τις δημοσιεύσεις μου καθώς και τις περιγραφές περιοχών (Υπολογιστική Βιολογία, Κατανεμημένοι Υπολογισμοί, Θεωρία Παιγνίων, Υπολογιστική Γεωμετρία) στις οποίες έχω ήδη δώσει πτυχιακές εργασίες τα τελευταία χρόνια. Φυσικά μπορούμε να συζητήσουμε πάνω σε αυτές τις περιοχές από κοντά.

Παρακάτω δίνω μια λίστα από πτυχιακές εργασίες που έχω επιβλέψει και έχουν ολοκληρωθεί τα τελευταία χρόνια.

  • Φρόσω Δούτση (ολοκληρώθηκε τον Ιούνιο 2012, ενώ τώρα η Φρόσω κάνει το διδακτορικό της στο University of Nice Sophia Antipolis, France): Η Φρόσω ασχολήθηκε με το εξής πρόβλημα που ανήκει στην περιοχή της υπολογιστικής βιολογίας: Δεδομένης της τρισδιάστατης δομής μιας πρωτεϊνης (δίνονται δηλαδή οι συντεταγμένες όλων των αμινοξέων της πρωτεϊνης στο χώρο) να βρεθεί εκείνη η αναδίπλωση της πρωτεϊνης σε ένα πλέγμα (lattice) ή οποία είναι πιο 'κοντά' στην αρχική εικόνα. Πιο συγκεκριμένα σκοπός της Φρόσως ήταν να βρει εκείνη την αναδίπλωση της πρωτεϊνης σε ένα δεδομένο τρισδιάστατο πλέγμα, που ελαχιστοποιεί την μέση απόκλιση των συντεταγμένων (coordinate-Root Mean Square (c-RMS) deviation) των δύο τρισδιάστατων δομών. Το πρόβλημα αυτό έχει αποδειχθεί (J. Manuch and D. Gaur, 2008) ότι είναι NP-complete για συγκεκριμένα τρισδιάστατα πλέγματα. Σχεδιάσαμε και υλοποιήσαμε (σε γλώσσα C) έναν αλγόριθμο πολυπλοκότητας  O(n^4) ο οποίος παίρνει ως είσοδο την τρισδιάστατη δομή μιας πρωτεϊνης και ένα τρισδιάστατο πλέγμα και επιστρέφει τον ορισμό ενός προβλήματος ακέραιου προγραμματισμού του οποίου η λύση θα δώσει μια βέλτιστη αναδίπλωση (δηλαδή με την ελάχιστη απόκλιση c-RMS) της πρωτεϊνης πάνω στο συγκεκριμένο πλέγμα. Στη συνέχεια λύσαμε το πρόβλημα ακέραιου προγραμματισμού χρησιμοποιώντας το εμπορικό πρόγραμμα ILOG CPLEX της IBM. Τέλος εφαρμόσαμε την παραπάνω τεχνική σε συγκεκριμένες ομάδες πρωτεϊνών (με κοινά μακροσκοπικά χαρακτηριστικά) και συγκεκριμένα πλέγματα. Τα αποτελέσματα δίνουν ενδείξεις ότι πρωτεϊνες που ανήκουν στην ίδια ομάδα αναδιπλώνονται βέλτιστα στο ίδιο πλέγμα.
  • Χρήστος Παπαγεωργάκης (ολοκληρώθηκε τον Ιανουάριο 2012, ενώ τώρα ο Χρήστος κάνει το διδακτορικό του στο INRIA Sophia Antipolis, France): Ο Χρήστος ασχολήθηκε με το πρόβλημα της ανακάλυψης σφαλμάτων σε δίκτυα χρησιμοποιώντας κινητούς πράκτορες. Το πρόβλημα αυτό ανήκει στην περιοχή των κατανεμημένων υπολογισμών. Μελετήθηκαν τα σφάλματα που μοντελοποιούνται σαν μαύρες τρύπες (οι οποίες εξαφανίζουν οποιονδήποτε πράκτορα τις επισκεφτεί). Σχεδιάσαμε νέους αλγόριθμους που λύνουν το πρόβλημα της ανακάλυψης τέτοιων σφαλμάτων σε δίκτυα-δακτύλιους χρησιμοποιώντας κινητούς πράκτορες που τρέχουν τον ίδιο ντετερμινιστικό αλγόριθμο και αρχικά είναι διασκορπισμένοι στο δίκτυο. Αποδείξαμε ότι οι αλγόριθμοί μας χρησιμοποιούν τον ελάχιστο δυνατό αριθμό πρακτόρων για το πρόβλημα. Αποδείξαμε επίσης την ορθότητα των αλγορίθμων και αναλύσαμε την πολυπλοκότητά τους. Τέλος υλοποιήσαμε (σε γλώσσα Java) ένα βασικό υπολογιστικό περιβάλλον το οποίο δέχεται παραμέτρους από το χρήστη και εκτελεί έναν από τους αλγόριθμους που σχεδιάσαμε σε τοπολογίες δακτυλίου.
  • Μωυσής Συμεωνίδης (ολοκληρώθηκε τον Ιανουάριο 2012, ενώ τώρα ο Μωυσής είναι μεταπτυχιακός φοιτητής στο Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης): Ο Μωυσής ασχολήθηκε με το πρόβλημα της συνάντησης κινητών πρακτόρων στον κόμβο ενος δικτύου. Το πρόβλημα αυτό ανήκει στην περιοχή των κατανεμημένων υπολογισμών. Πιο συγκεκριμένα ο σκοπός ήταν η σχεδίαση αλγόριθμων που οδηγούν δύο ή περισσότερους πανομοιότυπους και ασύγχρονους κινητούς πράκτορες σε συνάντηση σε έναν κόμβο ενός δικτύου τοπολογίας torus. Μελετήσαμε περιπτώσεις στις οποίες οι πράκτορες συμφωνούν πλήρως, μερικώς ή καθόλου ως προς τον προσανατολισμό του torus. Αποδείξαμε ότι σε ορισμένες περιπτώσεις η επίλυση του προβλήματος είναι αδύνατη, ενώ για τις υπόλοιπες δώσαμε ντετερμινιστικούς αλγόριθμους, αποδείξαμε την ορθότητά τους και υπολογίσαμε την πολυπλοκότητά τους. Τέλος υλοποιήσαμε (σε γλώσσα Java) ένα βασικό υπολογιστικό περιβάλλον το οποίο δέχεται παραμέτρους από το χρήστη και εκτελεί έναν από τους αλγόριθμους που σχεδιάσαμε σε τοπολογίες torus.
Ενημέρωση: 19-Ιουλίου-2017                                                                                                                            email: emarkou@ucg.gr