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

Ξεκίνησε από Sergio, 21 Ιαν 2011, 03:17:25 ΜΜ

« προηγούμενο - επόμενο »

Sergio

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

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

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

alkisg

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

pgrontas

Συμφωνώ και εγώ με τον Άλκη.
Αν έλεγε όλα τα επιλύσιμα προβλήματα λύνονται και αλγοριθμικά είναι Σ ή Λ;
Έχω υπόψιν μου τα προβλήματα που λύνονται με την εις άτοπον απαγωγή.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

gpapargi

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

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

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

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

odysseas

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

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

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

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

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

http://blogs.sch.gr/lambrosbouk

Ο Θουκυδίδης  (που τον διαβάζουν οι ξένοι, αλλά όχι εμείς)  έγραφε: «Αταλαίπωρος τοις πολλοίς η ζήτησις της αληθείας, και επί τα ετοίμα μάλλον τρέπονται» (Ι, 20, 3). Οι περισσότεροι δηλαδή αναζητούν αβασάνιστα την αλήθεια και στρέφονται σε ό,τι βρίσκουν έτοιμο. Δεν προβληματίζονται...

Sergio

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




Παράθεση από: alkisg στις 21 Ιαν 2011, 03:25:33 ΜΜΕφόσον υπάρχουν αποδεδειγμένα άλυτα προβλήματα, πώς είναι δυνατόν να λύνονται αλγοριθμικά;
Παράθεση από: Λάμπρος Μπουκουβάλας στις 21 Ιαν 2011, 11:59:03 ΜΜ..οι αλγοριθμικές λύσεις, όπως τις μελετά το σχολικό βιβλίο, έχουν πεδίο εφαρμογής σε επιλύσιμα προβλήματα.

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




Παράθεση από: pgrontas στις 21 Ιαν 2011, 08:53:50 ΜΜΈχω υπόψιν μου τα προβλήματα που λύνονται με την εις άτοπον απαγωγή.
Δηλαδή η πρόταση:
Τα προβλήματα που λύνονται με την απαγωγή σε άτοπο δεν λύνονται αλγοριθμικά
είναι σωστή;




Παράθεση από: gpapargi στις 21 Ιαν 2011, 09:08:37 ΜΜ
Υπάρχει μια κατηγορία προβλημάτων, τα μη υπολογίσιμα, για τα οποία δεν υπάρχει αλγόριθμος που να τα λύνει. Ένα παράδειγμα είναι το πρόβλημα του τερματισμού δηλαδή το να φτιαχτεί αλγόριθμος που να δέχεται σαν είσοδο ένα πρόγραμμα και τις εισόδους του και να λέει αν τερματίζει η όχι. Ο Turing απέδειξε ότι τέτοιος αλγόριθμος δεν είναι δυνατόν να υπάρξει.
Τα μη υπολογίσιμα κατατάσσονται στα άλυτα ;




Παράθεση από: gpapargi στις 21 Ιαν 2011, 09:08:37 ΜΜ
..ο τετραγωνισμός του κύκλου με κανόνα και διαβήτη είναι άλυτο πρόβλημα  όχι γιατί δεν υπάρχει το τετράγωνο που έχει όσο εμβαδό με τον δοσμένο κύκλο (λύση) αλλά γιατί δεν υπάρχει η κατασκευή με κανόνα και διαβήτη (αλγόριθμος για η λύση).
Εδώ νομίζω ότι η διατύπωση του προβλήματος δεν είναι απλά αν υπάρχει τετράγωνο που έχει ίσο εμβαδό με τον δοσμένο κύκλο αλλά περιλαμβάνει και τον όρο να απαντηθεί χρησιμοποιώντας κανόνα και διαβήτη. Για το λόγο αυτό χαρακτηρίζεται άλυτο.




Παράθεση από: odysseas στις 21 Ιαν 2011, 11:55:51 ΜΜ
Υπάρχουν προβλήματα που είναι μια χαρά επιλύσιμα, απλά δεν επιδέχονται αλγοριθμική προσέγγιση. Στα παιδιά συνήθως λέω ότι αν ξέρουν κανέναν που να μπορεί να γράψει αλγόριθμο για τη συγγραφή ενός βιβλίου ή για το πως θα "προσεγγίσουν" την όμορφη της τάξης, θέλω να τον γνωρίσω...
Εύστοχο !!
Θα μπορούσαμε (?) επίσης να προσθέσουμε και το σχόλιο του βιβλίου (σελ.84):
Δεν υπάρχει αλγόριθμος για τη σχεδίαση αλγορίθμων
η (?) την άλλη (σελ.26):
Μία υπολογιστική διαδικασία που δεν τελειώνει μετά από ένα συγκεκριμένο αριθμό βημάτων δε λύνεται αλγοριθμικά
[/i]




Παράθεση από: odysseas στις 21 Ιαν 2011, 11:55:51 ΜΜ
Για να το θέσω με όρους του βιβλίου, τα παραπάνω προβλήματα είναι επιλύσιμα μεν, αδόμητα δε.
Δηλαδή η προτάσεις:
Όλα τα δομημένα προβλήματα λύνονται και αλγοριθμικά
Όλα τα αδόμητα προβλήματα δε λύνονται
είναι σωστές;
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

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

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

όχι βέβαια. το σχολικό βιβλίο είναι σαφές ως προς το θέμα αυτό.
Λάμπρος Μπουκουβάλας
MSc - MRes

http://blogs.sch.gr/lambrosbouk

Ο Θουκυδίδης  (που τον διαβάζουν οι ξένοι, αλλά όχι εμείς)  έγραφε: «Αταλαίπωρος τοις πολλοίς η ζήτησις της αληθείας, και επί τα ετοίμα μάλλον τρέπονται» (Ι, 20, 3). Οι περισσότεροι δηλαδή αναζητούν αβασάνιστα την αλήθεια και στρέφονται σε ό,τι βρίσκουν έτοιμο. Δεν προβληματίζονται...

Sergio

Παράθεση από: Λάμπρος Μπουκουβάλας στις 22 Ιαν 2011, 10:57:51 ΠΜ
Δηλαδή η πρόταση:
Όλα τα επιλύσιμα προβλήματα λύνονται και αλγοριθμικά
είναι σωστή «πέραν πάσης αμφιβολίας / αντίρρησης / αμφισβήτησης» ;;

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

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

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

pgrontas

Δεν ξέρω κατά πόσο πρέπει να προχωρήσουμε την συζήτηση γιατί ξεφεύγει από τα πλαίσια της ΑΕΠΠ, αλλά έχει ενδιαφέρον:
Παράθεση από: Sergio στις 22 Ιαν 2011, 10:26:46 ΠΜ
Δηλαδή η πρόταση:
Τα προβλήματα που λύνονται με την απαγωγή σε άτοπο δεν λύνονται αλγοριθμικά
είναι σωστή;

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

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

Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

gpapargi

Παράθεση από: pgrontas στις 22 Ιαν 2011, 11:39:08 ΠΜ
Είμαστε σίγουροι ότι δεν μπορεί να βρεθεί ένας μη παραδοσιακός αλγόριθμος (πχ. γενετικός) που μετά από μια εξελικτική διαδικασία και ένα μεγάλο σύνολο παραμέτρων να μπορεί να μάθει να γράφει βιβλία;

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

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

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

Αστέριε,

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

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

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

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

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

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

http://blogs.sch.gr/lambrosbouk

Ο Θουκυδίδης  (που τον διαβάζουν οι ξένοι, αλλά όχι εμείς)  έγραφε: «Αταλαίπωρος τοις πολλοίς η ζήτησις της αληθείας, και επί τα ετοίμα μάλλον τρέπονται» (Ι, 20, 3). Οι περισσότεροι δηλαδή αναζητούν αβασάνιστα την αλήθεια και στρέφονται σε ό,τι βρίσκουν έτοιμο. Δεν προβληματίζονται...

Sergio

Λάμπρο,

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

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

gpapargi

Παράθεση από: Sergio στις 23 Ιαν 2011, 10:35:40 ΜΜ
Οι ερωτήσεις που θέτω σε αυτό το topic αφορούν πάντα και μόνο την ΑΕΠΠ. 

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

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