Τι είναι αλγόριθμος
Κεφ. 2 §2.1–2.3 · Ορισμός, κριτήρια, σπουδαιότητα, αναπαράσταση
Η συνταγή για παστίτσιο, οι οδηγίες συναρμολόγησης μιας ντουλάπας και ο GPS που σε πηγαίνει σπίτι έχουν κάτι κοινό: είναι σειρές σαφών βημάτων που οδηγούν σε αποτέλεσμα. Είναι όμως όλα αλγόριθμοι;
Όχι απαραίτητα! «Αλάτι όσο πάρει» δεν είναι αρκετά σαφές για υπολογιστή. Εδώ μαθαίνεις τον ακριβή ορισμό και τα πέντε κριτήρια — βασική ερώτηση θεωρίας στις Πανελλαδικές.
Ορισμός
Αλγόριθμος είναι μια πεπερασμένη σειρά ενεργειών, αυστηρά καθορισμένων και εκτελέσιμων σε πεπερασμένο χρόνο, που στοχεύουν στην επίλυση ενός προβλήματος.
Τα πέντε κριτήρια
Κάθε αλγόριθμος πρέπει να ικανοποιεί:
- Είσοδος (input): καμία, μία ή περισσότερες τιμές δεδομένων δίνονται ως είσοδος.
- Έξοδος (output): ο αλγόριθμος δημιουργεί τουλάχιστον μία τιμή ως αποτέλεσμα.
- Καθοριστικότητα (definiteness): κάθε εντολή είναι σαφής και χωρίς αμφιβολία για τον τρόπο εκτέλεσής της.
- Περατότητα (finiteness): ο αλγόριθμος τελειώνει μετά από πεπερασμένα βήματα, για όλες τις περιπτώσεις.
- Αποτελεσματικότητα (effectiveness): κάθε εντολή είναι τόσο απλή ώστε να μπορεί να εκτελεστεί με μολύβι και χαρτί.
Ένας «αλγόριθμος» περιέχει την εντολή «Διαίρεσε το α με το β» χωρίς να εξασφαλίζει ότι . Ποιο κριτήριο παραβιάζεται;
Παράδειγμα 1: Ποια κριτήρια παραβιάζει το παρακάτω τμήμα;
x ← 1 ΟΣΟ x > 0 ΕΠΑΝΑΛΑΒΕ x ← x + 1 ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΡΑΨΕ x
Λύση: Το x ξεκινά από 1 και μόνο αυξάνεται, άρα η συνθήκη x > 0 είναι πάντα αληθής: η επανάληψη δεν τελειώνει ποτέ. Παραβιάζεται η περατότητα — και κατά συνέπεια η έξοδος, αφού η εντολή ΓΡΑΨΕ δεν εκτελείται ποτέ.
Σπουδαιότητα των αλγορίθμων
Η έννοια του αλγορίθμου δεν συνδέεται αποκλειστικά με την Πληροφορική — τη συναντάς στα μαθηματικά, στη φυσική, στη χημεία, στη βιολογία, στην οικονομία. Στην Επιστήμη των Υπολογιστών η μελέτη των αλγορίθμων γίνεται από τέσσερις οπτικές γωνίες:
- Θεωρητική: υπάρχει αλγόριθμος για το πρόβλημα;
- Αναλυτική: πόσους υπολογιστικούς πόρους (χρόνο, μνήμη) απαιτεί;
- Σχεδίασης: πώς σχεδιάζουμε αποδοτικούς αλγορίθμους;
- Υλοποίησης: πώς τους μετατρέπουμε σε προγράμματα;
Περιγραφή και αναπαράσταση αλγορίθμων
Ένας αλγόριθμος μπορεί να αναπαρασταθεί με τέσσερις τρόπους:
- Ελεύθερο κείμενο (free text): πεζή περιγραφή — ο πιο ανεπεξέργαστος τρόπος, που κινδυνεύει να παραβιάσει την καθοριστικότητα.
- Φυσική γλώσσα κατά βήματα (natural language): αριθμημένα βήματα σε φυσική γλώσσα — και εδώ υπάρχει κίνδυνος ασάφειας.
- Διαγραμματικές τεχνικές (diagramming techniques): γραφικές απεικονίσεις, με πιο γνωστό το διάγραμμα ροής (flow chart).
- Κωδικοποίηση (coding): με ψευδογλώσσα ή με πρόγραμμα σε γλώσσα προγραμματισμού, ώστε να μπορεί να εκτελεστεί από υπολογιστή.
Στο κεφάλαιο 2 το βιβλίο γράφει τους αλγορίθμους σε μια ψευδογλώσσα («Αλγόριθμος … Τέλος», «Διάβασε», «Εμφάνισε») σχεδόν ίδια με τη ΓΛΩΣΣΑ. Στις εξετάσεις γράφεις σε ΓΛΩΣΣΑ, εκτός αν η εκφώνηση ζητά άλλη μορφή — γι' αυτό σε όλο το μάθημα χρησιμοποιούμε λέξεις της ΓΛΩΣΣΑΣ.
Τα σύμβολα του διαγράμματος ροής
- Έλλειψη: αρχή και τέλος του αλγορίθμου.
- Ρόμβος: ερώτηση (συνθήκη) με δύο εξόδους, ναι / όχι.
- Ορθογώνιο: εκτέλεση πράξεων (π.χ. εκχώρηση).
- Πλάγιο παραλληλόγραμμο: είσοδος ή έξοδος δεδομένων.
- Βέλη: δείχνουν τη ροή, δηλαδή τη σειρά εκτέλεσης.
Σε ένα διάγραμμα ροής, ποιο σύμβολο χρησιμοποιείται για την εντολή «Διάβασε α»;
Παράδειγμα 2: Γράψε αλγόριθμο που διαβάζει την ακτίνα ενός κύκλου και εμφανίζει το εμβαδόν του. Περιέγραψε και το αντίστοιχο διάγραμμα ροής.
Λύση:
ΑΛΓΟΡΙΘΜΟΣ Εμβαδον_Κυκλου ΔΙΑΒΑΣΕ R Ε ← 3.14 * R ^ 2 ΓΡΑΨΕ Ε ΤΕΛΟΣ Εμβαδον_Κυκλου
Διάγραμμα ροής: έλλειψη «Αρχή» → πλάγιο παραλληλόγραμμο «Διάβασε R» → ορθογώνιο «Ε ← 3.14 * R ^ 2» → πλάγιο παραλληλόγραμμο «Εμφάνισε Ε» → έλλειψη «Τέλος». Δεν υπάρχει ρόμβος, αφού δεν γίνεται καμία ερώτηση.
Θέμα τύπου Πανελλαδικών: Να αναφέρετε τα κριτήρια που πρέπει απαραίτητα να ικανοποιεί ένας αλγόριθμος. Στη συνέχεια εξηγήστε γιατί η οδηγία «ανακάτεψε το μείγμα για λίγο» δεν μπορεί να είναι εντολή αλγορίθμου.
Λύση: Κριτήρια: είσοδος (καμία, μία ή περισσότερες τιμές), έξοδος (τουλάχιστον μία τιμή), καθοριστικότητα (κάθε εντολή σαφής), περατότητα (τερματισμός σε πεπερασμένα βήματα), αποτελεσματικότητα (κάθε εντολή απλή και εκτελέσιμη).
Το «για λίγο» είναι ασαφές: δεν ορίζει πόσα λεπτά ή πόσες κινήσεις. Παραβιάζεται η καθοριστικότητα. Αν γίνει «ανακάτεψε 20 φορές», γίνεται αποδεκτή εντολή.
Ποια πρόταση για την είσοδο ενός αλγορίθμου είναι σωστή;
Η λέξη «αλγόριθμος» προέρχεται από το όνομα του Πέρση μαθηματικού του 9ου αιώνα al-Khwarizmi. Ένας από τους αρχαιότερους αλγορίθμους που χρησιμοποιούμε ακόμη είναι ο αλγόριθμος του Ευκλείδη για τον Μέγιστο Κοινό Διαιρέτη, από τα «Στοιχεία» (περίπου 300 π.Χ.).
Τα πέντε κριτήρια: «Είσοδος, Εξοδος, Καθοριστικότητα, Περάτωση, Αποτελεσματικότητα» — «Εδώ Είναι Καθαρά Πράγματα Απλά». Και θυμήσου: είσοδος ≥ 0, έξοδος ≥ 1.
Ένας φίλος σου λέει: «Ο αλγόριθμός μου διαβάζει έναν θετικό ακέραιο Ν και, όσο ο Ν είναι διάφορος του 1, αν είναι άρτιος τον διαιρεί με 2, αλλιώς τον κάνει 3Ν + 1. Στο τέλος εμφανίζει πόσα βήματα έγιναν.» Ικανοποιεί με βεβαιότητα την περατότητα;
Δοκίμασε πρώτα μόνος σου — μετά δες τη λύση
Δεν μπορούμε να το εγγυηθούμε! Είναι η περίφημη εικασία του Collatz: για κάθε αριθμό που έχει δοκιμαστεί η ακολουθία φτάνει στο 1 (π.χ. 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1, 8 βήματα), όμως κανείς δεν έχει αποδείξει ότι αυτό ισχύει για όλους τους θετικούς ακέραιους. Αφού η περατότητα απαιτεί τερματισμό για όλες τις περιπτώσεις, δεν μπορούμε να τη βεβαιώσουμε — είναι ανοικτό πρόβλημα.
- «Κάθε αλγόριθμος πρέπει να έχει είσοδο.» Λάθος: είσοδος καμία ή περισσότερες, έξοδος τουλάχιστον μία.
- Σύγχυση καθοριστικότητας (σαφήνεια) με αποτελεσματικότητα (απλότητα, εκτελεσιμότητα).
- Χρήση ορθογωνίου αντί για πλάγιο παραλληλόγραμμο για τα ΔΙΑΒΑΣΕ / ΓΡΑΨΕ στο διάγραμμα ροής.
- Αλγόριθμος: πεπερασμένη σειρά ενεργειών, αυστηρά καθορισμένων και εκτελέσιμων σε πεπερασμένο χρόνο, για την επίλυση προβλήματος.
- Κριτήρια: είσοδος, έξοδος, καθοριστικότητα, περατότητα, αποτελεσματικότητα.
- Οπτικές μελέτης: θεωρητική, αναλυτική, σχεδίασης, υλοποίησης.
- Αναπαράσταση: ελεύθερο κείμενο, φυσική γλώσσα κατά βήματα, διαγράμματα ροής, κωδικοποίηση.
- Διάγραμμα ροής: έλλειψη (αρχή/τέλος), ρόμβος (ερώτηση), ορθογώνιο (πράξη), πλάγιο παραλληλόγραμμο (είσοδος/έξοδος).