Σειριακή Αναζήτηση με τη δομή Για...από...μέχρι

[agelos]

Evry καλησπέρα.Δεν του κόβω επειδή του κόβει.Του κόβω επειδή αν δεν διαβάζει όσο και να του κόβει θα κοπεί στις πανελλήνιες.

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

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

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

Από την άλλη είπα για κατηγορία "προβληματισμού" - δεν σημαίνει ότι τα αξιολογώ όλα το ίδιο. Ανέφερα "πιθανώς να έκοβα ελαφρώς κάτι βλέποντας όμως και τη συνολικότερη εικόνα του γραπτού...". Δηλαδή "πιθανώς", όχι στα σίγουρα. Σε ένα πολύ καλό γραπτό το ότι κάποιος έβαλε 1 αντί για 2 δεν είναι σημαντικό για να κόψεις...

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

[ntzios kostas]

Διάβασε α
max <- α
Για i από 1 μέχρι 20
   Διάβασε α
   Αν α>=max τότε max <- α
Τέλος_επανάληψης

Εδώ ο μαθητής διαβάζει έναν παραπάνω, οπότε κάτι πρέπει να του κόψεις

Δεν νομίζω ότι εδώ θα υπάρξουν πολλοί που θα διαφωνήσουν με αυτή την άποψη. Και αν ναι κακώς. Ο χρήστης πρέπει να δώσει 21 δεδομένα αντί για 20.

Το να σου ζητάνε  μέγιστο και να ταξινομείς όλον τον πίνακα δεν πρόκειται απλώς για περιττούς ελέγχους αλλά για κάτι πολύ περισσότερο (οπότε κατά τη γνώμη μου δεν πρέπει να το συζητάμε καν!).

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

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

Μάλλον είναι και η δικιά μου άποψη  . Μπορεί να είναι τυποποιημένη, αλλά δεν καταλαβαίνω γιατί μπακαλίστικη. Αντίθετα

Εγώ για όλα αυτά πιθανώς να έκοβα ελαφρώς κάτι βλέποντας όμως και τη συνολικότερη εικόνα του γραπτού...

αυτό το θεωρώ κάπως μπακαλίστικη. 

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

θα καταθέσω την άποψή μου για τον αλγόριθμο της αναζήτησης
Με δεδομένο ότι αναζητούμε το Key στον πίνακα Α έχουμε τον παρακάτω αλγόριθμο αναζήτησης:

Θέση<--0
Αρχή_ Επανάληψης
   Θέση<--Θέση+1
Μέχρις_ Ότου A[Θέση]= key ή Θέση=Ν
Αν Α[Θέση]= key τότε
     Εμφάνισε 'Βρέθηκε το', key, ' στη θέση', Θέση
Αλλιώς
    Εμφάνισε 'Δε βρέθηκε το', key
Τέλος_ Αν

Χρησιμοποιούμε την δομή Αρχή_ Επανάληψης διότι πρέπει να γίνει σύγκριση του key με τουλάχιστον ένα στοιχείο του πίνακα Α.
Αυτός ο αλγόριθμος είναι ο λιγότερο φλύαρος αλγόριθμος και ο περισσότερο κατανοητός από τους μαθητές.

Αν ο πίνακας είναι ταξινομημένος τότε μπορεί ο παραπάνω αλγόριθμος να τροποποιηθεί στην εντολή
"Μέχρις_ Ότου A[Θέση]>= key ή Θέση=Ν" ή
"Μέχρις_ Ότου A[Θέση]<= key ή Θέση=Ν"

Στην μεταβλητή "Θέση" έχουμε τις πληροφορίες:
α) για το αν το key υπάρχει στον πίνακα
β) και στην περίπτωση που υπάρχει σε ποια θέση

Και προπαντός να έχουμε κατά νου ότι  «Κάθε απάντηση επιστημονικά τεκμηριωμένη είναι αποδεκτή»
Το ίδιο αποτέλεσμα μπορεί να έλθει με πάρα πολλούς  διαφορετικούς τρόπους.
Στις εξετάσεις μας ενδιαφέρει η αποτελεσματικότητα του αλγόριθμου και όχι η πολυπλοκότητα του αλγόριθμου.

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

[sstergou]

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

Άσχετο αλλά αυτά είναι άμεσα σχετιζόμενα. Ένας αλγόριθμος με εκθετική πολυπλοκότητα μπορεί να μην είναι αποτελεσματικός.

[Wizard]

Θέση<--0
Αρχή_ Επανάληψης
   Θέση<--Θέση+1
Μέχρις_ Ότου A[Θέση]= key ή Θέση=Ν
Αν Α[Θέση]= key τότε
     Εμφάνισε 'Βρέθηκε το', key, ' στη θέση', Θέση
Αλλιώς
    Εμφάνισε 'Δε βρέθηκε το', key
Τέλος_ Αν

Aν η μεταβλητή "Θέση" ξεπεράσει το Ν, θα έχεις βγει από τα όρια του πίνακα και ο έλεγχος της έκφρασης A[Θέση]= key θα δημιουργήσει error.

[ntzios kostas]

Φίλε Wizard ο αλγόριθμος του Θανάση είναι σωστός. Δεν έχει το πρόβλημα που λες, αφου δεν υπάρχει περίπτωση η Θέση να γίνει Ν+1.
Επίσης, ο αλγόριθμος αυτός, όπως όλες οι δομές μέχρις_ότου γίνεται με όσο ως εξής:

Θέση<-1
όσο Θέση<Ν και Α[θέση]<>Key επανάλαβε
       θέση<-Θέση + 1
τέλος_επανάληψης

Αν Α[θέση]=key τότε
...

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

Απάντηση από τον Στάθη

Άσχετο αλλά αυτά είναι άμεσα σχετιζόμενα. Ένας αλγόριθμος με εκθετική πολυπλοκότητα μπορεί να μην είναι αποτελεσματικός.

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

Με εκτίμηση,
Ντζιός Κώστας

[Wizard]

Φίλε Wizard ο αλγόριθμος του Θανάση είναι σωστός. Δεν έχει το πρόβλημα που λες, αφου δεν υπάρχει περίπτωση η Θέση να γίνει Ν+1.

Ναι, δεν είδα καλά ότι έλεγε Θέση=Ν, σκεφτόμουνα με Θέση>Ν. 

[sstergou]

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

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

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

[pgrontas]

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

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

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

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

Το ίδιο ισχύει και για την εύρεση μεγίστου/ελαχίστου με ταξινόμηση: Αν φανταστείς ότι κάποιος για να βρεί το μικρότερο τα βάζει όλα σε σειρά τότε νομίζω ότι είναι λογικό να αναζητήσεις καλύτερο τρόπο.

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

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

Αντίθετα

Εγώ για όλα αυτά πιθανώς να έκοβα ελαφρώς κάτι βλέποντας όμως και τη συνολικότερη εικόνα του γραπτού...

αυτό το θεωρώ κάπως μπακαλίστικη. 

Τέλος πάντων! Εγώ την έννοια του "μπακαλίστικου" την χρησιμοποίησα όπως ο evry που ανέφερε ότι: "Η δουλειά μας λοιπόν σαν βαθμολογητές δεν είναι να μοιράζουμε τυποποιημένα τις μονάδες και να κάνουμε λογαριασμούς σαν μπακάληδες αλλά να προσπαθήσουμε να μπούμε στο πνεύμα του κάθε γραπτού και αν κόψουμε να είμαστε σίγουροι ότι πρόκειται για παρανόηση του μαθητή και όχι για κάποιο λάθος που δικαιολογείται από το άγχος και τη βιασύνη του." για να δείξω ότι συμφωνώ... Και όχι ότι θα βαθμολογούσα χωρίς να μελετήσω τις απαντήσεις...

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

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

Με την ευκαιρία: Έχει ποτέ συζητηθεί το ακόμα πιο σοβαρό πρόβλημα "Αν και η λύση είναι σωστή, ωστόσο δεν το καταλαβαίνει ο βαθμολογητής";

[ntzios kostas]

Με την ευκαιρία: Έχει ποτέ συζητηθεί το ακόμα πιο σοβαρό πρόβλημα "Αν και η λύση είναι σωστή, ωστόσο δεν το καταλαβαίνει ο βαθμολογητής";

Το αποφεύγουμε !!!

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

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

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

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

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

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

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

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

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

Αγαπητέ pgrontas  θα σου πω και το εξής παράλογο: αναφέρεις ότι ο μαθητής που συνεχίζει την αναζήτηση μπορεί να είναι απρόσεχτος ή να μην καταλαβαίνει τι κάνει. Σκέψου και την εκδοχή να έχει μάθε μόνο αυτόν τον τρόπο αναζήτησης. Ξέρω συναδέρφους που δεν διδάσκουν την σειριακή αναζήτηση με την ΟΣΟ αλλά μόνο με την ΓΙΑ. Όπως αναφέρουν στους μαθητές τους "είναι ένας τρόπος αναζήτησης που δουλεύει παντα"
[/quote]