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

[gthal]

Καταπληκτικό!
Μου άλλαξες τον τρόπο να διαβάζω αυτές τις παραγράφους!
Σ' ευχαριστώ!

[evry]

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

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

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

ΥΓ. Κατά τη γνώμη μου ακόμα και όλο το 5 να ήταν στην ύλη δεν ήταν δυνατόν να μπει θέμα που να ζητάει ακριβή υπολογισμό πράξεων , δηλαδή τη συνάρτηση Τ(Ν). Δεν έχει νόημα. Ο σκοπός θα έπρεπε να είναι να μπορεί ο μαθητής να διακρίνει εποπτικά (διαισθητικά) την πολυπλοκότητα του αλγορίθμου, π,χ, διπλή επανάληψη = Ν² , μέχρι εκεί.

[Diotima]

Συμφωνώ evry με το γενικό συλλογισμό σου μια και το σημαντικό είναι ο υπολογισμός της τάξης Ο ενός αλγορίθμου γι αυτό και υποστήριξα κι εγώ σε προηγούμενη ανάρτηση μου ότι θεωρώ ανούσια ασχολία τον ακριβή υπολογισμό των πράξεων του αλγορίθμου, πόσο μάλλον όταν μας αποκλείουν από το να διδάξουμε τι είναι και τι συμβολίζει η τάξη Ο (οδηγίες σελ. 10: Για τον συμβολισμό Ο της πολυπλοκότητας, δεν πρέπει να αναλυθεί τι ακριβώς εκφράζει και πως υπολογίζεται σε ένα αλγόριθμο.)

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

Σελ. 2 των οδηγιών:
Η διδασκαλία του κεφαλαίου 5 (Ανάλυση Αλγορίθμων) αποσκοπεί στο να γνωρίσουν και να κατανοήσουν, οι μαθητές, απλά θέματα σχετικά με την πολυπλοκότητα, την επίδοση και την αποδοτικότητα αλγορίθμων, που επιλύουν το ίδιο πρόβλημα.
Ενδεικτικές ασκήσεις αναφέρονται στις παραγράφους 5.1.1 και 5.1.3. του βιβλίου μαθητή και στο τετράδιο μαθητή.

Στην παράγραφο 5.1.3. του σχολικού γίνεται ακριβής υπολογισμός των πράξεων που εκτελεί ένα πρόγραμμα που υλοποιεί τον αλγόριθμο (32 πράξεις).
Ακολουθεί ο πίνακας (Πιν. 5.2) με τους χρόνους εκτέλεσης όταν αυξάνεται το μέγεθος n (πλήθος των επαναλήψεων του βρόχου).

Σελ. 10 των οδηγιών:  23.   &  24. Ενότητες 5.1 & 5.3
Η διαπραγμάτευση των εννοιών να γίνει με βάση το βιβλίο μαθητή και ως επιπλέον παραδείγματα να δοθούν τα παραδείγματα 1 & 2 του Κεφαλαίου 5 του τετραδίου του μαθητή.

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

Ζητείται πάλι να υπολογισθεί η επίδοσή του με βάση τον αριθμό των πράξεων που θα εκτελεσθούν. Ακολουθεί η λύση όπου γίνεται ακριβής υπολογισμός των πράξεων (506 πράξεις) και το συμπέρασμα:
Με δεδομένο ότι ο βρόχος του προγράμματος θα εκτελεσθεί 100 φορές προκύπτει η παραπάνω ανάλυση, η οποία αποτελεί εκτίμηση και του χρόνου εκτέλεσης του προγράμματος αλγορίθμου.
Είναι χρήσιμο εδώ να καταγραφεί το μέγεθος του προβλήματος και να εκφρασθεί το σύνολο των κριτηρίων επίδοσης σε σχέση με αυτό.

Στο παράδειγμα 2 (σελ. 46 τετραδίου μαθητή) που μας συστήνει πάλι η παραπάνω οδηγία είναι ένα διπλός βρόχος όπου διαβάζονται και εμφανίζονται τα στοιχεία ενός δισδιάστατου πίνακα και ζητείται:
Να υπολογισθεί ο χρόνος εκτέλεσης του αλγορίθμου αυτού και να σχολιασθεί η βαρύτητα των πράξεων επανάληψης σε σχέση με την απόφαση για την πολυπλοκότητα των αλγορίθμων.
Το συμπέρασμα γράφει: Από ό,τι παρατηρούμε υπάρχουν δύο βρόχοι επανάληψης (ένας βρόχος για κάθε διάσταση του πίνακα). Για κάθε στιγμή επανάληψης μέσα στο εσωτερικό των δύο βρόχων γίνονται δύο απλές πράξεις (ανάγνωση και εκτύπωση) μοναδιαίου κόστους n καθεμία. (εδώ αναφέρεται το κόστος των εσωτερικών πράξεων).
Επομένως η πολυπλοκότητα του παραπάνω αλγορίθμου θα εκφράζεται με n * n * 2, δηλαδή ο αλγόριθμος είναι τετραγωνικός. Είναι φανερό ότι οι βρόχοι επανάληψης είναι εκείνοι που καθορίζουν την επιβάρυνση στο κόστος εκτέλεσης του αλγορίθμου.

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

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

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

Σε αυτό θα ήθελα να μάθω αν συμφωνείς...

[pgrontas]

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

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

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

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

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

[Καρκαμάνης Γεώργιος]

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

Για το σκοπό αυτόν, θα πρέπει να στηριχτούμε στο διδακτικό πακέτο, καθώς είναι και το μοναδικό υλικό που έχουμε στα χέρια, τόσο εμείς οι καθηγητές όσο και οι μαθητές, και είναι αυτό που  θα συμβουλευόμαστε και θα χτίσουμε τη διδασκαλία μας.

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

β) η  εκχώρηση με πράξη αντιστοιχεί σε δύο πράξεις πχ ( χ <-- α + β)

Μέχρι να έρθουν νεότερες οδηγίες νομίζω ότι πρέπει να αποδεχθούμε αυτά που αναφέρονται στο διδακτικό πακέτο.

[gthal]

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

Συμφωνώ 100% Παναγιώτη!!

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

Γιώργο, και μαζί σου θέλω να συμφωνήσω. Όμως έχω δύο λόγους που με δυσκολεύουν:
Ο ένας είναι... πρακτικός! Το 5ο κεφ. το έχω ήδη διδάξει λίγο καιρό πριν, και όταν είχε ανοίξει το θέμα πριν 1-2 μήνες, είχα την εντύπωση πως όσοι είχαν συμμετάσχει τότε συμφωνούσαν ότι μάλλον πρόκειται για τυπογραφικό του βιβλίου (η αύξηση του ι ως μία πράξη στα παραδείγματα). Έτσι, το δίδαξα ως 2 πράξεις, άρα έχω ήδη εκτεθεί

Ο δεύτερος είναι ότι δεν βλέπω με ποιον σαφή τρόπο αναφέρεται στο διδακτικό πακέτο ότι η αύξηση του μετρητή είναι μία πράξη (και άραγε αυτό το δεχόμαστε στη ΓΙΑ μόνο? ή σε οποιαδήποτε τέτοια εκχώρηση, όπως λέει ο Ντζιός? ο καθένας συμπεραίνει ό,τι νομίζει). Το βιβλίο από μόνο του αυτοαναιρείται. Δεν είναι ότι εγώ θέλω να το πω αλλιώς, είναι ότι το βιβλίο το λέει με 2 διαφορετικούς τρόπους (και άρα έπρεπε να διαλέξω, και διάλεξα έναν που είναι απλός για τους μαθητές και συνεπής με όλες τις αρ. πράξεις και εκχωρήσεις). Ενώ απ' όσα έχει πει πριν το παράδειγμα είναι ξεκάθαρο ότι η ι <- ι +1 περιλαμβάνει 2 πράξεις, έρχεται με το παράδειγμα και (χωρίς να το λέει μεν) μας βάζει να εξάγουμε έναν άλλο κανόνα (στον οποίο για να φτάσουμε πρέπει να περάσουμε από συζήτηση για assembly και μεταγλωττιστές!). Άρα αυτό, θέλω να πω,  δεν δηλώνεται καθαρά μέσα στο πακέτο. Συμπέρασμα δικό μας είναι κι αυτό, και δεν έχω κανένα πρόβλημα να συμφωνήσουμε ως κοινότητα ότι θα το δεχθούμε έτσι (πάντως, μυρίσαμε τα νύχια μας για να το βρούμε και δεν είναι αλήθεια ότι όποιος το δίδαξε διαφορετικά, αμφισβητεί κατ' ανάκγη το διδακτικό πακέτο)

Αλλά το καλύτερο σου το έχω για το τέλος κι ελπίζω να έχεις υπομονή:
Ακόμα κι αν το δεχθούμε έτσι το παραπάνω, έρχεται ένα άλλο παράδειγμα να μας αναιρέσει πάλι  !!!!
Είναι το παράδειγμα στην 5.1.3  και ο πίνακας 5.2
Υπολογίζω τις πράξεις γενικεύοντας, θεωρώντας όπου 4 το n, και μετρώντας την αύξηση του ι ως μία πράξη και βρίσκω ότι το πλήθος των πράξεων είναι 5n+12 (δες εικ 1). Για n=4, ο τύπος πράγαμτι επαληθεύει τις 32 πράξεις που υπολογίζει και το βιβλίο λύνοντας το παράδειγμα.
(αν θεωρούσαμε την αύξηση του ι ως 2 πράξεις θα βρίσκαμε 6n+13 πράξεις)
Πάμε όμως στον πίνακα 5.2 που δίνει τους χρόνους εκτέλεσης του συγκεκριμένου αλγορίθμου για διάφορα n.
Για n=5 o τύπος 5n+12 δίνει 37 πράξεις, άρα 37 μικροδευτερόλεπτα ενώ ο πίνακας δίνει 42 !  Ασυμφωνία! Το ίδιο συμβαίνει με κάθε n που δοκιμάζει !!!
Κι έτσι, από περιέργεια, ο τύπος 6n+13 για n=5 δίνει 43 πράξεις !! Πιο κοντά, αν και η τιμή του βιβλίου δε συμφωνεί με καμία από τις δικές μας.
Ομοίως και στα υπόλοιπα n.     (βάζω και την εικ 2 για τις συγκρίσεις)
Ποια θεωρία επιβεβαιώνει λοιπόν; Τι να εμπιστευθώ από το βιβλίο; Αυτά που λέει θεωρητικά ή αυτά που εξάγονται από τα παραδείγματα; (αν εξάγεται κάτι... )   
Είπα τον καημό μου και ησύχασα.

[Diotima]

Είναι το παράδειγμα στην 5.1.3  και ο πίνακας 5.2
Υπολογίζω τις πράξεις γενικεύοντας, θεωρώντας όπου 4 το n, και μετρώντας την αύξηση του ι ως μία πράξη και βρίσκω ότι το πλήθος των πράξεων είναι 5n+12 (δες εικ 1). Για n=4, ο τύπος πράγαμτι επαληθεύει τις 32 πράξεις που υπολογίζει και το βιβλίο λύνοντας το παράδειγμα.
(αν θεωρούσαμε την αύξηση του ι ως 2 πράξεις θα βρίσκαμε 6n+13 πράξεις)
Πάμε όμως στον πίνακα 5.2 που δίνει τους χρόνους εκτέλεσης του συγκεκριμένου αλγορίθμου για διάφορα n.
Για n=5 o τύπος 5n+12 δίνει 37 πράξεις, άρα 37 μικροδευτερόλεπτα ενώ ο πίνακας δίνει 42 !  Ασυμφωνία! Το ίδιο συμβαίνει με κάθε n που δοκιμάζει !!!
Κι έτσι, από περιέργεια, ο τύπος 6n+13 για n=5 δίνει 43 πράξεις !! Πιο κοντά, αν και η τιμή του βιβλίου δε συμφωνεί με καμία από τις δικές μας.
Ομοίως και στα υπόλοιπα n.     (βάζω και την εικ 2 για τις συγκρίσεις)
Ποια θεωρία επιβεβαιώνει λοιπόν; Τι να εμπιστευθώ από το βιβλίο; Αυτά που λέει θεωρητικά ή αυτά που εξάγονται από τα παραδείγματα; (αν εξάγεται κάτι... )   
Είπα τον καημό μου και ησύχασα.

Καλησπέρα σε όλους,

Γιώργο συμφωνώ με όλα όσα λες και σε ευχαριστώ πολύ για τα καλά σου λόγια για τη νοηματική μου ανάλυση στις παραγράφους του βιβλίου.
Στο παραπάνω παράδειγμα ο τύπος βγάζει 5n+7 και όχι 5n+12. Οπότε επαληθεύονται όλες οι τιμές του πίνακα 5.2.
Είχα κάνει την ανάλυση του παραδείγματος τον Αύγουστο και αρχικά έκανα το ίδιο λάθος που κάνεις εσύ και βγάζεις 5n+12. Το λάθος μου το βρήκε ο SPY και διόρθωσα την ανάλυση για να μη μπερδέψω κανένα.
Δες εδώ https://alkisg.mysch.gr/steki/index.php?topic=6275.150
τη διορθωμένη ανάλυση μου και πιο κάτω στην ίδια σελίδα την παρατήρηση που μου έκανε ο SPY και τη διόρθωσα, φαίνεται και η παλιά λάθος ανάλυση.

[Diotima]

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

Για το σκοπό αυτόν, θα πρέπει να στηριχτούμε στο διδακτικό πακέτο, καθώς είναι και το μοναδικό υλικό που έχουμε στα χέρια, τόσο εμείς οι καθηγητές όσο και οι μαθητές, και είναι αυτό που  θα συμβουλευόμαστε και θα χτίσουμε τη διδασκαλία μας.

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

β) η  εκχώρηση με πράξη αντιστοιχεί σε δύο πράξεις πχ ( χ <-- α + β)

Μέχρι να έρθουν νεότερες οδηγίες νομίζω ότι πρέπει να αποδεχθούμε αυτά που αναφέρονται στο διδακτικό πακέτο.

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

Κάποιοι καθηγητές έχουν κατανοήσει λάθος την αναφορά παραδειγμάτων βασικών πράξεων στην παράγραφο 5.1.1., έχουν μεταφράσει αυτά τα παραδείγματα ως ορισμό των στοιχειωδών πράξεων και γι αυτό μετατρέπουν τη ΓΙΑ σε ΟΣΟ, για να εκφράσουν τη ΓΙΑ με αυτές τις πράξεις και ύστερα να τη μετρήσουν. Οπότε κάνουν i<-- i+1 και μετράνε 2 πράξεις. Η παράγραφος αυτή μιλάει για εντελώς άλλο πράγμα και όχι για τις στοιχειώδεις μοναδιαίου κόστους πράξεις. Μιλάει για την έκφραση της χειρότερης περίπτωσης ενός αλγορίθμου και για το μέγεθος αναφοράς που χρειαζόμαστε για να την εκφράσουμε, που είναι το πλήθος των βασικών πράξεων που έχουμε ορίσει γι αυτόν τον αλγόριθμο.
Π.χ. στην ταξινόμηση και αναζήτηση το πλήθος των συγκρίσεων που γίνονται στη χειρότερη περίπτωση, γι αυτό και αναφέρει και το επόμενο παράδειγμα χειρότερης περίπτωσης. Οπότε, αναφέρει μερικά συνήθη παραδείγματα βασικής πράξης για την έκφραση της χειρότερης περίπτωσης.

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

Κατά τη γνώμη μου υπάρχουν δύο λύσεις:

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

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

[Diotima]

Καλημέρα σε όλους,

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

"Όσο και αν τυχόν ξαφνιάζει, ο υπολογιστής δεν μπορεί να εκτελεί παρά μόνο τρεις λειτουργίες:

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

σύγκριση, η οποία συνιστά τη βασική λειτουργία για την επιτέλεση όλων των λογικών πράξεων,

μεταφορά δεδομένων, λειτουργία που προηγείται και έπεται της επεξεργασίας δεδομένων.

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

Οπότε στην πρόσθεση ανάγεται οποιαδήποτε αριθμητική πράξη.
Στην εντολή i<-- i+1 γίνεται μία πρόσθεση στην τιμή μιας μεταβλητής i αλλά όχι μεταφορά σε άλλη μεταβλητή (1 πράξη), ενώ στην εντολή χ <-- α+β γίνεται μία πρόσθεση και μεταφορά της τιμής στη μεταβλητή χ (2 πράξεις).
χ <-- χ^2 (1 πράξη),  Α[ι] <-- Α[ι]+1 (1 πράξη), χ<-- χ mod 2 (1 πράξη) κ.τ.λ.

Γράψε χ (1 πράξη, μεταφορά της τιμής της χ από τη μνήμη στη μονάδα εξόδου)
Διάβασε χ (1 πράξη, μεταφορά της τιμής της χ από τη μονάδα εισόδου στη μνήμη)
Γράψε χ, ψ (2 πράξεις), Διάβασε χ, ψ, ζ (3 πράξεις) κ.τ.λ.

Α<-- Α και Β (1 πράξη), Α<-- Β και Γ (2 πράξεις) κ.τ.λ.

Υπάρχει περίπτωση να ισχύει; Περιμένω τη γνώμη σας........

[nick_papag]

Χμμμ... εμένα μου φαίνεται πολύ ενδιαφέρουσα αυτή η προσέγγιση!
Δε θα είχα καμιά διαφωνία με το παραπάνω. Όπως και να'χει όμως ο μαθητής θέλει χειροπιαστά πράγματα τα οποία όπως μπήκε φέτος σφήνα αυτό το κεφάλαιο, αδυνατούμε να τα ξεκαθαρίσουμε 100%. Θα εξεταστεί μόνο ως θεωρία μεν, αλλά σε ένα θέμα α ή β που θα δίνει πιθανόν ένα αλγόριθμο για να υπολογιστούν πράξεις θα γίνει χαμός από διαφορετικές ---με "σωστά???" διδαγμένους τρόπους--- λύσεις.
Ας ελπίσουμε μόνο να το έχουμε ανάγει μόνο εμείς σε τέτοιο επίπεδο και να μη χρειαστεί να κλάψουν μανούλες.

[Diotima]

Έκανα μια έρευνα στο internet για να δω τι λέει και ο υπόλοιπος πλανήτης για το θέμα (την έχω αυτήν την τάση όταν μου προκύψει θέμα που δεν είναι ξεκάθαρο, τα γράφω για όσους ενδιαφέρονται και όχι για να κουράσω).
Λίγα πράγματα βρήκα, γιατί ποιος κάθεται ν' ασχοληθεί με αυτό. Αυτά όμως είναι υπέρ αρκετά και μου επιβεβαίωσαν αυτά που ήθελα.

Εδώ είναι ένα εισαγωγικό κεφάλαιο στην ανάλυση αλγορίθμων από ένα σύγγραμμα του Πανεπιστημίου της Νέας Υόρκης:
https://cs.nyu.edu/courses/fall02/V22.0310-002/chapters/chapter-01.html

Ο συγγραφέας παρουσιάζει ένα παράδειγμα αλγορίθμου σε ψευδογλώσσα, με ένα for, με σκοπό να μετρήσει τις στοιχειώδεις πράξεις (primitive operations).
Στην παράγραφο 1.1.2, πριν κάνει τη μέτρηση, όχι μόνο ορίζει ποιες είναι οι στοιχειώδεις πράξεις αλλά ορίζει ακόμα και το μοντέλο που θεωρεί ότι εκτελείται ο αλγόριθμος, μια μη απόλυτα ρεαλιστική RAM, όπου εξηγεί ακόμα και τη διαφορά της με μια πραγματική RAM και τι θα αγνοήσει στη μέτρηση, προφανώς για λόγους απλούστευσης (θεωρεί την αύξηση του i στο for 2 πράξεις, πρόσθεση και ανάθεση).

Δείτε πώς παρουσιάζει τη μέτρηση στη συνέχεια (1.1.3) και συγκρίνετε................

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

for i:=0 to n do
  print test
end

http://stackoverflow.com/questions/5069840/how-many-primitive-operations-in-a-simple-loop

Αξίζει να δείτε τις απαντήσεις, κάποιος που αναλύει μετατρέπει το for σε while αλλά εδώ την εντολή i = i + 1 τη μετράει ως μία στοιχειώδη πράξη.
Θεωρώ πολύ πλήρη την τελευταία απάντηση, γι αυτό την παραθέτω:

@K.K: There are many different thoughts on what is considered a primitive operation. As described in a previous comment, the definition of "primitive operation" depends a lot on the language, the compiler, and the architecture. Or on the rules set forth in whatever text you're reading. – Jim Mischel Sep 3 '15 at 7:47

[ether]

Απλώς και μόνο για να δούμε, όπως λέει και η Diotima, τι λέει και ο υπόλοιπος πλανήτης για το θέμα, παραθέτω μερικά links σχετικά με το θέμα, όπως το παρουσιάζει ο Robert Sedgewick, ο οποίος ασχολείται αρκετά με την ανάλυση αλγορίθμων:

1.
Ένα απόσπασμα από το
Robert Sedgewick, Philippe Flajolet, An Introduction to the Analysis of Algorithms (2nd Edition, 2013), Addison-Wesley Professional, p. 4-5
"
...
The term analysis of algorithms has been used to describe two quite different general approaches to putting the study of the performance of computer programs on a scientific basis. We consider these two in turn.

The first, popularized by Aho, Hopcroft, and Ullman [2] and Cormen, Leiserson, Rivest, and Stein [6], concentrates on  determining the growth of the worst-case performance of the algorithm (an “upper bound”). A prime goal in such analyses is to determine which algorithms are optimal in the sense that a matching “lower bound” can be proved on the worst-case performance of any algorithm for the same problem. We use the term theory of algorithms to refer to this type of analysis. It is a special case of computational complexity, the general study of relationships between problems, algorithms, languages, and machines. The emergence of the theory of algorithms unleashed an Age of Design where multitudes of new algorithms with ever-improving worstcase performance bounds have been developed for multitudes of important problems. To establish the practical utility of such algorithms, however, more detailed analysis is needed, perhaps using the tools described in this book.

The second approach to the analysis of algorithms, popularized by Knuth [17][18][19][20][22], concentrates on precise characterizations of the bestcase, worst-case, and average-case performance of algorithms, using a methodology that can be refined to produce increasingly precise answers when desired. A prime goal in such analyses is to be able to accurately predict the performance characteristics of particular algorithms when run on particular computers, in order to be able to predict resource usage, set parameters, and compare algorithms. This approach is scientific: we build mathematical models to describe the performance of real-world algorithm implementations, then use these models to develop hypotheses that we validate through experimentation.

We may view both these approaches as necessary stages in the design and analysis of efficient algorithms. When faced with a new algorithm to solve a new problem, we are interested in developing a rough idea of how well it might be expected to perform and how it might compare to other algorithms for the same problem, even the best possible. The theory of algorithms can provide this. However, so much precision is typically sacrificed in such an analysis that it provides little specific information that would allow us to predict performance for an actual implementation or to properly compare one algorithm to another. To be able to do so, we need details on the implementation, the computer to be used, and, as we see in this book, mathematical properties of the structures manipulated by the algorithm. The theory of algorithms may be viewed as the first step in an ongoing process of developing a more refined, more accurate analysis; we prefer to use the term analysis of algorithms to refer to the whole process, with the goal of providing answers with as much accuracy as necessary.
...
"

2.
https://www.youtube.com/watch?v=ZCgnwo0bRDI

https://www.youtube.com/watch?v=SQ-DHCAy1E4

https://www.youtube.com/watch?v=7pYU2H2XwCI

https://www.youtube.com/watch?v=RPsajyxCBVQ

https://www.youtube.com/watch?v=oVT8eYqY8pc

https://www.youtube.com/watch?v=MQCa0G7xXbk

Οι σχετικές διαφάνειες υπάρχουν στο
http://algs4.cs.princeton.edu/lectures/14AnalysisOfAlgorithms.pdf

3.
Μερικές ακόμα διαφάνειες σχετικές με την ανάλυση αλγορίθμων
http://aofa.cs.princeton.edu/lectures/lectures13/AA01-AofA.pdf

[Diotima]

Καταπληκτικές οι παραπομπές σου ether, για βαθιά επιστημονική μελέτη!
Πρόλαβα να δω μόνο τις διαφάνειες, υπέροχες!
Σε ευχαριστώ πολύ που τις ανάρτησες!

Θα ήθελα να μάθω, τι προτείνεις να γίνει;
Αλλά αν δε θες να απαντήσεις, μπορώ να το καταλάβω.....

[ether]

Καταπληκτικές οι παραπομπές σου ether, για βαθιά επιστημονική μελέτη!
Πρόλαβα να δω μόνο τις διαφάνειες, υπέροχες!
Σε ευχαριστώ πολύ που τις ανάρτησες!

Θα ήθελα να μάθω, τι προτείνεις να γίνει;
Αλλά αν δε θες να απαντήσεις, μπορώ να το καταλάβω.....

Με την πρώτη ευκαιρία δες και τα βίντεο (με τη σειρά). Αξίζουν.

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

Όπως και να 'χει, από το μοντέλο κόστους (cost model), το κόστος κάθε εντολής (που εξαρτάται από την υλοποίηση (compiler, H/W, λειτουργικό))  δεν πρέπει να μας απασχολεί σε επίπεδο εξετάσεων. Μας απασχολεί η συχνότητα εκτέλεσης κάθε εντολής, η οποία εξαρτάται από τον αλγόριθμο και ενδεχομένως και από το μοντέλο δεδομένων (input model) (κι όταν μελετάμε τη χειρότερη περίπτωση, εξαρτάται μόνο από τον αλγόριθμο). Το ποιες εντολές θέλουμε να μετρήσουμε (π.χ. συγκρίσεις, προσπελάσεις πίνακα κτλ) θα πρέπει να δηλώνεται στην εκφώνηση μια άσκησης.

[Diotima]

Φυσικά και θα δω και τα video ether, είμαι σίγουρη ότι αξίζουν...
Συμφωνώ και με τις απαντήσεις σου, σε ευχαριστώ.