Θέμα: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η

[gpapargi]

Δε νομίζω να υπάρχει κάποιος που να θεωρεί ότι ο παρακάτω αλγόριθμος έχει γραμμική πολυπλοκότητα. Αφού μετράμε την πολυπλοκότητα συναρτήσει του μεγέθους της εισόδου, και εδώ η είσοδος είναι ο αριθμός ν, και το μέγεθος του ν είναι το πλήθος των ψηφίων του, ως προς το πλήθος των ψηφίων του ν ο συγκεκριμένος αλγόριθμος έχει εκθετική πολυπλοκότητα. Δε νομίζω να διαφωνεί κάποιος, αφού είναι γνωστό το θέμα τέτοιων αλγορίθμων (όπως ο brute force για τον έλεγχο πρώτου, ο αλγόριθμος δυναμικού προγραμματισμού για το knapsack), που τους χαρακτηρίζουν ψευδοπολυωνυμικούς γιατί είναι πολυωνυμικοί ως προς την αριθμητική τιμή της εισόδου, άρα είναι εκθετικοί ως προς το μέγεθος της εισόδου.

Διάβασε ν
Για ι από 1 μέχρι ν
  Γράψε ι
Τέλος_επανάληψης

ether συμφωνούμε σε όλα.
Το ερώτημα για μένα που πρέπει να συζητήσουμε είναι το πότε επιτρέπεται να κάνουμε αλλαγή ανεξάρτητης μεταβλητής και να μην βρίσκουμε την πολυπλοκότητα συναρτήσει των bits εισόδου, αλλά συναρτήσει κάποια άλλης μεταβλητής.
Κατά τη γνώμη μου επιτρέπεται  όταν απλά πολλαπλασιάζεις την είσοδο με μια σταθερά πχ αντί για bits μετράς χαρακτήρες. Δεν πρόκειται αυτά να αλλάξει την τάξη του αλγορίθμου. Δεν επιτρέπεται όταν αλλάζεις την τάξη από πολυωνυμική σε εκθετική και ανάποδα. Το ερώτημα είναι: επιτρέπεται το να αλλάξεις από πολυωνυμική κάποιου βαθμού σε πολυωνυμική άλλου βαθμού (όπως κάνει το τετράδιο μαθητή στο παράδειγμα το ν σε ν^2); Ποια είναι τα όρια ανοχής;

Επίσης μια ερώτηση προς ether για να δούμε με ποια άποψη συμφωνείς ως προς την είσοδο: Ο παρακάτω αλγόριθμος έχει είσοδο;
Για ι από 1 ως 100
Γράψε ι
Τέλος_επανάληψης
Δηλαδή δεν έχω διάβασε. Έχει είσοδο ή όχι;

[ether]

Οπότε λοιπόν εαν κάποιος κάνει την εύλογη ερώτηση με τον αλγόριθμο που έγραψες, τι του απαντάμε; Υπάρχει για μας η ψευδο-πολυωνυμική πολυπλοκότητα; Εγώ ειλικρινά δεν καταλαβαίνω γιατί αυτό το κεφαλαίο μπήκε στην ύλη.

Θα μπορούσαμε να δώσουμε διαφορετική απάντηση από αυτή που αναφέρεται στη σχετική βιβλιογραφία;
Όταν λες αν υπάρχει για εμάς η ψευδοπολυωνυμική πολυπλοκότητα, που ουσιαστικά είναι εκθετική ως προς το μέγεθος της εισόδου, τι εννοείς, στα πλαίσια της ΑΕΠΠ; Θεωρώ ότι είναι κάτι που δεν πρέπει να απασχολεί εμάς και τους μαθητές στα πλαίσια της ΑΕΠΠ και ούτε κι εγώ καταλαβαίνω γιατί μπήκε στην ύλη το συγκεκριμένο κεφάλαιο. Είναι κακογραμμένο, αλλά ακόμα και καλογραμμένο να ήταν θεωρώ ότι δε θα έπρεπε να αποτελεί αντικείμενο εξέτασης.

[ether]

ether συμφωνούμε σε όλα.
Το ερώτημα για μένα που πρέπει να συζητήσουμε είναι το πότε επιτρέπεται να κάνουμε αλλαγή ανεξάρτητης μεταβλητής και να μην βρίσκουμε την πολυπλοκότητα συναρτήσει των bits εισόδου, αλλά συναρτήσει κάποια άλλης μεταβλητής.
Κατά τη γνώμη μου επιτρέπεται  όταν απλά πολλαπλασιάζεις την είσοδο με μια σταθερά πχ αντί για bits μετράς χαρακτήρες. Δεν πρόκειται αυτά να αλλάξει την τάξη του αλγορίθμου. Δεν επιτρέπεται όταν αλλάζεις την τάξη από πολυωνυμική σε εκθετική και ανάποδα. Το ερώτημα είναι: επιτρέπεται το να αλλάξεις από πολυωνυμική κάποιου βαθμού σε πολυωνυμική άλλου βαθμού (όπως κάνει το τετράδιο μαθητή στο παράδειγμα το ν σε ν^2); Ποια είναι τα όρια ανοχής;

Επίσης μια ερώτηση προς ether για να δούμε με ποια άποψη συμφωνείς ως προς την είσοδο: Ο παρακάτω αλγόριθμος έχει είσοδο;
Για ι από 1 ως 100
Γράψε ι
Τέλος_επανάληψης
Δηλαδή δεν έχω διάβασε. Έχει είσοδο ή όχι;

Στο CLRS (3rd edition, p. 25) αναφέρει:
The best notion for input size depends on the problem being studied. For many problems, such as sorting or computing discrete Fourier transforms, the most natural measure is the number of items in the input—for example, the array size n for sorting. For many other problems, such as multiplying two integers, the best measure of input size is the total number of bits needed to represent the input in ordinary binary notation. Sometimes, it is more appropriate to describe the size of the input with two numbers rather than one. For instance, if the input to an algorithm is a graph, the input size can be described by the numbers of vertices and edges in the graph. We shall indicate which input size measure is being used with each problem we study

Ο αλγόριθμος που έδωσες παραπάνω, αν κάθε φορά τον τρέχεις έτσι όπως είναι, χωρίς να αλλάξεις τις τιμές ΑΠΟ ΜΕΧΡΙ, έχει πολυπλοκότητα Ο(1) ως προς οποιαδήποτε είσοδο, γιατί οποιαδήποτε είσοδο κι αν του δώσεις την αγνοεί και εκτελεί πάντοτε τον συγκεκριμένο αριθμό εντολών.

Σχετικά με το παράδειγμα 2 του κεφ. 5 του τετραδίου μαθητή, προφανώς ως προς το πλήθος των στοιχείων του πίνακα (n^2) η πολυπλοκότητα του αλγορίθμου είναι γραμμική.
Αν υποθέσουμε όμως ότι ο πίνακας αυτός είναι ο πίνακας γειτνίασης ενός γράφου n κόμβων, τότε ενδεχομένως θα μας ενδιέφερε να μετρήσουμε την πολυπλοκότητα συναρτήσει του πλήθους των κόμβων n και να πούμε π.χ. ότι με το συγκεκριμένο τρόπο αναπαράστασης (πίνακας γειτνίασης), η πολυπλοκότητα εμφάνισης όλων των ακμών είναι O(n^2). Όπως λέει λοιπόν και το CLRS, η έννοια του μεγέθους εισόδου εξαρτάται από το πρόβλημα και θα πρέπει να αναφέρεται.

[gpapargi]

Μια μικρή παρένθεση ως προς το αν έπρεπε να μπει ή όχι το κεφάλαιο 5 στην ύλη:
Πιο παλιά, έβλεπες εύρεση μεγίστου σε πίνακα με πλήρη ταξινόμηση. Σε κανέναν δεν άρεσε, αλλά κανείς δεν μπορούσε να κάνει τίποτα. Σου έλεγαν «μετράει μόνο το σωστό αποτέλεσμα» και «η πολυπλοκότητα είναι εκτός ύλης». Έπρεπε να βρεθεί ένα πλαίσιο για να μη δεχόμαστε σαν σωστούς εντελώς απαράδεκτους αλγορίθμους. Το κεφάλαιο 5 δίνει ένα τέτοιο πλαίσιο. Θα συζητήσουμε και θα ξεδιαλύνουμε τις λεπτομέρειες, δεν είναι η πρώτη φορά που γίνεται αυτό. Ίσα ίσα που το στέκι δείχνει να ξαναβρίσκει τον παλιό καλό του εαυτό που οι επιστημονικές  παιδαγωγικές συζητήσεις ήταν καθημερινότητα.   

[gpapargi]

Στο CLRS (3rd edition, p. 25) αναφέρει:
The best notion for input size depends on the problem being studied. For many problems, such as sorting or computing discrete Fourier transforms, the most natural measure is the number of items in the input—for example, the array size n for sorting. For many other problems, such as multiplying two integers, the best measure of input size is the total number of bits needed to represent the input in ordinary binary notation. Sometimes, it is more appropriate to describe the size of the input with two numbers rather than one. For instance, if the input to an algorithm is a graph, the input size can be described by the numbers of vertices and edges in the graph. We shall indicate which input size measure is being used with each problem we study

Ο αλγόριθμος που έδωσες παραπάνω, αν κάθε φορά τον τρέχεις έτσι όπως είναι, χωρίς να αλλάξεις τις τιμές ΑΠΟ ΜΕΧΡΙ, έχει πολυπλοκότητα Ο(1) ως προς οποιαδήποτε είσοδο, γιατί οποιαδήποτε είσοδο κι αν του δώσεις την αγνοεί και εκτελεί πάντοτε τον συγκεκριμένο αριθμό εντολών.

Σχετικά με το παράδειγμα 2 του κεφ. 5 του τετραδίου μαθητή, προφανώς ως προς το πλήθος των στοιχείων του πίνακα (n^2) η πολυπλοκότητα του αλγορίθμου είναι γραμμική.
Αν υποθέσουμε όμως ότι ο πίνακας αυτός είναι ο πίνακας γειτνίασης ενός γράφου n κόμβων, τότε ενδεχομένως θα μας ενδιέφερε να μετρήσουμε την πολυπλοκότητα συναρτήσει του πλήθους των κόμβων n και να πούμε π.χ. ότι με το συγκεκριμένο τρόπο αναπαράστασης (πίνακας γειτνίασης), η πολυπλοκότητα εμφάνισης όλων των ακμών είναι O(n^2). Όπως λέει λοιπόν και το CLRS, η έννοια του μεγέθους εισόδου εξαρτάται από το πρόβλημα και θα πρέπει να αναφέρεται.

Σύμφωνα με την άποψη που διατυπώνεις ether (διόρθωσέ με αν κατάλαβα λάθος) και πηγάζει από το CLR, το να δεις τον κώδικα (χωρίς εκφώνηση) στο παράδειγμα του τετραδίου μαθητή, δε σημαίνει τίποτα για την επιλογή της μεταβλητής ως προς την οποία θα υπολογίσουμε την πολυπλοκότητα. Τη μεταβλητή την επιλέγουμε με βάση τη φυσική σημασία του κώδικα και προέρχεται από την εκφώνηση. Έχουμε το δικαίωμα να επιλέξουμε ανεξάρτητη μεταβλητή και να φτιάξουμε τη συνάρτηση.
Γενικά δηλαδή ο κώδικας δεν καθορίζει τη μεταβλητή. Η εκφώνηση (=φυσική σημασία) την καθορίζει.

[gpapargi]

Γράφω ένα σχόλιο στην παραπάνω άποψη. Αν έχεις πίνακα γειτνίασης γράφου, η αύξηση των κόμβων κατά 1 σημαίνει  αύξηση των κελιών κατά 2ν+1=(ν+1)^2 - ν^2. Δε γίνεται να αυξήσεις τα κελιά του πίνακα κατά 1, αλλά μόνο κατά 2ν+1. Πάλι γραμμική είναι η πολυπλοκότητα ως προς το μέγεθος εισόδου. Το θέμα είναι αν μπορείς να ονομάσεις μέγεθος εισόδου το πλήθος των κόμβων τη στιγμή που κάθε νέος κόμβος σημαίνει αύξηση κατά μεταβλητό (2ν+1)πλήθος κελιών κάθε φορά. Αν θέλεις την πολυπλοκότητα συναρτήσει του ν φυσικά γίνεται. 

[ether]

Σύμφωνα με την άποψη που διατυπώνεις ether (διόρθωσέ με αν κατάλαβα λάθος) και πηγάζει από το CLR, το να δεις τον κώδικα (χωρίς εκφώνηση) στο παράδειγμα του τετραδίου μαθητή, δε σημαίνει τίποτα για την επιλογή της μεταβλητής ως προς την οποία θα υπολογίσουμε την πολυπλοκότητα. Τη μεταβλητή την επιλέγουμε με βάση τη φυσική σημασία του κώδικα και προέρχεται από την εκφώνηση. Έχουμε το δικαίωμα να επιλέξουμε ανεξάρτητη μεταβλητή και να φτιάξουμε τη συνάρτηση.
Γενικά δηλαδή ο κώδικας δεν καθορίζει τη μεταβλητή. Η εκφώνηση (=φυσική σημασία) την καθορίζει.

Ο προφανής αλγόριθμος που υπολογίζει το άθροισμα δυο τετραγωνικών πινάκων ΝxN έχει τετραγωνική πολυπλοκότητα ως προς το Ν.
Ο αλγόριθμος της φυσσαλίδας για την ταξινόμηση ενός πίνακα Ν στοιχείων έχει επίσης τετραγωνική πολυπλοκότητα ως προς το Ν.
Και οι δύο έχουν διπλό εμφωλευμένο βρόχο (ίδιας τάξης πολυπλοκότητας).
Ο πρώτος έχει γραμμική πολυπλοκότητα ως προς το μέγεθος εισόδου και είναι βέλτιστος για το συγκεκριμένο πρόβλημα.
Ο δεύτερος έχει τετραγωνική πολυπλοκότητα ως προς το μέγεθος εισόδου και δεν είναι βέλτιστος για το συγκεκριμένο πρόβλημα.

Ο προφανής αλγόριθμος που υπολογίζει το άθροισμα των στοιχείων ενός πίνακα ΝxΜ έχει πολυπλοκότητα Ο(NM).
Ο κλασσικός αλγόριθμος δυναμικού προγραμματισμού για το 0/1 knapsack για N αντικείμενα με μέγιστο βάρος M έχει πολυπλοκότητα επίσης Ο(NM).
Και οι δύο έχουν διπλό εμφωλευμένο βρόχο (ίδιας τάξης πολυπλοκότητας).
Ο πρώτος έχει γραμμική πολυπλοκότητα ως προς το μέγεθος εισόδου και είναι βέλτιστος για το συγκεκριμένο πρόβλημα.
Ο δεύτερος έχει εκθετική πολυπλοκότητα ως προς το μέγεθος εισόδου (αν είχε γραμμική θα σήμαινε ότι P=NP οπότε θα ήμασταν (; ) όλοι χαρούμενοι) και δεν ξέρουμε αν είναι βέλτιστος για το συγκεκριμένο πρόβλημα (είναι πολύ πιθανό να είναι, παρόλο που ευχόμαστε (; ) να μην είναι)

[ether]

Γράφω ένα σχόλιο στην παραπάνω άποψη. Αν έχεις πίνακα γειτνίασης γράφου, η αύξηση των κόμβων κατά 1 σημαίνει  αύξηση των κελιών κατά 2ν+1=(ν+1)^2 - ν^2. Δε γίνεται να αυξήσεις τα κελιά του πίνακα κατά 1, αλλά μόνο κατά 2ν+1. Πάλι γραμμική είναι η πολυπλοκότητα ως προς το μέγεθος εισόδου. Το θέμα είναι αν μπορείς να ονομάσεις μέγεθος εισόδου το πλήθος των κόμβων τη στιγμή που κάθε νέος κόμβος σημαίνει αύξηση κατά μεταβλητό (2ν+1)πλήθος κελιών κάθε φορά. Αν θέλεις την πολυπλοκότητα συναρτήσει του ν φυσικά γίνεται.

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

Προφανώς και δεν μπορείς να ονομάσεις ως μέγεθος εισόδου του αλγορίθμου το πλήθος των κόμβων. Το μέγεθος εισόδου σε έναν αλγόριθμο επεξεργασίας γραφήματος με N κόμβους και M ακμές συνήθως μας βολεύει να το θεωρούμε Ν+Μ.
Επομένως, γραμμικοί θεωρούνται οι αλγόριθμοι επεξεργασίας γραφημάτων με πολυπλοκότητα Ο(Ν+Μ).
Συνήθως είσοδος στους αλγορίθμους αυτούς δεν είναι ο πίνακας γειτνίασης αλλά οι κόμβοι και οι ακμές.
Αν λοιπόν από τους Ν κόμβους πάω στους Ν+1, οπότε ο πίνακας γειτνίασης θα αυξηθεί όσο ανέφερες, δε σημαίνει ότι και η είσοδος θα έχει αυξηθεί τόσο. Αν π.χ. ο κόμβος που πρόσθεσα δεν έχει καμία ακμή, τότε το μέγεθος της εισόδου αυξήθηκε απλά κατά ένα.

[gpapargi]

Εντάξει συμφωνώ σε αυτά. Εμένα το πρόβλημα που με απασχολεί είναι το εξής:
Το μέγεθος της εισόδου τυπικά μετριέται στο πλήθος των bits εισόδου. Μπορώ επίσης να χρησιμοποιήσω κάποια άλλη μεταβλητή που να συνδέεται με το πλήθος των bits με κάποια πολλαπλασιαστική σταθερά πχ πλήθος χαρακτήρων. Το ερώτημα είναι: μπορώ να χρησιμοποιήσω κάποια άλλη μεταβλητή επειδή θέλω ή επειδή με βολεύει; Μπορώ πχ να πω ότι στον αλγόριθμο
Διάβασε ν
Για ι από 1 μέχρι ν
  Γράψε ι
Τέλος_επανάληψης
χρησιμοποιώ σαν μεταβλητή τον αριθμό εισόδου ν και έχω πολυπλοκότητα γραμμική ως προς ν ή είμαι παράτυπος;
Μπορώ πχ να εξηγήσω γιατί αν ταξινομώ πίνακες με αριθμούς χρησιμοποιώντας το πλήθος των αριθμών και όχι τα ψηφία τους έχω μεταβλητή πολλαπλασιασμένη με το πλήθος των bits εισόδου, αλλά τι γίνεται με το παράδειγμα που δίνω; Έχω δικαίωμα να εκφράσω πολυπλοκότητα ως προς ν αλλάζοντας την τάξη από εκθετική ως προς τα bits σε πολυωνυμική ως προς ν ή όχι;

[ether]

Εντάξει συμφωνώ σε αυτά. Εμένα το πρόβλημα που με απασχολεί είναι το εξής:
Το μέγεθος της εισόδου τυπικά μετριέται στο πλήθος των bits εισόδου. Μπορώ επίσης να χρησιμοποιήσω κάποια άλλη μεταβλητή που να συνδέεται με το πλήθος των bits με κάποια πολλαπλασιαστική σταθερά πχ πλήθος χαρακτήρων. Το ερώτημα είναι: μπορώ να χρησιμοποιήσω κάποια άλλη μεταβλητή επειδή θέλω ή επειδή με βολεύει; Μπορώ πχ να πω ότι στον αλγόριθμο
Διάβασε ν
Για ι από 1 μέχρι ν
  Γράψε ι
Τέλος_επανάληψης
χρησιμοποιώ σαν μεταβλητή τον αριθμό εισόδου ν και έχω πολυπλοκότητα γραμμική ως προς ν ή είμαι παράτυπος;
Μπορώ πχ να εξηγήσω γιατί αν ταξινομώ πίνακες με αριθμούς χρησιμοποιώντας το πλήθος των αριθμών και όχι τα ψηφία τους έχω μεταβλητή πολλαπλασιασμένη με το πλήθος των bits εισόδου, αλλά τι γίνεται με το παράδειγμα που δίνω; Έχω δικαίωμα να εκφράσω πολυπλοκότητα ως προς ν αλλάζοντας την τάξη από εκθετική ως προς τα bits σε πολυωνυμική ως προς ν ή όχι;

Έχουμε λοιπόν έναν αλγόριθμο που δέχεται ως είσοδο έναν ακέραιο ν κι εμφανίζει όλους τους ακέραιους από το 1 μέχρι το ν.

Έχουμε κάθε δικαίωμα να πούμε ότι ο αλγόριθμός μας έχει πολυπλοκότητα Ο(ν). Δεν έχουμε όμως δικαίωμα να πούμε ότι ο αλγόριθμός μας είναι πολυωνυμικού χρόνου, αφού αυτό θα σήμαινε ότι είναι πολυωνυμικού χρόνου ως προς το μέγεθος της εισόδου (αφού ως προς το μέγεθος της εισόδου μετράμε την πολυπλοκότητα για να χαρακτηρίσουμε τον αλγόριθμο ως πολυωνυμικού, εκθετικού κτλ χρόνου), από τη στιγμή που το μέγεθος της εισόδου είναι lgν κι ο αλγόριθμός μας είναι Ο(2^lgν).

Και για τον αλγόριθμο δυναμικού προγραμματισμού για το knapsack, αναφέρουμε την πολυπλοκότητά του ως Ο(nW). Κανένας όμως αυτό δεν το ερμηνεύει ως πολυωνυμικού χρόνου, αφού στο συγκεκριμένο πρόβλημα το W δεν αντιστοιχεί σε πλήθος δεδομένων αλλά είναι απλά μια αριθμητική τιμή, άρα ουσιαστικά ο αλγόριθμος είναι εκθετικός, Ο(n*2^lgW), ως προς το μέγεθος της εισόδου.

[gpapargi]

Με βάση αυτά, στο παράδειγμα του τετραδίου μπορώ να πω ότι ο αλγόριθμος έχει τετραγωνική πολυπλοκότητα Ο(ν^2) αν και φυσικά δεν μπορώ να πω ότι είναι τετραγωνικός ως προς το χρόνος εκτέλεσης. Φοβάμαι πως θα δημιουργηθούν μπερδέματα.