|
Title: Διπλωματική εργασία σε Προγραμματισμό - Γραφήματα - Θεωρία Μητροειδών Post by: l_pitsoulis on October 10, 2014, 14:39:46 pm Αφορά φοιτητές που έχουνε πάρει το μάθημα Διακριτών Μαθηματικών, αλλά και αυτούς που ενδιαφέρονται να εκπονήσουνε διπλώματική εργασία που να συνδυάζει προγραμματισμό και αλγόριθμους σε γραφήματα.
Το θέμα της διπλωματικής είναι η ανάπτυξη και υλοποίηση ενός αλγορίθμου που περιγράφεται στο βιβλίο (http://www.springer.com/new+%26+forthcoming+titles+(default)/book/978-1-4614-8956-6 (http://www.springer.com/new+%26+forthcoming+titles+(default)/book/978-1-4614-8956-6) στην πλατφόρμα μαθηματικών αλγορίθμων Sage (http://www.sagemath.org/ (http://www.sagemath.org/)). Ο αλγόριθμος αφορά την αναγνώριση γραφικών μητροειδών. Θα δέχεται ώς δεδομένα ένα πίνακα στο δυαδικό πεδίο GF(2) και θα απαντάει στο ερώτημα εάν αυτός ο πίνακας αντιστοιχεί σε γράφημα, όπου θα το κατασκευάζει επίσης. Η διπλώματική θα περιλαμβάνει μεταξύ άλλων: -παρουσίαση της θεωρίας που σχετίζεται με το πρόβλημα -ανάπτυξη κατάλληλων δομών δεδομένων -ανάπτυξη ειδικών συναρτήσεων για πράξεις σε γραφήματα -υλοποίηση - προγραμματισμός -επέκταση σε προσημασμένα γραφικά μητροειδή (προαιρετικό) Η συγγραφή θα πρέπει να είναι σε LaTeX. Η πλατφόρμα Sage είναι βασισμένη στην python, και γρήγορα εξελίσεται σε κυρίαρχη open-source σύστημα για μαθηματικά (σε αντίθεση με τα matlab, maple, mathematica κλπ.). Υπάρχει βιβλιοθήκη για matroids αλλά δεν υπάρχει ακόμα ρουτίνα που να κάνει αναγνώριση γραφικών μητροειδών. Οπότε η υλοποίηση της προτεινόμενης διπλωματικής έχει μεγάλη πιθανότητα να γίνει μέρος της βιβλιοθήκης. Οι ενδιαφερόμενοι μπορούνε να επικοινωνήσουνε μαζί μου. Λ. Πιτσούλης |