ΑΛΓΟΡΙΘΜΙΚΑ ΚΡΙΤΗΡΙΑ... ΚΑΘΟΡΙΣΤΙΚΟΤΗΤΑ ΚΑΙ ΑΠΟΤΕΛΕΣΜΑΤΙΚΟΤΗΤΑ

Ξεκίνησε από Juan, 07 Μαΐου 2007, 10:42:31 ΜΜ

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

Juan

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

gpapargi

Με είχε απασχολήσει αρκετά το θέμα παλαιότερα επειδή ακριβώς δεν έβγαζα άκρη από το σχολικό βιβλίο. Έτσι διάβασα το συγκεκριμένο κομμάτι από το βιβλίο του Knuth από όπου είναι παρμένα τα αλγοριθμικά κριτήρια. Κατάλαβα τα εξής:

Στην αποτελεσματικότητα δεν έχει γίνει σωστή μεταφορά του όρου effectiveness από τα αγγλικά. Μεταφράστηκε σαν αποτελεσματικότητα αλλά το νόημα είναι κάτι σαν «πραγματοποιησιμότητα» αν μου επιτραπεί η έκφραση. Δηλαδή μιλάμε για τη δεύτερη ερμηνεία της λέξης effect.
http://www.in.gr/dictionary/lookup.asp?Word=effect

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

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

Κάπως έτσι κατάλαβα αυτά που γράφει ο μεγάλος Donald Knuth.   

Η καθοριστικότητα είναι κάτι απλό: Παραβίασή της έχουμε όταν αυτός που εκτελεί τον αλγόριθμο φτάσει σε κάποιο σημείο και πει «Ουπς… τι κάνουμε τώρα;»
Παραδείγματα παραβίασης της καθοριστικότητας είναι η διαίρεση με 0 αφού βάζεις τον υπολογιστή να κάνει κάτι που δεν γίνεται και λέει το «Ουπς… τώρα τι κάνουμε;»
ʼλλο παράδειγμα παραβίασης της καθοριστικότητας είναι το να πεις «Βάλε λίγο αλάτι» σε μια μαγειρική συνταγή. Πόσο είναι το λίγο αλάτι; Μια χούφτα; Ένα κουταλάκι της σούπας; Ένα κουταλάκι του γλυκού;

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

Δεν ξέρω αν σε φώτισα ή σε σκότισα περισσότερο, αλλά αυτά είναι που προέκυψαν από το ψάξιμο που έριξα.


anasta

ΚΑΘΟΡΙΣΤΙΚΟΤΗΤΑ= "ΕΚΤΕΛΕΣΙΜΟΤΗΤΑ" + ΠΛΗΡΟΤΗΤΑ
"ΕΚΤΕΛΕΣΙΜΟTHTA": τα βήματα να είναι έτσι διατυπωμένα ώστε να μπορούν να εκτελεστούν απο τον Η/Υ
ΠΛΗΡΟΤΗΤΑ: ο αλγόριθμος να προβλέπει κάθε πιθανό ενδεχόμενο κατά την εκτέλεσή του, π.χ. διαίρεση με μηδέν

ΑΠΟΤΕΛΕΣΜΑΤΙΚΟΤΗΤΑ=Διάφορα δοκιμαστικά δεδομένα μας δίνουν τα αναμενόμενα αποτελέσματα. Μετά το πέρας της εκτέλεσης των βημάτων να έχει επιτευχθεί ο στόχος (το ζητούμενο).

Juan

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

Φιλικά
Γιάννης