Θέμα: Εϋρεση επόμενου πρώτου αριθμού

[kpde]

Απορία μαθητή..
Έστω πως είναι γνωστός ο, μέχρι τώρα υπολογισμένος, μεγαλύτερος πρώτος αριθμός.. Το πρόβλημα της εύρεσης του επόμενου πρώτου αριθμού ΤΙ είναι; 

Επιλυσιμότητα: Μάλλον ανοικτό αφού ούτε έχει λυθεί αλλά ούτε και έχει αποδειχθεί πως δε λύνεται..

Είδος επίλυσης: Είναι πρόβλημα υπολογιστικό ή απόφασης;

Και ΒΑΣΙΚΑ..
Βαθμός Δόμησης:  Αν όντως θεωρήσουμε πως είναι ΑΝΟΙΚΤΟ, γιατί να μη μπορούμε να το χαρακτηρίσουμε ως δομημένο (ή έστω ημιδομημένο) ;  Το βιβλίο αναφέρει πως η κατάταξη των προβλημάτων με βάση το βαθμό δόμησης, αφορά ΜΟΝΟ στα επιλύσιμα προβλήματα 

[soron80]

Απορία μαθητή..
Έστω πως είναι γνωστός ο, μέχρι τώρα υπολογισμένος, μεγαλύτερος πρώτος αριθμός.. Το πρόβλημα της εύρεσης του επόμενου πρώτου αριθμού ΤΙ είναι; 

Επιλυσιμότητα: Μάλλον ανοικτό αφού ούτε έχει λυθεί αλλά ούτε και έχει αποδειχθεί πως δε λύνεται..

Είδος επίλυσης: Είναι πρόβλημα υπολογιστικό ή απόφασης;

Και ΒΑΣΙΚΑ..
Βαθμός Δόμησης:  Αν όντως θεωρήσουμε πως είναι ΑΝΟΙΚΤΟ, γιατί να μη μπορούμε να το χαρακτηρίσουμε ως δομημένο (ή έστω ημιδομημένο) ;  Το βιβλίο αναφέρει πως η κατάταξη των προβλημάτων με βάση το βαθμό δόμησης, αφορά ΜΟΝΟ στα επιλύσιμα προβλήματα 

Απλά Ανοικτό και τίποτα άλλο!

[kpde]

και γιατί όχι δομημένο ;

[soron80]

σελ. 17 σχολικού βιβλίου..

"Με κριτήριο το Βαθμό δόμησης των λύσεών τους τα επιλύσιμα προβλήματα μπορούν να διακριθούν σε ...."

[kpde]

Σύμφωνοι..

Άντε δώσε αυτή την απάντηση όμως σε σκεπτόμενο μαθητή

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

Σου λέει.. ναι, οκ.. δεν έχει αποδειχθεί ότι δεν υπάρχει, ούτε όμως και έχει βρεθεί.. επομένως είναι ανοικτό.. Μπορούμε να το κατατάξουμε είτε στα υπολογιστικά (βρες τον) είτε στα απόφασης (υπάρχει;). Και υπάρχει απόλυτα δομημένος τρόπος για την αναζήτηση της λύσης του..  Οπότε γιατί να μη χαρακτηριστεί δομημένο;

[alkisg]

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

[kpde]

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

[alkisg]

Για να τεστάρεις αν ένας αριθμός είναι πρώτος, δοκιμάζεις όλους τους μικρότερους αριθμούς του αν τον διαιρούν.
Για να βρεις τον "επόμενο πρώτο", τους δοκιμάζεις με τη σειρά.

Δηλαδή με ένα διπλό loop λύνεις το πρόβλημα με πολυπλοκότητα Ο(n²). Και φυσικά εφόσον υπάρχει αλγόριθμος, είναι επιλύσιμο.

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

[soron80]

Ο μεγαλύτερος γνωστός πρώτος αριθμός

Μέχρι τον Απρίλιο του 2011, ο μεγαλύτερος γνωστός πρώτος αριθμός είναι ο:

    243.112.609 − 1.

Η ανακάλυψη του έγινε στις 23 Αυγούστου 2008, μέσω του διαδικτυακού προγράμματος κατανεμημένης επεξεργασίας GIMPS (Great Internet Mersenne Prime Search)[1]. Ο αριθμός αυτός έχει 12.978.189 ψηφία (ο πρώτος πρώτος με πάνω από 10 εκατομμύρια ψηφία) και έχει την πρόσθετη ιδιότητα να είναι ο 45ος Μερσέν πρώτος (Mersenne prime) που ανακαλύφθηκε. Ο 46ος Μερσέν πρώτος, ο 237.156.667 − 1, ανακαλύφθηκε δύο βδομάδες αργότερα -- είναι πρώτος, αλλά μικρότερος.

Στο πρόσφατο παρελθόν, όλοι οι πρώτοι που ανακαλύφθηκαν ήταν Μερσέν πρώτοι. [2]

http://el.wikipedia.org/wiki/%CE%A0%CF%81%CF%8E%CF%84%CE%BF%CF%82_%CE%B1%CF%81%CE%B9%CE%B8%CE%BC%CF%8C%CF%82

[kpde]

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

Όπως καταλαβαίνεις, προσπαθώ να απαντήσω στο σκεπτόμενο μαθητή, χωρίς να σιαπράξω 2 βασικά παιδαγωγικά σφάλματα:
1) να καταδικάσω το βιβλίο
2) να περιορίσω την ελευθερία σκέψης του

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

[alkisg]

Να τα ξαναπώ μήπως μπλεχτήκαμε:
1) Δεν ξέρουμε όλους τους πρώτους αριθμούς.
2) Ξέρουμε αλγόριθμο να τους βρούμε. Απλά τους δοκιμάζουμε με τη σειρά με βάση τον ορισμό των πρώτων.
3) Ο αλγόριθμος αυτός είναι υπερβολικά αργός.
4) Άρα το πρόβλημα που απασχολεί την επιστημονική κοινότητα έγκειται στο να βρούμε πρώτους (ή τον επόμενο πρώτο) με κάποιον αλγόριθμο μικρότερης πολυπλοκότητας.

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

Εάν δεν πείτε στο μαθητή "απαγορεύονται οι λύσεις με πολυπλοκότητα O(n²)", τότε το πρόβλημα εύρεσης του επόμενου πρώτου είναι επιλύσιμο.

[mikeg]

Όπως καταλαβαίνεις, προσπαθώ να απαντήσω στο σκεπτόμενο μαθητή, χωρίς να σιαπράξω 2 βασικά παιδαγωγικά σφάλματα:

1) να καταδικάσω το βιβλίο

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

2) να περιορίσω την ελευθερία σκέψης του

όσοι μένουν προσκολλημένοι στα βιβλία αυτό ακριβώς κάνουν

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

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

[kpde]

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

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

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

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

Όπως καταλαβαίνεις, προσπαθώ να απαντήσω στο σκεπτόμενο μαθητή, χωρίς να σιαπράξω 2 βασικά παιδαγωγικά σφάλματα:
1) να καταδικάσω το βιβλίο

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

2) να περιορίσω την ελευθερία σκέψης του

όσοι μένουν προσκολλημένοι στα βιβλία αυτό ακριβώς κάνουν

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

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

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

[alkisg]

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

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

Αναφέρθηκα σε αλγόριθμο μόνο και μόνο για να αποδείξω μεταξύ καθηγητών ότι είναι επιλύσιμο και όχι ανοικτό. Δεν αναφέρθηκα σε τρόπο διδασκαλίας.

Ένας καλός μαθητής φαντάζομαι ότι θα σκεφτόταν τα παρακάτω:

• "Ξέρω πώς να ελέγχω αν ένας αριθμός είναι πρώτος. Δοκιμάζω να δω αν διαιρείται με όλους τους μικρότερούς του".
• "Αφού λοιπόν μου δίνεται ένας πρώτος αριθμός Α, τότε για να βρω τον επόμενο Β, αρκεί να δοκιμάσω τον Α+1 αν είναι πρώτος, τον Α+2 αν είναι πρώτος, τον Α+3 αν είναι πρώτος κτλ. μέχρι να βρω κάποιον πρώτο."

Έτσι λοιπόν αφού με δομημένο τρόπο σκέψης έλυσε το πρόβλημα, αυτό είναι επιλύσιμο.
Παρεμπιπτόντως, αυτός ο τρόπος αναφέρεται και στο link που παράθεσε λίγο παραπάνω ο soron80.

Το γεγονός ότι αυτή η μέθοδος ίσως του πάρει αιώνες για να βρει τον επόμενο πρώτο μετά τον 2^43.112.609 − 1 δεν μας απασχολεί σε αυτό το σημείο, θα μας απασχολούσε στο κεφάλαιο που θα διδάσκαμε την πολυπλοκότητα, εάν αυτή ήταν εντός ύλης.

[evry]

Λοιπόν, το 300 π.Χ. ο Ευκλείδης έδωσε μια πραγματικά ιδιοφυής και σύντομη απόδειξη ότι υπάρχουν άπειροι πρώτοι αριθμοί. Άρα ξέρουμε
1) ότι υπάρχουν άπειροι πρώτοι αριθμοί 
2) πως μπορούμε να τους βρούμε όλους με εξαντλητική αναζήτηση

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