Θέμα: ΑΝΑΖΗΤΗΣΗ ΣΕ ΤΑΞΙΝΟΜΗΜΕΝΟ ΠΙΝΑΚΑ

[evry]

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

1) Γιατί χρειαζόμαστε την pos αφού το i δεν θα αλλάξει;
2) Γιατί υπάρχει αυτό το αλλιώς;
3) Γιατί να μην βάλω τη συνθηκή pos>0 αντι για την done? δεν είναι το ίδιο;
4) Μπορώ να ονομάσω τη δική μου μεταβλητή ΒΡΕΘΗΚΕ ή θα μου κόψουν τίποτα

άσε το άλλο που κάποιοι μαθητές όποια λογική μεταβλητή χρησιμοποιήσουν θα την ονομάσουν done!!! Αυτό που το πάς;

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

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

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

[pgrontas]

Πάντως παιδιά, κατά την γνώμη μου το i<-i+1 μέσα στο αλλιώς της σειριακής δεν το θεωρώ τόσο τραγικό.
Συμβαδίζει με την περιγραφή σε υψηλότερο επίπεδο που λέει: αν το βρεις σημείωσε την θέση, αλλιώς προχώρα (i<-i+1).
Αλλιώς κάποιος οξυδερκής μαθητής μπορεί να μας βουλώσει λέγοντας αφού το βρήκαμε γιατί προχωράμε; Δεν είναι περιττό βήμα, χωρίς νόημα αφού το έχεις βρει;
Έχετε δίκιο βέβαια ότι μας χαλάει τον σχηματισμό της όσο. Μπορούμε όμως να φτιάξουμε την όσο και να το παρουσιάσουμε αυτό ως μια βελτίωση μετά τον σχηματισμό της.
Και φυσικά δεν χρειάζομαστε την pos ή από την άλλη την ΒΡΕΘΗΚΕ, done, όπως λέει ο Ευριπίδης. Προσωπικά όμως νομίζω ότι η παραπάνω ερώτηση (γιατί προχωράμε δηλ. μας 'εκθέτει' περισσότερο)

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

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

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

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

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

Εντάξει, δεν πάνε όμως όλοι οι μαθητές της τεχνολογικής σε σχολές πληροφορικής αλλά τι εννοείς να την αξιολογήσεις πλήρως?

[evry]

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

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

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

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

for (int k=0; k<N;k++)
   if (A[k]==key)
       return true;
return false;
 

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

Αν και ξεφεύγω λίγο από το θέμα της αναζήτησης αλλά παραμένοντας στο πότε θα κόβονταν μονάδες από έναν αλγόριθμο.
3ο θέμα στις Πανελλήνιες των εσπερινών 2007. Σε μια άσκηση που ζητάει να υπολογίσουμε το κόστος ασφάλισης. Αφού λοιπόν έχουμε υπολογίσει γενικά το κόστος ασφάλισης μας λέει οτι προσαυξάνεται κατά 10% αν ο οδηγός είναι από 18 ως και 24 χρονών. Και επίσης έχει μια σημείωση στο τέλος ότι θεωρούμε η ηλικία είναι μεγαλύτερη του 18. Οπότε κάποιος γράφει το παρακάτω:

Αν η>=18 και η<=24 Τότε
  τελικό_κόστος <- αρχικό_κόστος + 0.10*αρχικό_κόστος
Αλλιώς_Αν η>24 Τότε
   τελικό_κόστος <- αρχικό_κόστος
Τέλος_Αν

έχουμε κάνει βασικά δυο περιττούς ελέγχους αφού μπορεί να γραφεί απλά

Αν η<=24 Τότε
 τελικό_κόστος <- αρχικό_κόστος + 0.10*αρχικό_κόστος
Αλλιώς
   τελικό_κόστος <- αρχικό_κόστος
Τέλος_Αν

ή ακόμα πιο απλά να μην είχαμε καν την μεταβλητή τελικό_κόστος και να το γράφαμε

Αν η<=24 Τότε
 αρχικό_κόστος <- αρχικό_κόστος + 0.10*αρχικό_κόστος
Τέλος_Αν

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

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

...πληρoί...

for (int k=1; k<=N;k++)
   if (A[k-1]==key)
       return true;
return false;

(αν και δεν ξέρω το γενικότερο πλαίσιο του παραπάνω τμήματος κώδικα...)

OK, παίδες, καταλάβαμε...!  Όχι άλλο!   

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

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

Σχετική ήταν και η εξής συζήτηση: https://alkisg.mysch.gr/steki/index.php?topic=2145.0

[evry]

Σωστός Νίκο το διόρθωσα

@Αλεξόπουλος Ανδρέας
Αυτό είναι το πρόβλημα. Ότι αν αρχίσουμε να κόβουμε για θέματα απόδοσης ή περιττούς υπολογισμούς τότε ανοίγουμε κυριολεκτικά το κουτί της Πανδώρας. Υπάρχουν πολλές περιπτώσεις στις οποίες μπορείς να κόψεις έλα όμως που δεν είναι όλες ίδιες. Οπότε πόσο θα κόψεις σε κάθε περίπτωση;
Η μόνη λύση στο θέμα αυτό κατά τη γνώμη μου είναι να εισάγουμε τον όρο της αλγοριθμικής τάξης οπότε θα δίνουμε μονάδες ανάλογα με την πολυπλοκότητα του αλγορίθμου που είναι μετρήσιμο χαρακτηριστικά.

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

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

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

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

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

Συμφωνώ μαζί σου Νικο ότι αυτό είναι απαράδεκτο και δεν πρέπει να συμβαίνει.

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

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

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