ΑΝΑΖΗΤΗΣΗ ΣΕ ΤΑΞΙΝΟΜΗΜΕΝΟ ΠΙΝΑΚΑ

[giannhs555]

ΚΑΛΗΣΠΕΡΑ,

ΠΑΡΑΚΟΛΟΥΘΩ ΤΙΣ ΣΥΖΗΤΗΣΕΙΣ  ΠΟΥ ΕΧΟΥΝ ΓΙΝΕΙ ΣΧΕΤΙΚΑ ΜΕ ΤΗ ΣΕΙΡΙΑΚΗ ΑΝΑΖΗΤΗΣΗ ΣΕ ΤΑΞΙΝΟΜΗΜΕΝΟ ΠΙΝΑΚΑ. ΕΠΕΙΔΗ ΕΧΟΥΝ ΔΙΑΤΥΠΩΘΕΙ ΔΙΑΦΟΡΕΣ ΓΝΩΜΕΣ ΚΑΙ ΔΙΑΦΟΡΟΙ ΑΛΓΟΡΙΘΜΟΙ, ΤΕΛΙΚΑ ΥΠΑΡΧΕΙ ΚΑΤΙ ΣΥΓΚΕΚΡΙΜΕΝΟ ΤΟ ΟΠΟΙΟ ΜΠΟΡΟΥΜΕ ΝΑ ΔΙΔΑΣΚΟΥΜΕ ΣΤΟΥΣ ΜΑΘΗΤΕΣ?

ΕΥΧΑΡΙΣΤΩ ΓΙΑ ΤΟΝ ΧΡΟΝΟ ΣΑΣ.

[Laertis]

Συγκεκριμένος αλγόριθμος δεν υπάρχει στο βιβλίο αλλά υπάρχουν οι οδηγίες για να τον φτιάξεις (Κεφ. 3 σελ. 64).  Στην ουσία είναι ο αλγόριθμος σειριακής αναζήτησης που δίνεται στο βιβλίο με την προσθήκη μιας ακόμη συνθήκης όπου το στοιχείο του πίνακα είναι μεγαλύτερο της τιμής αναζήτησης.
Δες στο παρακάτω link απο το site του Παναγιώτη :

http://users.kor.sch.gr/ptsiotakis/aepp/aepp_theory3b.htm

[sstergou]

Δες και αυτόν, ίσως σου φανεί χρήσιμος

Αλγόριθμος σειριακή_αναζήτηση_ταξινομημένος
Δεδομένα //π, Ν, τιμή//

ξεπέρασε ← Ψευδής
βρέθηκε ← Ψευδής
θέση ← 0
ι ← 1

Όσο όχι βρέθηκε και όχι ξεπέρασε και ι ≤ Ν επανάλαβε
	Αν π[ι] = τιμή τότε
		βρέθηκε ←  Αληθής
		θέση ← ι
	αλλιώς_αν π[ι] > τιμή τότε
		ξεπέρασε ← Αληθής
	Τέλος_αν
	ι← ι + 1
Τέλος_επανάληψης

Αποτελέσματα //βρέθηκε, θέση//
Τέλος σειριακή_αναζήτηση_ταξινομημένος

[giannhs555]

ΕΧΩ ΔΕΙ ΤΟΝ ΑΛΓΟΡΙΘΜΟ ΤΟΥ ΠΑΝΑΓΙΩΤΗ. ΕΙΝΑΙ ΜΙΑ ΚΑΛΗ ΛΥΣΗ.

ΝΟΜΙΖΩ ΟΜΩΣ ΟΤΙ ΔΕΝ ΚΑΛΥΠΤΕΙ ΤΗΝ ΠΕΡΙΠΤΩΣΗ ΝΑ ΒΡΕΙ ΟΛΕΣ ΤΙΣ ΘΕΣΕΙΣ ΤΟΥ ΣΤΟΙΧΕΙΟΥ ΠΡΟΣ ΑΝΑΖΗΤΗΣΗ, ΟΤΑΝ ΑΥΤΟ ΥΠΑΡΧΕΙ ΣΕ ΠΕΡΙΣΣΟΤΕΡΕΣ ΑΠΟ ΜΙΑ.

ΜΗΠΩΣ ΤΟ ΠΟΤΕ ΘΑ ΣΤΑΜΑΤΑ Ο ΑΛΓΟΡΙΘΜΟΣ ΘΑ ΕΠΡΕΠΕ ΝΑ ΕΙΝΑΙ ΑΝΕΞΑΡΤΗΤΗ ΛΟΓΙΚΗ ΜΕΤΑΒΛΗΤΗ ΑΠΟ ΑΥΤΗ ΠΟΥ ΔΗΛΩΝΕΙ ΟΤΙ ΤΟ ΣΤΟΙΧΕΙΟ ΒΡΕΘΗΚΕ?

[Laertis]

Στην περίπτωση αυτή η λύση του Στάθη είναι ενδεδειγμένη βάζοντας μάλιστα σε πίνακα με δείκτη μετρητή τις θέσεις των στοιχείων που βρέθηκαν. Μεταφέρω απο τη λύση του Στάθη:
.......
κ <--0
Όσο όχι βρέθηκε και όχι ξεπέρασε και ι ≤ Ν επανάλαβε
   Αν π[ι] = τιμή τότε
      βρέθηκε ←  Αληθής
      κ <-- κ +1
      θέση[κ] ← ι
   αλλιώς_αν π[ι] > τιμή τότε
........

[sstergou]

το "όχι βρέθηκε" όμως πρέπει να φύγει από πάνω οπότε η όσο γίνεται :
....
Όσο όχι ξεπέρασε και ι ≤ Ν επανάλαβε
...

[Laertis]

Σωστά Στάθη 

[Σπύρος Δουκάκης]

Ευκαιρία να εξετασθεί και ως υποερώτημα σε θέμα εξετάσεων...

[Σπύρος Δουκάκης]

Επανέρχομαι λίγο στο θέμα για τον ακόλουθο λόγο...

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

Την πρόταση αυτή την έχω ερμηνεύσει ως εξής:

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

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

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

[Σπύρος Δουκάκης]

Είναι μία προσέγγιση και αυτή. Δεν έχει λειτουργήσει έτσι μέχρι σήμερα. Το ερώτημα είναι γιατί δεν λαμβάνουμε υπόψη τα πρέπει του βιβλίου; Μας βοηθούν να κάνουμε πιο αποδοτικούς αλγορίθμους, που είναι και πιο κοντά στην ανθώπινη σκέψη.

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

[ntzios kostas]

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

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

Είναι μία προσέγγιση και αυτή. Δεν έχει λειτουργήσει έτσι μέχρι σήμερα. Το ερώτημα είναι γιατί δεν λαμβάνουμε υπόψη τα πρέπει του βιβλίου; Μας βοηθούν να κάνουμε πιο αποδοτικούς αλγορίθμους, που είναι και πιο κοντά στην ανθώπινη σκέψη.

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

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

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

[Σπύρος Δουκάκης]

Θα προσπαθήσω να κάνω μία συνολική τοποθέτηση επί του θέματος της αναζήτησης, της ταξινόμησης και της εύρεσης min και max.

Οδηγός μου θα είναι το βιβλίο μαθητή.

Πρώτα από όλα θεωρώ ότι κανείς εκπαιδευτικός:
α) δεν παροτρύνει τους μαθητές και τις μαθήτριες να χρησιμοποιούν πάντα στην αναζήτηση τη Για είτε ζητάει την ύπαρξη είτε ζητάει το πλήθος, είτε είναι, είτε δεν είναι ταξινομημένος. Άρα νομίζω ότι όλοι μας συμπορευόμαστε με το βιβλίο μαθητή και πράττουμε βάσει αυτού.
β) δεν υποκινεί τους μαθητές και τις μαθήτριες να κάνουν ταξινόμηση για να βρουν το max ή το min.
γ) δεν ενθαρρύνει τους μαθητές και τις μαθήτριες να κάνουν εύρεση του min και max με τη γνωστή διαδικασία, αν ο πίνακας είναι ταξινομημένος.

Πάμε τώρα στο βιβλίο. Στην αναζήτηση, σελ. 64, λέει τα ακόλουθα:

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

2. "... ο προηγούμενος (εννοεί τον αλγόριθμο με το done και το Όσο) αλγόριθμος ισχύει για την περίπτωση όπου κάθε στοιχείο υπάρχει μία μόνο φορά στον πίνακα".

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

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

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

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

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

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

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

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

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

Τέλος, θα ήθελα να επανέλθω σε κάτι που όλοι το συζητάμε και το θέλουμε.

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

θα έχουμε επιτύχει ως δάσκαλοι.

[Αλεξόπουλος Ανδρέας]

κι εμένα η άποψή μου είναι ότι κακώς κόβονται μονάδες σε περίπτωση που κάποιος κάνει αναζήτηση με το ΓΙΑ αντί του ΟΣΟ. Θα συμφωνήσω με τον sdoukakis (δυστυχώς δε ξέρω ποιο είναι το κανονικό σου όνομα για να το γράψω!) ότι πρέπει να καλλιεργούμε στους μαθητές την σκέψη να χρησιμοποιούν αποδοτικά τους αλγορίθμους. Αλλά αυτό δεν συνιστά λόγο να κόψω σε κάποιον μονάδες επειδή ο αλγόριθμός του κάνει σάρωση σε όλον τον πίνακα ενώ θα μπορούσε να είχε σταματήσει. Εξάλλου η αποδοτικότητα των αλγορίθμων είναι κάτι που δεν μας απασχολεί στα πλαίσια αυτού του μαθήματος.
Χωρίς να διαφωνώ λοιπόν με το σκεπτικό σου παραπάνω (και ίσως θέλοντας να κάνω τον δικηγόρο του διαβόλου) να σου φέρω ένα αντιπαράδειγμα. Ακόμα κι αν θέλουμε λοιπόν να πάρουμε αυτά που λέει το βιβλίο κατά γράμμα, ότι πρέπει δηλαδή εξ ορισμού να σταματάμε όταν βρούμε κάτι που ξέρουμε ότι υπάρχει μια φορά. Αυτό σε ποιον αλγόριθμο ισχύει; Στον αλγόριθμο που ονομάζει το βιβλίο Σειριακή Αναζήτηση. Στο θέμα πανελληνίων λοιπόν του 2006 γιατί να κοπούν μονάδες; Το ερώτημα εννοεί ότι πρέπει να γίνει αναζήτηση για να δούμε αν η πόλη υπάρχει, αλλά δε μας λέει με ποιον τρόπο πρέπει να γίνει. Τι θέλω να πω: Ότι αν έλεγε να ψάξετε να βρείτε αν υπάρχει η πολή χρησιμοποιώντας τον αλγόριθμο της σειριακής αναζήτησης, τότε ναι να κοπούν μονάδες αν κάποιος το κάνει με Για (ακόμα κι αν δεν αναφέρεται στην εκφόνιση ότι η αναζήτηση πρέπει να σταματάει όταν η πόλη βρεθεί). Από την στιγμή όμως που δεν αναφέρεται σχεδόν σε καμμία άσκηση ο όρος Σειριακή Αναζήτηση αλλά αφήνεται στον μαθητή να σκεφτεί το πώς θα ψάξει να βρει αν κάτι υπάρχει, τότε δε πρέπει να κοπούν μονάδες. Ακόμα κι αν αυτό που θα κάνει δεν έχει την καλύτερη απόδοση σαν ταχύτητα αλγορίθμου.
Και για να το πάω και λίγο παραπέρα (χωρίς να το τονίσω να θέλω να έρθω σε αντιπαράθεση με κανέναν, απλά μια σκέψη κάνω) γιατί να μην κοπούν πχ μονάδες και από κάποιον που χρησιμοποίησε σε ένα πρόγραμμα δυο-τρεις μεταβλητές παραπάνω από αυτές που πιθανώς χρειαζόντουσαν; Θα μπορούσα πχ να πω ότι το πρόγραμμα λύνεται και πιο απλά. Το ξέρω ότι είναι πολύ τραβιγμένο αυτό το τελευταίο που γράφω, απλά το λέω για να δείξω πως αφού δεν εξετάζουμε την αποδοτικότητα (ταχύτητα) ενός αλγορίθμου τότε θεωρώ άδικο πώς από την στιγμή που δεν δηλώνεται ξεκάθαρα σε μια άσκηση, να κόβονται μονάδες επειδή μια αναζήτηση γίνεται με ΓΙΑ αντί του ΟΣΟ.

Και κάτι τελευταίο. Ακόμα κι αν ο μαθητής έχει στο μυαλό του ότι θα μπορούσε να χρησιμοποιήσει σε μια άσκηση την σειριακή αναζήτηση με το done, το ΟΣΟ κλπ , αν δε του το ζητάει η άσκηση συνήθως δε το κάνει γιατί η λύση με το ΓΙΑ είναι πιο σύντομη (άποψή μου, αλλά νομίζω ότι ισχύει αυτό)