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

Ξεκίνησε από giannhs555, 09 Μαρ 2010, 12:11:00 ΠΜ

« προηγούμενο - επόμενο »

evry

#15
Αν κόβουμε μονάδες από κάτι τέτοιο θα πρέπει να κόβουμε και σε όποιον μαθητή χρησιμοποιεί πίνακα όταν δεν πρέπει, αφού όπως λέει το βιβλίο οι πίνακες απαιτούν μνήμη και περιορίζουν τις δυνατότητες του προγράμματος.
  Το παραμυθάκι αυτό το ζητάμε από τους μαθητές σαν θεωρία αλλά δεν τους ζητάμε να το εφαρμόσουν στην πράξη!!! Καλό ε?
   Αφού κάθε λύση με πίνακες είναι αποδεκτή ακόμα και αν μπορεί γίνει χωρίς πίνακες γιατί να μην είναι αποδεκτή αυτή η μορφή της σειριακής αναζήτησης?
   
   Επίσης το επιχείρημα της απόδοσης δεν ισχύει. Μην ξεχνάμε πως είτε χρησιμοποιήσεις Όσο είτε Για η πολυπλοκότητα είναι η ίδια Ο(n) για πίνακα n στοιχείων. Άρα δεν υπάρχει θέμα επιστημονικότητας. Σίγουρα όταν ψάχνουμε έναν τηλεφωνικό κατάλογο σταματάμε μόλις βρούμε αυτό  που ψάχνουμε και σίγουρα μπορεί να θεωρηθεί χαζό να συνεχίσουμε και σίγουρα το λέει και το βιβλίο!!! αλλά αυτό δε σημαίνει ότι έχουμε δικαίωμα να κόψουμε μονάδες από έναν μαθητή από την στιγμή που η ποιότητα της λύσης δεν βαθμολογείται και αφού κάθε επιστημονικά τεκμηριωμένη λύση είναι αποδεκτή.
   
  Και θα πω και ένα άλλο επιχείρημα. Όταν βλέπω έναν μαθητή να εκτελεί σειριακή αναζήτηση με Για βγάζω το συμπέρασμα ότι το σκέφτηκε μόνος του. όταν βλέπω την σειριακή αναζήτηση του βιβλίου με done, pos και ειδικά αυτό το απίστευτο    αλλιώς   ι <-- ι + 1   δίνω στον μαθητή το όσκαρ της αποστήθισης αφού τα έχει μάθει καλά.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

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

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

Όπως είπε και ο Ευριπίδης, αν κοβουμε μονάδες και γι'αυτό τότε θα βρούμε πολλά λάθη σύμφωνα με το βιβλιο που πρέπει να κόψουμε.

Νίκος Αδαμόπουλος

Παράθεση από: Καρκαμάνης Γεώργιος στις 12 Μαΐου 2010, 12:24:19 ΠΜ
... πολλοί συνάδερφοι διδάσκουν  αναζήτησημόνο με ΓΙΑ και αυτήν χρησιμοποιούν κατά κατά κανόνα, και στην σειριακή αναζήτηση του βιβλιου κάνουν απλη αναφορά...

Άσχετα με το αν πρέπει να κόβονται μονάδες ή όχι, που από ότι φαίνεται οι απόψεις διίστανται, το παραπάνω κατά τη γνώμη μου είναι απαράδεκτο!  :-X

P.Tsiotakis

αν στα μαθηματικά/φυσική κάποιος μαθητής αποδείξει/λύσει κάτι σε ΜΙΑ σελίδα αν και μπορεί να το κάνει σε 5 γραμμές κόβονται μονάδες;;

Δεν είναι ειρωνική η ερώτηση, απλά αναρωτιέμαι πως αντιμετωπίζουν το ζήτημα παλιότερα/ωριμότερα από εμάς μαθήματα

Βασίλης Παπαχρήστος

Παράθεση από: evry στις 11 Μαΐου 2010, 10:37:38 ΠΜ
Αν κόβουμε μονάδες από κάτι τέτοιο θα πρέπει να κόβουμε και σε όποιον μαθητή χρησιμοποιεί πίνακα όταν δεν πρέπει, αφού όπως λέει το βιβλίο οι πίνακες απαιτούν μνήμη και περιορίζουν τις δυνατότητες του προγράμματος.
  Το παραμυθάκι αυτό το ζητάμε από τους μαθητές σαν θεωρία αλλά δεν τους ζητάμε να το εφαρμόσουν στην πράξη!!! Καλό ε?
   Αφού κάθε λύση με πίνακες είναι αποδεκτή ακόμα και αν μπορεί γίνει χωρίς πίνακες γιατί να μην είναι αποδεκτή αυτή η μορφή της σειριακής αναζήτησης?
   
   Επίσης το επιχείρημα της απόδοσης δεν ισχύει. Μην ξεχνάμε πως είτε χρησιμοποιήσεις Όσο είτε Για η πολυπλοκότητα είναι η ίδια Ο(n) για πίνακα n στοιχείων. Άρα δεν υπάρχει θέμα επιστημονικότητας. Σίγουρα όταν ψάχνουμε έναν τηλεφωνικό κατάλογο σταματάμε μόλις βρούμε αυτό  που ψάχνουμε και σίγουρα μπορεί να θεωρηθεί χαζό να συνεχίσουμε και σίγουρα το λέει και το βιβλίο!!! αλλά αυτό δε σημαίνει ότι έχουμε δικαίωμα να κόψουμε μονάδες από έναν μαθητή από την στιγμή που η ποιότητα της λύσης δεν βαθμολογείται και αφού κάθε επιστημονικά τεκμηριωμένη λύση είναι αποδεκτή.
   
  Και θα πω και ένα άλλο επιχείρημα. Όταν βλέπω έναν μαθητή να εκτελεί σειριακή αναζήτηση με Για βγάζω το συμπέρασμα ότι το σκέφτηκε μόνος του. όταν βλέπω την σειριακή αναζήτηση του βιβλίου με done, pos και ειδικά αυτό το απίστευτο    αλλιώς   ι <-- ι + 1   δίνω στον μαθητή το όσκαρ της αποστήθισης αφού τα έχει μάθει καλά.

Συγνώμη αλλά για να καταλάβω, τι εννοείς απίστευτο i <- i + 1 ;;;

Νίκος Αδαμόπουλος

...εννοεί που μπαίνει μέσα σε αλλιώς ....

Βασίλης Παπαχρήστος

Δηλαδή θέλεις να πεις πως θα ήταν προτιμότερο να μην υπήρχε καθόλου το Αλλιώς και να υπήρχε ένα απλό Αν το οποίο θα περιείχε και το i <- i + 1;;;

sstergou

Όντως αυτό το :

αλλιώς
  ι <- ι + 1

είναι άθλιο γιατί δεν σου επιτρέπει να σχηματίσεις σταδιακά τον αλγόριθμο.

Ξεκινάς με μια δομή επανάληψης η οποία προσπελαύνει όλα τα στοιχεία του πίνακα
Όσο ι <= Ν επανάλαβε

  ι <- ι + 1
Τέλος_επανάληψης

και στη συνέχεια προσθέτεις τον έλεγχο, την λογική μεταβλητή την θέση κοκ.

Το μόνο που στα χαλάει για να καταλήξεις στον αλγόριθμο του βιβλίου είναι αυτό το ρημάδι το αλλιώς!

Φαντάζομαι αυτό εννοεί και ο Ευριπίδης.

Νίκος Αδαμόπουλος

Παράθεση από: Τσιωτάκης Παναγιώτης στις 12 Μαΐου 2010, 10:13:31 ΠΜ
αν στα μαθηματικά/φυσική κάποιος μαθητής αποδείξει/λύσει κάτι σε ΜΙΑ σελίδα αν και μπορεί να το κάνει σε 5 γραμμές κόβονται μονάδες;;

Δεν είναι ειρωνική η ερώτηση, απλά αναρωτιέμαι πως αντιμετωπίζουν το ζήτημα παλιότερα/ωριμότερα από εμάς μαθήματα

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

Προσωπικά, με την τρέχουσα μορφή που έχει το μάθημα, δεν έχω αποφασίσει με ποια άποψη είμαι περισσότερο σύμφωνος...

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

Βασίλης Παπαχρήστος

Παράθεση από: sstergou στις 12 Μαΐου 2010, 01:10:52 ΜΜ
Όντως αυτό το :

αλλιώς
  ι <- ι + 1

είναι άθλιο γιατί δεν σου επιτρέπει να σχηματίσεις σταδιακά τον αλγόριθμο.

Ξεκινάς με μια δομή επανάληψης η οποία προσπελαύνει όλα τα στοιχεία του πίνακα
Όσο ι <= Ν επανάλαβε

  ι <- ι + 1
Τέλος_επανάληψης

και στη συνέχεια προσθέτεις τον έλεγχο, την λογική μεταβλητή την θέση κοκ.

Το μόνο που στα χαλάει για να καταλήξεις στον αλγόριθμο του βιβλίου είναι αυτό το ρημάδι το αλλιώς!

Φαντάζομαι αυτό εννοεί και ο Ευριπίδης.

Υπάρχει πάντως λογική μιας και θεωρείς πως στην περίπτωση που βρεθεί το προς αναζήτηση στοιχείο δεν υπάρχει λόγος να συνεχίσεις να προσπελαύνεις τον πίνακα. Φαντάζομαι αυτό ήθελε να τονίσει ο αλγόριθμος που παρουσιάζεται στο βιβλίο. Θα ήταν βέβαια πιο κομψό αν δεν χρησιμοποιούσε κάθολου το pos και σου έλεγε πως αν το στοιχείο έχει βρεθεί, η θέση του είναι το ίδιο το i.

Νίκος Αδαμόπουλος

Παράθεση από: Βασίλης Παπαχρήστος στις 12 Μαΐου 2010, 01:01:56 ΜΜ
Δηλαδή θέλεις να πεις πως θα ήταν προτιμότερο να μην υπήρχε καθόλου το Αλλιώς και να υπήρχε ένα απλό Αν το οποίο θα περιείχε και το i <- i + 1;;;

Το  i <- i + 1 θα μπορούσε να βρίσκεται έξω από την Αν και πριν το Τέλος_επανάληψης. Με αυτόν το τρόπο η Όσο θα ερχόταν πιο κοντά στη Για για την οποία γίνεται παράλληλη συζήτηση και άρα οι μαθητές (και όχι μόνο!) θα έβλεπαν ουσιαστικά ότι η Όσο της σειριακής αναζήτησης είναι ουσιαστικά μια ενισχυμένη Για (τώρα από κάπου το έχω κλέψει αυτό!) με δυνατότητα γρηγορότερου τερματισμού...

Βασίλης Παπαχρήστος

Παράθεση από: Νίκος Αδαμόπουλος στις 12 Μαΐου 2010, 01:18:58 ΜΜ
Το  i <- i + 1 θα μπορούσε να βρίσκεται έξω από την Αν και πριν το Τέλος_επανάληψης. Με αυτόν το τρόπο η Όσο θα ερχόταν πιο κοντά στη Για για την οποία γίνεται παράλληλη συζήτηση και άρα οι μαθητές (και όχι μόνο!) θα έβλεπαν ουσιαστικά ότι η Όσο της σειριακής αναζήτησης είναι ουσιαστικά μια ενισχυμένη Για (τώρα από κάπου το έχω κλέψει αυτό!) με δυνατότητα γρηγορότερου τερματισμού...
ok κατανοητό! ευχαριστώ για τη διευκρίνιση

Νίκος Αδαμόπουλος

Παράθεση από: Νίκος Αδαμόπουλος στις 12 Μαΐου 2010, 01:18:58 ΜΜ
... είναι ουσιαστικά μια ενισχυμένη Για (τώρα από κάπου το έχω κλέψει αυτό!) με δυνατότητα γρηγορότερου τερματισμού...

Το βρήκα: https://alkisg.mysch.gr/steki/index.php?topic=2373.msg19244#msg19244

Και ένα σχετικό θέμα: https://alkisg.mysch.gr/steki/index.php?topic=2531.msg21229#msg21229

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

Δεν νομίζω ότι είναι επιστημονικά τεκμηριωμένη λύση η χρήση της Για κατά την αναζήτηση σε ταξινομημένο.

Μάλλον είναι τεκμηριωμένο ότι δεν είναι σωστή λύση και μάλιστα είναι και αντιεπιστημονική.

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

Όμως η αναζήτηση σε ταξινομημένο...

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

Πέρσι στα θέματα μπήκε η εντολή

Αν συνθήκη τότε Αντιμετάθεσε x, y
...

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

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

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

evry

Παράθεση από: sdoukakis στις 12 Μαΐου 2010, 01:28:43 ΜΜ
Δεν νομίζω ότι είναι επιστημονικά τεκμηριωμένη λύση η χρήση της Για κατά την αναζήτηση σε ταξινομημένο.

Μάλλον είναι τεκμηριωμένο ότι δεν είναι σωστή λύση και μάλιστα είναι και αντιεπιστημονική.
Ποια αναζήτηση έχεις στο μυαλό σου? Η δυαδική δεν είναι εκτός ύλης? Αν εννοείς τη σειριακή σκέψου ότι κάνει μια σύγκριση παραπάνω για να ελέγξει αν α[ι]>key οπότε το overhead που έχεις από αυτό δεν ξέρω αν σου δίνει τόσο καλή απόδοση. Αν υπολογίσεις τις μέσες χρονικές πολυπλοκότητες των 2 αλγορίθμων θα δεις ότι δεν έχουν και τόσο μεγάλη διαφορά.
Αυτό λοιπόν που λες ισχύει εφόσον οι μαθητές έχουν διδαχθεί την δυαδική αναζήτηση. Αν δεν έχουν διδαχθεί αυτή την αναζήτηση γιατί θα το βαθμολογήσεις λάθος? Δεν είναι τραβηγμένο? Θα σου δώσω ένα παράδειγμα για να καταλάβεις γιατί στο μάθημα που διδάσκουμε με αυτή τη μορφή δεν μπορείς να κόψεις μονάδες από κάτι τέτοιο:

Ζητήθηκε από έναν μαθητή να εμφανίσει το στοιχείο που βρίσκεται στην 3η γραμμή και την 7η στήλη ενός πίνακα ΝxN και έδωσε τον παρακάτω αλγόριθμο

Για γ από 1 μέχρι Ν
   Για σ από 1 μέχρι Ν
       Αν (γ=3 και σ=7)  Τότε   Εμφάνισε Α[γ,σ]
   Τέλος_Επανάληψης
Τέλος_Επανάληψης


Θα μπορούσες να κόψεις από αυτό? Προφανώς όχι γιατί η έννοια της επίδοσης του αλγορίθμου δεν είναι στην ύλη. Εδώ λοιπόν έχουμε ένα πρόβλημα που μπορεί να λυθει με αλγόριθμο πολυπλοκότητας Ο(1) και ο μαθητής το λύνει με αλγόριθμο τάξης O(n^2) και δεν του κόβουμε και εσύ προτείνεις να κόβουμε για λύση η οποία έχει την ίδια πολυπλοκότητα O(n) με τη βέλτιστη? Δεν σου φαίνεται λίγο παράδοξο?

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

Παράθεση
Να πω και κάτι τελευταίο. Σύμφωνα με το ΠΣ (πρόγραμμα σουδών) πρετοιμάζουμε μαθητές και για την τριτοβάθμια εκπάιδευση. Αποτελεί βασικό θέμα των δομών δεδομένων η αναζήτηση και αφού μπορούμε σε επίπεδο στατικών δομών να την αξιολογήσουμε πλήρως , θεωρώ ότι είναι σημαντικό να την αξιολογούμε πλήρως.
Εντάξει, δεν πάνε όμως όλοι οι μαθητές της τεχνολογικής σε σχολές πληροφορικής αλλά τι εννοείς να την αξιολογήσεις πλήρως?
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr