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

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

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

evry

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

gpapargi

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

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

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

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

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

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

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

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

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