Πρόβλημα υπολογιστικό ή βελτιστοποίησης?

[Obelix]

Γεια χαρά σε όλους.Πρόσφατα μου δημιουργήθηκε η εξής απορία:

Έστω το πρόβλημα εύρεσης του μεγίστου από ένα σύνολο ακεραίων.

Το κατατάσσουμε στα υπολογιστικά προβλήματα ή στα προβλήματα βελτιστοποίησης.

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

[alkisg]

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

Επομένως η εύρεση μεγίστου ενός συνόλου ακεραίων δεν έχει σχέση με προβλήματα βελτιστοποίησης.

[evry]

  Θα έλεγα ότι ένας τρόπος για να το εξηγήσεις σε έναν μαθητή είναι να του δώσεις ένα πρόβλημα το οποίο έχεις πολλές διακριτές λύσεις και να του εξηγήσεις ότι θέλεις τη βέλτιστη. Κλασικό παράδειγμα το συντομότερο μονοπάτι μεταξύ δύο πόλεων.
Το μέγιστο έχει μόνο μια λύση, άρα δεν είναι πρόβλημα βελτιστοποίησης. Αυτό που λέει ο Άλκης συμβαίνει όταν χρησιμοποιούμε μια επαναληπτική μέθοδο για να υπολογίσουμε π.χ. τη ρίζα μιας εξίσωσης. Υπάρχει κάποια παράμετρος s=0.001 η οποία "βελτιστοποίει" τη λύση, εννοώντας ότι συνεχώς προσεγγίζει όλο και πιο κοντά της. Η λύση όμως είναι μια και το πρόβλημα είναι υπολογιστικό. Φοβάμαι ότι εδώ μπλέκουμε με το Optimization των μαθηματικών που είναι λίγο διαφορετικό από αυτό που έχουμε στην πληροφορική και από τον ορισμό που δίνει το βιβλίο.

[Obelix]

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

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

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

Για παράδειγμα, έστω τα εξής προβλήματα:

Δίνονται τέσσερις ακέραιοι αριθμοί κ,λ,μ,ν.
Α)Να βρεθούν όλα τα  αθροίσματα που μπορούμε να έχουμε προσθέτοντας τους αριθμούς αυτούς ανά δύο.
Β)Να βρεθεί το μέγιστο άθροισμα που μπορούμε να έχουμε προσθέτοντας τους αριθμούς αυτούς ανά δύο.

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

[alkisg]

Sorry παιδιά είχα στο νου μου αυτά:
http://el.wikipedia.org/wiki/Βελτιστοποίηση
http://en.wikipedia.org/wiki/Optimization_(mathematics)
ενώ εσείς (και μάλλον και το βιβλίο) λέτε γι' αυτό:
http://en.wikipedia.org/wiki/Optimization_problem
...μάλλον παραέκανα fortran και αριθμητικές μεθόδους στο μεταπτυχιακό!

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

ΟΚ, ας δούμε τα παραδείγματα του βιβλίου και του Obelix με τον τυπικό ορισμό:
Δίδεται ένας ακέραιος Ν και ζητείται ποια είναι η παραγοντοποίηση για το Ν με το μεγαλύτερο πλήθος παραγόντων.
Το I (set of instances) είναι το σύνολο Z, δηλαδή όλοι οι ακέραιοι.
Το x (a given instance) είναι ο συγκεκριμένος αριθμός Ν.
Το f(x) (set of feasible solutions) είναι οι διαφορετικές παραγοντοποιήσεις του x.
Το m(x,y) (measure of feasible solution) είναι ο αριθμός των παραγόντων (η συνάρτηση που θέλουμε να μεγιστοποιήσουμε ή να ελαχιστοποιήσουμε).
Η g (goal function) είναι το max, δηλαδή θέλουμε μεγιστοποίηση και όχι ελαχιστοποίηση.

Πάμε στο πρόβλημα εύρεσης μεγίστου από ένα σύνολο ακεραίων.
Το I (set of instances) είναι όλα τα σύνολα ακεραίων.
Το x (a given instance) είναι ένα συγκεκριμένο σύνολο.
Το f(x) (set of feasible solutions) είναι όλες οι λύσεις του προβλήματος. Εδώ είναι το πρόβλημα, έχει μόνο μία λύση.
Το m(x,y) (measure of feasible solution) είναι μια συνάρτηση βαθμολόγησης για το πόσο καλός μέγιστος είναι αυτός που διαλέξαμε. Κι άλλο πρόβλημα, δεν μπορούμε να την ορίσουμε αφού έχουμε μόνο μια λύση και ότι τιμή και να δώσουμε στη συνάρτηση γι' αυτή δεν παίζει ρόλο αφού δεν υπάρχει άλλη τιμή για να συγκριθεί μαζί της.
Η g (goal function) είναι το max, δηλαδή θέλουμε μεγιστοποίηση και όχι ελαχιστοποίηση.

Αν όμως παίξουμε με τις λέξεις, μπορούμε να ορίσουμε αλλιώς το πρόβλημα και να το κάνουμε πρόβλημα βελτιστοποίησης.
Θα πρέπει να θεωρήσουμε ότι αποδεκτή λύση είναι οποιοσδήποτε από τους αριθμούς στο σύνολο ακεραίων, και αναζητούμε τη βέλτιση (=μέγιστη) λύση. Για παράδειγμα, λέει ο διευθυντής "φέρε μου τον ψηλότερο μαθητή να τον στείλω σημαιοφόρο" - οποιοσδήποτε μαθητής μπορεί να κάνει το σημαιοφόρο, απλά αναζητούμε το βέλτιστο = ψηλότερο. Ή, αν δεν θέλουμε να θεωρούνται αποδεκτές λύσεις όλοι οι αριθμοί, θα μπορούσαμε να ζητάμε "το μέγιστο άρτιο" του συνόλου. Επομένως,
Το I (set of instances) είναι όλα τα σύνολα ακεραίων.
Το x (a given instance) είναι ένα συγκεκριμένο σύνολο.
Το f(x) (set of feasible solutions) είναι όλες οι λύσεις του προβλήματος. Δηλαδή όλοι οι αριθμοί του συνόλου.
Το m(x,y) (measure of feasible solution) είναι μια συνάρτηση βαθμολόγησης για το πόσο καλή λύση είναι αυτή που διαλέξαμε. Την ορίζουμε σαν m(x,y) = y (δηλαδή ο ίδιος ο αριθμός).
Η g (goal function) είναι το max, δηλαδή θέλουμε μεγιστοποίηση και όχι ελαχιστοποίηση.

Και έτσι το κατατάξαμε στα προβλήματα βελτιστοποίησης...

Επομένως Obelix μαζί σου είμαι κι εγώ, έχω την ίδια απορία μ' εσένα.

[gpapargi]

Συμφωνώ με το δεύτερο Άλκη. Το “feasible solutions” το αντιλαμβάνομαι ως «υποψήφιες» λύσεις δηλαδή όλους τους αριθμούς αν μιλάμε για μέγιστο ακεραίων, ή όλες τις πιθανές παραγοντοποιήσεις αν μιλάμε για παραγοντοποίηση αριθμού ή όλες τις πιθανές διαδρομές αν μιλάμε για συντομότερο μονοπάτι.

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

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

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

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

Αν δεν είναι κάπως έτσι τα πράγματα… τότε δεν μπορώ να καταλάβω πότε ένα πρόβλημα είναι μη υπολογιστικό. Μήπως κάτι παίχτηκε με τη μετάφραση του computational στα ελληνικά (αντίστοιχο με το effectiveness στα αλγοριθμικά κριτήρια);