Βελτιωμένοι αλγόριθμοι για δύσκολα προβλήματα τύπου knapsack

 
δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
κοινοποιήστε το τεκμήριο




2016 (EL)
Βελτιωμένοι αλγόριθμοι για δύσκολα προβλήματα τύπου knapsack

Παπαδοπούλου, Αναστασία Χαραλάμπους

In the present study we consider two variants of Schnorr-Shevchenko method (SS) for solving hard knapsack problems, which are in average faster than the SS method. Furthermore, we apply a variant of SS method to find small integer solutions on linear Diophantine equations and also find solutions in a specific interval. Finally, we provide an id-scheme based on the compact knapsack problem.
Στην παρούσα εργασία παραθέτουμε δυο βελτιώσεις της μεθόδου Schnorr-Shevchenko (SS), με τις οποίες λύνουμε το πρόβλημα του knapsack, και είναι γρηγορότερες κατά μέσο όρο από την αρχική μέθοδο. Επιπλέον, εφαρμόζουμε μια παραλλαγή στην ίδια μέθοδο (SS) έτσι ώστε να βρούμε μικρές ακέραιες λύσεις σε γραμμικές διοφαντικές εξισώσεις αλλά και λύσεις μέσα σε ένα συγκεκριμένο διάστημα. Τέλος, παραθέτουμε ένα σύστημα ταυτοποίησης που βασίζεται στο πρόβλημα του compact knapsack.

info:eu-repo/semantics/masterThesis
Postgraduate Thesis / Μεταπτυχιακή Εργασία

Knapsack Problem
Πλέγμα
Πρόβλημα του γυλιού
Cryptography
Κρυπτογραφία
Lattice

Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης (EL)
Aristotle University of Thessaloniki (EN)

Αρχαία ελληνική γλώσσα
Ελληνική γλώσσα

2016
2016-10-21T12:25:25Z


Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης, Σχολή Θετικών Επιστημών, Τμήμα Μαθηματικών

This record is part of 'IKEE', the Institutional Repository of Aristotle University of Thessaloniki's Library and Information Centre found at http://ikee.lib.auth.gr. Unless otherwise stated above, the record metadata were created by and belong to Aristotle University of Thessaloniki Library, Greece and are made available to the public under Creative Commons Attribution-ShareAlike 4.0 International license (http://creativecommons.org/licenses/by-sa/4.0). Unless otherwise stated in the record, the content and copyright of files and fulltext documents belong to their respective authors. Out-of-copyright content that was digitized, converted, processed, modified, etc by AUTh Library, is made available to the public under Creative Commons Attribution-ShareAlike 4.0 International license (http://creativecommons.org/licenses/by-sa/4.0). You are kindly requested to make a reference to AUTh Library and the URL of the record containing the resource whenever you make use of this material.
info:eu-repo/semantics/openAccess



*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.