Θέμα: Δε λέει με πίνακες. Κόβουν μονάδες αν το κάνω;

[nikolasmer]

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

[DaKnOb]

Το συγκεκριμένο είναι σαν και το πρόβλημα του να χρησιμοποιήσεις πίνακα σε άγνωστο αριθμό επαναλήψεων σε αλγόριθμο. Μπορεί να γίνει αλλά δεν είναι 100% σωστό.

Κανονικά θα έπρεπε να μην κοπεί καμία μονάδα

[petrosp13]

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

[evry]

Στο σχολικό βιβλίο στη σελίδα 184 αναφέρει τους διδακτικούς στόχους σχετικά με τους πίνακες και ένας από αυτούς είναι:

Να είναι σε θέση ο μαθητής να αποφασίζει αν είναι απαραίτητη η χρήση πίνακα.

Υποθέτω ότι όλοι κάνουμε μάθημα βάσει των διδακτικών στόχων που θέτει το βιβλίο ή όχι?

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

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

Γενικότερα υπάρχουν και πραγματικά προβλήματα όπου δεν μπορούμε να έχουμε όλα τα δεδομένα στη μνήμη, π.χ. όταν έχουμε συνεχείς ροές δεδομένων (streams) ,
http://en.wikipedia.org/wiki/Streaming_algorithm
http://en.wikipedia.org/wiki/Online_algorithm

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

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

Ας δώσω και το παρακάτω πρόβλημα για συζήτηση:

Πρόβλημα
Να γραφτεί αλγόριθμος ο οποίος να διαβάζει 100000000 αριθμούς και να εμφανίζει τον μεγαλύτερο.

Λύση 1
Χρησιμοποιεί μια μεταβλητή για κάθε επανάληψη και μια για το max, ο κλασικός αλγόριθμος χωρίς πίνακα

Λύση 2
Τα αποθηκεύει όλα σε πίνακα και στη συνέχεια κάνει ταξινόμηση και εμφανίζει το 1ο στοιχείο

Ερώτηση: Οι δυο παραπάνω λύσεις πρέπει να βαθμολογηθούν το ίδιο κατά τη γνώμη σας;

[noname]

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

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

Όσο για το πρόβλημα που θέτει ο evry, δυστυχώς, αν και πιστεύω "επιστημονικά" ότι θα έπρεπε να κοπούν μονάδες, έτσι όπως είναι "στημένο" το μάθημα δεν θα ήταν δίκαιο να κοπούν.  Άρα τυπικά θα θεωρούσα σωστές και τις δύο λύσεις.

[petrosp13]

Πρόβλημα
Να γραφτεί αλγόριθμος ο οποίος να διαβάζει 100000000 αριθμούς και να εμφανίζει τον μεγαλύτερο.

Λύση 1
Χρησιμοποιεί μια μεταβλητή για κάθε επανάληψη και μια για το max, ο κλασικός αλγόριθμος χωρίς πίνακα

Λύση 2
Τα αποθηκεύει όλα σε πίνακα και στη συνέχεια κάνει ταξινόμηση και εμφανίζει το 1ο στοιχείο

Ερώτηση: Οι δυο παραπάνω λύσεις πρέπει να βαθμολογηθούν το ίδιο κατά τη γνώμη σας;

Ναι...

[nikolasmer]

Ναι...

Ναι και από μένα...

[gthal]

Στο παράδειγμα του Ευριπίδη κι εγώ λέω πως αξίζει να κοπούν μονάδες (για 1-2 μόρια για κάθε "παράβαση" συζητάω - κι εδώ κάνει 2 "παραβάσεις")   
Εντάξει, οι μαθητές δεν αξιολογούνται με κριτήριο την αποδοτικότητα του αλγορίθμου, με την έννοια ότι δεν ψάχνουμε την αποδοτικότερη λύση. Όμως μια κακή λύση είναι μια κακή λύση (η διαχωριστική γραμμή είναι υποκειμενική, βέβαια)
Γιατί θα έπρεπε ο μαθητής να ξέρει ότι αυτή είναι κακή λύση;
Στην παράγρ. 9.2 λέει ότι "η άσκοπη χρήση μεγάλων πινάκων μπορεί να οδηγήσει και σε αδυναμία εκτέλεσης"
πρέπει εδώ να καταλαβαίνει ότι η χρήση είναι άσκοπη (εξηγείται στην ίδια παράγραφο πότε είναι σκόπιμη) και ότι ο πίνακας είναι μεγάλος. Αν δεν συνειδητοποιεί αυτά τα δύο, έχει ένα βασικό έλλειμμα.
Επίσης δεν έχει καταλάβει την πεμπτουσία της φυσαλίδας (και της εμφώλευσης των επαναλήψεων κατ' επέκταση) και δεν αντιλαμβανεται ότι αυτος ο αλγόριθμος θα βρει το αποτέλεσμα περίπου 100000000 φορές αργότερα, που είναι πολύ σημαντικός χρόνος, ακόμα κι αν τον σκεφτεί σε δευτερόλεπτα. Αν ο μαθητής έχει καταλάβει προγραμματισμό, το καταλαβαίνει αυτό. Τι, θέλουμε να προστατέψουμε τους επιφανειακούς μαθητές και να τους εξισώσουμε με αυτούς που εμβαθύνουν;
Εν πάση περιπτώσει πιστεύω ότι ο μαθητής της 2ης λύσης είναι ή αστοιχείωτος ή "εξυπνάκιας" που θέλει να προκαλέσει τους βαθμολογητές και σε κάθε περίπτωση θεωρώ ότι πρέπει να αποθαρρύνεται, έστω και με λίγα μόρια ποινής.
Αν δεν αποθαρρύνεται, μπορεί να σκεφτεί και 3η λύση:
Αποθηκεύει τους αριθμούς στην κύρια διαγώνιο ενός 100000000 Χ 100000000 πίνακα και ταξινομεί την κύρια διαγώνιο ! 

[petrosp13]

Νομίζω ότι από τα πρώτα μαθήματα με τα παιδιά, τους περνάμε την αντίληψη ότι ο προγραμματισμός είναι ελευθερία, φαντασία, δημιουργικότητα, ενώ το μόνο στο οποίο εξετάζονται είναι εάν ο κώδικας τους υλοποιεί σωστά το ζητούμενο
Δεν μιλάμε για τραγικές καταστάσεις όπου κάποιος θα χρησιμοποιήσει 100 μεταβλητές για 100 αριθμούς
Αλλά, για να μπόρεσε κάποιος να θυμηθεί τον αλγόριθμο της φυσαλίδας, με τις όποιες δυσκολίες του, να έκανε την σωστή ταξινόμηση και να εμφανίσε το σωστό στοιχείο (πρώτο ή τελευταίο), για μένα δεν είναι λιγότερης σημασίας
Θα ακούσει σοβαρές αντιρρήσεις από μένα για την αποδοτικότητα του αλγορίθμου του, αλλά στο πλαίσιο του μαθήματος, ΔΕΝ ΜΠΟΡΩ να του αφαιρέσω μονάδες, αφού αυτό συζητάμε

[noname]

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

[petrosp13]

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

[noname]

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

[nikolasmer]

Κάποτε έδωσα εισαγωγικές εξετάσεις σε 14 μαθήματα. Σκότωμα.
Όταν αναφέρω στα παιδιά ποιά χρονιά έδωσα πανελλήνιες λαμβάνω πάντα την εξής απάντηση:"Γελοία τα θέματα".
Σήμερα τα θέματα ΑΕΠΠ δεν έχουν καμία σχέση με τότε αλλά τα ούτε και τα μαθηματικά και η φυσική. Τα μαθήματα βέβαια έγιναν 6 αλλά αυτό δεν αναιρεί το γεγονός του φόρτου και του άγχους των παιδιών. Επιπλέον σε ενα 2ωρο μάθημα δεν μπορείς να διδάξεις τη βελτιστοποίηση ενός αλγορίθμο. Τα παιδιά σου λένε "παίζει" και συ απαντάς "ναι μια χαρά". Επειδή η υπόθεση παιζεται στο νήμα ακόμα και με 2 μονάδες δεν μπορείς να γκρεμίσεις όνειρα και φιλοδοξίες ετών.

[nikolasmer]

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

[nikolasmer]

Δείτε και αυτό

Δίνεται δισδιάστατος πίνακας Α με μ γραμμές και ν στήλες. Να αντιγραφούν τα στοιχεία του γραμμή προς γραμμή σε έναν μονοδιάστατο πίνακα Β (εννοείται μ*ν στοιχείων!).

1) Με λίγους δείκτες και αριθμητικές εκφράσεις:

α) Με εμφωλευμένες Για (με 2 δείκτες για τον δισδιάστατο πίνακα):

Για i από 1 μέχρι μ
   Για j από 1 μέχρι ν
      Β[(i-1)*ν+j] <- A[i, j]
   Τέλος_επανάληψης
Τέλος_επανάληψης

β) Με μία Για (με 1 δείκτη για τον μονοδιάστατο πίνακα):

Για i από 1 μέχρι μ*ν
   B[ i ] <- Α[(i-1) div ν+1, (i-1) mod ν+1]
Τέλος_επανάληψης

2) Με ξεχωριστούς δείκτες:

α) Με μία Για:

γρ <- 1
στ <- 1
Για i από 1 μέχρι μ*ν
   B[ i ] <- Α[γρ, στ]
   στ <- στ+1
   Αν στ>ν τότε
      στ <- 1
      γρ <- γρ+1
   Τέλος_αν
Τέλος_επανάληψης

Δεν θα είχαμε πάνω από 2 -3 άτομα για τις παραπάνω λύσεις.

Άστο έτσι

κ <- 1
Για i από 1 μέχρι μ
   Για j από 1 μέχρι ν
      Β[κ] <- A[i, j]
      κ <- κ+1
   Τέλος_επανάληψης
Τέλος_επανάληψης

Μια χαρούλα είναι.