Το Στέκι των Πληροφορικών

Γενικό Λύκειο => Γ΄ Λυκείου => Θεωρία => Μήνυμα ξεκίνησε από: gpapargi στις 20 Σεπ 2006, 11:42:14 πμ

Τίτλος: Επιλύσιμο ή άλυτο;
Αποστολή από: gpapargi στις 20 Σεπ 2006, 11:42:14 πμ
Να θέσω ένα περίεργο ερώτημα:

Δίνεται το πρόβλημα:
«Να βρεθεί ένας αριθμός που αν πολλαπλασιαστεί με το 0 θα μας δώσει 3»

Ουσιαστικά το πρόβλημά μας είναι η επίλυση της εξίσωσης 0*x=3 η οποία είναι αδύνατη.

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

Αλλά πως μπορείς να πεις ότι το συγκεκριμένο επιλύσιμο πρόβλημα δεν έχει λύση; Δεν είναι αυτοαναιρούμενη η πρόταση που μόλις έγραψα;
 
Τελικά είναι επιλύσιμο ή άλυτο το πρόβλημα; Πως μπορούμε να έχουμε μια συνεπή θέση;

Για να δούμε απόψεις
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: evry στις 20 Σεπ 2006, 02:57:39 μμ


   Η λύση της πρωτοβάθμιας εξίσωσης  a*x = b  είναι γνωστή όταν a <> 0. Όταν a=0 δεν υπάρχει αυτοματοποιημένος τύπος αλλά παίρνουμε περιπτώσεις.

Οπότε ψηφίζω άλυτο
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: alkisg στις 20 Σεπ 2006, 06:46:09 μμ
Δε θα χαρακτήριζα τη λύση πρωτοβάθμιας εξίσωσης επιλύσιμο πρόβλημα... Θα έλεγα ότι είναι:
1) Επιλύσιμο ΟΤΑΝ υπάρχει λύση,
2) Άλυτο όταν ΔΕΝ υπάρχει λύση,
3) Δομημένο, αφού πάντα απαντάμε, είτε βρίσκοντας τη λύση είτε απαντώντας ότι δεν υπάρχει λύση.

Δηλαδή για τη συγκεκριμένη περίπτωση (=[2]) ψηφίζω κι εγώ «ʼλυτο».
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: koraki στις 21 Σεπ 2006, 05:01:10 μμ
Το πρόβλημα είναι "επιλύσιμο" και η λύση είναι :
"Δεν υπάρχει τέτοιος άριθμος"

Το πρόβλημα θα ήταν άλυτο αν δεν ήταν δυνατόν εμείς (και, κατ' επέκταση, κάποιος αλγόριθμος) να καταλήξοιυμε στην παραπάνω θέση.
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: alkisg στις 21 Σεπ 2006, 07:39:49 μμ
Τον τετραγωνισμό του κύκλου όμως τον κατατάσσει στα άλυτα, ενώ κι αυτός έχει αποδεδειγμένη "λύση", την "δε γίνεται"... Σε τι διαφέρει αυτό από το "δεν υπάρχει τέτοιος αριθμός";

Παράθεση από: Ο Γκρινιάρης από τα Στρουμφάκια
Μου τη δίνουν τα κριτήρια...
 
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: evry στις 21 Σεπ 2006, 10:41:01 μμ
Αν κατάλαβα καλά αυτό που περιγράφεις είναι το ανοικτό πρόβλημα και όχι το άλυτο. Όταν δεν μπορείς να καταλήξεις αν ένα πρόβλημα έχει λύση τότε αυτό είναι ανοικτό. Όταν μπορείς να αποδειξεις ότι δεν έχει λύση τότε είναι άλυτο

Το πρόβλημα είναι "επιλύσιμο" και η λύση είναι :
"Δεν υπάρχει τέτοιος άριθμος"

Το πρόβλημα θα ήταν άλυτο αν δεν ήταν δυνατόν εμείς (και, κατ' επέκταση, κάποιος αλγόριθμος) να καταλήξοιυμε στην παραπάνω θέση.
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: gpapargi στις 22 Σεπ 2006, 09:25:38 πμ
Η αλήθεια είναι πως δεν έχω μια καθαρή θέση για το τι συμβαίνει. Με έχει απασχολήσει το πρόβλημα αλλά καμία απάντηση δε με έχει ικανοποιήσει απόλυτα. Οπότε ας τα αναφέρουμε όλα για να υπάρχουν και το πολύ πολύ το αφήνουμε έτσι.

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

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

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

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

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

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

Ούτε αυτό που περιέγραψα παραπάνω με ικανοποιεί απόλυτα αλλά νομίζω ότι άξιζε να αναφερθεί. Νομίζω ότι με ενοχλεί λιγότερο από τα άλλα. Αν έχει κάποιος άλλος καμιά ιδέα ας την πει.
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: koraki στις 22 Σεπ 2006, 11:21:30 πμ
Η πρωτοβάθμια εξίσωση είναι πρόβλημα που η ανθρώπινη διανόηση έχει λύσει. Η θέση "Δεν υπάρχει λύση στην πρωτοβάθμια εξίσωση με α = 0 και β = 3" δε σημαίνει ότι το ίδιο το πρόβλημα επίλυσης της πρωτοβάθμιας εξίσωσης δεν έχει λύση. Άλλωστε, το αν ένα πρόβλημα είναι επιλύσιμο ή όχι δεν - πρέπει - να εξαρτάται από τα δεδομένα (στην προκειμένη περίπτωση τα α και b, στην εξίσωση αx=b).

Αντιθέτως, ο τετραγωνισμός του κύκλου είναι άλυτο πρόβλημα όποια και αν είναι η ακτίνα του κύκλου.
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: gpapargi στις 22 Σεπ 2006, 11:54:06 πμ
Αν μας πούνε ότι ο δοσμένος κύκλος έχει ακτίνα 1/ρίζα (π) τότε το πρόβλημα λύνεται αφού το εμβαδό είναι 1. Δηλαδή με την ειδική ακτίνα "εξουδετερώνεται" η υπερβατικότητα του π.

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

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

Δεν είναι σωστό να αποφασίζεις το τι ισχύει ανάλογα με το που θα ήθελες να καταλήξεις. Άσε που καταλήγω σε κάποιο όρο που υπάρχει στην πληροφορική. Γιατί δεν το λέγαμε "μη υπολογιστικό" να τελείωνουμε; Μήπως θέλει κάτι άλλο να πει το βιβλίο; Γι αυτό δεν είμαι ικανοποιημένος.
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: Vangelis στις 22 Σεπ 2006, 11:55:56 πμ
Άλυτο είναι ένα πρόβλημα όταν έχει αποδειχθεί ότι δεν υπάρχει λύση.  Στον ορισμό αυτό παραλείπεται το περιβάλλον του προβλήματος.  Συνεπώς θα έπρεπε να συμπληρωθεί ότι "ʼλυτο είναι ένα πρόβλημα όταν κάτω απο ορισμένες συνθήκες (ή σε συγκεκριμένο περιβάλλον) έχει αποδειχθεί ότι δεν υπάρχει λύση.
Η πρωτοβάθμια εξίσωση που έθεσε ο/η  koraki  είναι πρόβλημα άλυτο.
Ακριβώς το ίδιο συμβαίνει με τον τετραγωνισμό του κύκλου.  Φυσικά και υπάρχει γενική λύση (με όση ακρίβεια θέλουμε) δεν υπάρχει λύση -και χαρακτηρίζεται σαν άλυτο πρόβλημα- κάτω απο ορισμένες συνθήκες.

Για να καταλάβουν το θέμα αυτό οι μαθητές μου χρησιμοποιώ ένα παράδειγμα απο το σκάκι. Τους ρωτάω αν στο σκάκι ο αξιωματικός μπορεί να κινηθεί οριζόντια ή κάθετα π.χ να μεταφερθεί στο διπλανό τετράγωνο (ή αν ο Πύργος μπορείνα κινηθεί διαγώνια) η απάντηση τους  φυσικά είναι  όχι.  Μα τους λέω εγώ πιάνω τον Αξιωματικό και  τον β'αζω στο διπλανό τετράγωνο (τονκινώ ορίζοντια) τι πρόβλημα έχω;, δεν με εμποδίζει κανένας;.
Η απάντηση που καταλήγουμε με συζήτηση, είναι ότι φυσικά μπορώ να κινήσω τον αξιωματικό οριζόντια  (και να βρώ λύση στο πρόβλημα) αν το κάνω όμως έχω παραβεί κάποιους κανόνες και αυτό που παίζω δεν έιναι σκάκι.   Η μετακίνηση του αξιωματικού λοιπόν στο διπλανό τετράγωνο είναι άλυτο πρόβλημα αλλά μέσα σε ένα ορισμένο περιβάλλον (ή κάτω απο ορισμένες συνθήκες).  
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: gpapargi στις 22 Σεπ 2006, 02:04:23 μμ
Το θέμα των περιορισμών υπό τους οποίους πρέπει να λυθεί το πρόβλημα τους θεωρώ μέρος της εκφώνησης και άρα μέρος του προβλήματος. Για τον τετραγωνισμό του κύκλου, είναι ξεκάθαρο ότι ενδιαφερόμαστε για ακριβή λύση και όχι για προσεγγιστικές. Επίσης πρέπει να χρησιμοποιήσουμε πεπερασμένο αριθμό βημάτων και όχι άπειρο. Τόσο αυτά όσο και το ότι επιτρέπεται να χρησιμοποιήσουμε μόνο κανόνα και διαβήτη είναι μέρος της εκφώνησης.

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

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

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

Ίσως το άλυτο πρόβλημα να μην έχει κάποιο αυστηρό ορισμό και να το κουβαλάμε από την αρχαιότητα. Δηλαδή να το χρησιμοποιούμε κάπως πιο «λαϊκά» σε σχέση με  τα μη υπολογίσιμα προβλήματα  που έχει ορίσει αυστηρά σήμερα η πληροφορική.
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: Vangelis στις 26 Σεπ 2006, 01:30:03 μμ
Γιώργο πράγματι θα πρέπει να ορίσουμε με ακρίβεια τι ακριβώς σημαίνει άλυτο πρόβλημα και τη διαφορά που έχει από ένα πρόβλημα που δεν έχει λύση. Πράγματι μια δευτεροβάθμια εξίσωση με αρνητική διακρίνουσα δεν έχει πραγματικές ρίζες άρα δεν λύνεται στο R.  Το ερώτημα είναι αν θα χαρακτηριστεί άλυτο ή αδύνατο.   Προσωπικά (με προϊστορία μαθηματικού) προτιμό το αδύνατο.  Αλλά ένα πρόβλημα που έχει λύση δεν θα μπορούσε να χαρακτηριστεί απλά άλυτο;.
Πιστεύω ότι είναι θέμα καλού ορισμού των περιορισμών που πρέπει να ικανοποιούνται.  Το θέμα των περιορισμών είναι πολύ σημαντικό και δεν αποτελούν πάντοτε μέρος της εκφώνησης του προβλήματος.  Πολλά είναι αυτά που εννοούνται και οδηγούν σε λάθος συμπεράσματα.
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: alkisg στις 26 Σεπ 2006, 03:05:06 μμ
Πάντως εμένα ο τετραγωνισμός του κύκλου με τους γνωστούς περιορισμούς, η δευτεροβάθμια με αρνητική διακρίνουσα στο R, η πρωτοβάθμια με α = 0 και β <> 0 κτλ μου φαίνεται ότι ανήκουν στην ίδια λογική κατηγορία των αδυνάτων προβλημάτων. Δηλαδή με την ορολογία του βιβλίου, στα άλυτα (btw, κι εγώ προτιμώ τη λέξη "αδύνατο").

Όλα τους είναι προβλήματα με περιορισμούς. Όλα υπό άλλες προϋποθέσεις είναι επιλύσιμα (π.χ. μιγαδικοί αριθμοί κτλ). Όλα τους μπορούν να θεωρηθούν κομμάτι ενός μεγαλύτερου προβλήματος:
* Ο τετραγωνισμός του κύκλου μπορεί να θεωρηθεί κομμάτι του προβλήματος "τετραγωνισμός σχημάτων που μπορούν να δημιουργηθούν με χάρακα και διαβήτη".
* Η δευτεροβάθμια με αρνητική διακρίνουσα, κομμάτι του γενικότερου προβλήματος "επίλυση δευτεροβάθμιας".
* Μια από τα ίδια για την πρωτοβάθμια.

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

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

Finally, χρησιμοποιώντας τη λέξη "αδύνατο" (σε αντίθεση με το "άλυτο" του βιβλίου), πώς θα χαρακτηρίζατε τη δευτεροβάθμια; Απλά "επιλύσιμο" ή "επιλύσιμο όταν Δ >= 0 και αδύνατο όταν Δ < 0;
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: gpapargi στις 27 Σεπ 2006, 09:55:30 πμ
Αυτό που λέω για τους περιορισμούς είναι το ότι πρέπει να περιέχονται στην εκφώνηση. Δηλαδή μια πλήρης και σαφής εκφώνηση θα πρέπει να περιέχει και τους περιορισμούς. Πχ «να λυθεί η δευτεροβάθμια στο σύνολο των πραγματικών» ή «να μεταφερθεί ο πύργος διαγώνια δεδομένου ότι οι κινήσεις είναι αυτές που περιγράφονται στους κανόνες του σκακιού» κλπ. Δε νομίζω ότι δημιουργεί κάποιο πρόβλημα αυτό ανεξάρτητα από το ποια είναι η γνώμη μας πάνω σε αυτό που κουβεντιάζουμε. Ουσιαστικά αυτό που περιγράφω είναι μόνο και μόνο για να έχουμε ένα σωστά διατυπωμένο πρόβλημα, που το διαβάζεις και ξέρεις ότι χρειάζεται (δεδομένα, ζητούμενα, περιορισμούς κλπ)

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

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

Στον τετραγωνισμό του κύκλου το ζητούμενο τετράγωνο υπάρχει. Αυτό που δεν υπάρχει είναι η διαδικασία για να το κατασκευάσουμε με κανόνα και διαβήτη.

Δηλαδή το πραγματικό θέμα είναι το τι ζητάμε; Το τελικό αποτέλεσμα ή τη διαδικασία;

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

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

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

Το βιβλίο έτσι κι αλλιώς έχει κάποια παράληψη (αφού λέει ότι η δευτεροβάθμια είναι επιλύσιμη)
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: nplatis στις 30 Σεπ 2006, 11:52:28 πμ
Εγώ προσωπικά έχω καταλάβει ότι το όλο θέμα με τα επιλύσιμα / ανοικτά / άλυτα προβλήματα αναφέρεται κυρίως στην ύπαρξη τρόπου επίλυσης του προβλήματος -- επομένως στη συγκεκριμένη περίπτωση ψηφίζω "επιλύσιμο" και η λύση είναι "δεν υπάρχει τέτοιος αριθμός". Εξάλλου, αν ο όρος "άλυτο" προκαλεί σύγχυση, οι άλλοι δύο όροι "επιλύσιμο" και "ανοικτό" καθώς και οι αντίστοιχες εξηγήσεις είναι, πιστεύω, πολύ πιο ξεκάθαρες: στο βιβλίο χρησιμοποιείται ο όρος "επιδέχονται λύση" επανειλλημένα στο σημείο αυτό.

Δυστυχώς στο βιβλίο δεν τονίζεται αρκετά η σημασία του "περιβάλλοντος" του προβλήματος (π.χ. τετραγωνισμός με κανόνα και διαβήτη ή με απειροστικό λογισμό;) και η εξήγηση που δίνεται σε μία γραμμή για τον τετραγωνισμό του κύκλου είναι πολύ πρόχειρη και σύντομη για να είναι καθόλου ουσιαστική.
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: nekis στις 02 Οκτ 2006, 10:44:41 πμ
Θέλω και εγω να παρατηρήσω ότι οι πρωτες δυο διαμερίσεις που επιχειρεί το βιβλίο να αναφέρει (δομηση - επιλυση) δεν επιδεχονται επι της ουσιας κριτικη και αυτη που πραγματικα απασχολει απο την παραγραφο είναι η τρίτη κατηγοριοποίηση. Αν ψαξουμε θα δούμε ότι δεν ειναι διαμεριση και μπορούμε να σκεφτούμε πολλα παραδειγματα στην ΜΗ ΚΕΝΗ τομη τους. Για αυτο και θεωρώ ότι τέτοιο παραδειγμα δεν προκειται να τεθει σαν θεμα εξετασεων
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: alkisg στις 07 Σεπ 2007, 02:01:42 μμ
Γιώργο συνεχίζω εδώ (από αυτό το θέμα (https://alkisg.mysch.gr/steki/index.php?topic=1031.msg5948#msg5948)), το παρόν topic είναι πιο σχετικό.

Για το π, το πρόβλημα (νομίζω ότι) δεν είναι το σχεδιαστικό κομμάτι, είναι ότι δεν προκύπτει σαν λύση αλγεβρικής εξίσωσης (εννοείται ότι δεν μπορούμε να θεωρήσουμε γνωστά και την ακτίνα και το εμβαδόν). Χωρίς να το ψάξω, πιατεύω ότι θα υπάρχουν άρρητοι αριθμοί που δεν μπορούμε να τους σχεδιάσουμε στο χαρτί, μπορούμε όμως να τους υπολογίσουμε αλγεβρικά σε Ο(1) λύνοντας κάποια εξίσωση, και έτσι δεν ανήκουν στα άλυτα προβλήματα. Το π δεν είναι απλά άρρητος, είναι υπερβατικός (αν θυμάμαι καλά την ορολογία από τα σχολικά μου χρόνια).

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

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

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

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

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

π.χ. το πρόβλημα με την οργάνωση ενός πάρτυ έχει λύση (όχι αριθμητική), αλλά δεν έχουμε ούτε καν προσεγγιστικό αλγόριθμο για κάτι τέτοιο... Νομίζω πρέπει αναγκαστικά να περιοριστούμε σε αριθμητικές τιμές ή προβλήματα απόδειξης...
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: pgrontas στις 07 Σεπ 2007, 02:20:06 μμ
>>Δεν ξέρω αν βγάζουν νόημα τα παραπάνω, αυτό που εννοώ είναι ότι ο δικός σου ορισμός του άλυτου αναγκαστικά συμπίπτει με τον δικό  μου: κάθε απόδειξη ότι δεν υπάρχει αλγοριθμική λύση για κάποιο πρόβλημα αναγκαστικά θα αποδείξει παράλληλα ότι το πρόβλημα είναι  αδύνατο.

Μην ξεχνάς ότι στα μαθηματικά μπορείς να πεις: έστω ότι δεν έχει λύση - μετά κάνεις κάποιους συλλογισμούς και καταλήγεις σε άτοπο. Άρα έχει λύση. Δεν εξετάζεις δηλαδή αν μπορείς να κατασκευάσεις την λύση (μέσω αλγορίθμου ή υπολογιστικής διαδικασίας)
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: gpapargi στις 07 Σεπ 2007, 02:57:19 μμ
Για το π, το πρόβλημα (νομίζω ότι) δεν είναι το σχεδιαστικό κομμάτι, είναι ότι δεν προκύπτει σαν λύση αλγεβρικής εξίσωσης (εννοείται ότι δεν μπορούμε να θεωρήσουμε γνωστά και την ακτίνα και το εμβαδόν). Χωρίς να το ψάξω, πιατεύω ότι θα υπάρχουν άρρητοι αριθμοί που δεν μπορούμε να τους σχεδιάσουμε στο χαρτί, μπορούμε όμως να τους υπολογίσουμε αλγεβρικά σε Ο(1) λύνοντας κάποια εξίσωση, και έτσι δεν ανήκουν στα άλυτα προβλήματα. Το π δεν είναι απλά άρρητος, είναι υπερβατικός (αν θυμάμαι καλά την ορολογία από τα σχολικά μου χρόνια).

Εδώ δε διαφωνούμε Άλκη. Ο π είναι υπερβατικός δηλαδή δεν μπορεί να προκύψει σαν λύση εξίσωσης με ρητούς συντελεστές. Αυτό αποδεικνύεται ότι είναι η αιτία που δεν κατασκευάζεται ο π με κανόνα και διαβήτη. Τελικά είναι το ίδιο.

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

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

Έτσι λοιπόν έχουμε 2 περιπτώσεις ερμηνείας του άλυτου.

Περίπτωση 1: ʼΛυτο είναι το πρόβλημα που δεν έχει λύση. Σε αυτή την περίπτωση το πρόβλημα είναι άλυτο αφου δεν έχει λύση.
Περίπτωση 2: ʼλυτο είναι το πρόβλημα που δεν έχει αλγόριθμο για τη λύση. Σε αυτή την περίπτωση το πρόβλημα είναι επιλύσιμο αφού υπάρχει αλγόριθμος για διευρεύνηση. 

Αυτό εννοώ ότι άλλο να μην υπάρχει λύση και άλλο να μην υπάρχει αλγόριθμος για τη λύση. 

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

Θα διαβάσω τα παρακάτω καθώς και του Παναγιώτη και τα ξαναλέμε

Καλό ΣΚ
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: alkisg στις 07 Σεπ 2007, 03:14:29 μμ
Μην ξεχνάς ότι στα μαθηματικά μπορείς να πεις: έστω ότι δεν έχει λύση - μετά κάνεις κάποιους συλλογισμούς και καταλήγεις σε άτοπο. Άρα έχει λύση. Δεν εξετάζεις δηλαδή αν μπορείς να κατασκευάσεις την λύση (μέσω αλγορίθμου ή υπολογιστικής διαδικασίας)
Δε διαφωνώ καθόλου, γι' αυτό και πουθενά δεν μίλησα για προβλήματα που έχουν λύση. Όπως τα καταλαβαίνω, η διαφορά μου με το Γιώργο εντοπίζεται στα άλυτα.

Ας δούμε το πρόβλημα της δευτεροβάθμιας εξίσωσης στο R με αρνητική διακρίνουσα.
Λύση δεν υπάρχει. Υπάρχει όμως αλγόριθμος πλήρους διερεύνησης που να μας δίνει τη λύση (αν υπάρχει) ή μας λέει ότι δεν υπάρχει. Εννοώ προφανώς τη γνωστή διαδικασία του γυμνασίου.
Πρόσεξε τα bold σημεία στην εκφώνηση που έδωσες. Το πρόβλημα όπως το έθεσες δεν έχει λύση, αλλά ούτε αλγόριθμο διερεύνησης. Ένας αλγόριθμος για το παραπάνω πρόβλημα θα μπορούσε απλά να γράφει το μήνυμα "Δεν έχει λύση" χωρίς να διερευνά τίποτα.

Είναι σημαντικό να κρατάμε την εκφώνηση ίδια και στο μαθηματική αλλά και στην αλγοριθμική λύση. Ή θα μιλήσουμε γενικά για τριώνυμο, οπότε και λύση έχει και αλγόριθμο διερεύνησης (με τις γνωστές εξαιρέσεις και στα δύο...), ή μόνο για την περίπτωση αρνητικής διακρίνουσας που ούτε λύση έχει ούτε αλγόριθμο διερεύνησης.
Τα ίδια τα μαθηματικά μας δίνουν τον αλγόριθμο της διερεύνησης, δεν τον βρήκαμε στα πλαίσια της πληροφορικής...
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: gpapargi στις 10 Σεπ 2007, 09:19:15 πμ
Καλημέρα
Μίλησα για την αρνητική διακρίνουσα για να εστιάσω εκεί που θέλω. Υποτίθεται ότι η αρνητική διακρίνουσα θα ήταν θέμα συντελεστών που δίνονται ως είσοδο.

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

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

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

Φυσικά όταν λέμε ότι κάτι δεν έχει λύση ή αλγόριθμο εννοούμε ότι έχει αποδειχτεί κάτι τέτοιο.
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: alkisg στις 10 Σεπ 2007, 10:18:20 πμ
Η εκφώνηση είναι ιδιαίτερα σημαντική.

Πρόβλημα: Θέλουμε να βρούμε τον π πάνω στην ευθεία των πραγματικών με κανόνα και διαβήτη.
Λύση: Δεν υπάρχει (με κανόνα και διαβήτη).
Μαθηματική λύση: Δεν υπάρχει.
Αλγόριθμος: Δεν υπάρχει.

Πρόβλημα: Θέλουμε να προσδιορίσουμε επακριβώς το π (με οποιονδήποτε τρόπο).
Λύση: Υπάρχει.
Μαθηματική λύση: Δεν υπάρχει.
Αλγόριθμος: Δεν υπάρχει.

Πρόβλημα: Εντοπισμός των ριζών μιας δευτεροβάθμιας στο R.
Λύση: Άλλοτε υπάρχει (Δ >= 0), άλλοτε όχι.
Μαθηματική λύση: Υπάρχει αλλά δεν δουλεύει πάντα.
Αλγόριθμος: Υπάρχει αλλά δεν δουλεύει πάντα.

Πρόβλημα: Διερεύνηση για το αν μια δευτεροβάθμια έχει ρίζες στο R.
Λύση: Υπάρχει πάντα.
Μαθηματική λύση: Υπάρχει πάντα (μέθοδος διερεύνησης).
Αλγόριθμος: Υπάρχει πάντα (αλγόριθμος διερεύνησης).

Τι θέλω να πω με τα παραπάνω:
1) Όταν υπάρχει λύση στο πρόβλημα, δεν είναι απαραίτητο να υπάρχει μαθηματική λύση ούτε είναι απαραίτητο να υπάρχει αλγόριθμος.
Μπορεί όμως να υπάρχει αλγόριθμος που να είναι πιθανό να βρει τη λύση ενώ δεν υπάρχει αντίστοιχη μαθηματική λύση (π.χ. με δοκιμές).
2) Όταν υπάρχει μαθηματική λύση, πάντα υπάρχει αλγόριθμος (=απλή εφαρμογή της μαθηματικής λύσης).
3) Από το (1) και το (2) προκύπτει ότι οι λύσεις με αλγορίθμους είναι υπερσύνολο των μαθηματικών λύσεων.
4) Αντιστρέφοντας το (2), προκύπτει ότι κάθε πρόβλημα για το οποίο αποδεδειγμένα δεν υπάρχει αλγοριθμική λύση, δεν έχει ούτε μαθηματική λύση.

5) Και το σημαντικότερο, ξανά για την εκφώνηση: το επιλύσιμο πρόβλημα ΔΕΝ είναι η εύρεση των ριζών μιας δευτεροβάθμιας. Το επιλύσιμο πρόβλημα είναι το "Εύρεση των πραγματικών ριζών μιας δευτεροβάθμιας, αν υπάρχουν, ή η εκτύπωση κατάλληλου μηνύματος εάν δεν υπάρχουν". Δηλαδή (in my opinion πάντα...) επιλύσιμο είναι εφόσον στην εκφώνησή μας ζητάμε διερεύνηση και όχι συγκεκριμένα τις ρίζες. Αν ζητάει συγκεκριμένα τις ρίζες τότε πρέπει υποχρεωτικά να απαντήσουμε ότι άλλοτε είναι επιλύσιμο και άλλοτε αδύνατο (=άλυτο).
Τα ίδια και για τις εκφωνήσεις με το π, οπότε έτσι δεν υπάρχει ασυμφωνία με το βιβλίο.
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: gpapargi στις 10 Σεπ 2007, 12:30:12 μμ
Δεν μπορώ να πω ότι κατάλαβα τι λες Άλκη. Υποπτεύομαι από τα παραδείγματά που γράφεις ότι εγώ συγκρίνω αυτό που εσύ λες λύση και αλγόριθμος, ενώ εσύ συγκρίνεις αυτό που λέει μαθηματική λύση και αλγόριθμος. Λύση εννοώ τους συγκεκριμένους αριθμούς που ζητάμε και αλγόριθμο τα βήματα που πρέπει να κάνουμε για να βρούμε τη λύση. Δεν είμαι σίγουρος ότι καταλαβαίνω τι ακριβώς εννοείς λέγοντας «μαθηματική λύση». Τα άλλα 2 νομίζω φτάνουν. Κάπου εκεί πρέπει να είναι η διαφωνία.

Να δώσω και ένα ακόμα παράδειγμα:

Ας φανταστούμε μια εξίσωση f(x)=0 που έχει μέσα εκθετικά, ημίτονα, συνημίτονα, δυνάμεις, κλάσματα κλπ. Η συνάρτηση ορίζεται και είναι συνεχής  στο [0,10]. Βρίσκουμε λοιπόν ότι f(0) * f(10) <0 (δηλαδή πχ είναι πάνω απόν άξονα χ’χ στο 0 και κάτω στο 10) άρα καταλαβαίνουμε ότι κάπου κόβει τον οριζόντιο άξονα (θεώρημα Bolzano). Ξέρουμε λοιπόν ότι υπάρχει λύση αλλά δεν ξέρουμε μέθοδο να λύσουμε με ακρίβεια τέτοιες εξισώσεις που περιέχουν εκθετικά, συνημίτονα κλπ. (Ας παραβλέψουμε για λίγο το ότι δεν έχουμε απόδειξη ότι δεν υπάρχει αυτή η διαδικασία).

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

Όταν λέω εγώ αλγόριθμο στην πρωτοβάθμια εννοώ τα βήματα που κάνουμε για να βρούμε τη λύση.
Δηλ
Βρίσκουμε το ΕΚΠ.
Πολλαπλάσιάζουμε με το ΕΚΠ και τα 2 μέλη
Κάνουμε πράξεις
Χωρίζουμε γνωστούς αγνώστους
Αναγωγές ομοίων όρων
Έλεγχος αν ο συντελεστής του αγνώστου είναι 0
…
Διαίρεση με το συντελεστή του αγνώστου
Κλπ, καταλαβαίνεις…
 
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: Τhanos στις 27 Οκτ 2007, 11:24:36 μμ
Πιστευω και εγω με την σειρα μου πως το προβλημα ειναι ΕΠΙΛΥΣΙΜΟ!
Και η απαντηση ειναι '' Η εξισωση δεν επιδεχεται λυση στο συνολο των πραγματικων αριθμων ''!
Θα θεωρουνταν αλυτο σε περιπτωση που δεν ειχαμε ιδεα περι τινος προκειται και δεν μπορουσαμε να δωσουμε καμια επισημως αποδεκτη επιστημονικη απαντηση! ;)
Τίτλος: Απ: Επιλύσιμο ή άλυτο;
Αποστολή από: alexis_zoure στις 28 Οκτ 2007, 05:24:18 μμ
Οπως το βλεπω εγω...Ενας μαθηματικος πιστευω θα ελεγε πως ειναι αλυτο αφου "δεν υπαρχουν λυσεις" αλλα ενας πληροφορικος θα ελεγε πως ειναι επιλυσημο γιατι υπαρχει κατατοπιστικη και συγκεκριμενη απαντηση!!!(Αρα συμφωνω με τον κ.Αλκη...)Στο θεμα του προβληματος για την τετραγωνηση του κυκλου εχω την εξης αποψη: λυση εχει...Στο πεδιο των μαθηματικων μπορει να θεωρηθει επιλυσημο αλλα στις Εφαρμογες θεωρειται αλυτο γιατι αν προσπαθησουμε να το λυσουμε με αλγοριθμο εχουμε προβλημα με το κριτηριο περατοτητας αφου εχουμε υπεβολικο ογκο βηματων...Αν κανω λαθος διορθωστε με γιατι με απασχολει αρκετα αυτο το θεμα... 8)