Θέματα Ατομικής Διπλωματικής Εργασίας

Ακαδημαϊκό Έτος 2011/2012

Επίκουρος Καθηγητής Χρύσης Γεωργίου

Οι ενδιαφερόμενοι φοιτητές/τριες πρέπει να διαβάσουν τις πιο κάτω περιγραφές και να μου στείλουν μήνυμα στο οποίο να αναφέρεται:

o Το θέμα ή τα θέματα που τον/την ενδιαφέρουν.

o Για κάθε θέμα μια σύντομη (1-2 προτάσεις) δικαιολόγηση του ενδιαφέροντος για το συγκεκριμένο θέμα.

Δεν θα δέχομαι φοιτητές/τριες για συζήτηση θέματος διπλωματικής αν δεν έχουν πρώτα πράξει το πιο πάνω.

Θέμα 1: Υλοποίηση και Πειραματική Αξιολόγηση Αλγορίθμων Δυναμικού Κατανεμημένου Υπολογισμού με την Πλατφόρμα YALPS

Οι αυξημένες ανάγκες για πολύπλοκους υπολογισμούς όπου οι σειριακοί υπολογιστές δεν μπορούν να διεκπεραιώσουν (και η χρήση ειδικευμένων παράλληλων υπερυπολιστών αποτελεί προνόμιο για μόνο μεγάλες εταιρίες ή οργανισμούς) έχουν μετατρέψει το Διαδίκτυο ως μια από τις πιο δημοφιλείς πλατφόρμες παράλληλου υπολογισμού. Στην προσπάθεια αξιοποίησης της υπολογιστικής προοπτικής του Διαδικτυακού Υπολογισμού έχουν σχεδιαστεί και αναλυθεί εύρωστοι κατανεμημένοι αλγόριθμοι οι οποίοι είναι αποδοτικοί στην παρουσία σφαλμάτων και δυναμικών αφίξεων νέων υπολογιστικών εργασιών.

Σκοπός αυτής της διπλωματικής εργασίας είναι η υλοποίηση (σε γλώσσα προγραμματισμού Java) και η πειραματική αξιολόγηση επιλεγμένων αλγορίθμων δυναμικού κατανεμημένου υπολογισμού με τη πλατφόρμα YALPS: είναι ουσιαστικά μια βιβλιοθήκη που επιτρέπει την υλοποίηση κατανεμημένων αλγορίθμων και την προσομοίωση τους ή εκτέλεση τους σε πραγματικό υπολογιστικό περιβάλλον (χωρίς καμία αλλαγή στον κώδικα της υλοποίησης). Αυτό συνεπάγει την αυτοδίδακτη εκμάθηση αυτής της βιβλιοθήκης και την εις βάθος κατανόηση των αλγορίθμων προς υλοποίηση.

Προαπαιτούμενα: Πολύ καλή αλγοριθμική ωριμότητα και πολύ καλές προγραμματιστικές ικανότητες σε Java. (Δεν προαπαιτείται παρακολούθηση μαθήματος Παράλληλων/Κατανεμημένων Αλγορίθμων ή μαθήματος Προγραμματισμού Παράλληλων Συστημάτων, αλλά θα θεωρηθεί επιπλέον προσόν).

Θέμα 2: Προσδιορισμός και Υλοποίηση Χρονισμένων Κατανεμημένων Αλγορίθμων με το Εργαλείο Tempo/TIOA

H ΤΙΟΑ είναι μια γλώσσα προγραμματισμού και μοντελοποίησης βασισμένη στο μοντέλο Timed Input/Output Automata, και είναι ιδιαίτερα κατάλληλη για την περιγραφή και προγραμματισμό χρονισμένων κατανεμημένων αλγορίθμων, δηλαδή αλγορίθμων που η λειτουργία τους βασίζεται έως κάποιο βαθμό σε προθεσμίες-βάσει-χρόνου (timed-based timeouts). Βάσει της γλώσσας αυτής έχει αναπτυχθεί (από την VeroModo Inc) ένα πακέτο εργαλείων (Tempo) το οποίο παρέχει τη δυνατότητα προδιαγραφής, προσομοίωσης και αυτοματοποιημένης υλοποίησης χρονισμένων κατανεμημένων αλγορίθμων.

Σκοπός αυτής της διπλωματικής εργασίας είναι η εκμάθηση της γλώσσας ΤIOA και του εργαλείου Tempo και ο προσδιορισμός και η υλοποίηση επιλεγμένων χρονισμένων κατανεμημένων αλγορίθμων.

Προαπαιτούμενα: Πολύ καλή μαθηματική και αλγοριθμική ωριμότητα και πολύ καλές προγραμματιστικές ικανότητες (Δεν προαπαιτείται παρακολούθηση μαθήματος Παράλληλων/Κατανεμημένων Αλγορίθμων ή μαθήματος Προγραμματισμού Παράλληλων Συστημάτων, αλλά θα θεωρηθεί επιπλέον προσόν).

Θέμα 3: Προσομοίωση Εύρωστων Παράλληλων Αλγορίθμων στο Περιβάλλον XMT

Το PRAM είναι πιθανότατα το πιο δημοφιλή «αλγοριθμικό» μοντέλο παράλληλου υπολογισμού που επιτρέπει την σχεδίαση και ανάλυση παράλληλων αλγορίθμων. Το XMT (eXplicit Mutli-Threading) είναι ένας προσομοιωτής που επιτρέπει την εκτέλεση PRAM αλγορίθμων σε σειριακούς υπολογιστές. Ο προσομοιωτής βασίζεται σε μια απλή επέκταση της γλώσσας προγραμματισμού C (που ονομάζεται XMTC) και υποστηρίζεται από πολλά λειτουργικά συστήματα (συμπεριλαμβανομένων Linux και Windows).

Σκοπός αυτής της διπλωματικής εργασίας είναι η προσομοίωση και πειραματική αξιολόγηση επιλεγμένων εύρωστων παράλληλων αλγορίθμων χρησιμοποιώντας τον προσομοιωτή ΧΜΤ. Αυτό συνεπάγει ουσιαστικά την αυτοδίδακτη εκμάθηση της (απλής) γλώσσας XMTC και την εις βάθος κατανόηση των αλγορίθμων που θα προσομοιωθούν.

Προαπαιτούμενα: Αλγοριθμική ωριμότητα, πολύ καλές προγραμματιστικές ικανότητες σε C και βασικός χειρισμός λειτουργικού συστήματος unix/windows (ικανότητα εγκατάστασης και χρήση νέου λογισμικού). Θα δοθεί προτεραιότητα σε φοιτητές που έχουν παρακολουθήσει το μάθημα ΕΠΛ431 – Σύνθεση Παράλληλων Αλγορίθμων (όπου μελετείται σε βάθος το μοντέλο PRAM αλλά και οι εύρωστοι αλγόριθμοι που θα υλοποιηθούν), αλλά το θέμα είναι ανοικτό και σε φοιτητές που δεν πήραν το μάθημα αυτό.

Θέμα 4: Κβαντικός Υπολογισμός: Ανασκόπηση και Προοπτικές

Το τεχνολογικό υπόβαθρο των σύγχρονων υπολογιστικών συστημάτων στηρίζεται στην κλασσική μηχανική. Πολλοί επιστήμονες υποστηρίζουν ότι τα μελλοντικά υπολογιστικά συστήματα θα στηρίζονται στην Κβαντική Μηχανική (Quantum Mechanics). Οπότε τα τελευταία 10 χρόνια έχει λάβει αλματώδη ανάπτυξη η μελέτη του Κβαντικού Υπολογισμού (Quantum Computing). Αν οι εκτιμήσεις είναι ορθές και οι Κβαντικοί Υπολογιστές (Quantum Computers) υλοποιηθούν στην πράξη, τότε θα υπάρχει η δυνατότητα επίλυσης υπολογιστικών προβλημάτων σε απίστευτα μεγάλες ταχύτητες.

Σκοπός αυτής της διπλωματικής εργασίας είναι να γίνει μια εις βάθος βιβλιογραφική μελέτη του Κβαντικού Υπολογισμού. Συγκεκριμένα, θα πρέπει να γίνει μια ιστορική αναδρομή, να περιγραφούν οι κυριότερες έννοιες της περιοχής αυτής, να περιγραφή η υπάρχουσα γνώση (σε λογισμικό (αλγόριθμοι) και υλικό (αρχιτεκτονική, συστήματα κτλ)) και να αναγνωριστούν οι προοπτικές του Κβαντικού Υπολογισμού. Θα δοθεί μια αρχική βιβλιογραφία την οποία ο φοιτητής/τρια αναμένεται να εμπλουτίσει και να μελετήσει.

Προαπαιτούμενα: Καλή μαθηματική ωριμότητα και πολύ καλή γνώση αγγλικών.

Τα τρία επόμενα θέματα θα γίνουν με τη συνεπίβλεψη του Γιώργου Πάλλη (Λέκτορας, Τμήμα Πληροφορικής).

Θέμα ΓΠ-ΧΓ1: Ανεκτικότητα Σφαλμάτων σε Δίκτυα Παράδοσης Περιεχομένου

Tα Δίκτυα Παράδοσης Περιεχομένου (CDN: Content Distribution Network) είναι δίκτυα από εξυπηρετητές που βρίσκονται σε διάφορες τοποθεσίες ανά το παγκόσμιο και κρατούν αντίγραφα (replicas) από το περιεχόμενο των εξυπηρετητών του Παγκόσμιου Ιστού. Με αυτό τον τρόπο, το περιεχόμενο βρίσκεται πιο κοντά στο χρήστη μειώνοντας δραστικά την κυκλοφορία στο δίκτυο, καθώς επίσης και τους χρόνους προσπέλασης της προσφερόμενης πληροφορίας. Σε κατανεμημένα συστήματα ευρείας κλίμακας, όπως τα CDNs, η εμφάνιση ενός σφάλματος κάπου στο σύστημα είναι σχεδόν καθημερινό φαινόμενο. Συγκεκριμένα, καθώς ο αριθμός των εξυπηρετητών αυξάνεται, αυξάνεται και ο αριθμός των σφαλμάτων τους. Σε αυτό το πλαίσιο, τα CDNs οφείλουν να έχουν υψηλή ανεκτικότητα σε σφάλματα (fault tolerance).

Σκοπός αυτής της διπλωματικής εργασίας είναι να γίνει μία πλήρης βιβλιογραφική μελέτη της υπάρχουσας γνώσης για το παραπάνω πρόβλημα.

Προαπαιτούμενα: Αλγοριθμική ωριμότητα και πολύ καλή γνώση αγγλικών.

Θέμα ΓΠ-ΧΓ2: Ανάπτυξη αλγορίθμων για βελτίωση της επίδοσης των Δικτύων Παράδοσης Περιεχομένου

Tα Δίκτυα Παράδοσης Περιεχομένου (CDN: Content Distribution Network) είναι δίκτυα από εξυπηρετητές που βρίσκονται σε διάφορες τοποθεσίες ανά το παγκόσμιο και κρατούν αντίγραφα (replicas) από το περιεχόμενο των εξυπηρετητών του Παγκόσμιου Ιστού. Με αυτό τον τρόπο, το περιεχόμενο βρίσκεται πιο κοντά στο χρήστη μειώνοντας δραστικά την κυκλοφορία στο δίκτυο, καθώς επίσης και τους χρόνους προσπέλασης της προσφερόμενης πληροφορίας. Σημαντικός παράγοντας που επηρεάζει την επίδοση ενός CDN είναι η γεωγραφία των αιτήσεων των χρηστών. Θα ήταν εξαιρετικά χρήσιμο να καταλάβουμε αν μία ιστοσελίδα ή μια συλλογή από ιστοσελίδες ενός Διαδικτυακού τόπου, τα οποία αναφέρονται σε ένα συναφές θέμα και έχουν πυκνή συνδεσμολογία μεταξύ τους (Web Communities) γίνονται δημοφιλείς από μια συγκεκριμένη γεωγραφική περιοχή (δηλαδή αν οι χρήστες που ζητούν το ίδιο περιεχόμενο βρίσκονται σε κοντινή γεωγραφική περιοχή) ή σε μεγαλύτερη γεωγραφική κλίμακα. Μία δημοφιλής ιστοσελίδα/κοινότητα σε μεγάλη γεωγραφική κλίμακα θα πρέπει να αντιγραφεί σε πολλά αντίγραφα (replicas). Από την άλλη πλευρά, όταν το περιεχόμενο είναι μόνο τοπικά δημοφιλές, θα πρέπει να αποθηκεύονται προσωρινά μόνο στους CDN εξυπηρετητές όπου θα δεχτούν τα περισσότερα αιτήματα. Το σημαντικό για μια τέτοια στρατηγική είναι να μπορούμε να προβλέπουμε γρήγορα εάν μία ιστοσελίδα/κοινότητα γίνεται σε τοπικό επίπεδο δημοφιλές.

Σκοπός αυτής της διπλωματικής εργασίας είναι να αναπτυχθούν αλγόριθμοι όπου θα εντοπίζουν ιστοσελίδες που γίνονται σε τοπικό επίπεδο δημοφιλείς καθώς και θα αντιγράφουν το περιεχόμενο στους κατάλληλους CDN εξυπηρετητές. Στο τέλος θα γίνει πειραματική αξιολόγηση των αλγορίθμων αυτών.

Προαπαιτούμενα: Αλγοριθμική ωριμότητα, καλές προγραμματιστικές ικανότητες σε C και βασικός χειρισμός λειτουργικού συστήματος Unix/Windows (ικανότητα εγκατάστασης και χρήση νέου λογισμικού).

Θέμα ΓΠ-ΧΓ3: Ανάπτυξη Πληροφοριακού Συστήματος για την πιστοποίηση Τίτλων Σπουδών

Σκοπός αυτής της διπλωματικής εργασίας είναι η υλοποίηση ενός πληροφοριακού συστήματος για τη διαχείριση των αιτήσεων αναγνώρισης τίτλων σπουδών. Το λογισμικό θα είναι μία διαδικτυακή εφαρμογή και θα υλοποιηθεί με τη χρήση της PHP και της MySQL.

Προαπαιτούμενα: Καλές προγραμματιστικές ικανότητες και καλή γνώση τεχνολογίας λογισμικού.