Κάθε φορά που διαβάζω το κεφάλαιο 5 αισθάνομαι σαν τον αρχαιολόγο που προσπαθεί να αποκρυπτογραφήσει την Γραμμική Α και να κατανοήσει τι είχε στο μυαλό του σε κάθε σημείο του κειμένου αυτός που το έγραψε.
Σας γράφω μερικά συμπεράσματα στα οποία έχει καταλήξει αυτή η "αποκρυπτογράφηση" με τα οποία μπορεί να συμφωνήσετε, μπορεί και όχι. Σε κάθε περίπτωση η γνώμη σας είναι σημαντική για μένα.

1. Νομίζω ότι κάνουμε λάθος να θεωρούμε ότι το βιβλίο δίνει γενικά και συγκεκριμένα τον ορισμό των "βασικών πράξεων" ενός αλγορίθμου. Και το εξηγώ:
Στην παράγραφο
5.1.1. Χειρότερη περίπτωση ενός αλγορίθμου γράφει:
Η χειρότερη περίπτωση ενός αλγορίθμου αφορά στο μέγιστο κόστος εκτέλεσης του αλγορίθμου, κόστος που μετράται σε υπολογιστικούς πόρους. Το κόστος αυτό πολλές φορές κρίνει την επιλογή και το σχεδιασμό ενός αλγορίθμου. Για να εκφρασθεί αυτή η χειρότερη περίπτωση, χρειάζεται
κάποιο μέγεθος σύγκρισης και αναφοράς που να χαρακτηρίζει τον αλγόριθμο. Η πλέον συνηθισμένη πρακτική είναι η μέτρηση του αριθμού των
βασικών πράξεων που θα πρέπει να εκτελέσει ο αλγόριθμος στη χειρότερη περίπτωση.
Για
παράδειγμα, μία βασική πράξη
μπορεί να είναι:
ανάθεση τιμής, σύγκριση μεταξύ δύο μεταβλητών, ή οποιαδήποτε αριθμητική πράξη μεταξύ δύο μεταβλητών.
Η χειρότερη περίπτωση αντιπροσωπεύει τις τιμές εκείνες, που, όταν δίνονται ως είσοδος στον αλγόριθμο, οδηγούν στην εκτέλεση μέγιστου αριθμού βασικών πράξεων.
Τόνισα με bold τις λέξεις που με οδηγούν στο συμπέρασμα ότι εδώ
δεν πρόκειται για απόλυτο ορισμό των βασικών πράξεων (ποιες είναι πάντα) αλλά ποια θα μπορούσε να είναι
παραδειγματικά μια βασική πράξη με την οποία θέλουμε να μελετήσουμε την επίδοση ενός αλγορίθμου. Δε λέει πουθενά ότι "αυτές είναι οι βασικές πράξεις με τις οποίες μελετάμε αλγορίθμους", δε γράφει "ορίζουμε αυτές τις βασικές πράξεις" αλλά δίνει κάποια παραδείγματα για το ποιες θα μπορούσαν να είναι.
Αυτό δε σημαίνει ότι είναι πάντα μόνο αυτές, μπορεί να είναι κάποια ή κάποιες από αυτές (χρησιμοποιεί το "ή" και όχι το "και"), μπορεί να είναι και κάποια άλλη ή κάποιες άλλες.
Νοηματικά και διαισθητικά καταλαβαίνω (και από το υπογραμμισμένο αρχικά) ότι εδώ μιλάει για την έννοια του πλήθους των βασικών πράξεων ως μέγεθος σύγκρισης και αναφοράς, όμως αυτές οι βασικές πράξεις με τις οποίες μετράμε αυτό το πλήθος δεν είναι πάντα οι ίδιες για όλους τους αλγορίθμους.
Περισσότερο νομίζω έχει στο μυαλό του ο συγγραφέας εδώ κάποιους γνωστούς αλγορίθμους ταξινόμησης, αναζήτησης κ.τ.λ. και όχι κάποια assembly στην οποία μετράμε με ακρίβεια το πλήθος των πράξεων που κάνει ο επεξεργαστής, άλλωστε μιλάει για αλγορίθμους και όχι για προγράμματα σε συγκεκριμένη γλώσσα προγραμματισμού.
2. Ο παραπάνω ισχυρισμός, ότι δηλαδή δεν πρόκειται για απόλυτο ορισμό των βασικών πράξεων, αλλά για κάποια παραδείγματα, ίσως εξηγεί και το γεγονός ότι δεν υπάρχει η αύξηση της τιμής μιας μεταβλητής μέσα σε αυτές.
3. Στην αμέσως επόμενη παράγραφο
5.1.2 Μέγεθος εισόδου ενός αλγορίθμου γράφει:
Ο πίνακας 5.1 περιλαμβάνει παραδείγματα από συνήθεις κατηγορίες προβλημάτων, με δήλωση του μεγέθους που βασικά εκφράζει την είσοδό τους και
των αντίστοιχων βασικών πράξεων:
Πιν. 5.1. Μέγεθος εισόδου και βασική πράξη αλγορίθμων
Αλγόριθμος Βασική πράξη
ΤΑΞΙΝΟΜΗΣΗ σύγκριση
ΠΟΛΛΑΠΛΑΣΙΑΣΜΟΣ αριθμητικές πράξεις
ΑΝΑΖΗΤΗΣΗ σύγκριση
Βέβαια σε έναν αλγόριθμο ταξινόμησης ή αναζήτησης δε γίνονται μόνο συγκρίσεις, αλλά θεωρούμε ως βασικές πράξεις και μετράμε μόνο τις συγκρίσεις κλειδιών, ενώ στον πολλαπλασιασμό μετράμε το πλήθος των αριθμητικών πράξεων που γίνονται.
Ορίζουμε λοιπόν ποια θα είναι η βασική πράξη αναλόγως το πρόβλημα και τον αλγόριθμο που θα μελετήσουμε. (Και αυτό μπορεί να απαντήσει και στην απορία ενός μαθητή, γιατί σε αυτούς τους αλγορίθμους μετράμε μόνο αυτές ως βασικές πράξεις και όχι όλες όπως στο παράδειγμα της 5.1.3.)
Στην παράγραφο
5.3.1.Ταξινόμηση ευθείας ανταλλαγής γράφει:
Το πιο βασικό κριτήριο της επίδοσης μίας μεθόδου ταξινόμησης είναι ο αριθμός C, που μετρά τις απαιτούμενες συγκρίσεις κλειδιών (key comparisons), που εκτελούνται μέχρι να τελειώσει η ταξινόμηση. Ένα άλλο κριτήριο είναι ο αριθμός Μ που μετρά τις μετακινήσεις (moves) των στοιχείων.
Θα μπορούσαμε λοιπόν με βάση το βιβλίο να ορίσουμε ως βασική πράξη για την ταξινόμηση τη μετακίνηση ενός στοιχείου.
Το συμπέρασμα μου λοιπόν από όλα αυτά είναι:
Αν θέλεις να μετρήσω το πλήθος των βασικών πράξεων που εκτελεί ένας αλγόριθμος θα πρέπει να μου ορίσεις πρώτα ποιες θα είναι αυτές οι βασικές πράξεις με τις οποίες θα μετρήσω και κάθε φορά που εκτελείται μία τέτοια πράξη θα προσθέτω 1 σε αυτό το πλήθος.(Εκτός αν πρόκειται για πολύ γνωστούς αλγορίθμους που επιλύουν βασικά προβλήματα, ταξινόμηση, αναζήτηση κ.τ.λ. όπου εκεί γνωρίζω ποια είναι η βασική πράξη με την οποία θα μετρήσω).
Και έρχομαι στην επίμαχη παράγραφο
5.1.3.Χρόνος εκτέλεσης προγράμματος ενός αλγορίθμου. Γράφει:
Θα υπολογισθεί η επίδοσή του με βάση τον αριθμό των πράξεων που θα εκτελεσθούν.
Εδώ αναγκάστηκε ο συγγραφέας να μετρήσει όλες τις πράξεις για να δώσει το παράδειγμα (τις οποίες δεν ονομάζει βασικές, ούτε στον πίνακα που ακολουθεί, τις λέει απλώς πράξεις, γιατί άραγε;).
Ξέχασε όμως να ορίσει, πριν μετρήσει, ποιες θα είναι αυτές οι πράξεις που θα αυξάνουν κατά ένα το πλήθος, ίσως αποφάσισε να χρησιμοποιήσει αυτές που αναφέρονται στην παράγραφο 5.1.1., αλλά όταν έφτασε στην αύξηση του i αποφάσισε να τη θεωρήσει ως μία πράξη. Εδώ πιστεύω ότι όντως σκέφτηκε κάποια assembly, εδώ συμφωνώ με τον Κώστα και την πολύ ωραία εξήγηση που έδωσε μέσω της Χ86 Assembly.
ΥΓ: Αν υπάρχει περίπτωση να μπει τέτοιο θέμα θα πρέπει να
ορίζει τις βασικές πράξεις με τις οποίες θα γίνει η μέτρηση, διαφορετικά εγώ το θεωρώ ασαφές και ελλιπές. Ήδη έχω μαθητή που ο καθηγητής στο σχολείο μετατρέπει τη Για σε Όσο και μετράει το i <-- i+1 ως δύο πράξεις. Άλλοι θα το μετράνε ως μία πράξη.
Καταλαβαίνετε τι πρόκειται να γίνει....