Αποστολέας Θέμα: Λύσεις του Τελικού Επαναληπτικού Διαγωνίσματος 2008-2009 από το Στέκι  (Αναγνώστηκε 6091 φορές)

Laertis

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 1465
  • Δεν αντέχω την (συμ)-πίεσηηη .......
    • ΑΣΚΗΣΕΙΣ-ΘΕΜΑΤΑ ΑΕΠΠ
Οι Λύσεις Τελικού Επαναληπτικού Διαγωνίσματος 2008-2009 από την ομάδα διαγωνισμάτων του Στεκιού

Σημειώνεται ότι οι λύσεις αυτές είναι ενδεικτικές και δεν αποτελούν μοναδικό τρόπο λύσης
Νικολακάκης Γιώργος
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής
http://users.sch.gr/gnikola

klitos

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 133
Στο 1ο Θεμα το ερωτημα 3 δινεται σαν απαντηση ΣΩΣΤΟ
Το ερωτημα ειναι
"3. Κανενα αλυτο προβλημα δεν θα μπορουσε να χαρακτηριστει δομημενο"
Τα αλυτα προβληματα ειναι αυτα που εχουμε αποδειξει οτι δεν εχουν λυση . Η λυση τους ειναι οτι ειναι αλυτα.
Υπαρχουν αλυτα προβληματα ( τριχοτομηση γωνιας, διπλασιασμος κυβου κλπ ) των οποιων οι λυσεις ειναι δομημενες.
Απορια ?
κλητος χατζηγεωργιου

andreas_p

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 1014
Η λυση τους ειναι οτι ειναι αλυτα.

Αυτή η διατύπωση έχει έννοια ;

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2448
  • I 'm not young enough to know everything
Το βιβλίο στη σελίδα 17 πάνω πάνω γράφει:
«Με κριτήριο το βαθμό δόμησης των λύσεών τους, τα επιλύσιμα προβλήματα μπορούν να διακριθούν σε τρεις επίσης κατηγορίες:»

Δηλαδή το «δομημένο» είναι χαρακτηρισμός που αφορά τα επιλύσιμα προβλήματα και όχι τα άλυτα.

Δεν μπορούμε να πούμε ότι η λύση ενός άλυτου προβλήματος είναι το ότι δεν έχει λύση. Είναι κάτι σαν λογοπαίγνιο.
Βέβαια υπάρχουν διάφορα σημεία που σηκώνουν κουβέντα όπως πχ το πρόβλημα «Να λυθεί η εξίσωση 0*χ=3» είναι άλυτο κατά την ίδια έννοια που είναι άλυτο πρόβλημα ο τετραγωνισμός του κύκλου;
http://alkisg.mysch.gr/steki/index.php?topic=637.0

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

Πάντως όσο αφορά το ερώτημά του διαγωνίσματος το βιβλίο νομίζω είναι σαφές σε αυτό το σημείο.

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
  Τα τρία γνωστά από την αρχαιότητα προβλήματα, δηλαδή ο τετραγωνισμός του κύκλου, ο διπλασιασμός του κύβου (Δήλιο πρόβλημα) και η τριχοτόμηση γωνίας θεωρούνται άλυτα υπό συγκεκριμένες προυποθέσεις. Εφόσον χρησιμοποιείς για την επίλυσή τους μόνο κανόνα και διαβήτη.
Χωρίς κανόνα και διαβήτη μια χαρά επιλύσιμα είναι και μάλιστα με δομημένη λύση.
    Πρόκειται ουσιαστικά για 3 εντελώς διαφορετικά προβλήματα. Η μια κατηγορία είναι προβλήματα γεωμετρικής κατασκευής και άλλη πάει αν μπορούμε να το πούμε με πιο "μοντέρνα" μαθηματικά

http://mathforum.org/dr.math/faq/faq.impossible.construct.html


   
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

merlin

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 320
Στο 4ο θέμα, μήπως η επανάληψη στο γέμισμα του πίνακα αποστάσεων πρέπει να είναι Για γραμμή από 2 μέχρι 15; Το Αποστάσεις[1,1] δεν πρέπει να έχει κάτι μέσα.
Παρασκευάς Πανάγου
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής ΠΕ20

andreas_p

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 1014
ΓΙΑ γραμμή ΑΠΟ 1 ΜΕΧΡΙ 15            !  β) ερώτημα
      ΓΙΑ στήλη ΑΠΟ 1 ΜΕΧΡΙ γραμμή – 1

ΕΙΝΑΙ  ΣΩΣΤΟ !

Όταν γραμμή= 1 (εξ. βρόχος) 
   στήλη ΑΠΟ 1 ΜΕΧΡΙ  0 (γραμμή -1)  (εσ. βρόχος)
       
      ΔΕΝ  μπαίνει στη ΓΙΑ ,  άρα   δε 'γεμίζει'  το   Απόσταση[1, 1]

merlin

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 320
Έχεις απόλυτο δίκιο. Πλήρωσα το τίμημα της βιαστικής ανάγνωσης.
Πάντως ένας μαθητής θεωρώ ότι θα το καταλάβαινε καλύτερα με 2, έτσι δεν είναι;
Παρασκευάς Πανάγου
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής ΠΕ20

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
  Για το αν θα το καταλάβαινε καλύτερα το συζητάμε. Απλά επειδή πολλοί μαθητές έχουν συνηθίσει με έναν συγκεκριμένο τρόπο θα τους ξενίσει αυτό που θα δουν και θα τους βάλει να σκεφτούν γιατί είναι έτσι. Τη συγκεκριμένη άσκηση την είχα δώσει σε έναν μαθητή μου που είναι πολύ καλός την ξεκίνησε και αυτός από 3 και όχι από 2, και έθεσε έξω σαν Min το [2,1]. Όταν τον ρώτησα γιατί το έκανε έτσι μου είπε ότι το είδε από το σχήμα. Έτσι θεώρησα ότι θα ήταν καλό να το δώσουμε έτσι.
   Πιστεύω ότι στη συγκεκριμένη άσκηση το σχήμα μπορεί να βοηθήσει πολύ τους μαθητές στον σχεδιασμό του αλγορίθμου.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

merlin

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 320
  Για το αν θα το καταλάβαινε καλύτερα το συζητάμε. Απλά επειδή πολλοί μαθητές έχουν συνηθίσει με έναν συγκεκριμένο τρόπο θα τους ξενίσει αυτό που θα δουν και θα τους βάλει να σκεφτούν γιατί είναι έτσι. Τη συγκεκριμένη άσκηση την είχα δώσει σε έναν μαθητή μου που είναι πολύ καλός την ξεκίνησε και αυτός από 3 και όχι από 2, και έθεσε έξω σαν Min το [2,1]. Όταν τον ρώτησα γιατί το έκανε έτσι μου είπε ότι το είδε από το σχήμα. Έτσι θεώρησα ότι θα ήταν καλό να το δώσουμε έτσι.
   Πιστεύω ότι στη συγκεκριμένη άσκηση το σχήμα μπορεί να βοηθήσει πολύ τους μαθητές στον σχεδιασμό του αλγορίθμου.

Μάλλον μιλάς για την εύρεση του min. Εγώ μίλησα για το 'γέμισμα' του πίνακα στην αρχή. Έκανα λάθος όμως γιατί ήμουν βιαστικός και δεν κάθησα να σκεφτώ καθόλου βλέποντας το 1 (λες και θα έβρισκα λάθος μετά από τόσο ξεσκόνισμα από τόσο αξιόλογους συναδέλφους)

Απλά σκεφτόμενος, βλέπω από το σχήμα ότι ο πίνακας αρχίζει να γεμίζει από την 2η γραμμή (άρα ξεκινάω από το 2, δεν υπάρχει λόγος να ξεκινήσω από την 1η και να βάλω την μηχανή να κάνει extra κόπο). Βρίσκω στη συνέχεια την σχέση γραμμής - στήλης και φτιάχνω την εσωτερική επανάληψη.
Παρασκευάς Πανάγου
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής ΠΕ20

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
ναι έχεις δίκιο, μου φάνηκε ότι εννοούσες το min γιατί αυτό είναι πιο τραβηγμένο από το απλό γέμισμα επειδή ξεκινάει από την 3η γραμμή
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

merlin

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 320
ναι έχεις δίκιο, μου φάνηκε ότι εννοούσες το min γιατί αυτό είναι πιο τραβηγμένο από το απλό γέμισμα επειδή ξεκινάει από την 3η γραμμή
Καθόλου τραβηγμένο δεν μου φαίνεται. Αντιθέτως, είναι έστω και ελάχιστα πιο αποδοτικός ο αλγόριθμος ξεκινώντας από την 3η γραμμή. Ο μαθητής σου πολύ λογικά σκέφτηκε (και νομίζω είναι κατανοητό από τους περισσότερους μαθητές), το Α[2,1] είναι μόνο του στην 2η γραμμή, δεν χρειάζομαι μετρητή γραμμής για να προσπελάσω άλλο διπλανό στοιχείο, οπότε το θέτω min και ξεκινώ τις συγκρίσεις στα υπόλοιπα στοιχεία του πίνακα.

Πολλές φορές έχω παρατηρήσει (όπως και εσείς φαντάζομαι) μαθητές να θέτουν σε 2διάστατο πίνακα min το Α[1,1] και να ξεκινούν τις επαναλήψεις για γραμμή και στήλη από 2, "χάνοντας" ολόκληρη την 1η γραμμή και στήλη.

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

Παρασκευάς Πανάγου
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής ΠΕ20