Σύνολα γενικευμένων λύσεων στις υπολογιστικές κοινωνικές επιστήμες, κατασκευή αλγορίθμων εύρεσης των συνόλων αυτών και η πολυπλοκότητά τους
O υπολογισμός της βέλτιστης επιλογής στην Κοινωνική Επιστήμη, ουσιαστικά, μπορεί εύκολα να θεωρηθεί ως ένα πρόβλημα μεγιστοποίησης. Η διαδικασία επίλυσης ενός τέτοιους προβλήματος αποτελείται από μία συνάρτηση επιλογής, που μετατρέπει κάθε πιθανό υποσύνολο των εναλλακτικών λύσεων σε μία δυαδική συσχ...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Γλώσσα: | Greek |
| Έκδοση: |
2022
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/16024 |
| id |
nemertes-10889-16024 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-160242022-09-05T11:16:23Z Σύνολα γενικευμένων λύσεων στις υπολογιστικές κοινωνικές επιστήμες, κατασκευή αλγορίθμων εύρεσης των συνόλων αυτών και η πολυπλοκότητά τους Generalized choice sets in computational social science, development of algorithms for finding these sets and analysis of their complexity Λένης, Νικόλαος Lenis, Nikolaos Σύνολα επιλογής Κοινωνικές επιστήμες Θεωρία συνόλων Αλγόριθμοι και πολυπλοκότητα Choice sets Social science Set theory Algorithms and complexity O υπολογισμός της βέλτιστης επιλογής στην Κοινωνική Επιστήμη, ουσιαστικά, μπορεί εύκολα να θεωρηθεί ως ένα πρόβλημα μεγιστοποίησης. Η διαδικασία επίλυσης ενός τέτοιους προβλήματος αποτελείται από μία συνάρτηση επιλογής, που μετατρέπει κάθε πιθανό υποσύνολο των εναλλακτικών λύσεων σε μία δυαδική συσχέτιση. Όπως γίνεται εύκολα αντιληπτό, τα παραπάνω υποσύνολα λύσεων μπορεί να είναι κενά. Αρκετό ενδιαφέρον παρουσιάζεται σε αυτές τις περιπτώσεις, τις οποίες δεν υπάρχει προφανής λύση στο πρόβλημα μεγιστοποίησης αλλά καλούμαστε να κάνουμε μία πιο πολύπλοκη επιλογή συνόλου λύσεων. Η βιβλιογραφία για τη θεωρία της κοινωνικής επιλογής συχνά αναφέρει ότι ο κανόνας εύρεσης της κορυφαίας επιλογής είναι «πιο δύσκολο να υπολογιστεί» από οποιονδήποτε άλλο. Αυτό συμβαίνει γιατί πολλές φορές τα σύνολα λύσεων για τέτοιου είδους προβλήματα μπορεί να είναι κενά. Σε αυτή την εργασία, θα παρουσιάσουμε σύνολα λύσεων, τα οποία σε κάθε περίπτωση είναι μη κενά και θα αναλύσουμε εκτενώς ιδιότητές τους. Στην συνέχεια, θα παραθέσουμε ορισμούς από περισσότερα σύνολα και θα προσπαθήσουμε, χρησιμοποιώντας την Θεωρία Συνόλων, να συσχετίσουμε τα σύνολα αυτά μεταξύ τους. Ο κύριος στόχος αυτής της εργασίας, είναι να αναλύσει γενικευμένες λύσεις βασιζόμενες στην θεωρία της κοινωνικής επιλογής, να παρουσιάσει κάτω όρια για την υπολογιστική πολυπλοκότητα κάθε κατηγορίας συναρτήσεων επιλογής και να αναδείξει αλγόριθμους για την εύρεση κάποιων εκ των σημαντικότερων συνόλων επιλογής, καταλήγοντας, τελικά, στην προσπάθεια υλοποίησης αυτών. The process of calculating the optimal choice in Social Science, in fact, can easily be considered as a maximization problem. The process of solving such a problem consists of a selection function, which converts each possible subset of alternatives into a binary correlation. As can be easily seen, the above subsets of solutions can be empty. Quite a lot of interest arises in these cases, which there is no obvious solution to the maximization problem, but we are asked to make a more complex choice of solution set. The literature on social choice theory often states that the rule for finding the top choice is "more difficult to compute" than any other. This is because, many times, solution sets for such problems may be empty. In this paper, we will present solution sets, which in every case are non-empty, and extensively analyze their properties. Then, we will provide definitions of some extra sets and try, using the Set Theory, to correlate them to each other. The main goal of this paper, is to analyze generalized solutions based on social choice theory, to present lower bounds on the computational complexity of entire classes of choice functions, to highlight algorithms for computing some of the most important choice sets, concluding, finally, with an attempt to implement them. 2022-03-14T06:48:10Z 2022-03-14T06:48:10Z 2022-03-09 http://hdl.handle.net/10889/16024 gr application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Σύνολα επιλογής Κοινωνικές επιστήμες Θεωρία συνόλων Αλγόριθμοι και πολυπλοκότητα Choice sets Social science Set theory Algorithms and complexity |
| spellingShingle |
Σύνολα επιλογής Κοινωνικές επιστήμες Θεωρία συνόλων Αλγόριθμοι και πολυπλοκότητα Choice sets Social science Set theory Algorithms and complexity Λένης, Νικόλαος Σύνολα γενικευμένων λύσεων στις υπολογιστικές κοινωνικές επιστήμες, κατασκευή αλγορίθμων εύρεσης των συνόλων αυτών και η πολυπλοκότητά τους |
| description |
O υπολογισμός της βέλτιστης επιλογής στην Κοινωνική Επιστήμη, ουσιαστικά, μπορεί εύκολα να θεωρηθεί ως ένα πρόβλημα μεγιστοποίησης. Η διαδικασία επίλυσης ενός τέτοιους προβλήματος αποτελείται από μία συνάρτηση επιλογής, που μετατρέπει κάθε πιθανό υποσύνολο των εναλλακτικών λύσεων σε μία δυαδική συσχέτιση. Όπως γίνεται εύκολα αντιληπτό, τα παραπάνω υποσύνολα λύσεων μπορεί να είναι κενά. Αρκετό ενδιαφέρον παρουσιάζεται σε αυτές τις περιπτώσεις, τις οποίες δεν υπάρχει προφανής λύση στο πρόβλημα μεγιστοποίησης αλλά καλούμαστε να κάνουμε μία πιο πολύπλοκη επιλογή συνόλου λύσεων. Η βιβλιογραφία για τη θεωρία της κοινωνικής επιλογής συχνά αναφέρει ότι ο κανόνας εύρεσης της κορυφαίας επιλογής είναι «πιο δύσκολο να υπολογιστεί» από οποιονδήποτε άλλο. Αυτό συμβαίνει γιατί πολλές φορές τα σύνολα λύσεων για τέτοιου είδους προβλήματα μπορεί να είναι κενά. Σε αυτή την εργασία, θα παρουσιάσουμε σύνολα λύσεων, τα οποία σε κάθε περίπτωση είναι μη κενά και θα αναλύσουμε εκτενώς ιδιότητές τους. Στην συνέχεια, θα παραθέσουμε ορισμούς από περισσότερα σύνολα και θα προσπαθήσουμε, χρησιμοποιώντας την Θεωρία Συνόλων, να συσχετίσουμε τα σύνολα αυτά μεταξύ τους. Ο κύριος στόχος αυτής της εργασίας, είναι να αναλύσει γενικευμένες λύσεις βασιζόμενες στην θεωρία της κοινωνικής επιλογής, να παρουσιάσει κάτω όρια για την υπολογιστική πολυπλοκότητα κάθε κατηγορίας συναρτήσεων επιλογής και να αναδείξει αλγόριθμους για την εύρεση κάποιων εκ των σημαντικότερων συνόλων επιλογής, καταλήγοντας, τελικά, στην προσπάθεια υλοποίησης αυτών. |
| author2 |
Lenis, Nikolaos |
| author_facet |
Lenis, Nikolaos Λένης, Νικόλαος |
| author |
Λένης, Νικόλαος |
| author_sort |
Λένης, Νικόλαος |
| title |
Σύνολα γενικευμένων λύσεων στις υπολογιστικές κοινωνικές επιστήμες, κατασκευή αλγορίθμων εύρεσης των συνόλων αυτών και η πολυπλοκότητά τους |
| title_short |
Σύνολα γενικευμένων λύσεων στις υπολογιστικές κοινωνικές επιστήμες, κατασκευή αλγορίθμων εύρεσης των συνόλων αυτών και η πολυπλοκότητά τους |
| title_full |
Σύνολα γενικευμένων λύσεων στις υπολογιστικές κοινωνικές επιστήμες, κατασκευή αλγορίθμων εύρεσης των συνόλων αυτών και η πολυπλοκότητά τους |
| title_fullStr |
Σύνολα γενικευμένων λύσεων στις υπολογιστικές κοινωνικές επιστήμες, κατασκευή αλγορίθμων εύρεσης των συνόλων αυτών και η πολυπλοκότητά τους |
| title_full_unstemmed |
Σύνολα γενικευμένων λύσεων στις υπολογιστικές κοινωνικές επιστήμες, κατασκευή αλγορίθμων εύρεσης των συνόλων αυτών και η πολυπλοκότητά τους |
| title_sort |
σύνολα γενικευμένων λύσεων στις υπολογιστικές κοινωνικές επιστήμες, κατασκευή αλγορίθμων εύρεσης των συνόλων αυτών και η πολυπλοκότητά τους |
| publishDate |
2022 |
| url |
http://hdl.handle.net/10889/16024 |
| work_keys_str_mv |
AT lenēsnikolaos synolagenikeumenōnlyseōnstisypologistikeskoinōnikesepistēmeskataskeuēalgorithmōneuresēstōnsynolōnautōnkaiēpolyplokotētatous AT lenēsnikolaos generalizedchoicesetsincomputationalsocialsciencedevelopmentofalgorithmsforfindingthesesetsandanalysisoftheircomplexity |
| _version_ |
1771297210136264704 |
