Spelling suggestions: "subject:"συναρτήσεις"" "subject:"συναρτήσει""
11 |
Μελέτη των ριζών μικτών συναρτήσεων BesselΚοκολογιαννάκη-Κωνσταντοπούλου, Χρυσή 06 May 2015 (has links)
Στην παρούσα διατριβή μελετώνται οι ρίζες της συνάρτησης Mν(z), στην περίπτωση όπου οι συναρτήσεις F(z) και G(z) είναι της μορφής: y(z) = Σ ynzn-1 αναλυτικές στον μοναδιαίο δίσκο και πληρούν τη συνθήκη: Σ |yn|2 < ∞, δηλ. ανήκουν στον χώρο Hardy-Lebesgue Η2 (Δ). / --
|
12 |
Πρόβλημα και ιδιότητες σε κλάσεις καθολικών συναρτήσεωνΜεγάλου, Φωτεινή Ι. 11 September 2008 (has links)
- / -
|
13 |
Σχεδιασμός και υλοποίηση σε υλικό κρυπτογραφικών μηχανισμών με δυνατότητα ανίχνευσης σφαλμάτωνΚοτσιώλης, Απόστολος 21 March 2011 (has links)
Σκοπός της διπλωματικής εργασίας είναι ο σχεδιασμός και η υλοποίηση σε υλικό κρυπτογραφικών μηχανισμών με τέτοιο τρόπο έτσι ώστε να αποκτήσουν ιδιότητες αυτό-ελέγχου χρησιμοποιώντας μηχανισμούς ανίχνευσης σφαλμάτων. Για το σκοπό αυτό θα προσπαθήσουμε να επιλέξουμε μέσα από γνωστούς μηχανισμούς ανίχνευσης λαθών που είναι διαθέσιμοι στη βιβλιογραφία, αυτούς που θα μας βοηθήσουν να εισάγουμε στο σύστημά μας τις επιθυμητές ιδιότητες αυτό-ελέγχου λαμβάνοντας παράλληλα φροντίδα για την διατήρηση των ιδιαίτερων χαρακτηριστικών του.
Λόγω της κρισιμότητας που έχει η διαδικασία κρυπτογράφησης είναι πολύ σημαντικό να πραγματοποιείται χωρίς σφάλματα. Πιθανά σφάλματα θα μπορούσε να τα εκμεταλλευτεί κάποιος εισβολέας ώστε να διαβάσει το περιεχόμενο του μηνύματος κατά τη διάρκεια μιας μετάδοσης ή θα μπορούσαν να προκαλέσουν λάθη στο ίδιο το μήνυμα και την hash value που του αντιστοιχεί. Για αυτούς τους λόγους θα προσπαθήσουμε να εισάγουμε στην υλοποίηση του αλγόριθμου κρυπτογράφησης μηχανισμούς ανίχνευσης σφαλμάτων ώστε να διασφαλιστεί η απροβλημάτιστη λειτουργία του. Παράλληλα λόγω των ιδιαίτερων απαιτήσεων που υπάρχουν για ένα σύστημα κρυπτογράφησης που έχουν να κάνουν με ταχύτητα επεξεργασίας και την όσο το δυνατόν μικρότερη επιφάνεια ολοκλήρωσης θα λάβουμε ιδιαίτερη φροντίδα ώστε το σύστημα μας να διατηρήσει αυτά τα επιθυμητά χαρακτηριστικά. / The purpose of this thesis is the design and implementation in hardware of cryptographic mechanisms in order to gain self-checking properties using error detection techniques. In order to do so we will try to pick through known error detection mechanisms, those who will help us apply the desired self-checking characteristics to our system while taking care to maintain its characteristics.
It is critical for the encryption process to be error-free. Possible errors could be exploited by an attacker to read the contents of the message during a broadcast or could cause errors in the message itself and the hash value that corresponds. For these reasons, we try to apply error detection mechanisms to the hardware implementation of the hash algorithms in order to ensure trouble free operation. At the same time, due to the special requirements of an encryption system about high processing speed and the smallest integration area possible we will take care so as our system to maintain these desired characteristics.
|
14 |
Συναρτήσεις Mittag-LefflerΡίζος, Δημήτριος 07 April 2011 (has links)
Οι συναρτήσεις Mittag-Leffler χρησιμοποιούνται στις κλασματικές διαφορικές εξισώσεις, διότι η λύση τους εκφράζεται με τις συναρτήσεις Mittag-Leffler και γενικεύσεις αυτών.
Η εργασία αυτή αποτελεί ανασκόπηση για τις συναρτήσεις Mittag-Leffler και περιλαμβάνει εκτός από τους ορισμούς αυτών και των γενικεύσεών τους, ιδιότητες και αναδρομικές σχέσεις που ικανοποιούν. Εκφράζουμε γνωστές συναρτήσεις με τη βοήθεια των συναρτήσεων Mittag-Leffler. Βρίσκουμε το μετασχηματισμό Laplace αυτών και των γενικεύσεών τους, διότι ο μετασχηματισμός Laplace είναι μια μέθοδος επίλυσης των κλασματικών διαφορικών εξισώσεων. Τέλος, αναφέρουμε εφαρμογές και προβλήματα, που εκφράζονται μέσω κλασματικών διαφορικών εξισώσεων και δίνουμε τη λύση τους με μορφή συναρτήσεων Mittag-Leffler. / The Mittag-Leffler functions are used in fractional differential equations, because their solution is expressed with the Mittag-Leffler functions and generalizations of them.
This diploma thesis constitutes a review of the Mittag-Leffler functions and includes besides the definitions of them and their generalizations, some properties and recurrence relations that they satisfy. We express some acquaintances functions with the Mittag-Leffler functions. In addition, we calculate the Laplace transform of these functions and their generalizations, which is useful in deriving the solution of fractional differential equations. Finally, we present some applications and problems, which are expressed through fractional differential equations and we give their solution with terms of the Mittag-Leffler functions.
|
15 |
Αναδρομικές τεχνικές πυρήναΒουγιούκας, Κωνσταντίνος 03 October 2011 (has links)
Στη διπλωματική εργασία αυτή ασχοληθήκαμε με την πρόβλεψη της εξόδου μη-γραμμικών συστημάτων με τη χρήση αναδρομικών αλγορίθμων που χρησιμοποιούν συναρτήσεις πυρήνα. Παρουσιάζεται ο δικός μας αναδρομικός αλγόριθμος πρόβλεψης και βλέπουμε πως αποδίδει σε σχέση με έναν άλλο ήδη υπάρχων και ιδιαίτερα δημοφιλή αλγόριθμο.
Στο πρώτο κεφάλαιο δίνουμε μια σύντομη περιγραφή του προβλήματος που καλούμαστε να λύσουμε. Στη συνέχεια δείχνουμε πως οι συναρτήσεις πυρήνα μπορούν να χρησιμοποιηθούν για να μας βοηθήσουν να λύσουμε το πρόβλημα αυτό.
Στο δεύτερο κεφάλαιο αναλύουμε περισσότερο τις συναρτήσεις πυρήνα και τις ιδιότητες που τις χαρακτηρίζουν. Παρουσιάζουμε τα βασικά θεωρήματα και βλέπουμε πώς διαμορφώνεται το πρόβλημα της πρόβλεψης με την εφαρμογή αυτών. Επιπλέον παρουσιάζουμε πως το πρόβλημα μας μετατρέπεται στο γνωστό πρόβλημα γραμμικών ελαχίστων τετραγώνων στην περίπτωση που χρησιμοποιήσουμε γραμμικό πυρήνα.
Στο τρίτο κεφάλαιο παρουσιάζουμε τον αλγόριθμο μας, αναλύοντας το συλλογισμό που μας οδήγησε σε αυτόν. Δίνουμε επίσης μια περιγραφή ενός άλλου αλγορίθμου που χρησιμοποιείται ήδη για την επίλυση τέτοιων προβλημάτων.
Στο τέταρτο κεφάλαιο γίνονται μια σειρά από προσομοιώσεις σε MATLAB οπού βλέπουμε πόσο καλά μπορεί να κάνει την πρόβλεψη των εξόδων μη-γραμικών συστημάτων ο αλγόριθμός μας. Επίσης αντιπαραθέτουμε και την απόδοση του ανταγωνιστικού αλγορίθμου. Στα πειράματα μας εξετάζουμε το σφάλμα πρόβλεψης των προαναφερθέντων αλγορίθμων, την ταχύτητα σύγκλισης τους καθώς και την σθεναρότητα τους.
Τέλος παρουσιάζουμε τα συμπεράσματα μας εξηγώντας γιατί πιστεύουμε ότι η δικία μας προσέγγιση υπερτερεί της άλλης. / This dissertation deals with the problem of predicting the output of non-linear systems using recursive kernel methods. We will present our own prediction algorithm and see how it performs in relation to a widely used alternative algorithm.
In the first chapter we provide a short description of the problem of non-linear prediction. We then describe how kernel methods could help us solve this problem.
In the second chapter we further analyze kernel functions and their properties. We present the basic theorems and see how these affect and transform the problem at hand. Furthermore, we explain how this problem results in the linear least squares problem in case we use the linear kernel.
In the third chapter we present our algorithm and reasoning that led to it. We also describe a different algorithm that is already used to predict such signals.
In the fourth chapter we perform a series of simulations in the Matlab environment were we evaluate how well the two approaches predict the output. In this evaluation we consider the complexity, the error and robustness of the algorithms.
Finally we present our conclusion and explain why our algorithm is superior to the alternative.
|
16 |
Ιδιότητες των τροποποιημένων συναρτήσεων Bessel 1ου και 2ου είδουςΜαυρίδης, Ανδρέας 01 October 2012 (has links)
Στη παρούσα εργασία ασχοληθήκαμε με ιδιότητες μονοτονίας των Τροποποιημένων συναρτήσεων Bessel 1ου και 2ου είδους. Συγκεκριμένα ομαδοποιήσαμε ήδη υπάρχοντα φράγματα για τα κλάσματα των συναρτήσεων αυτών.
Η εύρεση φραγμάτων για τα κλάσματα των Τροποποιημένων Συναρτήσεων Bessel είναι σημαντική, λόγω της χρησιμότητάς τους σε διάφορους κλάδους των Μαθηματικών και όχι μόνο, όπως ενδεικτικά, στην Πεπερασμένη Ελαστικότητα, στην Στατιστική και στις Πιθανότητες, στην Ειδική Θεωρία Σχετικότητας, στην Μηχανική των Ρευστών, στην Ηλεκτρομηχανική, στη Βιοφυσική, στη Μαθηματική Φυσική και αλλού.
Αρχικά, στο Κεφάλαιο 1, παρατέθηκαν κάποια βασικά στοιχεία, όπως ορισμοί των συναρτήσεων Bessel 1ου και 2ου είδους (Τροποποιημένων και μη) και αναδρομικές σχέσεις που ικανοποιούν.
Στο Κεφάλαιο 2, γίνεται η καταγραφή και σύγκριση άνω και κάτω φραγμάτων για τα διάφορα κλάσματα των Τροποποιημένων συναρτήσεων Bessel 1ου είδους, καθώς και αναφορά σε ανισότητες τύπου Turán για τις συναρτήσεις αυτές. Επίσης, αναφέρεται η μεθοδολογία στην οποία στηρίχθηκε ο κάθε ερευνητής για να πάρει τα αντίστοιχα αποτελέσματα.
Στο Κεφάλαιο 3, γίνεται η αντίστοιχη διαδικασία για τα κλάσματα και εκ νέου αναφορά σε ανισότητες τύπου Turán για αυτές τις συναρτήσεις. / In this project we described properties of Modified Bessel functions of the 1st and 2nd kind. Specifically we have grouped existing bounds for the quotients of these functions. These bounds of the Modified Bessel functions is very importand and could be found in different branches of Mathematics and other sciences, such as in Finite Elasticity, in Statistics and Probability Theory, in Relativity Theory, in Fluid Mechanics, in Engineering, in Biophysics, in Mathematical Physics and so on. Firsty, in Chapter 1, we cited some basic data, such as definitions of definitions of Bessel fynctions of the 1st and 2nd kind (both simple and Modified) and recurrence relations that they satisfy. In Chapter 2, we describe upper and lower bounds of different quotients of Modified Bessel functions of the 1st kind and reference to Turán type Inequalities of those functions. Moreover, we refer to the method that each recearcher based on in order to prove the required results. In Chapter 3, we have the same process but for Modified Bessel functons of the 2nd kind as well as reference to Turán type Inequalities for the corresponding functions.
|
17 |
Βελτιστοποίηση επαναπροσδιοριζομένων αρχιτεκτονικών για απόδοση και κατανάλωση ενέργειας σε κρυπτογραφικές εφαρμογές κυριαρχούμενες από δεδομέναΜιχαήλ, Χαράλαμπος 12 April 2010 (has links)
Στη παρούσα διδακτορική διατριβή του κ. Χαράλαμπου Μιχαήλ με τίτλο «Βελτιστοποίηση Επαναπροσδιοριζόμενων Αρχιτεκτονικών για Απόδοση και Κατανάλωση Ενέργειας για Κρυπτογραφικές Εφαρμογές και Εφαρμογές Κυριαρχούμενες από Δεδομένα» προτείνονται, αναπτύσσονται και μελετώνται αποδοτικές τεχνικές βελτιστοποίησης της απόδοσης ή/και της κατανάλωσης ενέργειας για κρυπτογραφικές εφαρμογές καθώς και εφαρμογές κυριαρχούμενες από δεδομένα που υλοποιούνται σε ενσωματωμένες πλατφόρμες ειδικού σκοπού. Συνολικά, οι προτεινόμενες τεχνικές μελετήθηκαν για τις διάφορες παραμέτρους που έχουν και συνολικά οδήγησαν στην διαμόρφωση της προτεινόμενης γενικής μεθοδολογίας βελτιστοποίησης των κρυπτογραφικών και λοιπών εφαρμογών κυριαρχούμενων από δεδομένα. Τα θεωρούμενα συστήματα στοχεύουν σε αριθμητικά απαιτητικές εφαρμογές και προέκυψαν εντυπωσιακές βελτιστοποιήσεις ειδικά δε στην απόδοση συγκεκριμένων κρυπτογραφικών εφαρμογών όπως οι συναρτήσεις κατακερματισμού και ανάμειξης (hash functions) και κατά συνέπεια και των αντίστοιχων κρυπτογραφιών μηχανισμών στους οποίους αυτές χρησιμοποιούνται. Πρωταρχικός σχεδιαστικός στόχος είναι η αύξηση της ρυθμαπόδοσης σχεδιάζοντας κρυπτογραφικές εφαρμογές για διακομιστές υπηρεσιών ή γενικότερα εφαρμογές κυριαρχούμενες από δεδομένα.
Λαμβάνοντας επίσης υπόψη το γεγονός ότι η κρυπτογραφία αποτελεί σήμερα –πιο πολύ παρά ποτέ- ένα αναγκαίο και αναντικατάστατο συστατικό της ανάπτυξης ηλεκτρονικών υπηρεσιών μέσω διαδικτύου και της εν τέλει μετάβασης της ανθρωπότητας στο νέο οικονομικό μοντέλο της «ηλεκτρονικής οικονομίας» είναι προφανής η σημασία της προτεινόμενης μεθοδολογίας και των αντίστοιχων σχεδιασμών που προκύπτουν. Η ολοκλήρωση των κρυπτογραφικών συστημάτων ασφαλείας σε υλικό είναι σχεδόν αναγκαία για τα ενσωματωμένα συστήματα κρυπτογράφησης. Τα πλεονεκτήματα που έχουμε είναι η υψηλή απόδοση, η μειωμένη κατανάλωση ισχύος με μειονέκτημα το κόστος της ολοκλήρωσης σε υλικό. Νέες τεχνολογίες όπως FPGAs (Field-Programmable Gate Array), επιτρέπουν την πιο εύκολη ολοκλήρωση του αλγορίθμου και την ανανέωση - αντικατάστασή του από νεώτερους-βελτιωμένους. Ήδη τα τελευταίας γενιάς FPGAs τείνουν να έχουν τις ιδιότητες των ASICs (Application-Specific Integrated Circuit) -μειωμένη κατανάλωση ισχύος, υψηλή απόδοση, και ρύθμιση της λειτουργικότητας ανάλογα την εφαρμογή. Ένα άλλο πλεονέκτημα των υλοποιήσεων σε υλικό είναι πως από την φύση τους είναι λιγότερο ευαίσθητο σε επιθέσεις κρυπτανάλυσης ενώ μπορούν ευκολότερα να ενσωματώσουν πολιτικές αντιμετώπισης κρυπταναλυτικών τεχνικών .
Ερευνητική Συνεισφορά
Ανάπτυξη και μελέτη τεχνικών βελτιστοποίησης που οδηγούν σε σχέδια με πολύ υψηλή ρυθμαπόδοση και περιορισμένο κόστος σε επιφάνεια ολοκλήρωσης για κρυπτογραφικές και υπολογιστικά απαιτητικές εφαρμογές
Αναπτύσσονται και αναλύονται όλες οι επιμέρους τεχνικές που αξιολογήθηκαν κατά την εκπόνηση της εν λόγω διδακτορικής διατριβής και χρησιμοποιούνται για την βελτιστοποίηση των σχεδίων σε υλικό. Μελετώνται οι παράμετροι εφαρμογής ανάλογα με την υφή της κάθε τεχνικής και τα τιθέμενα σχεδιαστικά κριτήρια, τα οποία εξαρτώνται από τα επιθυμητά χαρακτηριστικά των σχεδίων σε υλικό καθώς και από τις εν γένει προδιαγραφές τους ανάλογα με τον εκάστοτε σχεδιαστικό στόχο.
Ανάπτυξη και μελέτη «πάνω-προς-τα-κάτω» μεθοδολογίας βελτιστοποίησης των σχεδίων που οδηγούν σε πολύ υψηλή ρυθμαπόδοση και περιορισμένο κόστος σε επιφάνεια ολοκλήρωσης για κρυπτογραφικές και υπολογιστικά απαιτητικές εφαρμογές
Αναπτύσσεται ολοκληρωμένη και δομημένη συνολική μεθοδολογία βελτιστοποίησης σχεδίων, με βάση τις επιμέρους τεχνικές που παρουσιάστηκαν και αναλύθηκαν, που οδηγεί σε γενική μεθοδολογία η οποία είναι εφαρμόσιμη σε όλες σχεδόν τις συναρτήσεις κατακερματισμού για τις οποίες καταφέρνει να παράγει σχέδια υψηλής απόδοσης με περιορισμένο κόστος σε επιφάνεια ολοκλήρωσης. Ταυτόχρονα, αναλύονται τα θεωρητικώς αναμενόμενα οφέλη από την κάθε επιμέρους τεχνική βελτιστοποίησης καθώς και από την συνολική εφαρμογή της μεθοδολογίας βελτιστοποίησης του σχεδιασμού σε υλικό ανάλογα με την επιλεχθείσα τιμή των παραμέτρων της κάθε εφαρμοζόμενης τεχνικής.
Ανάπτυξη σχεδίων σε υλικό πολύ υψηλής βελτιστοποίησης για τις συναρτήσεις κατακερματισμού SHA-1 και SHA-256
Παρουσιάζεται η διαδικασία βελτιστοποίησης του σχεδιασμού σε υλικό των δυο πιο σημαντικών συναρτήσεων κατακερματισμού αναφέροντας σε κάθε περίπτωση τα επιμέρους κέρδη, καθώς και την συνολική βελτίωση που επιτεύχθηκε με την εφαρμογή της προτεινόμενης μεθοδολογίας. Οι δύο συναρτήσεις είναι οι SHA-1 (η πιο δημοφιλής συνάρτηση κατακερματισμού στις σημερινές εφαρμογές) και SHA-256 (που αναμένεται να χρησιμοποιηθεί ευρύτατα στο μέλλον παρέχοντας υψηλότερο επίπεδο ασφάλειας). Υλοποιήσεις σε συγκεκριμένες επαναπροσδιοριζόμενες αρχιτεκτονικές συγκρίνονται με αντίστοιχες που έχουν προταθεί ερευνητικά ή είναι εμπορικά διαθέσιμες, αποδεικνύωντας την υπεροχή των προτεινόμενων σχεδίων. Έτσι προκύπτουν σχέδια πολύ υψηλής ρυθμαπόδοσης (τουλάχιστον 160% βελτιωμένοι σε σχέση με συμβατικές υλοποιήσεις) με περιορισμένο κόστος σε επιφάνεια ολοκλήρωσης (λιγότερο από 10% σε επίπεδο συνολικού κρυπτογραφικού συστήματος στην χειρότερη περίπτωση σε σχέση με συμβατικές υλοποιήσεις), βελτιστοποιώντας τον σχεδιαστικό παράγοντα «απόδοση x επιφάνεια ολοκλήρωσης» σε σχέση με άλλες εμπορικές ή ακαδημαϊκές υλοποιήσεις. / In this Ph.D dissertation, certain design techniques and methodologies, for various hardware platforms, aiming to boost performance of cryptographic modules and data intensive applications are presented. This way we manage to obtain hardware designs with extremely high throughput performing much better that anyone else that has been previously proposed either by academia or industry.
Taking in consideration the rapid evolution of e-commerce and the need to secure all kind of electronic transactions, it is obvious that there is a great need to achieve much higher throughputs for certain cryptographic primitives. Especially in IPv6, HMAC etc it is crucial to design hash functions that achieve the highest degree of throughput since hashing is the limiting factor in such security schemes. The proposed methodology achieves to tackle this problem achieving to offer design solutions for hashing cores that can increase their throughput up to 160%. The proposed methodology is generally applicable to all kind of hash functions and this is a main characteristic of its importance. The proposed techniques and methodologies go far beyond from just unrolling the rounds of the algorithm and/or using extended pipelining techniques. It offers an analysis on these techniques while at the same time proposes some new, which all together form a holistic methodology for designing high-throughput hardware implementations for hash functions or other data intensive applications. These designs that can achieve high throughput rates are appropriate for high-end applications that are not constrained in power consumption and chip covered area.
The main contributions of this PhD thesis involve:
Developing and study of certain optimizing techniques for increasing throughput in cryptographic primitives and data intensive applications
Certain design techniques that can take part in a generic methodology for improving hardware performance characteristics are proposed and studied. This study has been conducted in terms of each technique’s parameters and certain design criteria are mentioned in order to choose their values. These design criteria depend on the intended hardware characteristics, specifications and available hardware resources for the cryptographic primitive or data intensive application.
Developing and study of top-down methodology for increasing throughput in cryptographic primitives and data intensive applications
Techniques that were previously proposed and analyzed are merged in order to form propose a top-down methodology able to boost performance of cryptographic primitives and data intensive applications. Design parameters are studied in order to propose various design options with the default one being achieving the highest degree of throughput maintaining the best throughput/area ratio. The proposed methodology can significantly increase throughput of hardware designs leading theoretically even to 160% increase of throughput with less than 10% cost in integration area for the whole cryptographic system.
Highly optimized hardware designs for the two main hash functions: SHA-1 and SHA-256 with high-throughput properties.
In this contribution high throughput designs and implementations are proposed concerning the two most widely used hash functions SHA-1 and SHA-256. SHA-1 is currently the most widely deployed hashing function whereas SHA-256 has started to phase out SHA-1 due to security issues that have recently been reported. These two designs also serve as case studies for the application of the proposed methodology aiming to increase throughput in cryptographic modules and data intensive applications. Our implementation does not only increases throughput by a large degree, but it also utilizes limited area resources thus offering an advantageous "throughput x area" product in comparison with other hashing cores implementations, proposed either by academia or industry. The proposed design achieves maximum throughput over 4.7 Gbps for SHA-1 and over 4.4 Gbps for SHA-256 in Xilinx Virtex II platform with minor area penalty comparing to conventional implementations. These synthesis results are only slightly decreased after the place-and-route procedure
|
18 |
Ζητήματα δικαιοσύνης σε προβλήματα κατανομής αγαθών και επιμερισμού κόστουςΚυροπούλου, Μαρία 27 July 2010 (has links)
Το πρόβλημα της δίκαιης κατανομής είναι ένα πολύ σημαντικό πρόβλημα που έχει ανακύψει στον τομέα της επιστήμης των υπολογιστών και όχι μόνο. Κάποιες από τις μορφές που έχει εμφανιστεί είναι π.χ. στην κατανομή πόρων σε δίκτυα υπολογιστών, στο διακανονισμό συνόρων σε διεθνείς διαφωνίες, στο οικογενειακό δίκαιο και ως πρόβλημα της μείωσης των εκπομπών αερίων του θερμοκηπίου.
Θεωρούμε προβλήματα αναθέσεων στα οποία ένα σύνολο αγαθών είτε αγγαρειών πρέπει να ανατεθεί σε κάποιους παίκτες. Κάθε παίκτης έχει μία συνάρτηση κέρδους (κόστους) που δείχνει πόσο εκτιμά κάθε αγαθό (αγγαρεία, αντίστοιχα) και το κέρδος (κόστος) του παίκτη για κάθε πιθανό σύνολο αντικειμένων προκύπτει αθροιστικά. Στόχος του προβλήματος είναι, φυσικά, η αποδοτικότητα και η δικαιοσύνη της ανάθεσης, περιορισμοί όμως, όπως η εγωιστική συμπεριφορά των παικτών οδηγούν σε πολύ ενδιαφέρουσες παραλλαγές του προβλήματος.
Το πρώτο αποτέλεσμα της εργασίας προκύπτει από τη μελέτη του προβλήματος ανάθεσης ενός συνόλου αδιαίρετων αγαθών σε παίκτες όταν μας ενδιαφέρει να μην υπάρχει μεγάλη ζήλεια μεταξύ των παικτών. Αδιαίρετα λέγονται τα αντικείμενα που δεν μπορούν να κοπούν σε κομμάτια και πρέπει να ανατεθούν ακέραια σε κάποιο παίκτη, ενώ ζήλεια, διαισθητικά, είναι η προτίμηση που έχει κάποιος παίκτης για το σύνολο αγαθών που ανατέθηκαν σε κάποιον άλλον σε σχέση με τα αγαθά που ανατέθηκαν στον ίδιο. Όπως έχουμε αναφέρει, στην πράξη οι παίκτες έχουν εγωιστική συμπεριφορά, υπό την έννοια ότι προσπαθούν να μεγιστοποιήσουν το κέρδος τους. Για αυτό το λόγο, μπορεί να αναφέρουν εσφαλμένες συναρτήσεις κέρδους για να πετύχουν μία καλύτερη ανάθεση. Ως ειλικρινής χαρακτηρίζεται ένας μηχανισμός ανάθεσης ο οποίος εγγυάται ότι η ανάθεση των αντικειμένων βασίζεται στις σωστές συναρτήσεις κέρδους των παικτών. Υπό μία έννοια, ένας ειλικρινής μηχανισμός ανάθεσης αναγκάζει τους παίκτες να πουν την αλήθεια για τις συναρτήσεις κέρδους τους, ή αλλιώς, εγγυάται πως το κέρδος ενός παίκτη από την ανάθεση που βασίζεται σε εσφαλμένη συνάρτηση κέρδους δεν είναι μεγαλύτερο από το κέρδος που θα είχε αν η ανάθεση είχε βασιστεί στην πραγματική συνάρτηση κέρδους του, δεδομένου του ότι οι υπόλοιποι παίκτες λένε την αλήθεια.
Παρουσιάζουμε μία απλή απόδειξη ότι ειλικρινείς ντετερμινιστικοί μηχανισμοί ανάθεσης δεν ελαχιστοποιούν τη ζήλεια, χαρακτηρίζοντας τέτοιους μηχανισμούς για δύο παίκτες και δύο αντικείμενα. Συγκεκριμένα, στην απόδειξη μας φαίνεται ότι για κάθε τέτοιο ειλικρινή μηχανισμό υπάρχουν στιγμιότυπα για τα οποία η ζήλεια σχεδόν μεγιστοποιείται. Επίσης, παρουσιάζουμε μία ανάλυση για ομοιόμορφα τυχαίες αναθέσεις οι οποίες είναι ειλικρινείς μηχανισμοί κατά μέσο όρο. Τα αποτελέσματα αυτά απλοποιούν και βελτιώνουν προηγούμενα αποτελέσματα των Lipton, Markakis, Mossel και Saberi. Συγκεκριμένα, δείχνουμε ότι η ζήλεια φράσσεται εκ των άνω από την ποσότητα O(a√(m ln n)) με μεγάλη πιθανότητα, όπου a είναι το μέγιστο κέρδος για κάθε αντικείμενο για κάθε παίκτη, n είναι ο αριθμός των παικτών και m ο αριθμός των αντικειμένων. Για την περίπτωση που το κέρδος κάθε παίκτη στο σύνολο των αντικειμένων είναι 1, το φράγμα γίνεται O(√(a ln n)).
Στη συνέχεια μελετούμε την επίπτωση της δικαιοσύνης στην αποδοτικότητα των αναθέσεων. Στα ακόλουθα θα θεωρούμε ότι όντως είναι γνωστές οι πραγματικές συναρτήσεις κέρδους των παικτών. Επίσης, θεωρούμε και αναθέσεις αγγαρειών εκτός από αγαθών, καθώς επίσης και αναθέσεις διαιρετών εκτός από αδιαίρετων αντικειμένων. Ασχολούμαστε με τρείς διαφορετικές έννοιες δικαιοσύνης ανάμεσα στους παίκτες, συγκεκριμένα την αναλογικότητα, τη μη ύπαρξη ζήλειας και την ισοτιμία για αναθέσεις διαιρετών και αδιαίρετων αγαθών και αγγαρειών. Γενικά, μία ανάθεση αντικειμένων σε n παίκτες είναι αναλογική εάν σε κάθε παίκτη δίνεται η εντύπωση ότι παίρνει ένα σύνολο αντικειμένων “καλύτερο” από ποσοστό 1/n του συνόλου των αντικειμένων προς ανάθεση. Μία ανάθεση είναι χωρίς-ζήλεια εάν κάε παίκτης προτιμά όσα του έχουν ανατεθεί σε σύγκριση με το τι έχει πάρει οποιοσδήποτε άλλος παίκτης, ενώ μία ανάθεση είναι ισότιμη όταν όλοι οι παίκτες είναι εξ'ίσου ικανοποιημένοι με αυτά που τους έχουν ανατεθεί. Τέλος, μία ανάθεση είναι βέλτιστη εάν μεγιστοποιεί το κέρδος (ελαχιστοποιεί το κόστος, αντίστοιχα) του συνόλου των παικτών, δηλ. κάθε αντικείμενο ανατίθεται σε εκείνον τον παίκτη που το εκτιμά περισσότερο (του κοστίζει λιγότερο, αντίστοιχα).
Παρουσιάζουμε μία σειρά αποτελεσμάτων για το κόστος της δικαιοσύνης όσον αφορά σε κάθε μία από τις τρείς έννοιες δικαιοσύνης που αναφέρθηκαν παραπάνω, πάνω σε διαιρετά και αδιαίρετα αντικείμενα αγαθών και αγγαρειών και ποσοτικοποιούμε την απώλεια αποδοτικότητας σε δίκαιες αναθέσεις σε σύγκριση με τις βέλτιστες. Παρουσιάζουμε άνω και κάτω φράγματα για κάθε περίπτωση, τα περισσότερα από τα οποία είτε συμπίπτουν είτε απέχουν κατά σταθερούς πολλαπλασιαστικούς παράγοντες. / Fair division (or fair allocation) dates back to the ancient times and has found applications such as border settlement in international disputes, greenhouse gas emissions reduction, allocation of mineral riches in the ocean bed, inheritance, divorces, etc. In the era of the Internet, it appears regularly in distributed resource allocation and cost sharing in communication networks.
We consider allocation problems in which a set of goods or chores has to be allocated among several players. Each player has a utility (disutility) function indicating the happiness (regret) of the player if she is allocated the particular good (chore, respectively); this function is non-negative and additive. The objective of the problem is the efficiency and the fairness of the allocation, but restrictions like the selfish nature of the players lead to very interesting variants of the problem.
Our first result stems from the study of the problem where a set of indivisible items has to be allocated to some players and where allocations in which no player envies the bundle of items allocated to the other players too much are considered. Indivisibility implies that an item cannot be broken into parts and must be allocated to a single player, and envy, intuitively implies the preference of a player for the bundle of items allocated to another player compared to that of the items allocated to her. As we stated above, in practice, players are usually selfish in the sense that they aim to increase their benefit, i.e., their total utility on the bundle of items the algorithm allocates to them. In order to do so, they may report false valuations of items to the algorithm (i.e., different than their true utilities). Truthful allocation functions guarantee that the allocation is based on the true utilities of the players. In a sense, a truthful allocation function motivates the players to be truthful, or, put differently, guarantees that the benefit obtained by a player when reporting false valuations on the items is not greater than the benefit she would have obtained by telling the truth, given that the rest of the players are truthful.
We present a simple proof that deterministic truthful allocations do not minimize envy by characterizing the truthful mechanisms for two players and two items. Our proof actually shows that for any truthful allocation function, there are instances in which the envy is almost maximized. We also present an improved analysis of uniformly random allocations of m items over n players, which are truthful in expectation. We show that the envy is at most O(a√(mln n)) with high probability, where a is the maximum utility per item over all players and items. For the case where the sum of utilities of each player is 1, we prove a bound of O(√(aln n)). This improves the previous bound of O(√a n^{1/2+e}) for any e>0.
We also study the impact of fairness on the efficiency of allocations. For this part of the paper, we assume that the true utility functions of the players are public knowledge. We consider both goods and chores, as well as divisible and indivisible items. Furthermore, we consider three different notions of fairness, namely proportionality, envy-freeness, and equitability. Informally, an allocation among n players is proportional if each player has the impression that she gets a better share than a fraction of 1/n of the items to be allocated. An allocation is envy-free if no player envies some other player, whereas an allocation is equitable when all players are equally happy with their shares. Finally, an allocation is optimal when it maximizes the total utility (minimizes the total disutility, respectively) of the set of players, i.e., each item is allocated to the player that values it the most (costs her the least).
We present a series of results on the price of fairness under the three aforementioned different notions of fairness, for the cases of divisible and indivisible goods and chores, and quantify the efficiency loss in fair allocations compared to optimal ones. We present upper and lower bounds on each case, most of which are either exact or tight within constant factors.
|
19 |
Περιγραφή και μελέτη προβλημάτων συνοριακών τιμώνΠασχαλίδου, Μαρία 07 July 2010 (has links)
Σκοπός της παρούσας εργασίας είναι η ανάλυση προβλημάτων συνοριακών τιμών. Αρχικά αναφέρονται στοιχεία γραμμικής ανάλυσης και συγκεκριμένα εισάγεται η έννοια ενός τελεστή και τα είδη τελεστών που υπάρχουν, καθώς και η σημασία τους στη Φυσική. Επίσης, δίνεται ο ορισμός της διαφορικής εξίσωσης (Σ.Δ.Ε), ο ορισμός ενός προβλήματος αρχικών τιμών και ο ορισμός ενός προβλήματος συνοριακών τιμών. Έπειτα, αναλύεται η θεωρία Sturm-Liouville και περιγράφονται παραδείγματα συνοριακών τιμών τα οποία επιλύονται με αυτή. Ακόμη, μελετώνται οι συναρτήσεις Green και δίνονται παραδείγματα εφαρμογών τους. Στη συνέχεια εξάγεται η κυματική εξίσωση με τη βοήθεια του μοντέλου της ταλαντούμενης χορδής και επιλύεται με τη μέθοδο του χωρισμού των μεταβλητών για διάφορους τύπους αρχικών και συνοριακών τιμών. Κατόπιν, περιγράφονται μέθοδοι για την επίλυση προβλημάτων συνοριακών τιμών που συνδέονται με την εξίσωση της θερμότητας και μετά αναφέρονται εφαρμογές που προκύπτουν από την επίλυση προβλημάτων διάδοσης θερμότητας. Τέλος αναφέρεται η θεωρία Fredholm και η έννοια της κατανομής και δίνονται παραδείγματα λύσεων των διαφορικών εξισώσεων με την έννοια των κατανομών. Η θεωρία Fredholm είναι ιδιαίτερα σημαντική σε προβλήματα διαφορικών εξισώσεων που είναι μη ομογενή. / In the present project, the initial boundary value problems are analyzed. Firstly, elements of linear analysis are introduced. Particularly the concept of an operator and its types are introduced as well as the importance in the physics sector. Also, the definition of a differential equation and the initial boundary value problems are presented. Additionally, the theory of Sturm-Liouville and its example are described. Moreover, Green function and their applications are introduced. Furthermore, the wave equation was elicited with the basis of vibrating spring model and solved with the method of separating variables. Also with this method and by using Fourier series the heat equation was solved. Finally the theory of Fredholm and the concept of distribution are described. The theory of Fredholm is important in problems of not homogeneous differential equation problems.
|
20 |
Σχεδιασμός και υλοποίηση μηχανισμού πολλαπλών συναρτήσεων κατακερματισμού (Sha-256, Sha-512 και Multi-mode)Μάλτη, Παναγιώτα 09 January 2012 (has links)
Στην παρούσα διπλωματική εργασία θα μελετήσουμε τις διαδικασίες της κρυπτογράφησης και της αποκρυπτογράφησης. Θα αναφερθούμε στους λόγους που τις έκαναν δημοφιλείς σε πολλά πεδία εφαρμογής (μαθηματικά, εμπόριο, στρατός κ.α).
Ιδιαίτερη αναφορά θα γίνει στους κρυπτογραφικούς αλγορίθμους SHA-256 και SHA-512. Θα μελετήσουμε τη δομή τους και τον τρόπο λειτουργίας τους.
Στη συνέχεια θα μελετήσουμε πως μπορούμε σε ένα κύκλωμα να συνδυάσουμε τόσο τη λειτουργία του αλγορίθμου SHA-256, όσο και του SHA-512. Το καινούργιο αυτό κύκλωμα καλείται multi-mode.
Τέλος, θα χρησιμοποιήσουμε το Modelsim για την εξομοίωση των αλγορίθμων και το εργαλείο Xilinx ISE θα βοηθήσει στη σύνθεσή τόσο των μεμονωμένων αλγορίθμων, όσο και του multi-mode κυκλώματος. / In this diploma thesis, we will study the process of encryption and decryption. We will refer to the reasons why these processes are so popular in many fields (mathematics, trade, army, etc).
A special reference will be made in the cryptographic algorithms SHA-256 and SHA-512. We will study their structure and function.
Furthermore, we will discuss the two above mentioned algorithms can be operated in the same circuit. This is called multi-mode.
Finally, we will use Modelsim in order to compile our algorithms and Xilinx ISE for the synthesis not only for the stand-alone algorithms, but for the multi-mode circuit, as well.
|
Page generated in 0.0182 seconds