επιλύσιμα-απόφασης

[vagmal]

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

[dkotanid]

Αφού δεν είναι ΕΠΙΛΥΣΙΜΟ, πώς θα είναι ΑΠΟΦΑΣΗΣ;Στα επιλύσιμα προβλήματα αντιμετωπίζουμε μετά, το στάδιο του είδους της επίλυσης του προβλήματος!

Κάνουμε την ερώτηση:
Είναι επιλύσιμο, άρα τί είδους λύση έχει;

[yiannis laouris]

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

[trela]

* Κυπριακό πρόβλημα --> ανοικτό και απόφασης
* Εξίσωση που δεν δεν επιλύεται --> άλυτη και υπολογιστική
* Προσεγγιστικές λύσεις εξίσωσης --> βελτιστοποίησης και πιθανώς ανοικτό

[Petros]

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

Το κάθε πρόβλημα σε ότι αφορά την επίλυσή του είναι στενά συνδεδεμένο με την έννοια του αλγορίθμου που παρουσιάζουμε αναλυτικά στο επόμενο κεφάλαιο. Με κριτήριο το είδος επίλυσης που επιζητούν, τα προβλήματα διακρίνονται σε τρεις κατηγορίες:

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

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

[P.Tsiotakis]

Υπάρχουν εξωγήινοι;

Η (πιθανή) απάντηση είναι Ναι ή Όχι;

[sstergou]

Να υπολογίσετε το αν η διαδρομή πόλη1-πόλη4-πόλη3-πόλη2-πόλη1 είναι η βέλτιστη!

[Νίκος Αδαμόπουλος]

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

Παρόλο που δεν το λέει σαφώς, ωστόσο δεν μπορεί να μην αναφέρεται μόνο στα επιλύσιμα...!!

[gpapargi]

Δε συμφωνώ. Κατά τη γνώμη μου ένα πρόβλημα απόφασης είναι ένα πρόβλημα που ζητάει (επιδέχεται) μια απάντηση «ΝΑΙ» ή «ΌΧΙ». Αυτό δε σημαίνει ότι την απάντηση αυτή την έχουμε βρει. Είναι μια ερώτηση που ζητάει ένα ναι ή ένα όχι.
Κάλλιστα μπορεί ένα τέτοιο πρόβλημα να είναι ανοικτό πχ Η κλάση P είναι ίση με την κλάση NP (P vs NP);

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

[Petros]

Παρόλο που δεν το λέει σαφώς, ωστόσο δεν μπορεί να μην αναφέρεται μόνο στα επιλύσιμα...!!

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

Τα προβλήματα επομένως γενικώς! 
 

[MIMIS]

Τελικά ισχύει το ότι οι κατηγορίες με βάση το ΒΑΘΜΟ ΔΟΜΗΣΗΣ και ΤΟ ΕΙΔΟΣ ΤΗΣ ΛΥΣΗΣ των προβήμάτων αναφέρονται μόνο σε ΕΠΙΛΥΣΙΜΑ προβλήματα και όχι ΑΝΟΙΧΤΑ?

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

Καλημέρα σε όλους

[Νίκος Αδαμόπουλος]

Παρόλο που δεν το λέει σαφώς, ωστόσο δεν μπορεί να μην αναφέρεται μόνο στα επιλύσιμα...!!

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

Σύμφωνα και με με τις άλλες απόψεις που καταγράφτηκαν θα μπορούσαν να είναι και τα ανοιχτά... ΟΚ δεκτόν! Αν και, εδώ που τα λέμε, δύσκολα θα προέκυπτε να φανεί ότι κάποιος μαθητής θεωρεί μόνο τα "επιλύσιμα" και όχι τα "επιλύσιμα + ανοιχτά" ...

[gpapargi]

Θα προσέθετα και τα άλυτα. Δηλαδή να μην υπάρχει αλγόριθμος που να μπορεί να δώσει το "ΝΑΙ" ή το "ΌΧΙ" που ζητάει ένα πρόβλημα απόφασης. Πχ το πρόβλημα του τερματισμού (halting problem) που δίνεις ένα πρόγραμμα και ρωτάς αν τερματίζει. Δεν υπάρχει αλγόριθμος που να το απαντάει για όλα τα προγράμματα (όπως απέδειξε ο Turing).

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

Η γνώμη μου είναι ότι πρόκειται απλώς για ανεξάρτητες κατηγοριοποιήσεις. 

[Σπύρος Δουκάκης]

Συμφωνώ!

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

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

Ως προς τα υπολογιστικά έχουμε επίσης ορισμένα μαθηματικά προβλήματα που παραμένουν ανοικτά.

ΣΔ

[koniordos]

Η κατηγοριοποίηση ως προς το είδος της λύσης πώς είναι δυνατό να υφίσταται όταν αυτή δεν υπάρχει ? Το είδος της λύσης δεν έχει να κάνει με το "αίτημα" της λύσης αλλά με τη διαδικασία επίλυσης. Επομένως, η δεδομένη κατηγοριοπόιηση έχει να κάνει με τα επιλύσιμα, δομημένα και το δομημένο τμήμα των ημιδομημένων.

[gpapargi]

Η κατηγοριοποίηση ως προς το είδος της λύσης πώς είναι δυνατό να υφίσταται όταν αυτή δεν υπάρχει ?

Με το είδος της λύσης που ζητάει, όχι που έχει.

[pgrontas]

Πάντως για να μην λέμε μόνο τα αρνητικά πρέπει να παραδεχτούμε ότι στο συγκεκριμένο σημείο το βιβλίο είναι σαφές (και λογικό).
Όπως λοιπόν ανέφερε και ο Petros πριν:
Στην αρχή της σελ. 17 κατηγοριοποίηση 2 λέει ξεκάθαρα ότι:
τα επιλύσιμα χωρίζονται σε δομημένα-ημιδομημένα-αδόμητα.
Αντίθετα,
προς το τέλος της σελ. 17 στην κατηγοριοποίηση 3 αναφέρει ότι: τα προβλήματα (χωρίς να τα περιορίζει) χωρίζονται σε απόφασης,υπολογιστικά βελτιστοποίησης.