Αλγόριθμοι: κριτήρια και αναπαράσταση
Φυσική γλώσσα, διάγραμμα ροής, ψευδοκώδικας — και τι κάνει έναν αλγόριθμο σωστό.
35 λεπτά
Θα μάθεις να
- Να δίνεις τον ορισμό του αλγορίθμου και τα πέντε κριτήριά του.
- Να αναγνωρίζεις ποιο κριτήριο παραβιάζει μια λανθασμένη περιγραφή.
- Να αναπαριστάς έναν αλγόριθμο σε φυσική γλώσσα κατά βήματα, με διάγραμμα ροής και σε ψευδοκώδικα.
- Να ξεχωρίζεις τις τρεις βασικές δομές: ακολουθία, επιλογή, επανάληψη.
Τι είναι αλγόριθμος
Αλγόριθμος είναι μια πεπερασμένη σειρά ενεργειών, αυστηρά καθορισμένων και εκτελέσιμων σε πεπερασμένο χρόνο, που λύνουν ένα πρόβλημα.
Συνταγή μαγειρικής, οδηγίες συναρμολόγησης ενός επίπλου, ο τρόπος που κάνεις κάθετη διαίρεση: όλα αυτά είναι αλγόριθμοι, με μια προϋπόθεση. Κάθε βήμα πρέπει να είναι τόσο σαφές ώστε να το εκτελέσει κάποιος που δεν καταλαβαίνει τι προσπαθείς να πετύχεις. Ο υπολογιστής είναι ακριβώς τέτοιος εκτελεστής.
Τα πέντε κριτήρια
Μια σειρά οδηγιών είναι αλγόριθμος μόνο αν ικανοποιεί και τα πέντε:
| Κριτήριο | Τι απαιτεί | Παραβιάζεται από |
|---|---|---|
| Είσοδος (input) | καμία, μία ή περισσότερες τιμές δεδομένων | — (και το μηδέν επιτρέπεται) |
| Έξοδος (output) | τουλάχιστον μία τιμή αποτελέσματος | διαδικασία που δεν εμφανίζει ούτε επιστρέφει τίποτα |
| Καθοριστικότητα (definiteness) | κάθε εντολή έχει ένα μόνο νόημα | «πρόσθεσε λίγο αλάτι» |
| Περατότητα (finiteness) | τελειώνει μετά από πεπερασμένο πλήθος βημάτων | «όσο ο αριθμός είναι θετικός, πρόσθεσέ του » |
| Αποτελεσματικότητα (effectiveness) | κάθε εντολή είναι απλή και εκτελέσιμη | «γράψε όλα τα ψηφία του » |
Η αποτελεσματικότητα και η περατότητα μπερδεύονται εύκολα. Η πρώτη αφορά κάθε εντολή χωριστά: μπορεί να εκτελεστεί; Η δεύτερη αφορά όλο τον αλγόριθμο: θα τελειώσει ποτέ; Το «διαίρεσε με το μηδέν» παραβιάζει την αποτελεσματικότητα, γιατί η εντολή δεν μπορεί να εκτελεστεί ούτε μία φορά. Ένας βρόχος που δεν σταματά ποτέ παραβιάζει την περατότητα, αν και κάθε βήμα του εκτελείται μια χαρά.
Τέσσερις τρόποι να γραφτεί
Ο ίδιος αλγόριθμος μπορεί να γραφτεί με διαφορετικούς τρόπους. Ας τους δούμε όλους πάνω στο ίδιο πρόβλημα: διάβασε δύο αριθμούς και εμφάνισε τον μεγαλύτερο.
Φυσική γλώσσα κατά βήματα
- Διάβασε τον αριθμό a.
- Διάβασε τον αριθμό b.
- Αν ο a είναι μεγαλύτερος από τον b, εμφάνισε τον a.
- Αλλιώς, εμφάνισε τον b.
Είναι ο πιο φιλικός τρόπος, αλλά και ο πιο επικίνδυνος: η φυσική γλώσσα αφήνει εύκολα αμφισημίες, δηλαδή σπάει την καθοριστικότητα. Αν δεν αριθμήσεις τα βήματα και γράψεις σκέτο κείμενο, είναι ακόμα χειρότερα.
Διάγραμμα ροής
Το διάγραμμα ροής (flowchart) χρησιμοποιεί τυποποιημένα σχήματα που ενώνονται με βέλη:
| Σχήμα | Χρήση |
|---|---|
| Έλλειψη | αρχή και τέλος |
| Πλάγιο παραλληλόγραμμο | είσοδος (διάβασε) και έξοδος (εμφάνισε) |
| Ορθογώνιο | επεξεργασία, π.χ. υπολογισμός ή εκχώρηση |
| Ρόμβος | έλεγχος συνθήκης, με δύο εξόδους: ναι και όχι |
| Βέλος | η σειρά εκτέλεσης |
Σε κείμενο, το διάγραμμα για τον μεγαλύτερο αριθμό μοιάζει έτσι:
( Αρχή )
│
/ Διάβασε a, b /
│
◇ a > b ◇ ──όχι───┐
│ ναι │
│ │
/ Εμφάνισε a / / Εμφάνισε b /
│ │
└─────┬──────┘
│
( Τέλος )
Ο ρόμβος είναι το μόνο σχήμα με δύο εξόδους. Αν σε ένα διάγραμμα ροής δεις ορθογώνιο με δύο βέλη να βγαίνουν, κάτι είναι λάθος.
Ψευδοκώδικας
Ο ψευδοκώδικας είναι μια μέση λύση: μοιάζει με γλώσσα προγραμματισμού, αλλά δεν τρέχει σε υπολογιστή. Έχει λίγες, σταθερές λέξεις-κλειδιά, οπότε δεν αφήνει αμφισημίες, και δεν χρειάζεται να ξέρεις τους κανόνες μιας συγκεκριμένης γλώσσας.
Γλώσσα προγραμματισμού
Τέλος, ο αλγόριθμος γράφεται σε γλώσσα που εκτελεί ο υπολογιστής. Στην Python, με τους αριθμούς δοσμένους ώστε να φαίνεται η έξοδος:
a = 8
b = 13
if a > b:
print(a)
else:
print(b)
13
Οι τρεις βασικές δομές
Κάθε αλγόριθμος, όσο μεγάλος κι αν είναι, χτίζεται από τρεις μόνο δομές:
| Δομή | Τι κάνει | Στο διάγραμμα ροής |
|---|---|---|
| Ακολουθία | εντολές η μία μετά την άλλη | ορθογώνια στη σειρά |
| Επιλογή | ανάλογα με μια συνθήκη, εκτελείται το ένα ή το άλλο | ρόμβος με δύο κλάδους που ξαναενώνονται |
| Επανάληψη | ένα κομμάτι εκτελείται ξανά και ξανά όσο ισχύει μια συνθήκη | ρόμβος με βέλος που γυρίζει πίσω |
Ο αλγόριθμος του μεγαλύτερου αριθμού έχει ακολουθία (τα δύο διάβασε) και επιλογή (το ΑΝ). Η επανάληψη φαίνεται στο επόμενο:
Το <- είναι η εκχώρηση: υπολόγισε ό,τι είναι δεξιά και βάλ' το στη μεταβλητή αριστερά. Η γραμμή είναι αυτή που εξασφαλίζει την περατότητα: χωρίς αυτήν το i θα έμενε για πάντα και ο βρόχος δεν θα σταματούσε ποτέ.
Παραδείγματα
Παράδειγμα 1
Ποιο κριτήριο παραβιάζει η οδηγία «όσο ο αριθμός είναι θετικός, διπλασίασέ τον»;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Κάθε εντολή χωριστά εκτελείται: ο διπλασιασμός είναι απλή πράξη. Άρα η αποτελεσματικότητα ικανοποιείται.
Αν ο αριθμός ξεκινά θετικός, διπλασιάζεται και μένει θετικός, οπότε η συνθήκη δεν γίνεται ποτέ ψευδής.
Η διαδικασία δεν τελειώνει ποτέ: παραβιάζεται η περατότητα.
Αρκεί μία τιμή εισόδου για την οποία ο αλγόριθμος δεν τελειώνει ώστε να χαθεί το κριτήριο. Εδώ δεν τελειώνει για καμία θετική τιμή.
Παράδειγμα 2
Γράψε σε ψευδοκώδικα αλγόριθμο που διαβάζει τον βαθμό ενός μαθητή (0 έως 20) και εμφανίζει «Προάγεται» αν είναι τουλάχιστον 10, αλλιώς «Απορρίπτεται».
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Δομές που χρειάζονται: ακολουθία (διάβασε, μετά αποφάσισε) και επιλογή με δύο κλάδους. Δεν υπάρχει επανάληψη.
Η συνθήκη: «τουλάχιστον » σημαίνει ή περισσότερο, άρα
βαθμός >= 10, όχιβαθμός > 10.Ο ψευδοκώδικας:
ΑΛΓΟΡΙΘΜΟΣ Προαγωγή ΔΙΑΒΑΣΕ βαθμός ΑΝ βαθμός >= 10 ΤΟΤΕ ΕΜΦΑΝΙΣΕ 'Προάγεται' ΑΛΛΙΩΣ ΕΜΦΑΝΙΣΕ 'Απορρίπτεται' ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΑΛΓΟΡΙΘΜΟΥΈλεγχος με την οριακή τιμή: για βαθμό η συνθήκη είναι αληθής και εμφανίζεται «Προάγεται», όπως πρέπει. Με
>θα απορριπτόταν ο μαθητής με ακριβώς .
Παράδειγμα 3
Στο διάγραμμα ροής του αθροίσματος, πώς ξεχωρίζεις ότι υπάρχει επανάληψη και όχι απλή επιλογή;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Και οι δύο δομές έχουν ρόμβο με δύο εξόδους, οπότε το σχήμα από μόνο του δεν αρκεί.
Στην επιλογή, οι δύο κλάδοι προχωρούν προς τα κάτω και ξαναενώνονται πιο κάτω.
Στην επανάληψη, ένα βέλος γυρίζει πίσω πριν από τον ρόμβο, ώστε η συνθήκη να ελεγχθεί ξανά.
Αυτό το βέλος προς τα πίσω είναι το σημάδι του βρόχου. Αν λείπει, κάθε εντολή εκτελείται το πολύ μία φορά.
Πολλαπλή επιλογή
Ασκήσεις
Ποιο σχήμα του διαγράμματος ροής χρησιμοποιείται για την εντολή «Διάβασε x»;
Τα κατάφερες;
- Να δίνεις τον ορισμό του αλγορίθμου και τα πέντε κριτήριά του.
- Να αναγνωρίζεις ποιο κριτήριο παραβιάζει μια λανθασμένη περιγραφή.
- Να αναπαριστάς έναν αλγόριθμο σε φυσική γλώσσα κατά βήματα, με διάγραμμα ροής και σε ψευδοκώδικα.
- Να ξεχωρίζεις τις τρεις βασικές δομές: ακολουθία, επιλογή, επανάληψη.
Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.