δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Το παρόν έργο αποτελεί μελέτη του paper των Andreas Bjorklund, Thore Husfeldt
και Mikko Koivisto, ”Set partitioning via inclusion-exclusion”. Κύριος στόχος
κατά τη
συγγραφή ήταν να καταστούν οι έννοιες που παρουσιάζονται όσο το δυνατόν
περισσότερο
εύληπτες από προπτυχιακούς φοιτητές.
Αποδεικνύουμε την αρχή εγκλεισμού-αποκλεισμού και ορίζουμε το z-μετασχηματισμό
ενώ δίνουμε και έναν αλγόριθμο που τον υπολογίζει.
Δεδομένου ενός συνόλου N, n στοιχείων και μιας οικογένειας F υποσυνόλων του
N καθώς και ενός ακεραίου k, παρέχουμε έναν ακριβή αλγόριθμο που υπολογίζει το
πλήθος των k-κατατμήσεων σε εκθετικό χρόνο. Επίσης παρέχουμε και άλλους οι
οποίοι λύνουν παρόμοια προβλήματα όπως η καταμέτρηση των k-καλυμμάτων, η άθροιση
κατατμήσεων με βάρη και η εύρεση της πιο βαριάς κατάτμησης.
Στη συνέχεια παρέχουμε παραδείγματα προβλημάτων τα οποία ανάγονται σε αυτά
που λύσαμε παραπάνω και για τα οποία οι αναγωγές δεν απαιτούν πολύ χρόνο.
Οι προαναφερθέντες αλγόριθμοι στοχεύουν στον ελάχιστο χρόνο, με τη χωρική πολυ-
πλοκότητα να είναι εκθετική. Δεδομένου ότι την ευθύνη για αυτό φέρουν
αποκλειστικά
οι υπολογισμοί του z-μετασχηματισμού, δίνουμε εναλλακτικούς τρόπους επίλυσης των
παραπάνω χωρίς τη χρήση του z-μετασχηματισμού σε πολυωνιμικό χώρο. Το
μειονέκτημα
αυτών είναι ότι χρειάζονται περισσότερο χρόνο.
Κλείνουμε με έναν προσεγγιστικό αλγόριθμο πολυωνυμικού χώρου ο οποίος λύνει το
Πρόβλημα Χρωματικού Αριθμού Γραφήματος.
(EL)
The present work is a study of the paper by Andreas Bjorklund, Thore Husfeldt
and
Mikko Koivisto, ”Set partitioning via inclusion-exclusion”. The main aim of the
writer
was for the ideas presented to be as accessible as possible to undergraduate
students.
We prove the principle of inclusion-exclusion and define the zeta transform
while also
giving an algorithm that computes it.
Given a n element set N and a family F of subsets of N we provide an exact
algorithm
that computes the number of k-partitions in time exponential. We also provide
others
that solve similar problems like k-covers, sum of weighted partitions and
max-weighted
partition.
We then provide examples of problems which are reducible to the ones solved
above
and for which the reduction does not dominate the time complexity.
The aforementioned algorithms are optimized for time with the space complexity
being
also exponential. Considering that the responsibility for this falls squarely
on the calculations
for the z-transform, we provide alternate ways of solving the previous problems
where we substitute the z-transform by polynomial space tools with the drawback
of them
being more costly on time.
We conclude with an approximation algorithm for the Chromatic Number Problem in
polynomial space.
(EN)
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
