Θέμα: Όλα τα προβλήματα λύνονται και αλγοριθμικά

[Sergio]

Σ ή Λ και γιατί;

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

Ας βοηθήσει κάποιος

[alkisg]

Υπάρχει παγίδα κάπου;
Εφόσον υπάρχουν αποδεδειγμένα άλυτα προβλήματα, πώς είναι δυνατόν να λύνονται αλγοριθμικά;

[pgrontas]

Συμφωνώ και εγώ με τον Άλκη.
Αν έλεγε όλα τα επιλύσιμα προβλήματα λύνονται και αλγοριθμικά είναι Σ ή Λ;
Έχω υπόψιν μου τα προβλήματα που λύνονται με την εις άτοπον απαγωγή.

[gpapargi]

Υπάρχει μια κατηγορία προβλημάτων, τα μη υπολογίσιμα, για τα οποία δεν υπάρχει αλγόριθμος που να τα λύνει. Ένα παράδειγμα είναι το πρόβλημα του τερματισμού δηλαδή το να φτιαχτεί αλγόριθμος που να δέχεται σαν είσοδο ένα πρόγραμμα και τις εισόδους του και να λέει αν τερματίζει η όχι. Ο Turing απέδειξε ότι τέτοιος αλγόριθμος δεν είναι δυνατόν να υπάρξει.

http://en.wikipedia.org/wiki/Halting_problem

Μιλώντας λίγο ανεπίσημα και χύμα, δε μου κάνει εντύπωση αυτό. Αν υπήρχε τέτοιος αλγόριθμος θα ήταν ένα αληθινό τέρας… κάτι πολύ περίεργο θα συνέβαινε. Πχ θα φτιάχναμε ένα πρόγραμμα που θα το βάζαμε να ψάχνει μια προς μια τις λύσεις σε μια εξίσωση που δεν γνωρίζουμε αν έχει η όχι λύση (όπως ήταν το πρόβλημα του Fermat μέχρι πρόσφατα). Για σκέψου αυτό το πρόγραμμα να το ελέγχαμε με τον αλγόριθμο που μας λέει αν τερματίζει ένα πρόγραμμα η όχι. Αν μας έλεγε ΝΑΙ η ΟΧΙ θα ξέραμε αμέσως αν υπάρχει η όχι λύση στο προβλημάτων του Fermat χωρίς να κάνουμε τίποτα.

Παλαιοτέρα είχα εκφράσει την προσωπική άποψη ότι τα μη επιλύσιμα προβλήματα που λέει το βιβλίο είναι αυτά για τα οποία όχι δεν υπάρχει λύση… αλλά δεν υπάρχει αλγόριθμος που να για τη λύση. Συγκεκριμένα ο τετραγωνισμός του κύκλου με κανόνα και διαβήτη είναι άλυτο πρόβλημα  όχι γιατί δεν υπάρχει το τετράγωνο που έχει όσο εμβαδό με τον δοσμένο κύκλο (λύση) αλλά γιατί δεν υπάρχει η κατασκευή με κανόνα και διαβήτη (αλγόριθμος για η λύση).

[odysseas]

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

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

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

[Λάμπρος Μπουκουβάλας]

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

[Sergio]

Ωραία συλλογή απόψεων

Εφόσον υπάρχουν αποδεδειγμένα άλυτα προβλήματα, πώς είναι δυνατόν να λύνονται αλγοριθμικά;

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

Δηλαδή η πρόταση:

Όλα τα επιλύσιμα προβλήματα λύνονται και αλγοριθμικά

είναι σωστή «πέραν πάσης αμφιβολίας / αντίρρησης / αμφισβήτησης» ;;

Έχω υπόψιν μου τα προβλήματα που λύνονται με την εις άτοπον απαγωγή.

Δηλαδή η πρόταση:

Τα προβλήματα που λύνονται με την απαγωγή σε άτοπο δεν λύνονται αλγοριθμικά

είναι σωστή;

Υπάρχει μια κατηγορία προβλημάτων, τα μη υπολογίσιμα, για τα οποία δεν υπάρχει αλγόριθμος που να τα λύνει. Ένα παράδειγμα είναι το πρόβλημα του τερματισμού δηλαδή το να φτιαχτεί αλγόριθμος που να δέχεται σαν είσοδο ένα πρόγραμμα και τις εισόδους του και να λέει αν τερματίζει η όχι. Ο Turing απέδειξε ότι τέτοιος αλγόριθμος δεν είναι δυνατόν να υπάρξει.

Τα μη υπολογίσιμα κατατάσσονται στα άλυτα ;

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

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

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

Εύστοχο !!
Θα μπορούσαμε (?) επίσης να προσθέσουμε και το σχόλιο του βιβλίου (σελ.84):

Δεν υπάρχει αλγόριθμος για τη σχεδίαση αλγορίθμων

η (?) την άλλη (σελ.26):

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

[/i]

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

Δηλαδή η προτάσεις:

Όλα τα δομημένα προβλήματα λύνονται και αλγοριθμικά
Όλα τα αδόμητα προβλήματα δε λύνονται

είναι σωστές;

[Λάμπρος Μπουκουβάλας]

Δηλαδή η πρόταση:
Όλα τα επιλύσιμα προβλήματα λύνονται και αλγοριθμικά
είναι σωστή «πέραν πάσης αμφιβολίας / αντίρρησης / αμφισβήτησης» ;;

όχι βέβαια. το σχολικό βιβλίο είναι σαφές ως προς το θέμα αυτό.

[Sergio]

Δηλαδή η πρόταση:
Όλα τα επιλύσιμα προβλήματα λύνονται και αλγοριθμικά
είναι σωστή «πέραν πάσης αμφιβολίας / αντίρρησης / αμφισβήτησης» ;;

όχι βέβαια. το σχολικό βιβλίο είναι σαφές ως προς το θέμα αυτό.

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

Αν σου είναι εύκολο, ανάφερε σε παρακαλώ το σημείο του βιβλίου..

[pgrontas]

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

Δηλαδή η πρόταση:

Τα προβλήματα που λύνονται με την απαγωγή σε άτοπο δεν λύνονται αλγοριθμικά

είναι σωστή;

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

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

[gpapargi]

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

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

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

[Λάμπρος Μπουκουβάλας]

Αστέριε,

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

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

δες επίσης και την τελευταία παράγραφο από την 2.1

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

τέλος δες το βιβλίο καθηγητή, παρ. 2.5, σελ. 51, την 1η βούλα.

ΥΓ: όσα έγραψα είναι μάλλον άκυρα αν η συζήτησή μας και το θέμα που έθεσε ο Αστέριος ΔΕΝ αφορούν ΜΟΝΟ την ΑΕΠΠ.

[Sergio]

Λάμπρο,

Σε ευχαριστώ πολύ για τον κόπο που έκανες να καταγράψεις όλες αυτές τις αναφορές. Ήταν πραγματικά χρήσιμες.

Οι ερωτήσεις που θέτω σε αυτό το topic αφορούν πάντα και μόνο την ΑΕΠΠ. 

[gpapargi]

Οι ερωτήσεις που θέτω σε αυτό το topic αφορούν πάντα και μόνο την ΑΕΠΠ. 

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

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