Θέμα: Τα λάθη πλεονασμοί στο βιβλίου του μαθήματος ΑΕσΠΠ

[anasta]

1. Στον αλγόριθμο της σελίδας 33 του τετραδίου του Μαθητή υπάρχει ο παρακάτω αλγόριθμος τι εκφράζουν τα L,M γιατί δεν δηλώνονται στα δεδομένα;
Ο σωστός αλγόριθμος θα ήταν:
Αλγόριθμος Αραιός
Δεδομένα // sparse, n, L, M //
! sparse πίνακας μονοδιάστατος 3*Ν θέσεων
! L:γραμμές του δισδιάστατου αραιού πίνακα
!M:στήλες του δισδιάστατου αραιού πίνακα
για κ από 0 μέχρι Ν με βήμα 3 επανάλαβε
 i <- sparse [k+1]
 j <- sparse [k+2]
 result <- sparse [k+3]
Αν i <=L και j< =M τότε
Result[I, j] <- sparse [k+3]
Τέλος_αν
Τέλος_επανάληψης
Αποτελέσματα // result //
Τέλος Αραιός

Sto paradeigma auto leipei h parakatw entolh :
ΔΙΑΒΑΣΕ L, M
opou o xrhsths thelei na mathei an sthn grammh L kai sthlh M tou arxikou disdiastatou pinaka uparxei mh mhdeniko stoixeio.
o algorithmos tou paradeigmatos psaxnei ston modiastato pinaka.
to "AN i=L kai j=M TOTE" briskei to mh mhdeniko stoixeio k to epistrefei.
to "ΑΛΛΙΩΣ_ΑΝ (i>L 'Η (i=L ΚΑΙ j>M)) ΤΟΤΕ" termatizei ton algorithmo gia na mhn psaxnei askopa
kai to ΑΛΛΙΩΣ κ<-κ+1 apla metakinei ton deikth gia ton elegxo twn upoloipwn omadwn-triadwn.
 

[nplatis]

Σελ. 138, στο κεφ. 6.

Οι παράγραφοι 2-3 αναφέρουν ότι από το πηγαίο πρόγραμμα ο μεταγλωττιστής παράγει το αντικείμενο πρόγραμμα, το οποίο κατόπιν ο συνδέτης/φορτωτής το συνδέει με τις βιβλιοθήκες και παράγει το εκτελέσιμο πρόγραμμα, «το οποίο είναι το τελικό πρόγραμμα που εκτελείται από τον υπολογιστή» (το κείμενο μέσα στα εισαγωγικά ακριβής αντιγραφή από το βιβλίο, η υπογράμμιση δική μου).

Παρόλα αυτά το Σχήμα 6.5 έχει στη μέση την ένδειξη «Τελικό πρόγραμμα», εκεί που θα περίμενε κανείς να είναι το «Αντικείμενο πρόγραμμα».

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


Να επισημάνω επίσης ότι στο σχετικό διαγώνισμα που έφτιαξε η ομάδα από το «Στέκι», στο θέμα 2.ΙΙ.Α φαίνεται να ζητείται η σειρά του σχήματος -- παρόλα αυτά εγώ όταν βλέπω «τελικό πρόγραμμα» έχω μία τάση να το βάζω στο τέλος :-)

[KillBill]

Στον αλγόριθμο του Μαγικού τετραγώνου Τετράδιο του Μαθητή σελίδα 41 πρέπει να γίνουν οι εξής αλλαγές:

H εντολή κ<--n-1 πρέπει να αλλαχθεί σε k<--n (αυτό αναφέρεται και στις διορθώσεις του Π.Ι)
H εντολή l<--n-1 πρέπει να αλλαχθεί σε l<--n (αυτό δεν αναφερόταν)

Να σημειωθεί ότι ο αλγόριθμος αυτός είχε μπει στα θέματα ΟΕΦΕ 2006 χωρίς τις απαραίτητες διορθώσεις με αποτέλεσμα κάποια στοιχεία να παραμένουν συνεχώς μηδέν και οι μαθητές να χάσουν πολύ χρόνο ψάχνοντας το λάθος που τελικά υπήρχε στον ίδιο τον αλγόριθμο

[Βρακόπουλος Αθανάσιος Λ.]

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

Παρακαλώ ας μου εξηγήσει κάποιος από τους συγγραφείς του βιβλίου και όχι μόνο, τι σημαίνει το "λιγότερη αποτελεσματική".

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

[gpapargi]

Το "λιγότερο αποτελεσματική" σημαίνει ότι είναι πολύ αργή. Αν ο πίνακας είναι ταξινομημένος τότε μπορεί να εφαρμοστεί η δυαδική αναζήτηση που είναι ασύγκριτα γρηγορότερη.

Πχ σε ταξινομημένο πίνακα με 2³³ = περίπου 8.5 δισεκατομμύρια θέσεις η σειριακή αναζήτηση θέλει έλεγχο σε κάθε ένα από 2³³ τα στοιχεία του πίνακα (στη χειρότερη περίπτωση). Η δυαδική θέλει μόνο 33 βήματα. 

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

[evry]

   Νομίζω ότι με αποτελεσματική μάλλον θέλει να πει αποδοτική. Το αποτελεσματική δε μου φαίνεται και πολύ σωστό

[alkisg]

Η πρόταση "λιγότερο αποτελεσματικός αλγόριθμος" εμένα μου φαίνεται συνώνυμο του "λιγότερο αποδοτικός αλγόριθμος".

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

Γράφω όλο το κομμάτι από το βιβλίο του Knuth επειδή δεν το βρήκα στο google, και αρκετοί συνάδελφοι ρωτάνε συχνά για παράδειγμα αλγορίθμου που παραβιάζει την "αποτελεσματικότητα".

Effectiveness. An algorithm is also generally expected to be effective. This means that all of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a man using pencil and paper. Algorithm E uses only the operations of dividing one positive integer by another, testing if an integer is zero, and setting the value of one variable equal to the value of another. These operations are effective, because integers can be represented on paper in a finite manner and there is at least one method (the "division algorithm") for dividing one by another. But the same operations would not be effective if the values involved were arbitrary real numbers specified by an infinite decimal expansion, nor if the values were the lengths of physical line segments, which cannot be specified exactly. Another example of a non effective step is, "If 2 is the largest integer n for which there is a solution to the equation xⁿ + yⁿ = zⁿ in positive integers x, y, and z, then go to step E4." Such a statement would not be an effective operation until someone succeeds in showing that there is an algorithm to determine whether 2 is or is not the largest integer with the stated property.

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