Ανορθόδοξοι αλγόριθμοι

Ξεκίνησε από gpapargi, 11 Ιαν 2006, 10:40:57 ΠΜ

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

gpapargi

Καλημέρα

Θα ήθελα να θέσω το εξής θέμα: Θα περιγράψω λεκτικά  4 αλγόριθμους που λειτουργούν και δίνουν σωστά αποτελέσματα αλλά είναι ανορθόδοξοι. Θα ήθελα να μου πείτε πόσους βαθμούς θα κόβατε (αν θα κόβατε) και γιατί.

Περίπτωση 1

Η άσκηση ζητάει να τυπωθούν οι αριθμοί από το 1 ως το 30. Μαθητής γράφει 30 εντολές (Τύπωσε 1, τύπωσε 2, τύπωσε 3 κλπ). Δηλαδή δε χρησιμοποιεί εντολή επανάληψης.

Περίπτωση 2

Η άσκηση ζητάει να γίνει σάρωση πίνακα και η σάρωση να διακόπτεται όταν συμβεί κάποια συνθήκη διακοπής. Ο μαθητής χρησιμοποιεί τη «Για» και όταν συμβεί η συνθήκη διακοπής βάζει το μετρητή της «Για» να είναι ίσος με την τελική τιμή της «Για» προκαλώντας τη διακοπή του βρόχου.

Περίπτωση 3

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

Περίπτωση 4

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

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

Για... να δούμε τοποθετήσεις σε αυτό το πονηρό ερώτημα  :)  

Sergio

πολύ καλή ερώτηση !!

Για να ακούσουμε απόψεις !!
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

EleniK

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

Μου έχει τύχει να συναντήσω τις περιπτώσεις 3 και 4 και δεν έκοψα μονάδες μια που το αποτέλεσμα είναι σωστό.

Εξάλλου με τι δικαιολογία να αφαιρέσεις μονάδες;  

Πάντως όντως πολύ καλή ερώτηση
Ελένη Κοκκίνου
Καθηγήτρια Πληροφορικής, ΠΕ19

peterpan

ΟΛΑ ΤΑ ΠΑΡΑΠΑΝΩ ΕΙΝΑΙ ΑΝΤΙΣΤΟΙΧΑ ΜΕ ΤΟ ΘΕΜΑ 3 ΙΟΥΝΙΟΣ 2005 ΣΤΟ ΟΠΟΙΟ ΑΠ' ΟΤΙ ΓΝΩΡΙΖΩ ΚΑΙ ΟΠΩΣ ΕΧΕΙ ΣΥΖΗΤΗΘΕΙ ΣΕ ΠΑΛΑΙΟΤΕΡΟ POST, ΟΙ ΔΙΟΡΘΩΤΕΣ ΕΒΑΖΑΝ ΤΟ ΠΟΛΥ ΤΙΣ ΜΙΣΕΣ ΜΟΝΑΔΕΣ ΧΩΡΙΣ ΝΑ ΥΠΑΡΧΕΙ ΕΠΙΣΗΜΗ ΔΙΕΥΚΡΙΝΗΣΗ ΣΕ ΟΠΟΙΟΝ ΕΙΧΕ ΛΥΣΕΙ ΤΗ ΑΣΚΗΣΗ ΜΕ «ΓΙΑ» ΑΝΤΙ ΓΙΑ «ΟΣΟ».
ΚΑΠΟΙΑ ΣΤΙΓΜΗ ΠΡΕΠΕΙ ΕΠΙΤΕΛΟΥΣ ΝΑ ΓΙΝΕΙ ΜΙΑ ΚΟΙΝΗ ΣΥΜΦΩΝΙΑ ΓΙΑ ΟΛΕΣ ΑΥΤΕΣ ΤΙΣ ΠΕΡΙΠΤΩΣΕΙΣ.   :juggle:

P.Tsiotakis

Κατά τη γνώμη μου:

- Περίπτωση 1: Σωστή. Έχεις βάλει σε εισαγωγικά τους αριθμούς; Εκτύπωσε "1", Εκτύπωσε "2", .... Σε διαφορετική περίπτωση καμία μονάδα.  Αν θες να αποτρέψεις τις "μπακαλοδουλειές" μη βάζεις 30, αλλά 3000 επαναλήψεις

- Περίπτωση 2: Τελείως Λάθος (καμία μονάδα σωστή). Στο τετράδιο μαθητή (κεφάλαιο 8 αν δεν κάνω λάθος) λέει οτι δεν πρέπει να τροποποιείται στη δομή Για η τιμή του μετρητή (και η αρχική και τελική τιμή) εντός του βρόχου.

- Περίπτωση 3: Σωστή. Κάνει αυτό που ζητάει, αρκεί η ταξινόνηση να είναι φθίνουσα, έτσι;  ;)

- Περίπτωση 4: Σωστή. Κάνει αυτό που ζητάει, αρκεί η ταξινόνηση να είναι επίσης φθίνουσα, έτσι;  ;)

Μου ξέφυγε κάτι άλλο;

spinach

ΠαράθεσηΜου ξέφυγε κάτι άλλο;
nai. to

grapse 1
grapse 2
......
grapse 30

dhladh xoris eisagogika, den einai lathos.
meta apo mia grapse mporoyme na exoyme arithmitikh timh eite ayth proerxetai apo kapoia praksh (grapse 1+1) eite einai sketh.

P.Tsiotakis


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

gpapargi

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

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

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

Αυτά συμβαδίζουν; Πρέπει να συμβαδίζουν;




EleniK

Γιώργο σχετικά με τον τελευταίο σου προβληματισμό,

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

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

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

Εξάλλου ποιος μπορεί να κρίνει αντικειμενικά την ποιότητα ενός αλγορίθμου; Μέχρι ενός σημείου γίνεται, από εκεί και πέρα;...

Σχετικά με την Περίπτωση 2 νομίζω ότι παρασύρθηκα από τις άλλες. Συμφωνώ με τον Παναγιώτη ότι είναι λάθος. Νομίζω ότι έχουμε κάνει μια παρόμοια συζήτηση για το συγκεκριμένο θέμα σε ένα άλλο topic.
  
Ελένη Κοκκίνου
Καθηγήτρια Πληροφορικής, ΠΕ19

P.Tsiotakis

Το οτι εγώ διδάσκω το μάθημα μου σωστά, δεν σημαίνει οτι κάποιος μαθητής δεν θα γράψει 30 εκτύπωσε !!

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

Θα πρέπει να ζήσουμε με αυτό ...

evry

Άσκηση: Να γραφτεί αλγόριθμος ο οποίος να υπολογίζει το άθροισμα όλων των αριθμών από 1 εώς N.

Απάντηση μαθητή: Σ <-- Ν(Ν+1)/2

Τι κάνουμε;
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

EleniK

Συγγνώμη επειδή έχουν περάσει αρκετά χρόνια από τότε που έκανα αριθμητικές σειρές, Ο τύπος αυτός σου δίνει το άθροισμα από 1 μέχρι Ν;

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

gpapargi


P.Tsiotakis


Ο μικρός Gauss δεν πούλησε μαγκιά στον καθηγητή του έτσι;

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

Εκτός κι αν ο μικρός/ή είναι "Gauss" οπότε ...



Βαγγέλης  Κανίδης

Στου διαγωνισμούς πληροφορικής (Ελληνικούς και Παγκόσμιους) μετράει μόνο το αποτέλεσμα.  Για το λόγο αυτό ζητούν πάντα το πρόγραμα που θα γράψουν να διαβάζει απο ένα αρχείο τα δεδομένα και να γράφει τα αποτελέσματα σε ένα άλλο αρχείο.  Στη συνέχεια η επιτροπή έχει ορισμένα υποδειγματικά αρχεία εισόδου και με βάση αυτά ελέγχει τι αποτέλεσμα βγάζει το κάθε πρόγραμμα και έτσι βαθμολογείται.   Δηλαδή κανένας δεν ελέγχει τον κώδικα!!!
Προσωπικά θα δεχόμουν σωστά όλα τα παραδείγματα του Παναγιώτη  ακόμα και αν το τετράδιο μαθητή αναφέρει ότι δεν αλλάζει τιμή ο μετρητής στη δομή ΓΙΑ.  (Ιστορικά -Πρίν από πολλά χρόνια ήταν ενας διαδεδομένος τρόπος  τερματισμού της ΓΙΑ  στην BASIC-.)    Κακός αλγόριθμος αλλα αλγόριθμος !!!  

Βαγγέλης

evry

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

gpapargi

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

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

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

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

Με βάση το ρητό «ότι δίνει σωστά αποτελέσματα θεωρείται σωστό», είναι δύσκολο να κόψεις πόντους στις 4 περιπτώσεις που ανέφερα στην πρώτη μου αποστολή πάνω στο θέμα. Όμως κάποιος που καταλαβαίνει το αντικείμενο, καταλαβαίνει ότι κάτι δεν πάει καλά με αυτούς τους «ανορθόδοξους αλγορίθμους». Το δικό μου ένστικτό αντιδράει πολύ έντονα. Πιστεύω ότι το μάθημα είναι σε λάθος κατεύθυνση. Και ουσιαστικά αυτό το θέμα ήθελα να θίξω. Επέλεξα περιπτώσεις που να μην μπορείς να κόψεις πόντους αλλά να κάνουν το ένστικτο να αντιδρά έντονα. Η κατασκευή αλγορίθμου είναι επιστήμη. Έχει περιορισμούς. Δεν μπορεί ο καθένας να κάνει ότι θέλει.

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

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

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

Αυτή είναι η γενική μου τοποθέτηση. Θα στείλω χωριστά και πιο συγκεκριμένα σχόλια πάνω στους αλγόριθμους που ανέφερα, στον αλγόριθμο του «μικρού Gauss» και σε κάποιες από τις απόψεις που ακούστηκαν.