Back to search

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

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Παπαγεωργίου Γεώργιος. Αλγόριθμοι για τον υπολογισμό αραιών λύσεων αορίστων γραμμικών συστημάτων. 2012. https://pergamos.lib.uoa.gr/uoa/dl/object/1315642