National and Kapodistrian University of Athens
Αλγόριθμοι για τον υπολογισμό αραιών λύσεων αορίστων γραμμικών συστημάτων
Abstract
dc:descriptionΈνας σημαντικός κλάδος των Εφαρμοσμένων Μαθηματικών ο οποίος τις τελευταίες δεκαετίες γνώρισε ραγδαία ανάπτυξη και συνεχίζει να αναπτύσσεται με ακόμη γρηγορότερο ρυθμό, είναι η Θεωρία Βελτιστοποίησης. Μια ενδιαφέρουσα εφαρμογή της στον τομέα της Πληροφορικής και συγκεκριμένα στην επεξεργασία και μετάδοση σήματος, είναι η αναπαράσταση ενός σήματος το οποίο μεταφέρει πληροφορία (ήχο, εικόνα ή βίντεο) από έναν αραιό μετασχηματισμό διανύσματος. Ο αραιός μετασχηματισμός του διανύσματος χρησιμοποιείται ώστε τα δεδομένα να μεταφέρονται και να αποθηκεύονται καταλαμβάνοντας τον ελάχιστο δυνατό χώρο. Η μαθηματική διατύπωση του προβλήματος είναι πως μπορούμε να λύσουμε ένα γραμμικό σύστημα n εξισώσεων και m αγνώστων με n<m (αόριστο γραμμικό σύστημα), βρίσκοντας όμως λύσεις οι οποίες είναι αραιές. Δηλαδή, επιδιώκουμε η λύση μας να περιέχει αρκετά μηδενικά στοιχεία. Η παρούσα εργασία αποτελείται από δύο μέρη. Αρχικά ορίζουμε κατάλληλο μέτρο για το πρόβλημα βελτιστοποίησης. Δείχνουμε ότι το μέτρο αυτό αποτελεί μετρική και μάλιστα προκύπτει από τη διακριτή. Επειδή το πρόβλημα δεν είναι επιλύσιμο για οποιασδήποτε δομής πίνακα, ορίζουμε τις προϋποθέσεις κάτω υπό τις οποίες θα μπορούσε ένας πίνακας να είναι κατάλληλος. Κατόπιν ορίζουμε το πρόβλημα διαφορετικά, χρησιμοποιώντας μια κυρτή προσέγγιση του αρχικού μέτρου και εξετάζουμε πότε οι δύο μορφές του ίδιου προβλήματος είναι ισοδύναμες. Στο δεύτερο μέρος αντιμετωπίζουμε το πρόβλημα στην πράξη. Γενικά το πρόβλημα είναι επιλύσιμο με μια ποικιλία μεθόδων, εδώ εξετάζουμε τις πιο βασικές. Διατυπώνουμε το πρόβλημα στις τρεις διαφορετικές του μορφές και αναλύουμε τους αλγόριθμους τους οποίους χρησιμοποιούμε σε κάθε περίπτωση. Τέλος, ελέγχουμε κατά πόσο τα θεωρητικά αποτελέσματα επηρεάζουν τη διαδικασία επίλυσης του προβλήματος στην πράξη και ελέγχουμε την ποιότητα των αλγοριθμικών διαδικασιών, συγκρίνοντας τη μια με την άλλη.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Παπαγεωργίου Γεώργιος
Rights
- Language dc:language
- Ελληνικά, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:1315642