Μονάδα:
Κατεύθυνση Εφαρμοσμένα ΜαθηματικάΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2012-04-26
Συγγραφέας:
Παπαγεωργίου Γεώργιος
Στοιχεία επιβλεπόντων καθηγητών:
ΜΙχάλης Δρακόπουλος Επικ.Καθηγ. (Επιβλέπων), Λ. Ευαγελάτου-Δάλλα Αναπλ. Καθηγ., Σέργιος Θεοδωρίδης Καθηγ.
Πρωτότυπος Τίτλος:
Αλγόριθμοι για τον υπολογισμό αραιών λύσεων αορίστων γραμμικών συστημάτων
Γλώσσες εργασίας:
Ελληνικά
Περίληψη:
Ένας σημαντικός κλάδος των Εφαρμοσμένων Μαθηματικών ο οποίος τις τελευταίες
δεκαετίες γνώρισε ραγδαία ανάπτυξη και συνεχίζει να αναπτύσσεται με ακόμη
γρηγορότερο ρυθμό, είναι η Θεωρία Βελτιστοποίησης. Μια ενδιαφέρουσα εφαρμογή
της στον τομέα της Πληροφορικής και συγκεκριμένα στην επεξεργασία και μετάδοση
σήματος, είναι η αναπαράσταση ενός σήματος το οποίο μεταφέρει πληροφορία (ήχο,
εικόνα ή βίντεο) από έναν αραιό μετασχηματισμό διανύσματος. Ο αραιός
μετασχηματισμός του διανύσματος χρησιμοποιείται ώστε τα δεδομένα να
μεταφέρονται και να αποθηκεύονται καταλαμβάνοντας τον ελάχιστο δυνατό χώρο. Η
μαθηματική διατύπωση του προβλήματος είναι πως μπορούμε να λύσουμε ένα γραμμικό
σύστημα n εξισώσεων και m αγνώστων με nβρίσκοντας όμως λύσεις οι οποίες είναι αραιές. Δηλαδή, επιδιώκουμε η λύση μας
να περιέχει αρκετά μηδενικά στοιχεία.
Η παρούσα εργασία αποτελείται από δύο μέρη. Αρχικά ορίζουμε κατάλληλο μέτρο
για το πρόβλημα βελτιστοποίησης. Δείχνουμε ότι το μέτρο αυτό αποτελεί μετρική
και μάλιστα προκύπτει από τη διακριτή. Επειδή το πρόβλημα δεν είναι επιλύσιμο
για οποιασδήποτε δομής πίνακα, ορίζουμε τις προϋποθέσεις κάτω υπό τις οποίες θα
μπορούσε ένας πίνακας να είναι κατάλληλος. Κατόπιν ορίζουμε το πρόβλημα
διαφορετικά, χρησιμοποιώντας μια κυρτή προσέγγιση του αρχικού μέτρου και
εξετάζουμε πότε οι δύο μορφές του ίδιου προβλήματος είναι ισοδύναμες. Στο
δεύτερο μέρος αντιμετωπίζουμε το πρόβλημα στην πράξη. Γενικά το πρόβλημα είναι
επιλύσιμο με μια ποικιλία μεθόδων, εδώ εξετάζουμε τις πιο βασικές. Διατυπώνουμε
το πρόβλημα στις τρεις διαφορετικές του μορφές και αναλύουμε τους αλγόριθμους
τους οποίους χρησιμοποιούμε σε κάθε περίπτωση. Τέλος, ελέγχουμε κατά πόσο τα
θεωρητικά αποτελέσματα επηρεάζουν τη διαδικασία επίλυσης του προβλήματος στην
πράξη και ελέγχουμε την ποιότητα των αλγοριθμικών διαδικασιών, συγκρίνοντας τη
μια με την άλλη.
Λέξεις-κλειδιά:
Αραιές λύσεις, Αόριστο γραμμικό σύστημα, Αλγόριθμοι βελτιστοποίησης, Επεξεργασία σήματος, Συμπίεση δεδομένων
Αρ. σελίδων ευρετηρίου:
0
Αρ. βιβλιογραφικών αναφορών:
16
