Μέγεθος εισόδου και ο Θεός Βοηθός!!!

[pstasinos]

Το σχολικό βιβλίο μέσα αναφέρει :
"Μέγεθος εισόδου ενός αλγορίθμου
Πρέπει να υπάρχει κάποια ή κάποιες μεταβλητές που να εκφράζουν το μέγεθος (size) του αλγορίθμου. Οι μεταβλητές αυτές απεικονίζουν τους διαφορετικούς συνδυασμούς τιμών που κρίνουν τη συμπεριφορά ενός αλγορίθμου και δίνονται ως δεδομένα στον αλγόριθμο. Γενικά, τα δεδομένα συνιστούν το μέγεθος της εισόδου ενός αλγορίθμου. Για παράδειγμα, στον αλγόριθμο του προηγούμενου παραδείγματος ( παρακάτω το έβαλα ), το μέγεθος του αλγορίθμου μπορεί να εκφρασθεί από τη μεταβλητή n, που στην ουσία εκφράζει το πλήθος των επαναλήψεων του βασικού βρόχου του αλγορίθμου."

Αλγόριθμος Παράδειγμα1
n ← 10
Αρχή_επανάληψης
Διάβασε m
n ← n - 1
Μέχρις_ότου (m=0) ή (n=0)
Εκτύπωσε m
Τέλος Παράδειγμα1

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

Αν και το μπορεί δεν το σχολιάζω .... ( τι να πω για αυτό το κεφάλαιο ? ; ? .... ας μην σχολιάσω.... )

Στο παρακάτω αλγόριθμο τι θα απαντούσατε ότι αποτελεί μέγεθος εισόδου :

Αλγόριθμος Οτι_να_ναι
Διάβασε x
Αν x < 5 τότε
υ ←1
αλλιώς_αν x < 8 τότε
υ ←2
αλλιώς_αν x < 13 τότε
υ ←3
αλλιώς
υ ←4
Τέλος_αν
Εμφάνισε υ
Τέλος Οτι_να_ναι

[annastasios]

.

[Laertis]

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

Θεωρώ καλύτερο να βλέπουμε συνολικά το θέμα εξετάζοντας και την πολυπλοκότητα για να κατανοήσουμε τη συμπεριφορά των αλγορίθμων ως προς το μέγεθος εισόδου.

[pstasinos]

Συμφωνώ πως μια τέτοια ερώτηση δεν είναι και η πιο εύστοχη και καλό θα ήταν να μη ζητηθεί κάτι τέτοιο ξεχωριστά ,  αλλά αν έμπαινε κάτι τέτοιο θα απαντούσα προσωπικά πως :

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

Στο πίνακα 5.1 του σχολικού βιβλίου είναι ξεκάθαρο για τον κάθε αλγόριθμο τι αποτελεί μέγεθος εισόδου και για ποια βασική πράξη , απλά τη παραπάνω ερώτηση την συνάντησα σε βοήθημα και ψάχνω μια καλή απάντηση που θα μπορούσε να δώσει κάποιος μαθητής.

[alkisg]

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

Στον αλγόριθμο "υπολογίστε το ν-ιοστό δεκαδικό ψηφίο του αριθμού π" το δεδομένο είναι ένας μόνο αριθμός, το ν.
Επίσης η έξοδος του αλγορίθμου θα είναι πάλι μόνο ένα ψηφίο.

Το μέγεθος του προβλήματος όμως είναι "ν" και όχι "1", γιατί ο αριθμός των βημάτων που θα κάνουμε για να το λύσουμε, εξαρτάται από το "ν", το πλήθος των δεκαδικών, και όχι από το "1", το πόσα δεδομένα μας έδωσε ο χρήστης.

Θεωρητικά ο υπολογισμός της πολυπλοκότητας σημαίνει να εκφράσουμε τον χρόνο εκτέλεσης ενός προγράμματος σε συνάρτηση με ...κάτι.
χρόνος_εκτέλεσης=f(κάτι)
Το κάτι είναι το μέγεθος του προβλήματος, η μεταβλητή δηλαδή που μπαίνει ως παράμετρος στη συνάρτηση f() που μας υπολογίζει τον χρόνο εκτέλεσης, και πολλές φορές συμπίπτει και με το μέγεθος της εισόδου, αλλά όχι πάντα.
Ο χρόνος_εκτέλεσης δεν μπορεί να μετρηθεί σε δευτερόλεπτα γιατί αυτά αλλάζουν ανάλογα με το πόσο γρήγορος είναι ο Η/Υ που εκτελεί το πρόγραμμα.
Ούτε σε εντολές assembly (π.χ. είναι το i<-i+1 μια χρονική μονάδα, δηλαδή μία πράξη, ή δύο;) και ούτε σε κύκλους μηχανής γιατί κι αυτά μεταβάλλονται ανάλογα με τον μεταγλωττιστή και τον επεξεργαστή που χρησιμοποιούμε.

Το κοινό όμως με όλα τα παραπάνω, και αυτό που μας ενδιαφέρει, είναι ότι όλα τους είναι μεγέθη γραμμικώς ανάλογα, και γι' αυτό καταλήγουμε να απαντάμε με βάση την τάξη του προβλήματος αδιαφορώντας για τους συντελεστές των μεταβλητών.

Δηλαδή η απάντηση για το πόσο χρόνο θα χρειαστεί κάποιο πρόγραμμα θα μπορούσε να ήταν,
"10*ν + 2 δευτερόλεπτα", ή
"123*ν + 108 εντολές assembly", ή
"1234*ν + 1432 κύκλους μηχανής"

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

Εν τέλει λοιπόν μέγεθος του προβλήματος είναι αυτή η μεταβλητή που θα βάλουμε στον οριζόντιο άξονα της γραφικής παράστασης η οποία στον κάθετο άξονα προβλέπει τον χρόνο εκτέλεσης.
Και φυσικά κάποιες φορές η πρόβλεψη του χρόνου (=πολυπλοκότητα) μπορεί να εξαρτάται και από περισσότερες από μία μεταβλητές (n, m) οπότε αντίστοιχα η γραφική παράσταση θα ήταν πολυδιάστατη. Π.χ. το "πόσο χρόνο κάνει να εκτελεστεί η εντολή i<-i+1 όταν χρησιμοποιούμε βιβλιοθήκη αριθμών άπειρης ακρίβειας", εξαρτάται και από τον τρέχοντα αριθμό bit του αριθμού για να κάνουμε τις πράξεις, αλλά και από τον επιμέρους αλγόριθμο που θα χρειαστεί για δυναμική δέσμευση μνήμης realloc.

[gpapargi]

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

Εγώ αυτό που θα ανέμενα είναι να μου μιλήσει για το μέγεθος της εισόδου και το πλήθος των πράξεων συναρτήσει του μεγέθους της εισόδου. Το πως εφαρμόζεται αυτό στο συγκεκριμένο παράδειγμα θα το αφήσω για παρακάτω αφού αποσαφηνίσουμε πρώτα τους όρους.