Με είχε απασχολήσει αρκετά το θέμα παλαιότερα επειδή ακριβώς δεν έβγαζα άκρη από το σχολικό βιβλίο. Έτσι διάβασα το συγκεκριμένο κομμάτι από το βιβλίο του Knuth από όπου είναι παρμένα τα αλγοριθμικά κριτήρια. Κατάλαβα τα εξής:
Στην αποτελεσματικότητα δεν έχει γίνει σωστή μεταφορά του όρου effectiveness από τα αγγλικά. Μεταφράστηκε σαν αποτελεσματικότητα αλλά το νόημα είναι κάτι σαν «πραγματοποιησιμότητα» αν μου επιτραπεί η έκφραση. Δηλαδή μιλάμε για τη δεύτερη ερμηνεία της λέξης effect.
http://www.in.gr/dictionary/lookup.asp?Word=effectEffectiveness σημαίνει να είναι οι λειτουργίες απλές έτσι ώστε να μπορούν να εκτελεστούν ακριβώς και σε πεπερασμένο χρονικό διάστημα από κάποιον με μολύβι και χαρτί. Παραδείγματα παραβίασης του effectiveness είναι το να έχεις μια συνθήκη της μορφής
Αν η ε έχει λύση
όπου η «ε» είναι μια εξίσωση που ζητούμε μόνο ακέραια λύση (διοφαντική) για την οποία δεν ξέρουμε αν υπάρχει λύση.
Άλλο παράδειγμα είναι στη διαίρεση. Αν έχουμε να διαιρέσουμε ακέραιους τότε δεν υπάρχει παραβίαση του effectiveness αφού οι ακέραιοι αναπαρίστανται ακριβώς με χαρτί και μολύβι και υπάρχει αλγόριθμος για τη διαίρεσή τους (Ευκλείδια διαίρεση). Αν όμως έχουμε αυθαίρετους πραγματικούς αριθμούς που αναπαρίστανται από άπειρα δεκαδικά ψηφία τότε παραβιάζεται το effectiveness αφού δεν μπορείς να αναπαραστήσεις ακριβώς τους εμπλεκόμενους αριθμούς με μολύβι και χαρτί.
Κάπως έτσι κατάλαβα αυτά που γράφει ο μεγάλος Donald Knuth.
Η καθοριστικότητα είναι κάτι απλό: Παραβίασή της έχουμε όταν αυτός που εκτελεί τον αλγόριθμο φτάσει σε κάποιο σημείο και πει «Ουπς
τι κάνουμε τώρα;»
Παραδείγματα παραβίασης της καθοριστικότητας είναι η διαίρεση με 0 αφού βάζεις τον υπολογιστή να κάνει κάτι που δεν γίνεται και λέει το «Ουπς
τώρα τι κάνουμε;»
ʼλλο παράδειγμα παραβίασης της καθοριστικότητας είναι το να πεις «Βάλε λίγο αλάτι» σε μια μαγειρική συνταγή. Πόσο είναι το λίγο αλάτι; Μια χούφτα; Ένα κουταλάκι της σούπας; Ένα κουταλάκι του γλυκού;
Αυτά για αρχή. Από κει και πέρα έχουν τεθεί εύστοχα ερωτήματα του στυλ «Τι θα γίνει αν αυτός που εκτελεί τον αλγόριθμο ξέρει ότι αρνητική τιμή σε ρίζα δίνει μιγαδικό ή ότι η διαίρεση με 0 δίνει άπειρο». Υπάρχουν περιβάλλοντα που χειρίζονται τέτοιες καταστάσεις από μόνα τους και δεν απαιτούν την παρέμβαση του προγραμματιστή με συνθήκες. Αυτά τα ερωτήματα σηκώνουν κουβέντα και τέτοιες έχουμε κάνει αρκετές. Έχω και άλλα ερωτήματα να θέσω εγώ. Αλλά νομίζω ότι σε πρώτη φάση ας μην σε μπλέξουμε άλλο.
Δεν ξέρω αν σε φώτισα ή σε σκότισα περισσότερο, αλλά αυτά είναι που προέκυψαν από το ψάξιμο που έριξα.