Αποστολέας Θέμα: ΑΠΟΡΙΑ  (Αναγνώστηκε 5307 φορές)

droopy

  • Θαμώνας
  • ***
  • Μηνύματα: 36
  • you know what... i'm happy
ΑΠΟΡΙΑ
« στις: 05 Σεπ 2007, 09:39:08 μμ »
ΒΡΗΚΑ ΣΕ ΕΝΑ ΒΙΒΛΙΟ ΤΗΝ ΕΞΗΣ ΕΡΩΤΗΣΗ:

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

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

ΓΙΑΤΙ?

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3104
  • to Iterate is human to Recurse divine
Απ: ΑΠΟΡΙΑ
« Απάντηση #1 στις: 05 Σεπ 2007, 10:23:17 μμ »
Μήπως το βιβλίο λέει (η θέλει να πει)

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

EleniK

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 708
Απ: ΑΠΟΡΙΑ
« Απάντηση #2 στις: 05 Σεπ 2007, 11:48:27 μμ »
Εκτός απο την πρόταση του Ευριπίδη, σκεφτόμουν ότι π.χ. ο προσδιορισμός του π θεωρείται πρόβλημα άλυτο, παρολαυτα υπάρχει πρόγραμμα που μπορεί να υπολογίσει την τιμή του π κατά προσέγγιση! Στην ουσία με αριθμητικές μεθόδους προσδιορίζεις δεκαδικά ψηφία.

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

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4856
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: ΑΠΟΡΙΑ
« Απάντηση #3 στις: 07 Σεπ 2007, 07:49:23 πμ »
Όταν όμως ένας Η/Υ υπολογίζει το π με ακρίβεια 100 δεκαδικών ψηφίων, δεν λύνει το πρόβλημα "προσδιορισμός του π" που είναι άλυτο, αλλά λύνει το πρόβλημα "εύρεση των 100 πρώτων δεκαδικών ψηφίων του π" που είναι επιλύσιμο, και φυσικά θα μπορούσαμε να το λύσουμε και με μολύβι και χαρτί (σε μερικά χρόνια, αλλά αυτό δεν έχει σημασία)... Δηλαδή όποιο πρόβλημα λύνεται με Η/Υ μπορεί να λυθεί και χωρίς αυτόν...

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

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2448
  • I 'm not young enough to know everything
Απ: ΑΠΟΡΙΑ
« Απάντηση #4 στις: 07 Σεπ 2007, 09:19:33 πμ »
Αν ένα πρόβλημα μπορεί να λυθεί (με οποιοδήποτε τρόπο) είναι επιλύσιμο. Ο διαχωρισμός των προβλημάτων σε επιλύσιμα και άλυτα δε σχετίζεται με τον Η/Υ. Αν μάλιστα λύνεται και με υπολογιστή σημαίνει ότι υπάρχει αλγόριθμος που το λύνει και άρα η διαδικασία επίλυσης έχει αυτοματοποιηθεί. Θα το χαρακτήριζα και δομημένο.

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

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1310
  • There are always possibilities...
Απ: ΑΠΟΡΙΑ
« Απάντηση #5 στις: 07 Σεπ 2007, 09:54:25 πμ »
Κατά την γνώμη μου ο υπολογισμός του π δεν είναι άλυτο πρόβλημα. Υπάρχει αλγόριθμος που λύνει το πρόβλημα - απλά σε άπειρο χρόνο (δηλαδή υπολογιστική διαδικασία σύμφωνα με το βιβλίο). Η εύρεση ενός ρητού που να ισούται ακριβώς  με π είναι άλυτο πρόβλημα.
A man provided with paper, pencil, and rubber, and subject to strict discipline is in effect a universal machine - Alan Turing

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2448
  • I 'm not young enough to know everything
Απ: ΑΠΟΡΙΑ
« Απάντηση #6 στις: 07 Σεπ 2007, 12:25:05 μμ »
Παρένθεση:
Το πρόβλημα του π είναι κάτι βαθύτερο από το ότι δεν μπορεί να βρεθεί ρητός ίσος με αυτόν. Αυτή την ιδιότητα την έχουν όλοι οι άρρητοι (το λέει και η λέξη). Η διαφορά είναι ότι ο π είναι άρρητος υπερβατικός και άρα δεν μπορεί να κατασκευαστεί με κανόνα και διαβήτη ενώ οι άρρητοι αλγεβρικοί (όπως ο ρίζα 2) μπορούν. Το ότι ο π δεν κατασκευάζεται με κανόνα και διαβήτη σε πεπερασμένο αριθμό βημάτων είναι τελικά ισοδύναμο με το ότι δεν μπορεί να φτιαχτεί με κανόνα και διαβήτη τετράγωνο σε ίσο εμβαδό με δοσμένο κύκλο (που είναι και η κλασσική διατύπωση του τετραγωνισμού του κύκλου).

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

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

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

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



alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4856
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: ΑΠΟΡΙΑ
« Απάντηση #7 στις: 07 Σεπ 2007, 12:47:18 μμ »
Κάτι που ξεφεύγει κάπως είναι το ερώτημα: υπάρχουν άλυτα προβλήματα στα οποία δεν έχουμε λύση που συγκλίνει σε άπειρα βήματα (είμαστε δηλαδή τελείως στον αέρα) ή για κάθε άλυτο πρόβλημα υπάρχει δυνατότητα άπειρης προσέγγισης;

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

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

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

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4856
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: ΑΠΟΡΙΑ
« Απάντηση #8 στις: 07 Σεπ 2007, 01:02:41 μμ »
Υ.Γ. Γιώργο νομίζω ότι αυτό που έχεις στο νου σου είναι το "αν υπάρχουν προβλήματα εύρεσης αριθμητικής τιμής τα οποία να έχουν μεν λύση, όμως να μην έχουμε βρει αλγόριθμο για τη λύση τους (=ανοικτά), αλλά επίσης να μην έχουμε ούτε αλγόριθμο για κάποια προσεγγιστική λύση".

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

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2448
  • I 'm not young enough to know everything
Απ: ΑΠΟΡΙΑ
« Απάντηση #9 στις: 07 Σεπ 2007, 01:09:08 μμ »
Εδώ για να είναι ειλικρινής έχω την αίσθηση ότι άλυτο (για μας) είναι όχι αυτό που έχει αποδειχτεί ότι δεν έχει λύση αλλά αυτό που έχει αποδειχτεί ότι δεν υπάρχει αλγόριθμος που να δίνει τη λύση (δηλαδή ζητούμενο είναι ο αλγόριθμος). Το λέω αυτό γιατί ο π υπάρχει πάνω στην ευθεία των πραγματικών αλλά δεν έχουμε τρόπο (αλγόριθμο) να τον σχεδιάσουμε. Άρα μόνο αν ο αλγόριθμος είναι το ζητούμενο μπορούμε να πούμε ότι το πρόβλημα είναι άλυτο.

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

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

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

Παναγιώτης Τσιωτάκης

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3165
  • I love you 3000
    • Panagiotis Tsiotakis
Απ: ΑΠΟΡΙΑ
« Απάντηση #10 στις: 19 Σεπ 2007, 03:47:07 μμ »
Μήπως έχει γίνει λάθος στην απάντηση στο βοήθημα; Συμβαίνει και αυτό καμια φορά

d_bam

  • Οπαδός
  • **
  • Μηνύματα: 12
Απ: ΑΠΟΡΙΑ
« Απάντηση #11 στις: 24 Σεπ 2007, 07:24:48 μμ »
πιστεύω πως η πρόταση αυτή είναι ΣΩΣΤΗ! Ο υπολογιστή λύνει μόνο επιλύσιμα προβλήματα και μάλιστα μόνο ΔΟΜΗΜΕΝΑ!!!

anasta

  • Βετεράνος
  • ****
  • Μηνύματα: 58
  • Ok, yes... Ok, yes...
Απ: ΑΠΟΡΙΑ
« Απάντηση #12 στις: 27 Σεπ 2007, 02:37:24 μμ »
πιστεύω πως η πρόταση αυτή είναι ΣΩΣΤΗ! Ο υπολογιστή λύνει μόνο επιλύσιμα προβλήματα και μάλιστα μόνο ΔΟΜΗΜΕΝΑ!!!

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

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

tomemeto1

  • Θαμώνας
  • ***
  • Μηνύματα: 29
Απ: ΑΠΟΡΙΑ
« Απάντηση #13 στις: 03 Οκτ 2007, 03:42:44 πμ »
Το συγκεκριμένο βοήθημα λέει σαν θεωρία ότι Ανοικτά θεωρούνται και αυτά τα προβλήματα τα οποία μπορούν να λυθούν με την βοήθεια του ηλεκτρονικού υπολογιστή σε ένα μεγάλο πρακτικά μη αξιοποιήσιμο χρονικό διάστημα (χρόνια - αιώνες). (Πχ η ύπαρξη εξωγήινων , πύργοι Hanoi)
Σύμφωνα με αυτή την θεωρία η πρόταση είναι σωστή.

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

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4856
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: ΑΠΟΡΙΑ
« Απάντηση #14 στις: 03 Οκτ 2007, 07:29:24 πμ »
Ειδικά οι πύργοι του Ανόι είναι τόσο ...ανοικτό πρόβλημα, που ο αλγόριθμος για τη λύση του είναι στο τετράδιο μαθητή. :)

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

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

d_bam

  • Οπαδός
  • **
  • Μηνύματα: 12
Απ: ΑΠΟΡΙΑ
« Απάντηση #15 στις: 06 Οκτ 2007, 10:39:56 πμ »
πιστεύω πως η πρόταση αυτή είναι ΣΩΣΤΗ! Ο υπολογιστή λύνει μόνο επιλύσιμα προβλήματα και μάλιστα μόνο ΔΟΜΗΜΕΝΑ!!!

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

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


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

anasta

  • Βετεράνος
  • ****
  • Μηνύματα: 58
  • Ok, yes... Ok, yes...
Απ: ΑΠΟΡΙΑ
« Απάντηση #16 στις: 06 Οκτ 2007, 12:30:41 μμ »
στο βιβλίο αναφέρει πωσ για να φτάσω στην λύση ενός ημιδομημένου προβλήματος ή ενός αδόμητου, χρησιμοποιώ ανθρώπινη κρίση ή ανθρώπινο συναίσθημα! ο υπολογιστής δεν διαθέτει τίποτα από τα παραπάνω, άρα εδν μπορεί να τα λύσει! Λύνει μόνο δομημένα!

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

« Τελευταία τροποποίηση: 08 Οκτ 2007, 08:16:36 μμ από anasta »

d_bam

  • Οπαδός
  • **
  • Μηνύματα: 12
Απ: ΑΠΟΡΙΑ
« Απάντηση #17 στις: 12 Οκτ 2007, 01:09:46 μμ »
Συμφωνώ μαζί σου, ότι τα ΣΣΑ βοηθούν στη λήψη αποφάσεων, αυτό όμως δεν σημαίνει πως τα λύνει, απλά βοηθούν!  Ο άνθρωπος θα πάρει την απόφαση από ένα σύνολο λύσεων.
Τώρα αν μπαίνουν πολλοί παράμετροι ίσως το πρόβλημα παύει να είναι ημιδομημένο και γίνεται δομημένο, αφού θα υπάρχει μόνο μια λύση που να ικανοποιεί τις παραμέτρους.
Επίσης συμφωνώ πως ο υπολογιστής λύνει προβλήματα βελτιστοποίησης, αυτό όμως δεν σημαίνει πως αυτά είναι ημιδομημένα.