Τμήμα Μαθηματικών (ΔΔ)

Permanent URI for this collection

Browse

Recent Submissions

Now showing 1 - 5 of 124
  • Thumbnail Image
    Item
    Open Access
    Νέοι αλγόριθμοι για το πρόβλημα του δυικού υπεργραφήματος
    (2024-02-23) Παναγοπούλου, Αγγελική-Παναγιώτα; Panagopoulou, Angeliki-Panagiota
    Στη διατριβή αυτή μελετάται ένα σημαντικό πρόβλημα της Επιστήμης των Υπολογιστών και παρουσιάζονται νέοι αλγόριθμοι και νέα θεωρητικά αποτελέ- σματα για αυτό. Το πρόβλημα αυτό είναι ο υπολογισμός του δυικού ενός δοθέ- ντος υπεργραφήματος. Ένα υπεργράφημα ομοιάζει με ένα γράφημα κατά το ότι και τα δύο αποτελούνται από ένα σύνολο κορυφών και από ένα σύνολο ακμών, διαφέρουν όμως ως προς το ότι σε ένα γράφημα οι ακμές έχουν πληθάριθμο δύο (εδώ θεωρούμε μία ακμή σαν ένα διμελές σύνολο, το σύνολο των άκρων της), ενώ σε ένα υπεργράφημα οι ακμές έχουν αυθαίρετο πληθάριθμο (από 1 έως n, n το πλήθος των κορυφών). Για τον λόγο αυτό, στα υπεργραφήματα έχει υιοθετηθεί ο όρος υπερακμή, αντί για ακμή. Τα υπεργραφήματα χρησιμοποιούνται για τη μοντελοποίηση διαφόρων οντο- τήτων, όπως για παράδειγμα κοινοτήτων σε ένα δίκτυο, συσχετίσεων σε μία βάση δεδομένων, βιοχημικών διεργασιών και πολλών άλλων. Το δυικό ενός υπεργραφήματος, με την έννοια που χρησιμοποιείται ο όρος σε αυτήν εδώ την διατριβή, είναι και αυτό ένα υπεργράφημα με το ίδιο σύνολο κορυφών όπως το δοθέν, και με σύνολο υπερακμών το σύνολο των ελαχιστικών συνόλων τομής όλων των υπερακμών του υπεργραφήματος. Ένα σύνολο τομής, το οποίο ονομάζουμε διατέμνουσα, είναι ένα υποσύνολο των κορυφών του υπερ- γραφήματος, το οποίο έχει μη κενή τομή με όλες τις υπερακμές του υπεργραφή- ματος (hittting set ή transversal στην αγγλική βιβλιογραφία). Μία ελαχιστική δια- τέμνουσα (minimal transversal) είναι μία διατέμνουσα η οποία είναι ελαχιστική κατά το ότι η αφαίρεση οποιασδήποτε κορυφής συνεπάγεται ότι το σύνολο παύει να είναι διατέμνουσα, δηλαδή δεν έχει πλέον μη κενή τομή με τουλάχιστον μία υπερακμή. Η εύρεση του δυικού υπεργραφήματος είναι ένα σημαντικό πρόβλημα με πολλές εφαρμογές, κάποιες από τις οποίες είναι στην ουσία μία επαναδιατύ- πωση του ορισμού του. Μία σχετικά εκτενής παράθεση των εφαρμογών γίνεται σε ένα κεφάλαιο της παρούσης εργασίας, ενώ και στην βιβλιογραφία δίνονται αρκε- τές αναφορές. Ο φυσικός τρόπος με τον οποίο εμφανίζεται το πρόβλημα σε πολλές εφαρμογές ενισχύεται από μία νέα εφαρμογή την οποία παρουσιάζουμε, ανάγο- ντας τον υπολογισμό των αυτομορφισμών ενός γραφήματος (ή και τον έλεγχο του ισομορφισμού δύο γραφημάτων) στον υπολογισμό του δυικού υπεργραφήματος. Λόγω του ότι ο αλγοριθμικός υπολογισμός του δυικού υπεργραφήματος συ- νεπάγεται την εμφάνιση στην έξοδο των υπερακμών του δυικού, συνηθίζεται να χαρακτηρίζεται αυτή η διαδικασία σαν γένεση του δυικού υπεργραφήματος (Dual Hypergraph Generation - DHG). To πρόβλημα DHG, καθώς και η αποφαντική του εκδοχή, κατά την οποία δίδονται δύο υπεργραφήματα και ζητείται να απο- φασιστεί κατά πόσο είναι δυικά, εξετάζονται σε αυτήν τη διατριβή. Υπάρχουν πολλοί και αποτελεσματικοί αλγόριθμοι για τα προβλήματα αυτά, από τους οποί- ους τα καλύτερα θεωρητικά άνω φράγματα έχουν οι αλγόριθμοι των Fredman και Khachiyan (για την αποφαντική εκδοχή του προβλήματος), οι οποίοι έχουν σχεδόν πολυωνυμικό (quasi polynomial) άνω φράγμα χρόνου. Μέρος των αποτελεσμά- των της διατριβής συνίσταται στην μελέτη του αλγορίθμου Fredman-Khachiyan σε στιγμιότυπα τα οποία αναφέρονται συχνά στην βιβλιογραφία. Δείξαμε ότι για τα στιγμιότυπα αυτά ο αλγόριθμος Fredman-Khachiyan είναι πολυωνυμικός, δι- καιολογώντας έτσι την παρατηρούμενη καλή πρακτική απόδοση του αλγορίθ- μου, όπως αναφέρεται στην βιβλιογραφία. Ο αλγόριθμος Fredman-Khachiyan εί- ναι ένας αλγόριθμος «διαίρει και βασίλευε», ο οποίος προχωράει διασπώντας το πρόβλημα σε συνεχώς μικρότερα υποπροβλήματα. Πέρα από την βασική πράξη διάσπασης, προκαλείται επίσης και μία δευτερογενής μείωση του μεγέθους των υποπροβλημάτων από την απαίτηση τα υποπροβλήματα να βρίσκονται σε μία δε- δομένη μορφή (να είναι οικογένειες Sperner). Ονομάσαμε αυτές τις μειώσεις που παρατηρούνται απορροφήσεις, μελετήσαμε και χαρακτηρίσαμε τη δομή τους και τις υπολογίσαμε επακριβώς στα προαναφερθέντα στιγμιότυπα. Οι νέοι αλγόριθμοι που παρουσιάσαμε βασίζονται κυρίως στην μοντελοποί- ηση της αποφαντικής εκδοχής του προβλήματος σαν ένα πρόβλημα ικανοποιησι- μότητας ειδικής μορφής και του DHG σαν πρόβλημα παραγωγής όλων των ελα- χιστικών μοντέλων μίας πλήρως θετικής Συζευκτικής Κανονικής Μορφής. Η μο- ντελοποίηση αυτή έδωσε δύο νέους αλγορίθμους, έναν που ονομάσαμε Αλγόριθμο Ενσωμάτωσης και έναν που ονομάσαμε Αλγόριθμο Επέκτασης Υποδιατεμνουσών. Και στις δύο περιπτώσεις η κύρια μέθοδος που χρησιμοποιείται είναι η μέθοδος της Επίλυσης (Resolution). Ο αλγόριθμος ενσωμάτωσης προχωρεί παράγοντας ένα καινούριο ελαχιστικό μοντέλο και διατηρώντας ταυτόχρονα μία Συζευκτική Κανονική Μορφή, της οποίας τα ελαχιστικά μοντέλα είναι τα υπολειπόμενα. Σε όρους υπεργραφημάτων, ονομάσαμε το αντίστοιχο υπεργράφημα υπολειπόμενο δυικό υπεργράφημα. Ο αλγόριθμος επέκτασης υποδιατεμνουσών χρησιμοποιεί την έννοια της υποδιατέμνουσας (σύνολο κορυφών που μπορεί να επεκταθεί σε ελαχι- στική διατέμνουσα), διαμερίζοντας τις ελαχιστικές διατέμνουσες σε υπερσύνολα συγκεκριμένων υποδιατεμνουσών. Στην τρέχουσα μορφή του ο αλγόριθμος εν- σωμάτωσης είναι υπερπολυωνυμικός, ενώ ο αλγόριθμος επέκτασης των υποδια- τεμνουσών παράγει τις υποδιατέμνουσες που χρειάζεται σε πολυωνυμικό χώρο και έχει δυνατότητα παραλληλοποίησης στην συνέχεια. Άλλη μεγάλη κατηγορία αλγορίθμων για το πρόβλημα DHG είναι οι αλγόριθ- μοι που βασίζονται στην πολλαπλασιαστική μέθοδο. Ένας τέτοιος αλγόριθμος είναι ο αλγόριθμος των Kavvadias και Stavropoulos, τον οποίο βελτιώσαμε με τρόπο που να επιλύει πλέον πολυωνυμικά, στιγμιότυπα για τα οποία είχε υπερπολυω- νυμικό κάτω φράγμα. Παράλληλα μία άλλη απλή τροποποίηση του αλγορίθμου έδειξε μία σημαντική βελτίωση στην απόδοσή του, όπως έδειξαν πολλά πειραμα- τικά αποτελέσματα. Ασχοληθήκαμε επίσης με την πρακτική επίλυση του προβλήματος DHG βα- σιζόμενοι στην μέθοδο της Επίλυσης, για την οποία δόθηκε έμφαση στον ρυθμό αύξησης των προτάσεων, που είναι και η κύρια παράμετρος στην απόδοση αυ- τού του αλγορίθμου. Τέλος, στα ίδια πλαίσια, χρησιμοποιήθηκε ένα πρόγραμμα επίλυσης του προβλήματος της ικανοποιησιμότητας (sat-solver), το πρόγραμμα kissat, και διερευνήθηκε η κατάλληλη παραμετροποίησή του σε στιγμιότυπα του SAT προερχόμενα από το DHG.
  • Thumbnail Image
    Item
    Open Access
    Intrinsic interpretable machine learning frameworks for image classification
    (2023-01) Πιντέλας, Εμμανουήλ; Pintelas, Emmanouel
    In general, the goal of the interpretability and explainability domain in machine learning aims to provide an explanation for the predictions performed by intelligent machine models used in practical application domains. Interpretability/explainability in the machine learning field has recently become a significant problem because many real-world applications need justification and explanation for the decisions made by their ML models, even though it is essential to be able to comprehend their decision/prediction mechanism in order to trust them, particularly in critical situations. An area where explainability is extremely important is in medical applications like cancer prognosis, which is a crucial "life or death" decision dilemma. In these situations, a machine learning decision system's performance must take both accuracy and interpretation into account when assessing its effectiveness. Additionally, the European Union General Data Protection Regulation (GDPR) states that creating explainable models has become a need in real-world applications. A "right to explanation" obligation was established by the GDPR in 2018 for any automated judgments made by models using artificial intelligence. This new legislation encourages the development of algorithmic frameworks that must guarantee an explanation for each prediction made by a machine learning framework. The GDPR has legally required this demand. White box or interpretable models are those prediction modes whose decision processes are comprehensible, whereas explainable models are able to provide human-understandable justification for their decisions. These characteristics are crucial for establishing confidence in a model's predictions, especially when those predictions deal with vital issues like health, rights, security, and educational concerns. Convolutional Neural Networks (CNNs) have flourished in the machine learning and computer vision fields of image classification due to their success as highly effective image feature extractors. A CNN model is regarded as a "black box" model because the features it generates cannot be understood because they are calculated using an incredibly complex feature extraction function and have no practical human meaning. Every prediction model whose decision function is non-transparent, difficult to explain, or otherwise incapable of being understood is regarded as a black box model. The main focus of this PhD thesis is the developing of novel machine learning frameworks for image classification tasks that are trustworthy, comprehensible, and explainable. In particular, we introduced and developed new innovative Data Mining and Feature Extraction Techniques in order to build Intrinsic Interpretable/Explainable Machine Learning models for Image Recognition Applications. Our experimental results revealed the efficiency of the proposed methods.
  • Thumbnail Image
    Item
    Open Access
    Ένα ημι-περιοδικό πρόβλημα αρχικών τιμών για την εξίσωση Kadomtsev-Petviashvili II
    (2023-12-18) Καλαμβόκας, Πέτρος; Kalamvokas, Petros
    Θεωρούμε το πρόβλημα Cauchy στον κύλινδρο (S^1 x R) για την μη γραμμική μερική διαφορική εξίσωση Kadomtsev-Petviashvili II, με μία χρονική (t) και δύο χωρικές (x, y) ανεξάρτητες μεταβλητές, με περιοδικότητα στην x διεύθυνση και ελάττωση στο μηδέν στην y διεύθυνση. Λόγω της ύπαρξης ζεύγους Lax γίνεται χρήση της μεθόδου αντίστροφου φασματικού μετασχηματισμού. Για αρχικά δεδομένα με μικρές L^1 και L^2 νόρμες - υποθέτοντας και τη συνθήκη μηδενικής μάζας - το πρόβλημα αρχικών τιμών ανάγεται σε ένα πρόβλημα Riemann-Hilbert με μετατόπιση,στο σύνορο συγκεκριμένων άπειρων λωρίδων στο μιγαδικό επίπεδο της φασματικής παραμέτρου. Τα φασματικά προβλήματα, ευθύ και αντίστροφο, επιλύονται αυστηρά και αποδεικνύουμε ότι το πρόβλημα αρχικών τιμών έχει μοναδική λύση στον L^2(S^1 x R) για κάθε t μη αρνητικό, ομοιόμορφα φραγμένη για κάθε t, με την υπόθεση ότι τα αρχικά δεδομένα έχουν μικρές παραγώγους μέχρι και 8ης τάξης στους χώρους L^1(S^1 x R) και L^2(S^1 x R).
  • Thumbnail Image
    Item
    Open Access
    Μορφές ισοδυναμίας χώρων και αλγεβρών τελεστών
    (2023-09-26) Παπαπέτρος, Ευάγγελος; Papapetros, Evangelos
    Ο στόχος αυτής της διατριβής είναι η παρουσίαση και μελέτη μορφών ισοδυναμίας μεταξύ χώρων και αλγεβρών τελεστών. Ασχολούμαστε με ισοδυναμίες τύπου Morita που αντικαθιστούν την έννοια του ισομορφισμού με μια ασθενέστερη αλλά πιο ευέλικτη έννοια. Αυτή μας επιτρέπει να ταυτίζουμε άλγεβρες με ισοδύναμες κατηγορίες αναπαραστάσεων γενικεύοντας το πλαίσιο και τις έννοιες που όρισε αρχικά ο Rieffel για C*-άλγεβρες και von Neumann άλγεβρες, οι Blecher, Muhly και Paulsen για μη-αυτοσυζυγείς άλγεβρες τελεστών και αργότερα ο Ελευθεράκης για δυϊκές (και μη) άλγεβρες τελεστών και για χώρους τελεστών. Στο πρώτο μέρος της εργασίας αυτής ορίζουμε τη Δ-Morita και τη σΔ-Morita ισοδυναμία για άλγεβρες τελεστών και χώρους τελεστών. Χαρακτηρίζουμε τα Δ-ζεύγη και τα σΔ-ζεύγη μέσω των κατηγοριών των αριστερών προτύπων τους και αποδεικνύουμε ότι σΔ-Morita ισοδύναμοι χώροι τελεστών είναι ευσταθώς ισόμορφοι και αντίστροφα. Στη συνέχεια μελετούμε μια ειδική κατηγορία προτύπων υπεράνω αλγεβρών τελεστών, τα rigged modules, που αποτελούν γενίκευση της έννοιας των Hilbert modules όπως αυτή αναπτύχθηκε από τους Rieffel και Paschke. Χαρακτηρίζουμε τα rigged modules υπεράνω μιας άλγεβρας τελεστών Α που είναι ορθογώνια συμπληρώματα στην C_{oo}(A) και χρησιμοποιούμε αυτή την κατηγορία προτύπων για να ορίσουμε ισοδυναμίες τύπου Morita μεταξύ rigged modules εξετάζοντας πότε αυτές επάγουν ευσταθείς ισομορφισμούς και μεταξύ των προτύπων και μεταξύ των αλγεβρών τελεστών όπου τα πρότυπα δρουν. Μελετούμε επίσης ισοδυναμίες τύπου Morita για w*-rigged modules υπό το πρίσμα του πότε αυτές επιφέρουν ευσταθή ισομορφισμό. Στο δεύτερο μέρος της εργασίας μας, μελετούμε το ακόμα ανοιχτό πρόβλημα της ομοιότητας μορφισμών C*-αλγεβρών που εισήχθη από τον Kadison: Δοθείσης μιας μοναδιαίας C*-άλγεβρας A και ενός μοναδιαίου φραγμένου μορφισμού u: A -> B(H), όπου H είναι χώρος Hilbert, υπάρχει αντιστρέψιμος τελεστής S που ανήκει στον B(H) ώστε η απεικόνιση π(x)=S^{-1} u(x) S να ορίζει *-μορφισμό της A; Παρουσιάζουμε κάποια κριτήρια για το πότε το πρόβλημα αυτό έχει θετική απάντηση και αποδεικνύουμε ότι είναι ισοδύναμο με ένα άλλο ανοικτό πρόβλημα της Θεωρίας των C*-αλγεβρών: Κάθε υπερανακλαστική von Neumann άλγεβρα που δρα σε διαχωρίσιμο χώρο Hilbert είναι πλήρως υπερανακλαστική. Το αντίστροφο είναι αληθές. Επίσης, χρησιμοποιώντας την έννοια της υπερανακλαστικότητας των von Neumann αλγεβρών και αποδεικνύοντας σχετικά κριτήρια υπερανακλαστικότητας, δίνουμε νέα παραδείγματα von Neumann αλγεβρών που ικανοποιούν την εικασία της ομοιότητας. Τα τρία από τα τέσσερα άρθρα, των οποίων τα αποτελέσματα παρουσιάζουμε στην εργασία αυτή, έχουν ήδη δημοσιευθεί στα διεθνή περιοδικά "Integral Equations and Operator Theory (IEOT)", "New York Journal of Mathematics (NYJM)" και "Advances in Operator Theory (AIOT)". Tο 4ο έχει δημοσιευθεί στο arxiv και έχει σταλεί σε διεθνές περιοδικό προς δημοσίευση.
  • Thumbnail Image
    Item
    Open Access
    Categories of compact and compactly generated Hausdorff locales over a base topos
    (2022-12-28) Τσάμης, Κωνσταντίνος; Tsamis, Konstantinos
    This thesis is focused on the categories of compact Hausdorff locales and of compactly generated (Hausdorff) ones. Our main contributions have to do with the question of whether they share with the categories of the respective classical topological spaces the property of forming, respectively, a pretopos and a regular cartesian closed category. Locales constitute the correct substitute for topological spaces internally in toposes, where points may occur scarcely, as their existence may depend on non-constructive principles like the axiom of choice or the weaker prime ideal theorem for distributive lattices. They appear as duals of structures such as commutative rings, distributive lattices or C-algebras even when these structures lack sufficiently many prime or maximal ideals, they allow us to talk about fundamental structures like the real numbers as spaces which maintain the right properties, where their construction as Dedekind cuts or Cauchy sequence may produce nonisomorphic results in the absence of the axiom of choice. Hence we take care that all our arguments remain valid in the internal logic of a topos, meaning that we avoid using the axiom of choice or the principle of excluded middle with the sole exception of Chapter 3 which explicitly refers to categories of topological spaces. The benefits, from the point of view of classical mathematics, of such an approach are also well-known: The category of locales over a given locale is equivalent to the category of the locales internal to the topos of sheaves on the given locale, hence results about locales that are internally valid in a topos (for example our Corollary 4.2.5 and Proposition 5.1.2 in this thesis) translate to results about continuous maps over the given base. The method for developing a sufficiently rich theory of locales is algebraic. Algebraic structures have been in service of topology in various ways but we will focus on how distributive lattices and in particular frames play this role. The category of locales is by definition the one opposite to the category of frames. The latter allows us to construct categorical colimits in the category of locales (limits in the category of frames) in a simple way as in any category of algebraic structures. The main results of the thesis are presented in the last two chapters of the thesis. They include a proof that the category of compact Hausdorff locales is a pretopos and that the category of compactly generated Hausdorff locales is a regular category, provided that it is coreflective in the category of Hausdorff locales. Under the same hypothesis we show that in this category products commute with colimits, which is a necessary condition for cartesian closedness. We also investigate a possible characterization of the pretopos of compact Hausdorff locales by presenting a comparison functor from a pretopos that satisfies some extra properties to compact Hausdorff locales. This functor is faithful, full on subobjects and exact. In order to define that functor we prove first that closed quotients of compact Hausdorff locales are compact Hausdorff, generalizing the corresponding result for spaces in the localic setting. There are a few more minor results, such as an account of the functorial behaviour of the tensor product of sup-lattices, cast in terms of the concrete description of the tensor product in [24] (Propositions 1.4.1, 1.4.2). There are also new proofs of known results, primarily a proof of the regularity of the category of weakly Hausdorff compactly generated spaces (Section 2.4), and proofs in the theory of locales that use positive formulations of the involved concepts and are valid in the internal logic of a topos, where in the literature we could only find proofs involving negative formulations (for example Proposition 3.3.4). For reasons of unity and self-sufficiency of the text we have included known proofs of most known results exposed in the introductory three first chapters. We have only omitted proofs of results that are too technical and would occupy disproportionally big space in the text.