Αλγόριθμοι: κριτήρια και αναπαράσταση

Τι είναι αλγόριθμος

Αλγόριθμος είναι μια πεπερασμένη σειρά ενεργειών, αυστηρά καθορισμένων και εκτελέσιμων σε πεπερασμένο χρόνο, που λύνουν ένα πρόβλημα.

Συνταγή μαγειρικής, οδηγίες συναρμολόγησης ενός επίπλου, ο τρόπος που κάνεις κάθετη διαίρεση: όλα αυτά είναι αλγόριθμοι, με μια προϋπόθεση. Κάθε βήμα πρέπει να είναι τόσο σαφές ώστε να το εκτελέσει κάποιος που δεν καταλαβαίνει τι προσπαθείς να πετύχεις. Ο υπολογιστής είναι ακριβώς τέτοιος εκτελεστής.

Τα πέντε κριτήρια

Μια σειρά οδηγιών είναι αλγόριθμος μόνο αν ικανοποιεί και τα πέντε:

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

Τέσσερις τρόποι να γραφτεί

Ο ίδιος αλγόριθμος μπορεί να γραφτεί με διαφορετικούς τρόπους. Ας τους δούμε όλους πάνω στο ίδιο πρόβλημα: διάβασε δύο αριθμούς και εμφάνισε τον μεγαλύτερο.

Φυσική γλώσσα κατά βήματα

1. Διάβασε τον αριθμό a.
2. Διάβασε τον αριθμό b.
3. Αν ο a είναι μεγαλύτερος από τον b, εμφάνισε τον a.
4. Αλλιώς, εμφάνισε τον b.

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

Διάγραμμα ροής

Το διάγραμμα ροής (flowchart) χρησιμοποιεί τυποποιημένα σχήματα που ενώνονται με βέλη:

Σε κείμενο, το διάγραμμα για τον μεγαλύτερο αριθμό μοιάζει έτσι:

          ( Αρχή )
             │
     / Διάβασε a, b /
             │
        ◇ a > b ◇ ──όχι───┐
             │ ναι        │
             │            │
     / Εμφάνισε a /  / Εμφάνισε b /
             │            │
             └─────┬──────┘
                   │
               ( Τέλος )

Ο ρόμβος είναι το μόνο σχήμα με δύο εξόδους. Αν σε ένα διάγραμμα ροής δεις ορθογώνιο με δύο βέλη να βγαίνουν, κάτι είναι λάθος.

Ψευδοκώδικας

Ο ψευδοκώδικας είναι μια μέση λύση: μοιάζει με γλώσσα προγραμματισμού, αλλά δεν τρέχει σε υπολογιστή. Έχει λίγες, σταθερές λέξεις-κλειδιά, οπότε δεν αφήνει αμφισημίες, και δεν χρειάζεται να ξέρεις τους κανόνες μιας συγκεκριμένης γλώσσας.

1. 1ΑΛΓΟΡΙΘΜΟΣ Μέγιστος
2. 2ΔΙΑΒΑΣΕ a, b
3. 3ΑΝ a > b ΤΟΤΕ
4. 4ΕΜΦΑΝΙΣΕ a
5. 5ΑΛΛΙΩΣ
6. 6ΕΜΦΑΝΙΣΕ b
7. 7ΤΕΛΟΣ_ΑΝ
8. 8ΤΕΛΟΣ_ΑΛΓΟΡΙΘΜΟΥ

Γλώσσα προγραμματισμού

Τέλος, ο αλγόριθμος γράφεται σε γλώσσα που εκτελεί ο υπολογιστής. Στην Python, με τους αριθμούς δοσμένους ώστε να φαίνεται η έξοδος:

a = 8
b = 13
if a > b:
    print(a)
else:
    print(b)

13

Οι τρεις βασικές δομές

Κάθε αλγόριθμος, όσο μεγάλος κι αν είναι, χτίζεται από τρεις μόνο δομές:

Ο αλγόριθμος του μεγαλύτερου αριθμού έχει ακολουθία (τα δύο διάβασε) και επιλογή (το ΑΝ). Η επανάληψη φαίνεται στο επόμενο:

1. 1ΑΛΓΟΡΙΘΜΟΣ Άθροισμα
2. 2ΔΙΑΒΑΣΕ n
3. 3S ← 0
4. 4i ← 1
5. 5ΟΣΟ i <= n ΕΠΑΝΑΛΑΒΕ
6. 6S ← S + i
7. 7i ← i + 1
8. 8ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
9. 9ΕΜΦΑΝΙΣΕ S
10. 10ΤΕΛΟΣ_ΑΛΓΟΡΙΘΜΟΥ

Το <- είναι η εκχώρηση: υπολόγισε ό,τι είναι δεξιά και βάλ' το στη μεταβλητή αριστερά. Η γραμμή $7$ είναι αυτή που εξασφαλίζει την περατότητα: χωρίς αυτήν το i θα έμενε $1$ για πάντα και ο βρόχος δεν θα σταματούσε ποτέ.

Πίνακας τιμών για n = 3

Κάθε γραμμή είναι ένας έλεγχος της συνθήκης. Πες τις τιμές πριν πατήσεις.

Βήμα	i	i <= n	S	νέο i
Ζωντανή ενημέρωση

Επόμενο βήμαΌλαΕπαναφορά

Λυμένα παραδείγματα

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση