Την "πλήρωσαν" Ευαγγελάτος "Big"

Περιορισμοί ελέγχου ορθότητας ενός αλγορίθμου

"Big brother" και "Αποδείξεις" πρωταγωνίστησαν στη χθεσινή συνεδρίαση του Εθνικού Συμβουλίου Ραδιοτηλεόρασης. Η πρόταση ενός αλγορίθμου καταλήγει στη σύνταξη κώδικα για την επίλυσή του στον υπολογιστή. Ο λόγος; Αν ένας προγραμματιστής έχει υλοποιήσει κώδικα για την υλοποίηση ενός αλγορίθμου, μπορεί να ελέγξει το πρόγραμμα "τρέχοντας" τον κώδικα μία, δύο, τρεις κ.λπ. φορές. Η επιβολή προστίμων που έφερε τα δύο αυτά προγράμματα στο… σκαμνί του ΕΣΡ. Έστω ότι σε όλες τις περιπτώσεις καταλήγει σε σωστά αποτελέσματα. Ειδικότερα, πρόστιμο ύψους 50.000 ευρώ για παράβαση της νομοθεσίας περί προστασίας ανηλίκων και χαμηλή ποιότητα προγράμματος επιβλήθηκε στον ΑΝΤ1 για την εκπομπή "Big Brother", που μεταδόθηκε στις 16 Νοεμβρίου 2005. Είναι όμως βέβαιο ότι, ο αλγόριθμος του προγράμματος δίνει πάντοτε τη σωστή λύση; Επίσης το Συμβούλιο επέβαλε πρόστιμο 20.000 ευρώ στον ALPHA για την εκπομπή "Αποδείξεις" που παρουσιάζει ο Νίκος Ευαγγελάτος, λόγω χρήσης αθέμιτων μέσων. Η απάντηση είναι όχι, διότι υπάρχει πιθανότητα κάποια φορά να καταλήξει σε λάθος αποτέλεσμα λόγω κάποιου λάθους στον αλγόριθμο. Επιπλέον στο στόχαστρο του ραδιοτηλεοπτικού οργάνου βρέθηκαν το "Θριάσιο TV" του νομού Αττικής, που τιμωρήθηκε με πρόστιμο 20.000 ευρώ για μη δηλωθείσα συχνότητα όπως και τα κανάλια "Τσάνελ 9" και "Τηλε-Αστυ" που καλούνται να πληρώσουν έκαστο 20.000 ευρώ για εκπομπές εκτός χάρτη συχνοτήτων. Το παράδειγμα που ακολουθεί παρουσιάζει μία τέτοια περίπτωση :

Εξάλλου το ΕΣΡ δεν ενέκρινε τη χορήγηση βεβαίωσης νομίμου λειτουργίας στο "Ράδιο Χρυσούπολη" του νομού Καβάλας λόγω μη προσκόμισης των απαραίτητων δικαιολογητικών.

Παράδειγμα: Να βρεθεί ο μικρότερος αριθμός από το σύνολο των θετικών αριθμών που βρίσκονται αποθηκευμένοι σε ένα πίνακα 10 θέσεων.

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

Στη συνέχεια δίνεται ο σχετικός αλγόριθμος για την εύρεση του μικρότερου στοιχείου σε πίνακα:

Αλγόριθμος Παράδειγμα3 Δεδομένα // a // lowa^[1] i Όσο i < 10 επανάλαβε Αν a[i]< low τότε low Τέλος_επανάληψης Αποτελέσματα // low // Τέλος Παράδειγμα3

Από τον ψευδοκώδικα αυτό μπορεί να θεωρήσει κανείς ότι, ο αλγόριθμος είναι σωστός και παράγει το σωστό αποτέλεσμα. Η ορθότητα του αλγορίθμου θα ελεγχθεί με ένα σύνολο από πίνακες 10 θέσεων, που έχουν τυχαίους αριθμούς. Έστω ότι προκύπτουν οι επόμενοι πίνακες από 3 διαφορετικές εκτελέσεις του προγράμματος του αλγορίθμου :

11 3 2 56 32 69 81 90 222 2

2 444 1 65 51 51 99 98 1 1

90 11 333 38 224 61 73 80 7 59

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

6 8 3 4 3 7 8 9 5 2 τότε ο αλγόριθμος θα δώσει ως αποτέλεσμα το 3, ενώ το μικρότερο στοιχείο είναι το 2. Άρα είναι σαφές ότι, υπάρχει κάποιο σφάλμα στον αλγόριθμο, που εδώ παρουσιάστηκε με την τέταρτη εκτέλεση του αλγορίθμου. Θα μπορούσε να είχε παρουσιασθεί το σφάλμα πολύ αργότερα, δηλαδή μετά από μεγάλο αριθμό επαναληπτικών εκτελέσεων του αλγορίθμου.

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

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

Για τον υπολογισμό της πιθανότητας να υπάρξει λάθος κατά την εκτέλεση του αλγορίθμου, παρατηρούμε ότι η πιθανότητα αυτή προκύπτει, όταν το μικρότερο στοιχείο βρίσκεται στην τελευταία θέση του πίνακα. Άρα η πιθανότητα είναι 1/10, αφού υπάρχουν 10 θέσεις στον πίνακα. Έτσι η πιθανότητα να μη βρεθεί το λάθος με μία προσπάθεια είναι 0,9. Αν γίνουν δύο προσπάθειες, λόγω της τυχαιότητας των στοιχείων του πίνακα η πιθανότητα αυτή γίνεται 0,9*0,9=0,81. Όσο επαναλαμβάνεται η εκτέλεση του αλγορίθμου για κάποια επιπλέον τυχαία ακολουθία δεδομένων οι πιθανότητες διαμορφώνονται ως εξής :

Αριθμός Πιθανότητα Πιθανότητα Εκτελέσεων Ανεύρεσης Μη-Ανεύρεσης Αλγορίθμου Σφάλματος Σφάλματος 1 0,10,9 2 0,19 0,81 3 0,271 0,729 4 0,344 0,656 5 0,410 0,590 6 0,469 0,531 7 0,522 0,478

Από αυτόν τον πίνακα πιθανοτήτων, είναι φανερό ότι χρειάζονται τουλάχιστον 7 προσπάθειες εκτέλεσης του αλγορίθμου για να υπάρχει πιθανότητα της τάξης του 0,5 να βρεθεί ένα σφάλμα. Η παραπάνω καταγραφή των πιθανοτήτων αποτελεί έναν τρόπο εκτίμησης για τον εντοπισμό λαθών ενός αλγορίθμου. Ωστόσο, δεν μπορεί να υπάρξει απόλυτη ασφάλεια στην εκτίμηση των πιθανών σφαλμάτων ενός αλγορίθμου. Γενικότερα δεν μπορεί να υπάρξει απόλυτη επιβεβαίωση της εγκυρότητας ενός αλγορίθμου με χρήση κάποιας πιθανολογικής εκτίμησης των πιθανών σφαλμάτων του.

Η απόδειξη της ορθότητας ενός αλγορίθμου θα πρέπει να περιλαμβάνει τις εξής δύο συνθήκες : - απόδειξη ότι σε κάθε περίπτωση ο τερματισμός της εκτέλεσης του αλγορίθμου οδηγεί σε αποδεκτά αποτελέσματα, και - απόδειξη ότι θα υπάρξει τερματισμός της εκτέλεσης του αλγορίθμου

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

Έστω ότι δίνονται δύο μεταβλητές a και b με τις αντίστοιχες τιμές τους και ότι πρέπει να παρουσιασθεί ένας αλγόριθμος ανταλλαγής των τιμών τους. Αν υπάρχει εκ των προτέρων πρόβλεψη για την ορθότητα ενός αλγορίθμου ανταλλαγής των τιμών δύο μεταβλητών, τότε θα πρέπει να ακολουθηθεί κάποια τυποποίηση και στην ονοματολογία των μεταβλητών. Αυτό είναι απαραίτητο, γιατί είναι σαφές ότι η ανταλλαγή των μεταβλητών όπως: a Επομένως, οι αρχικές τιμές των μεταβλητών πρέπει να αποθηκευθούν σε κάποιες προσωρινές μεταβλητές a0 και b0 αντίστοιχα. Έτσι, ο στόχος του προβλήματος είναι να ισχύει: a=b0 και b=a0. Με αυτήν την ονοματολογία το πρόβλημα αντιμετωπίζεται στη γενική του μορφή. Ωστόσο, η προηγούμενη τυποποίηση είναι απλά ενδεικτική, γιατί τελικά επαρκεί μία επιπλέον μεταβλητή που θα λειτουργήσει ως ενδιάμεσος χώρος για την ανταλλαγή των τιμών των μεταβλητών. Ο προτεινόμενος αλγόριθμος λοιπόν είναι: t

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