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

> Φυσική γλώσσα, διάγραμμα ροής, ψευδοκώδικας — και τι κάνει έναν αλγόριθμο σωστό.

Πληροφορική, Α΄ Λυκείου. https://www.akademio.gr/el/lyk-a/informatics/algorithm-representation

## Τι θα μάθεις

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

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

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

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

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

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

| Κριτήριο                               | Τι απαιτεί                                    | Παραβιάζεται από                                    |
| -------------------------------------- | --------------------------------------------- | --------------------------------------------------- |
| **Είσοδος** (input)                    | καμία, μία ή περισσότερες τιμές δεδομένων     | — (και το μηδέν επιτρέπεται)                        |
| **Έξοδος** (output)                    | **τουλάχιστον μία** τιμή αποτελέσματος        | διαδικασία που δεν εμφανίζει ούτε επιστρέφει τίποτα |
| **Καθοριστικότητα** (definiteness)     | κάθε εντολή έχει ένα μόνο νόημα               | «πρόσθεσε λίγο αλάτι»                               |
| **Περατότητα** (finiteness)            | τελειώνει μετά από πεπερασμένο πλήθος βημάτων | «όσο ο αριθμός είναι θετικός, πρόσθεσέ του $1$»     |
| **Αποτελεσματικότητα** (effectiveness) | κάθε εντολή είναι απλή και εκτελέσιμη         | «γράψε όλα τα ψηφία του $\pi$»                      |

> **Κλειδί**
>
> **Μηδέν είσοδοι επιτρέπονται, μηδέν έξοδοι όχι.**
>
> Ένας αλγόριθμος που εμφανίζει τους αριθμούς από το $1$ ως το $10$ δεν χρειάζεται κανένα δεδομένο, και παραμένει αλγόριθμος. Μια διαδικασία που δεν βγάζει κανένα αποτέλεσμα όμως δεν λύνει τίποτα, όσο σωστά κι αν δουλεύει εσωτερικά.

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

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

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

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

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

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

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

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

| Σχήμα                  | Χρήση                                         |
| ---------------------- | --------------------------------------------- |
| Έλλειψη                | αρχή και τέλος                                |
| Πλάγιο παραλληλόγραμμο | είσοδος (διάβασε) και έξοδος (εμφάνισε)       |
| Ορθογώνιο              | επεξεργασία, π.χ. υπολογισμός ή εκχώρηση      |
| Ρόμβος                 | έλεγχος συνθήκης, με δύο εξόδους: ναι και όχι |
| Βέλος                  | η σειρά εκτέλεσης                             |

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

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

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

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

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

*Διαδραστικό στη σελίδα: Ο μεγαλύτερος από δύο αριθμούς*

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

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

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

```text
13
```

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

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

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

| Δομή          | Τι κάνει                                                    | Στο διάγραμμα ροής                      |
| ------------- | ----------------------------------------------------------- | --------------------------------------- |
| **Ακολουθία** | εντολές η μία μετά την άλλη                                 | ορθογώνια στη σειρά                     |
| **Επιλογή**   | ανάλογα με μια συνθήκη, εκτελείται το ένα ή το άλλο         | ρόμβος με δύο κλάδους που ξαναενώνονται |
| **Επανάληψη** | ένα κομμάτι εκτελείται ξανά και ξανά όσο ισχύει μια συνθήκη | ρόμβος με βέλος που **γυρίζει πίσω**    |

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

*Διαδραστικό στη σελίδα: Άθροισμα των αριθμών από 1 έως n*

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

*Διαδραστικό στη σελίδα: Πίνακας τιμών για n = 3*

> **Πρόσεχε**
>
> **Η εκχώρηση δεν είναι εξίσωση.**
>
> Το `S <- S + i` στα μαθηματικά θα ήταν παράλογο: κανένας αριθμός δεν ισούται με τον εαυτό του συν κάτι θετικό. Ως εντολή όμως σημαίνει απλώς «πάρε την τωρινή τιμή του S, πρόσθεσε i, και γράψε το αποτέλεσμα πίσω στο S».

## Παραδείγματα

### Παράδειγμα 1: Ποιο κριτήριο παραβιάζει η οδηγία «όσο ο αριθμός είναι θετικός, διπλασίασέ τον»;

1. Κάθε εντολή χωριστά εκτελείται: ο διπλασιασμός είναι απλή πράξη. Άρα η **αποτελεσματικότητα** ικανοποιείται.
2. Αν ο αριθμός ξεκινά θετικός, διπλασιάζεται και μένει θετικός, οπότε η συνθήκη δεν γίνεται ποτέ ψευδής.
3. Η διαδικασία δεν τελειώνει ποτέ: παραβιάζεται η **περατότητα**.

   Αρκεί **μία** τιμή εισόδου για την οποία ο αλγόριθμος δεν τελειώνει ώστε να χαθεί το κριτήριο. Εδώ δεν τελειώνει για καμία θετική τιμή.

### Παράδειγμα 2: Γράψε σε ψευδοκώδικα αλγόριθμο που διαβάζει τον βαθμό ενός μαθητή (0 έως 20) και εμφανίζει «Προάγεται» αν είναι τουλάχιστον 10, αλλιώς «Απορρίπτεται».

1. **Δομές που χρειάζονται:** ακολουθία (διάβασε, μετά αποφάσισε) και επιλογή με δύο κλάδους. Δεν υπάρχει επανάληψη.
2. **Η συνθήκη:** «τουλάχιστον $10$» σημαίνει $10$ ή περισσότερο, άρα `βαθμός >= 10`, όχι `βαθμός > 10`.
3. **Ο ψευδοκώδικας:**
   ```text
   ΑΛΓΟΡΙΘΜΟΣ Προαγωγή
   ΔΙΑΒΑΣΕ βαθμός
   ΑΝ βαθμός >= 10 ΤΟΤΕ
     ΕΜΦΑΝΙΣΕ 'Προάγεται'
   ΑΛΛΙΩΣ
     ΕΜΦΑΝΙΣΕ 'Απορρίπτεται'
   ΤΕΛΟΣ_ΑΝ
   ΤΕΛΟΣ_ΑΛΓΟΡΙΘΜΟΥ
   ```
4. **Έλεγχος με την οριακή τιμή:** για βαθμό $10$ η συνθήκη είναι αληθής και εμφανίζεται «Προάγεται», όπως πρέπει. Με `>` θα απορριπτόταν ο μαθητής με ακριβώς $10$.

### Παράδειγμα 3: Στο διάγραμμα ροής του αθροίσματος, πώς ξεχωρίζεις ότι υπάρχει επανάληψη και όχι απλή επιλογή;

1. Και οι δύο δομές έχουν **ρόμβο** με δύο εξόδους, οπότε το σχήμα από μόνο του δεν αρκεί.
2. Στην **επιλογή**, οι δύο κλάδοι προχωρούν προς τα κάτω και ξαναενώνονται πιο κάτω.
3. Στην **επανάληψη**, ένα βέλος **γυρίζει πίσω** πριν από τον ρόμβο, ώστε η συνθήκη να ελεγχθεί ξανά.

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

## Ερωτήσεις

1. Μια διαδικασία δεν δέχεται κανένα δεδομένο και εμφανίζει τους αριθμούς από το 1 ως το 10. Είναι αλγόριθμος;
   - Ναι, γιατί η είσοδος μπορεί να είναι και μηδενική
   - Όχι, γιατί παραβιάζει το κριτήριο της εισόδου
   - Όχι, γιατί δεν τελειώνει ποτέ
   - Μόνο αν γραφτεί σε γλώσσα προγραμματισμού
2. Η οδηγία «ψήσε μέχρι να ροδίσει ελαφρά» παραβιάζει κυρίως:
   - την καθοριστικότητα
   - την περατότητα
   - την έξοδο
   - την είσοδο
3. Η εντολή «διαίρεσε το x με το 0» παραβιάζει:
   - την αποτελεσματικότητα
   - την περατότητα
   - την καθοριστικότητα
   - κανένα κριτήριο
4. Ποιο από τα κριτήρια απαιτεί «τουλάχιστον μία» τιμή;
   - η έξοδος
   - η είσοδος
   - και η είσοδος και η έξοδος
   - η περατότητα
5. Στο διάγραμμα ροής, ποιο σχήμα έχει δύο εξόδους;
   - ο ρόμβος
   - το ορθογώνιο
   - το πλάγιο παραλληλόγραμμο
   - η έλλειψη
6. Σε ένα διάγραμμα ροής, τι δείχνει ότι υπάρχει επανάληψη;
   - Ένα βέλος που γυρίζει πίσω, πριν από τον έλεγχο της συνθήκης
   - Ένας ρόμβος που ελέγχει μια συνθήκη με ναι ή όχι
   - Πολλά ορθογώνια στη σειρά, ένα για κάθε εντολή
   - Δύο ελλείψεις τέλους, μία για κάθε κλάδο
7. Τι σημαίνει η εντολή «S <- S + i» σε ψευδοκώδικα;
   - Υπολόγισε S + i και αποθήκευσε το αποτέλεσμα στο S
   - Έλεγξε αν η τιμή του S ισούται με την τιμή του S + i
   - Είναι λάθος, γιατί η εξίσωση S = S + i δεν έχει λύση
   - Υπολόγισε S + i και αποθήκευσε το αποτέλεσμα στο i
8. Στον βρόχο του αθροίσματος από 1 έως n, λείπει η εντολή «i <- i + 1». Τι συμβαίνει για n = 3;
   - Ο βρόχος δεν τελειώνει ποτέ
   - Εμφανίζεται 6, όπως και πριν
   - Εμφανίζεται 3
   - Εμφανίζεται 0, γιατί ο βρόχος δεν εκτελείται
9. Ποιος τρόπος αναπαράστασης αφήνει τα περισσότερα περιθώρια παρερμηνείας;
   - το ελεύθερο κείμενο
   - ο ψευδοκώδικας
   - το διάγραμμα ροής
   - η γλώσσα προγραμματισμού
10. Ο αλγόριθμος «διάβασε δύο αριθμούς και εμφάνισε τον μεγαλύτερο» χρησιμοποιεί:
   - ακολουθία και επιλογή
   - ακολουθία, επιλογή και επανάληψη
   - μόνο ακολουθία
   - μόνο επιλογή

## Ασκήσεις

1. Ποιο σχήμα του διαγράμματος ροής χρησιμοποιείται για την εντολή «Διάβασε x»;
2. Ποιο κριτήριο παραβιάζει η οδηγία «γράψε όλους τους φυσικούς αριθμούς»;
3. Εκτέλεσε τον αλγόριθμο του αθροίσματος από $1$ έως $n$ για $n = 4$.
   α) Τι εμφανίζει;
   β) Πόσες φορές ελέγχεται η συνθήκη του βρόχου;
   γ) Ποια είναι η τιμή του i στο τέλος;
4. Ο αλγόριθμος «ΔΙΑΒΑΣΕ x· ΟΣΟ x ≠ 1 ΕΠΑΝΑΛΑΒΕ x <- x - 2» τρέχει για διάφορες τιμές του x.
   α) Τελειώνει για x = 7;
   β) Τελειώνει για x = 6;
   γ) Ποιο κριτήριο παραβιάζεται;

---

Οι απαντήσεις, τα διαδραστικά και τα παιχνίδια είναι στη σελίδα της ενότητας: https://www.akademio.gr/el/lyk-a/informatics/algorithm-representation
