Θέμα: Υπολογισμός χρόνου εκτέλεσης (υπολογισμός αριθμού πράξεων των εντολών)

[ether]

Εγώ θεωρώ ότι η ΑΕΠΠ χρησιμοποιεί το uniform, οπότε σαν απάντηση στον ether, όσα περιγράφονται σωστότερα με το logarithmic, αυτά είναι που θα χαρακτήριζα εκτός ύλης. Άρα το primality test ως προς την τιμή θα το θεωρούσα εντός ύλης, ενώ ως προς τα bits εισόδου εκτός ύλης.

Αφού στη βιβλιογραφία τέτοιοι αλγόριθμοι -όπως ο τετριμμένος brute force για τον έλεγχο πρώτου, ο κλασικός DP για το knapsack, ο DP για το subset sum και άλλοι- που είναι πολυωνυμικοί ως προς την αριθμητική τιμή της εισόδου δεν αναφέρονται ως πολυωνυμικοί αλλά ως ψευδοπολυωνυμικοί, και οι ψευδοπολυωνυμικοί στη βιβλιογραφία θεωρούνται εκθετικοί ως προς το input size, πώς εμείς στην ΑΕΠΠ θα τους χαρακτηρίζουμε πολυωνυμικούς;

[alkisg]

Χαρακτηρίζονται εκθετικοί ως προς input size αλλά πολυωνυμικοί ως προς την τιμή:

a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input

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

Να κι ένα ακόμα από τη wikipedia, ειδικά για το primality test που αναφέρεσαι:

For example, the complexity of primality tests and multiplication algorithms can be measured in two different ways: one in terms of the integers being tested or multiplied, and one in terms of the number of binary digits (bits) in those integers. For example, if n is the integer being tested for primality, trial division can test it in Θ(n1/2) arithmetic operations; but if n is the number of bits in the integer being tested for primality, it requires Θ(2n/2) time. In the fields of cryptography and computational number theory, it is more typical to define the variable as the number of bits in the input integers.

Εμείς τι επιλέγουμε να διδάξουμε στους μαθητές, ότι το ν είναι η τιμή του αριθμού που ελέγχουμε αν είναι πρώτος, ή ο αριθμός των bit του;

Φαντάσου το σαν τη Φυσική, όπου στο σχολείο τους διδάσκουν κλασσική μηχανική, και αργότερα στο πανεπιστήμιο μαθαίνουν ότι αυτά ίσχυαν μόνο για μικρές ταχύτητες και δεν ισχύουν όσο πλησιάζουμε την ταχύτητα του φωτός. Έτσι κι εδώ, όσο το ν αυξάνεται, το uniform μοντέλο δεν περιγράφει τόσο καλά τους αλγορίθμους που απειρίζουν τα bits του τύπου δεδομένων, αλλά δεν κάνουμε και επιστημονικό λάθος αν χρησιμοποιήσουμε το uniform μοντέλο στο Λύκειο για να μην κουράσουμε τους μαθητές.


Πάμε λίγο στο βιβλίο της ΑΕΠΠ. Αυτό σε πολλές περιπτώσεις λέει είτε πιο άμεσα είτε πιο έμμεσα ότι το μέγεθος του προβλήματος δεν ταυτίζεται με το μέγεθος της εισόδου, αλλά ένα παράδειγμα που μας ταιριάζει ιδιαίτερα εδώ είναι ο υπολογισμός fibonacci:

Η επαναληπτική διαδικασία, λοιπόν, βασίζεται σε ένα και μόνο βρόχο, άρα η πολυπλοκότητα της μεθόδου είναι τάξης O(n).

Είναι το ίδιο με το παράδειγμα "γράψε ν αριθμούς" του Γιώργου, με τον υπολογισμό της δύναμης, και με το trivial primarity test. Και το βιβλίο το λέει Ο(n), όχι εκθετικό.

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

Ο λόγος που αναμείχθηκα στην παρούσα συζήτηση είναι επειδή η πρώτη επιλογή μου φαίνεται σοφότερη.

Καλό ΣΚ σε όλους!

[ether]

Χαρακτηρίζονται εκθετικοί ως προς input size αλλά πολυωνυμικοί ως προς την τιμή:
Και τα δύο είναι επιστημονικώς αποδεκτά, δεν είναι ντροπή ή λάθος να πεις ότι ένας ψευδοπολυωνυμικός είναι πολυωνυμικός ως προς την τιμή. Είναι δύο διαφορετικές μέθοδοι προσδιορισμού της πολυπλοκότητας, αυτή με βάση τα bits εισόδου την εκφράζει καλύτερα για μεγάλα ν, αλλά σίγουρα και ο χαρακτηρισμός ως προς την τιμή δεν είναι λάθος.

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

Φαντάσου το σαν τη Φυσική, όπου στο σχολείο τους διδάσκουν κλασσική μηχανική, και αργότερα στο πανεπιστήμιο μαθαίνουν ότι αυτά ίσχυαν μόνο για μικρές ταχύτητες και δεν ισχύουν όσο πλησιάζουμε την ταχύτητα του φωτός. Έτσι κι εδώ, όσο το ν αυξάνεται, το uniform μοντέλο δεν περιγράφει τόσο καλά τους αλγορίθμους που απειρίζουν τα bits του τύπου δεδομένων, αλλά δεν κάνουμε και επιστημονικό λάθος αν χρησιμοποιήσουμε το uniform μοντέλο στο Λύκειο για να μην κουράσουμε τους μαθητές.

Πάμε λίγο στο βιβλίο της ΑΕΠΠ. Αυτό σε πολλές περιπτώσεις λέει είτε πιο άμεσα είτε πιο έμμεσα ότι το μέγεθος του προβλήματος δεν ταυτίζεται με το μέγεθος της εισόδου, αλλά ένα παράδειγμα που μας ταιριάζει ιδιαίτερα εδώ είναι ο υπολογισμός fibonacci:
Είναι το ίδιο με το παράδειγμα "γράψε ν αριθμούς" του Γιώργου, με τον υπολογισμό της δύναμης, και με το trivial primarity test. Και το βιβλίο το λέει Ο(n), όχι εκθετικό.

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

Όπως είδαμε, ο brute force για το primality testing θεωρείται εκθετικός στη βιβλιογραφία και με το uniform μοντέλο.
Ο DP για το knapsack θεωρείται εκθετικός στη βιβλιογραφία με το RAM μοντέλο, το οποίο θεωρεί ότι οι αριθμητικές λειτουργίες σε αριθμούς που χωράνε στη λέξη του υπολογιστή εκτελούνται σε Ο(1).
Και προφανώς δεν είναι καθόλου λάθος να πεις ότι ο DP για το knapsack είναι Ο(nW), ούτε ότι ο brute force για το primality testing είναι O(n). Αν όμως πεις απλά ότι είναι πολυωνυμικοί, απλά λες κάτι που είναι διαφορετικό από αυτό που αναφέρεται εκτενώς και εννοείται στη βιβλιογραφία.

Καλό ΣΚ σε όλους!

Καλό ΣΚ

[gpapargi]

Χαρακτηρίζονται εκθετικοί ως προς input size αλλά πολυωνυμικοί ως προς την τιμή:
Και τα δύο είναι επιστημονικώς αποδεκτά, δεν είναι ντροπή ή λάθος να πεις ότι ένας ψευδοπολυωνυμικός είναι πολυωνυμικός ως προς την τιμή. Είναι δύο διαφορετικές μέθοδοι προσδιορισμού της πολυπλοκότητας, αυτή με βάση τα bits εισόδου την εκφράζει καλύτερα για μεγάλα ν, αλλά σίγουρα και ο χαρακτηρισμός ως προς την τιμή δεν είναι λάθος.

Αρκεί όμως ο χαρακτηρισμός ως προς την τιμή για να τοποθετήσεις τον trivial αλγόριθμο ελέγχου πρώτου στην κλάση P των πολυωνυμικών αλγορίθμων; (εννοείται πριν ανακαλυφθεί ο AKS). Αυτό είναι το κρίσιμο ερώτημα.

[alkisg]

Αρκεί όμως ο χαρακτηρισμός ως προς την τιμή για να τοποθετήσεις τον trivial αλγόριθμο ελέγχου πρώτου στην κλάση P των πολυωνυμικών αλγορίθμων; (εννοείται πριν ανακαλυφθεί ο AKS). Αυτό είναι το κρίσιμο ερώτημα.

Γιώργο θεωρώ ότι ο εξ' ορισμού χαρακτηρισμός του εν λόγω αλγορίθμου είναι "ψευδοπολυωνυμικός, δηλαδή πολυωνυμικός ως προς την τιμή και εκθετικός ως προς το μέγεθος της εισόδου σε bit".
Γιατί να θέλουμε να τον βάλουμε στην κλάση P; Τα P/NP σε κάποιες πηγές που διάβασα ορίζονται συγκεκριμένα ως προς το μέγεθος της εισόδου, όχι ως προς την τιμή, ενώ η πολυπλοκότητα είναι πιο ευέλικτη και μπορεί να οριστεί και με βάση άλλες παραμέτρους και μοντέλα κόστους.

Στα πλαίσια της ΑΕΠΠ, το βιβλίο περιέχει εκφράσεις του στυλ "ο αλγόριθμος υπολογισμού του ν-οστού όρου της ακολουθίας Fibonacci έχει πολυπλοκότητα Ο(ν)", και εννοεί την τιμή του ν, οπότε χωρίς να αναφέρεται σε ψευδοπολυωνυμικούς/P/NP επιτυγχάνει απλότητα χωρίς να είναι επιστημονικά λάθος.

Κι αυτό που λέω εγώ είναι ότι καλά κάνει και δεν χρειάζεται να το αντικρούσουμε, όπως έγινε σε κάποιες περιπτώσεις στο παρόν θέμα.

[gpapargi]

Άλκη το σχολικό βιβλίο δεν αποτελεί ισχυρή βιβλιογραφική πηγή. Περιέχει αρκετά λάθη και ασάφειες σε διάφορα σημεία, οπότε το τι λέει δεν είναι ισχυρό επιχείρημα. Προτείνω να δούμε το θέμα με βάση τη  βιβλιογραφία.
Θα προσπαθήσω να δώσω μια περιγραφή του τι συμβαίνει κατά τη γνώμη μου. Θα πάρω για παράδειγμα τον trivial αλγόριθμο ελέγχου πρώτου που έγραψα πριν.
Ας πούμε ότι μετράμε τις διαιρέσεις. Αυτές είναι ξεκάθαρα ν. Άρα ρο πλήθος των βημάτων είναι ν. Μέχρι εδώ καλά.
Έστω τώρα ότι θέλουμε να εκφράσουμε το πλήθος των βημάτων (το ν δηλαδή) σα συνάρτηση κάποιας ανεξάρτητης μεταβλητής.
Αν αυτή η μεταβλητή είναι το ν τότε έχω f(ν)=ν. Δηλαδή ο αλγόριθμος είναι γραμμικός ως προς το ν.
Αν αυτή η μεταβλητή είναι το log(ν) τότε έχω f(logν)=ν. Με αλλαγή μεταβλητής καταλήγω σε f(κ)=10^κ που είναι το ίδιο με f(ν)=10^ν. Δηλαδή ο αλγόριθμος έχει εκθετική πολυπλοκότητα ως προς το logν.
Αν αυτή η μεταβλητή είναι το 10^ν τότε έχω f(10^ν)=ν και με κατάλληλη αλλαγή μεταβλητής έχω f(ν)=log(ν). Δηλαδή ο αλγόριθμος είναι λογαριθμικός ως προς το 10^ν.
Θέλω να πως ότι εγώ κάνοντας μαθηματικό παιχνίδι, δηλαδή επιλέγοντας ανεξάρτητη μεταβλητή μπορώ να βγάζω τον αλγόριθμο γραμμικό, εκθετικό λογαριθμικό και ότι άλλο θέλω. Εδώ λοιπόν κάτι συμβαίνει. Μπορώ εγώ αλλάζοντας απλά  μεταβλητές να μεταφέρω τον αλγόριθμο από την P στην NP , στην Ο(ν), στην Ο(ν^2) κλπ;
Αυτό που συμβαίνει είναι ότι για να χαρακτηρίσω έναν αλγόριθμο αν είναι πολυωνυμικός ή εκθετικός (σκέτο χωρίς να αναφέρω τη μεταβλητή), θα πρέπει να χρησιμοποιήσω υποχρεωτικά το μέγεθος εισόδου (δηλαδή τα bits ή κάποιο αριθμητικό πολλαπλάσιό τους). Έτσι από τις 3 προηγούμενες πιθανές μεταβλητές η δεύτερη (logn) είναι αυτή που θα καθορίσει αν ο αλγόριθμος είναι εκθετικός πολυωνυμικός ή γραμμικός.
Οπότε ο συγκεκριμένος αλγόριθμος είναι εκθετικός (σκέτο) χωρίς να αναφέρω τη μεταβλητή ως προς την οποία μετράω. Επίσης δεν ανήκει στην P. Μόνο με αυτή τη μεταβλητή αποφασίζω αν ανήκει στην P.
Τώρα… μπορώ να πω τη φράση ότι ο αλγόριθμος είναι γραμμικός ως προς το ν. Αλλά μπορώ να πω επίσης ότι είναι λογαριθμικός ως προς το 10^ν. Ο λόγος που το δεν το κάνω είναι ότι η συγκεκριμένη επιλογή μεταβλητής είναι δύσχρηστη και δεν έχει και φυσικό νόημα όπως η επιλογή του ν που είναι η τιμής της εισόδου. Δεν είναι όμως μαθηματικό σφάλμα.
Με άλλα λόγια το πλήθος των bits είναι κάτι σαν «προεπιλεγμένη» ανεξάρτητη μεταβλητή, αν μου επιτρέπεται η έκφραση. Αν θέλεις να κατατάξεις τον αλγόριθμο στους «πολυωνυμικού χρόνου» ή «εκθετικού χρόνου», και να τον πεις πολυωνυμικό (σκέτο) ή εκθετικό (σκέτο) το κάνεις μέσω του πλήθους των bits.
Δεν είναι λάθος το να πεις ότι έχω γραμμική πολυπλοκότητα ως προς την είσοδο, όπως δεν είναι λάθος (αν και είναι δύσχρηστο) να πεις ότι έχω λογαριθμική πως προς το 10^ν.
Δεν μπορείς όμως να κατατάξεις στην κλάση P τον αλγόριθμο και το πρόβλημα με βάση την τιμή εισόδου αλλά μόνο τα bits εισόδου.
Οι ψευδοπολυωνυμικοί είναι οι εκθετικοί αλγόριθμοι (χωρίς να λέμε ως προς ποια μεταβλητή, δηλαδή εννοώντας τα bits) που είναι γραμμικοί ως προς την τιμή εισόδου.

[gpapargi]

Ένα σημείο σύγκλισης των απόψεων στα πλαίσια του μαθήματος μπορεί να είναι το εξής:
Να μπορούμε να χρησιμοποιήσουμε όποια μεταβλητή θέλουμε αρκεί να την αναφέρουμε ρητά. Πχ ο αλγόριθμος είναι γραμμικός ως προς το μέγεθος της εισόδου ν. Αν δεν αναφέρουμε τίποτα για το ποια είναι η μεταβλητή σημαίνει ότι είναι τα bits ή κάποιο πολλαπλάσιο (ψηφία, χαρακτήρες κλπ). Πχ αν πεις ότι ο αλγόριθμος είναι γραμμικός (σκέτο) σημαίνει ως προς τα bits. Αν θέλεις άλλη μεταβλητή θα πρέπει να την αναφέρεις ρητά.
Επίσης όταν αναφέρουμε παράγωγα της λέξης χρόνος (πχ χρονική πολυπλοκότητα, αλγόριθμος πολυωνυμικού χρόνου) θα εννοούμε τα bits ή πολλαπλάσιό τους.
Ο συμβολιμός Ο() αφορά συναρτήσεις οπότε μπορεί να χρησιμοποιηθεί και όταν δεν έχουμε bits αρκεί να δηλώνουμε τη μεταβλητή. Πχ όταν λέμε ότι ο αλγόριθμος είναι Ο(ν) σκέτο εννοούμε ως προς τα bits. Αν είναι άλλη η μεταβλητή θα πρέπει να τη δηλώνουμε. Πχ ο trivial αλγόριθμος εύρεσης πρώτου είναι Ο(ν), όπου ν είναι η τιμή εισόδου. Αν δεν αναφέρεις τι είναι το ν εννοείται ως προς τα bits. Δεν μπορείς δηλαδή να πεις ότι ο συγκεκριμένο αλγόριθμος είναι Ο(ν) (σκέτο).
Επίσης καλό είναι να πούμε ότι το πλήθος των bits είναι κάτι σαν τη «φυσική» μας  μεταβλητή. Αλλά επειδή είναι δύσχρηστη αν θέλουμε να χρησιμοποιήσουμε κάποια πιο βολική θα πρέπει να τη δηλώνουμε ρητά. Οι χαρακτηρισμοί προβλημάτων και αλγορίθμων σαν πολυωνυμικοί, εκθετικοί κλπ γίνεται ως προς τη φυσική μεταβλητή.
Στα παραπάνω συμφωνούμε; Νομίζω ότι βιβλιογραφικά είμαστε εντάξει.

[alkisg]

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

Όμως αν δεν αναφερθεί, και φτάσουμε αφού γίνει το κακό να συζητάμε το αν "ο αλγόριθμος υπολογισμού του ν-οστού όρου της ακολουθίας Fibonacci έχει πολυπλοκότητα Ο(ν)" εννοεί βάσει τιμής ή μεγέθους εισόδου, φοβάμαι ότι εκεί θα υπάρξουν γενικευμένες διαφωνίες...

ΟΚ νομίζω ότι αναφέρθηκαν όλες οι πλευρές του θέματος, καλή συνέχεια να έχουμε με τα υπόλοιπα...