Επιλύσιμο ή άλυτο;

Ξεκίνησε από gpapargi, 20 Σεπ 2006, 11:42:14 ΠΜ

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

nekis

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

alkisg

#16
Γιώργο συνεχίζω εδώ (από αυτό το θέμα), το παρόν topic είναι πιο σχετικό.

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

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

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

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

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

Σχετικά με το
Παράθεση από: gpapargi στις 07 Σεπ 2007, 01:09:08 ΜΜ
Για ΥΓ συμφωνώ μόνο που δε θα μου άρεσε να περιορίστεί το ερώτημα στα προβλήματα εύρεσης αριθμητικής τιμής. Θα ήθελα κάτι που να τα απαντάει όλα  :)

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

pgrontas

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

Μην ξεχνάς ότι στα μαθηματικά μπορείς να πεις: έστω ότι δεν έχει λύση - μετά κάνεις κάποιους συλλογισμούς και καταλήγεις σε άτοπο. Άρα έχει λύση. Δεν εξετάζεις δηλαδή αν μπορείς να κατασκευάσεις την λύση (μέσω αλγορίθμου ή υπολογιστικής διαδικασίας)
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

gpapargi

Παράθεση από: alkisg στις 07 Σεπ 2007, 02:01:42 ΜΜ
Για το π, το πρόβλημα (νομίζω ότι) δεν είναι το σχεδιαστικό κομμάτι, είναι ότι δεν προκύπτει σαν λύση αλγεβρικής εξίσωσης (εννοείται ότι δεν μπορούμε να θεωρήσουμε γνωστά και την ακτίνα και το εμβαδόν). Χωρίς να το ψάξω, πιατεύω ότι θα υπάρχουν άρρητοι αριθμοί που δεν μπορούμε να τους σχεδιάσουμε στο χαρτί, μπορούμε όμως να τους υπολογίσουμε αλγεβρικά σε Ο(1) λύνοντας κάποια εξίσωση, και έτσι δεν ανήκουν στα άλυτα προβλήματα. Το π δεν είναι απλά άρρητος, είναι υπερβατικός (αν θυμάμαι καλά την ορολογία από τα σχολικά μου χρόνια).

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

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

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

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

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

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

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

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

Καλό ΣΚ

alkisg

Παράθεση από: pgrontas στις 07 Σεπ 2007, 02:20:06 ΜΜ
Μην ξεχνάς ότι στα μαθηματικά μπορείς να πεις: έστω ότι δεν έχει λύση - μετά κάνεις κάποιους συλλογισμούς και καταλήγεις σε άτοπο. Άρα έχει λύση. Δεν εξετάζεις δηλαδή αν μπορείς να κατασκευάσεις την λύση (μέσω αλγορίθμου ή υπολογιστικής διαδικασίας)
Δε διαφωνώ καθόλου, γι' αυτό και πουθενά δεν μίλησα για προβλήματα που έχουν λύση. Όπως τα καταλαβαίνω, η διαφορά μου με το Γιώργο εντοπίζεται στα άλυτα.

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

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

gpapargi

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

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

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

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

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

alkisg

#21
Η εκφώνηση είναι ιδιαίτερα σημαντική.

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

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

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

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

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

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

gpapargi

Δεν μπορώ να πω ότι κατάλαβα τι λες Άλκη. Υποπτεύομαι από τα παραδείγματά που γράφεις ότι εγώ συγκρίνω αυτό που εσύ λες λύση και αλγόριθμος, ενώ εσύ συγκρίνεις αυτό που λέει μαθηματική λύση και αλγόριθμος. Λύση εννοώ τους συγκεκριμένους αριθμούς που ζητάμε και αλγόριθμο τα βήματα που πρέπει να κάνουμε για να βρούμε τη λύση. Δεν είμαι σίγουρος ότι καταλαβαίνω τι ακριβώς εννοείς λέγοντας «μαθηματική λύση». Τα άλλα 2 νομίζω φτάνουν. Κάπου εκεί πρέπει να είναι η διαφωνία.

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

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

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

Όταν λέω εγώ αλγόριθμο στην πρωτοβάθμια εννοώ τα βήματα που κάνουμε για να βρούμε τη λύση.
Δηλ
Βρίσκουμε το ΕΚΠ.
Πολλαπλάσιάζουμε με το ΕΚΠ και τα 2 μέλη
Κάνουμε πράξεις
Χωρίζουμε γνωστούς αγνώστους
Αναγωγές ομοίων όρων
Έλεγχος αν ο συντελεστής του αγνώστου είναι 0
…
Διαίρεση με το συντελεστή του αγνώστου
Κλπ, καταλαβαίνεις…


Τhanos

Πιστευω και εγω με την σειρα μου πως το προβλημα ειναι ΕΠΙΛΥΣΙΜΟ!
Και η απαντηση ειναι '' Η εξισωση δεν επιδεχεται λυση στο συνολο των πραγματικων αριθμων ''!
Θα θεωρουνταν αλυτο σε περιπτωση που δεν ειχαμε ιδεα περι τινος προκειται και δεν μπορουσαμε να δωσουμε καμια επισημως αποδεκτη επιστημονικη απαντηση! ;)
Σαραντόπουλος Θανάσης
Μαθητής Γ΄Λυκείου

alexis_zoure

Οπως το βλεπω εγω...Ενας μαθηματικος πιστευω θα ελεγε πως ειναι αλυτο αφου "δεν υπαρχουν λυσεις" αλλα ενας πληροφορικος θα ελεγε πως ειναι επιλυσημο γιατι υπαρχει κατατοπιστικη και συγκεκριμενη απαντηση!!!(Αρα συμφωνω με τον κ.Αλκη...)Στο θεμα του προβληματος για την τετραγωνηση του κυκλου εχω την εξης αποψη: λυση εχει...Στο πεδιο των μαθηματικων μπορει να θεωρηθει επιλυσημο αλλα στις Εφαρμογες θεωρειται αλυτο γιατι αν προσπαθησουμε να το λυσουμε με αλγοριθμο εχουμε προβλημα με το κριτηριο περατοτητας αφου εχουμε υπεβολικο ογκο βηματων...Αν κανω λαθος διορθωστε με γιατι με απασχολει αρκετα αυτο το θεμα... 8)
Αλεξανδρος Ζουρελιδης
Μαθητης Γ Λυκειου