Αποστολέας Θέμα: Τροποποίηση άσκησης πανελληνίων για πολύ δυνατούς λύτες  (Αναγνώστηκε 3145 φορές)

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Μπορείς αν σαρώσεις 0,1,-1,2,-2,3,-3 κλπ

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 193
@bugman

Μπορείς, αποκλείεται να κάνεις άπειρες ερωτήσεις. Έστω m ο ακέραιος αριθμός που είναι γραμμένος στο χαρτί:

Είναι ο 0;
Είναι ο 1;
Είναι ο -1;
Είναι ο 2;
Είναι ο -2;
Είναι ο 3;
Είναι ο -3;
...
Είναι ο m;

Θα πέσεις πάνω στον αριθμό m σε πεπερασμένο πλήθος ερωτήσεων. Αυτό από μια πιο θεωρητική άποψη αποδεικνύει ότι "το σύνολο των ακέραιων είναι αριθμήσιμο (countable)".
« Τελευταία τροποποίηση: 08 Νοέ 2017, 11:20:18 πμ από gbougioukas »

bugman

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 530
  • The Bug Eater
    • Πληροφορική Προγραμματισμός
Η δική μου απάντηση παραμένει: Αν το γράψεις στο χαρτί πχ 1231231231230120381928391283918318239 θα πεθάνω πριν το  βρω με τον "αλγόριθμο" του gpapargi.
Ένας αλγόριθμος οφείλει να βρίσκει λύση σε εύλογο χρονικό διάστημα, αλλιώς δεν είναι αλγόριθμος.
Αν όμως ο ακέραιος βρίσκεται σε ένα πεπερασμένο διάστημα, πχ 0 έως 255 (για ένα byte ακέραιο, χωρίς πρόσημο) ή 0 έως 65535 ( για δυο bytes ακέραιο χωρίς πρόσημο) τότε  σαρώνεις 256 νούμερα ή 65536 νούμερα κάτι που δεν είναι αργό. Όμως έτσι έχεις από πριν την περιοχή.
Στο ερώτημα με "άνευ" περιοχής αναζήτηση η απάντηση είναι σε άπειρο χρόνο...άρα μη εφικτό για αλγόριθμο!

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Ένας δεδομένος ακέραιος, οσοδήποτε μεγάλος και να είναι, παραμένει πεπερασμένος. Σε καμία περίπτωση δεν είναι άπειρος. Για την ακρίβεια απέχει άπειρα πολύ από το άπειρο.
Έχει σημασία το ότι ο ακέραιος είναι ήδη γραμμένος σε χαρτί. Είναι άλλο πράγμα το να ψάχνεις για τις λύσεις μιας διοφαντικής χωρίς να ξέρεις αν υπάρχει η λύση. Το βιβλίο το αναφέρει αυτό ως υπολογιστική διαδικασία και όχι αλγόριθμο γιατί δεν ξέρεις αν τερματίζει.

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

bugman

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 530
  • The Bug Eater
    • Πληροφορική Προγραμματισμός
Νομίζω ο πιο γρήγορος αλγόριθμος έχει την γνωστή ελληνική περιφραστική ονομασία "να το πάει το ποτάμι". Είναι η τεχνική που ψήνει αυτόν που γνωρίζει τον αριθμό να τον πει χωρίς κανένα άλλο πεπερασμένο βήμα παρά αυτό της μιας ερώτησης "αν έλεγες ..να το πάρει το ποτάμι και απαντούσαμε ναι, ποιος αριθμός θα ήταν;".  Σε αυτή την περίπτωση υπάρχει ένα πρόβλημα να μην έχουμε λύση αν απορριφθεί η πρόταση, αλλά είναι ισοδύναμο με το να μην έχουμε λύση αν ψάχνουμε με τον "σωστό" αλγόριθμο για χρόνια και δεν τελειώνει...(μπορεί να πεθάνει και αυτός που ξέρει τον αριθμό-λύση), από την άλλη μεριά όμως μπορεί να πιάσει, και να πάρουμε την λύση!

gbougioukas

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 193
@bugman

Ο καθένας είναι ελεύθερος να ορίσει το άπειρο ή οποιαδήποτε άλλη έννοια θέλει όπως του αρέσει, ακόμα και να εισάγει νέα Μαθηματικά. It's Ok. Επειδή όμως εδώ είναι η κατηγορία ΑΕΠΠ, η οποία βασίζεται στα συνήθη Μαθηματικά, και διαβάζουν μαθητές που δίνουν εξετάσεις, να ξεκαθαρίσουμε ότι:

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

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

Επομένως, η εν λόγω διαδικασία τερματίζει σε πεπερασμένο πλήθος βημάτων. Και επειδή πληρούνται και οι άλλες προϋποθέσεις που θέτει το σχολικό βιβλίο είναι όντως αλγόριθμος, με βάση το  σχολικό βιβλίο πάντα.
-----------------------------------------------------------
Παρεμπιπτόντως, με την λογική αυτή που λες ούτε η λύση στο αρχικό πρόβλημα που παρουσιάζεις παραπάνω είναι αλγόριθμος, αφού, για παράδειγμα, για ελάχιστη τιμή μεταβλητής -2^112 (πίνακας κάτω[10] στην λύση σου) και μέγιστη 2^134 (πίνακας πάνω[10] στην λύση σου) ο χρόνος είναι "άπειρος" (με βάση τον δικό σου ορισμό του απείρου)

bugman

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 530
  • The Bug Eater
    • Πληροφορική Προγραμματισμός
Πρακτικά όταν κάτι εξαρτιέται σε τέτοιο βαθμό από την εισαγωγή στοιχείων, και μπορεί η διαδικασία να χρειάζεται τεράστιους χρόνους εκτέλεσης, τότε πρέπει ο αλγόριθμος να προβλέπει περιορισμό ή έναν τρόπο να τερματίσει με παρέμβαση του χρήστη. Δηλαδή δεν θα έφτιαχνα ποτέ ένα πρόγραμμα που θα ξεκίναγε με μια επανάληψη μέχρι να ικανοποιηθεί μια συνθήκη γνωρίζοντας ότι αυτό μπορεί να γίνει μερικά χρόνια μετά! Αν το πούλαγα ως μέθοδο επίλυσης, και εξηγούσα ότι ενδέχεται να βρει τη λύση σε χίλια χρόνια, αλλά σίγουρα έχω σωστό αλγόριθμο, τότε απλά δεν θα το αγόραζε κανείς! Δεν μπορεί να είναι κάτι αλγόριθμος, ως μια λύση, για ένα πρόβλημα και να δίνει λύση χίλια χρόνια μετά!


Στο "δικό μου" πρόγραμμα, οι μετρητές ξέρουμε από πριν πόσα βήματα θα κάνουν. πχ αν κάνει ο καθένας 3 και έχουμε τέσσερις τότε έχουμε 3Χ3Χ3Χ3 μετρήσεις. Αυτό είναι γνωστό από την αρχή. Εντελώς διαφορετικό με το βρες ένα ακέραιο αριθμό..που έχω γράψει σε χαρτί ρωτώντας με!


Μου  θύμισες κάτι που είχα διαβάσει παλιά. Αν έχεις μια ασπρόμαυρη οθόνη με ανάλυση 100χ100 στοιχεία μπορείς να διαβάσεις όλα τα βιβλία του κόσμου. Άρα θα μπορούσε να πει κανείς ότι αρκούν 10000bit για να έχουμε όλη τη σοφία του κόσμου, και απλά μια γεννήτρια τυχαίων συνδυασμών θα μπορούσε να μας κάνει την οθόνη να μας απαντάει σε ότι θέλουμε, αρκεί να περιμένουμε να έρθει το σωστό, αλλά σίγουρα το σωστό θα έρθει, αφού είναι βέβαιο ότι αν έχουμε το σωστό βιβλίο θα μας το δείξει η οθόνη!




gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Στο "δικό μου" πρόγραμμα, οι μετρητές ξέρουμε από πριν πόσα βήματα θα κάνουν. πχ αν κάνει ο καθένας 3 και έχουμε τέσσερις τότε έχουμε 3Χ3Χ3Χ3 μετρήσεις. Αυτό είναι γνωστό από την αρχή. Εντελώς διαφορετικό με το βρες ένα ακέραιο αριθμό..που έχω γράψει σε χαρτί ρωτώντας με!
Άλλο πράγμα το άγνωστο αλλά πεπερασμένο πλήθος (δε μας ενοχλεί)  και άλλο πράγμα το άπειρο πλήθος (μας ενοχλεί).

Μου  θύμισες κάτι που είχα διαβάσει παλιά. Αν έχεις μια ασπρόμαυρη οθόνη με ανάλυση 100χ100 στοιχεία μπορείς να διαβάσεις όλα τα βιβλία του κόσμου. Άρα θα μπορούσε να πει κανείς ότι αρκούν 10000bit για να έχουμε όλη τη σοφία του κόσμου, και απλά μια γεννήτρια τυχαίων συνδυασμών θα μπορούσε να μας κάνει την οθόνη να μας απαντάει σε ότι θέλουμε, αρκεί να περιμένουμε να έρθει το σωστό, αλλά σίγουρα το σωστό θα έρθει, αφού είναι βέβαιο ότι αν έχουμε το σωστό βιβλίο θα μας το δείξει η οθόνη!

Αυτό δεν είναι τόσο απλό. Αν έχεις μια οθόνη με 10000 στοιχεία ας πούμε ότι μπορείς να διαβάσεις μια σελίδα βιβλίου. Όλοι οι συνδυασμοί είναι 2^10000. Αν έχεις πιο πολλές σελίδες πολλαπλασιάζεται ανάλογα ο εκθέτης όχι το πλήθος των συνδυασμών. Πχ 2^1000000 για 100 σελίδες.
Αν μετρήσεις το μήκος του γνωστού σύμπαντος σε χιλιοστά  από άκρη σε άκρη είναι της τάξης του 2^130. Αυτό δίνει μια ιδέα του τι είναι το 2^1000000.

Και άντε… ότι τις φτιάξαμε και όλες τις πιθανές σελίδες. Τα βιβλία που θα φτιαχτούν θα λένε και αντιφατικά πράγματα μεταξύ τους. Πχ μια θα λέει «το άθροισμα γωνιών τριγώνου στο επίπεδο είναι 180 μοίρες» μια άλλη θα λέει «το άθροισμα γωνιών τριγώνου στο επίπεδο ΔΕΝ είναι 180 μοίρες» μια άλλη θα λέει «το άθροισμα γωνιών τριγώνου στο επίπεδο είναι 100 μοίρες» κλπ. Πως θα ξέρουμε ποια είναι η σελίδα που λέει το σωστό;
Καμία σοφία δεν μπορεί να υπάρξει με όλους τους πιθανούς συνδυασμούς. Τα λάθη θα είναι πολύ περισσότερα από τα σωστά και κανείς δεν μπορεί να κάνει το διαχωρισμό. Φυσικά θα δεις κάποια στιγμή και το σωστό βιβλίο (που έχεις στα χέρια σου), όμως δεν μπορείς να χρησιμοποιήσεις αυτόν τον αλγόριθμο για να πεις ότι θα μάθεις τα πάντα.

bugman

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 530
  • The Bug Eater
    • Πληροφορική Προγραμματισμός
Δεν περίμενα να το αναλύσεις!
 ;D

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



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