ΑΠΟΡΙΑ

Ξεκίνησε από droopy, 05 Σεπ 2007, 09:39:08 ΜΜ

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

droopy

ΒΡΗΚΑ ΣΕ ΕΝΑ ΒΙΒΛΙΟ ΤΗΝ ΕΞΗΣ ΕΡΩΤΗΣΗ:

ΟΛΑ ΤΑ ΠΡΟΒΛΗΜΑΤΑ ΠΟΥ ΜΠΟΡΟΎΝ ΝΑ ΛΥΘΟΥΝ ΜΕ Η/Υ ΕΙΝΑΙ ΕΠΙΛΥΣΙΜΑ.

ΤΟ ΒΙΒΛΙΟ ΛΕΕΙ ΟΤΙ ΕΙΝΑΙ ΛΑΘΟΣ

ΓΙΑΤΙ?

evry

Μήπως το βιβλίο λέει (η θέλει να πει)

  Επιλύσιμα είναι μόνο τα προβλήματα που μπορούν να λυθούν με Η/Υ?
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

EleniK

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

Ελένη Κοκκίνου
Καθηγήτρια Πληροφορικής, ΠΕ19

alkisg

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

Σωστή μου φαίνεται η πρόταση.

gpapargi

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

Επίσης συμφωνώ με Άλκη. Ο προσεγγιστικός υπολογισμός του π είναι επιλύσιμο πρόβλημα αφού η συνθήκη διακοπής είναι μέρος της εκφώνησης. Το πρόβλημα είναι: "εύρεση των 100 πρώτων δεκαδικών ψηφίων του π" που είναι διαφορετικό από το γνωστό άλυτο πρόβλημα της αρχιότητας. Και εμένα σωστή μου φαίνεται η πρόταση.

pgrontas

Κατά την γνώμη μου ο υπολογισμός του π δεν είναι άλυτο πρόβλημα. Υπάρχει αλγόριθμος που λύνει το πρόβλημα - απλά σε άπειρο χρόνο (δηλαδή υπολογιστική διαδικασία σύμφωνα με το βιβλίο). Η εύρεση ενός ρητού που να ισούται ακριβώς  με π είναι άλυτο πρόβλημα.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

gpapargi

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

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

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

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

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



alkisg

#7
Παράθεση από: gpapargi στις 07 Σεπ 2007, 12:25:05 ΜΜ
Κάτι που ξεφεύγει κάπως είναι το ερώτημα: υπάρχουν άλυτα προβλήματα στα οποία δεν έχουμε λύση που συγκλίνει σε άπειρα βήματα (είμαστε δηλαδή τελείως στον αέρα) ή για κάθε άλυτο πρόβλημα υπάρχει δυνατότητα άπειρης προσέγγισης;

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

Άλυτα προβλήματα για την πληροφορική είναι οτιδήποτε έχει αποδειχτεί ότι δεν έχει λύση, π.χ. το θεώρημα του Φερμά από το παραπάνω link: Δεν υπάρχουν θετικοί ακέραιοι x, y, και z τέτοιοι ώστε x^n + y^n = z^n, όπου n θετικός ακέραιος μεγαλύτερος του 2. Το συγκεκριμένο πρόβλημα (όχι το θεώρημα που όντως ισχύει, το πρόβλημα του να βρούμε τα x, y, z) λοιπόν για μας είναι άλυτο, όσες επαναλήψεις κι αν κάνουμε προσπαθώντας να τα βρούμε (για τους μαθηματικούς η αντίστοιχη ορολογία είναι "αδύνατο").

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

alkisg

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

Αυτό θέλει σκέψη...!!! :)

gpapargi

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

Η κουβέντα είναι άμεσα συσχετισμένη με την περυσινή όπου ρώτησα αν η 0*χ=3 είναι πρόβλημα επιλύσιμο ή άλυτο. Κάτι αντίστοιχο συμβαίνει με τη δευτεροβάθμια. Το βιβλίο τη λέει επιλύσιμη αλλά τι γίνεται στην αρνητική διακρίνουσα;
Εγώ τουλάχιστο είχα καταλήξει στο ότι θα ήθελα έναν ορισμό του άλυτου που να ξεκαθαρίζει αν το ζητούμενο είναι η λύση ή ο αλγόριθμος που να δίνει τη λύση (ή να αποφαίνεται τελεσίδικα ότι δεν υπάρχει).

Η περυσινή κουβέντα είναι παρακάτω:
https://alkisg.mysch.gr/steki/index.php?topic=637.0

Για ΥΓ συμφωνώ μόνο που δε θα μου άρεσε να περιορίστεί το ερώτημα στα προβλήματα εύρεσης αριθμητικής τιμής. Θα ήθελα κάτι που να τα απαντάει όλα  :)

P.Tsiotakis

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

d_bam

πιστεύω πως η πρόταση αυτή είναι ΣΩΣΤΗ! Ο υπολογιστή λύνει μόνο επιλύσιμα προβλήματα και μάλιστα μόνο ΔΟΜΗΜΕΝΑ!!!

anasta

Παράθεση από: d_bam στις 24 Σεπ 2007, 07:24:48 ΜΜ
πιστεύω πως η πρόταση αυτή είναι ΣΩΣΤΗ! Ο υπολογιστή λύνει μόνο επιλύσιμα προβλήματα και μάλιστα μόνο ΔΟΜΗΜΕΝΑ!!!

ΓΙΑΤΙ ΜΟΝΟ ΔΟΜΗΜΕΝΑ?
ΔΙΝΕΙ ΛΥΣΗ Κ ΣΕ ΗΜΙΔΟΜΗΜΕΝΑ Κ ΑΔΟΜΗΤΑ!
ΜΕ ΤΑ ΓΝΩΣΤΑ DSS - DECISION SUPPORT SYSTEMS!
http://en.wikipedia.org/wiki/Decision_support_system

ΜΑΛΛΟΝ ΠΡΕΠΕΙ ΝΑ ΣΚΕΦΤΟΥΜΕ Κ ΝΑ ΔΩΣΟΥΜΕ ΑΠΑΝΤΗΣΗ ΣΤΟ ΕΡΩΤΗΜΑ ΑΝ Ο Η/Υ ΜΠΟΡΕΙ ΝΑ ΔΩΣΕΙ ΛΥΣΗ ΣΕ ΑΝΟΙΚΤΑ Ή ΑΛΥΤΑ ΠΡΟΒΛΗΜΑΤΑ.
ΣΤΑ ΟΠΟΙΑ ΔΕΝ ΔΙΝΕΙ ΛΥΣΗ, ΓΙΑΤΙ ΑΝ ΕΔΙΝΕ ΔΕΝ ΘΑ ΗΤΑΝ ΑΝΟΙΚΤΑ Ή ΑΛΥΤΑ!
ΟΠΟΤΕ Η ΠΡΟΤΑΣΗ ΠΙΣΤΕΥΩ ΟΤΙ ΕΙΝΑΙ ΣΩΣΤΗ.

tomemeto1

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

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

alkisg

Ειδικά οι πύργοι του Ανόι είναι τόσο ...ανοικτό πρόβλημα, που ο αλγόριθμος για τη λύση του είναι στο τετράδιο μαθητή. :)

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

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