# Βασικές έννοιες αλγορίθμων

> Τα πέντε κριτήρια, και οι τρόποι να γραφτεί ένας αλγόριθμος.

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

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

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

## Ο ορισμός

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

Κάθε κομμάτι του ορισμού αντιστοιχεί σε ένα από τα κριτήρια που ακολουθούν. Δεν είναι τυχαίο: ο ορισμός είναι τα κριτήρια, συμπυκνωμένα σε μία πρόταση.

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

| Κριτήριο               | Τι απαιτεί                                                |
| ---------------------- | --------------------------------------------------------- |
| **Είσοδος**            | καμία, μία ή περισσότερες τιμές δεδομένων                 |
| **Έξοδος**             | **τουλάχιστον μία** τιμή αποτελέσματος                    |
| **Καθοριστικότητα**    | κάθε εντολή ορίζεται χωρίς αμφιβολία, με ένα μόνο νόημα   |
| **Περατότητα**         | τερματίζει μετά από πεπερασμένο πλήθος βημάτων            |
| **Αποτελεσματικότητα** | κάθε εντολή είναι απλή και εκτελέσιμη με χαρτί και μολύβι |

> **Κλειδί**
>
> **Η ασυμμετρία εισόδου και εξόδου είναι το πιο συχνά εξεταζόμενο σημείο.**
>
> Είσοδος: **μηδέν ή περισσότερες** τιμές. Ένας αλγόριθμος που τυπώνει τους πρώτους εκατό φυσικούς δεν χρειάζεται καμία είσοδο, και παραμένει αλγόριθμος.
>
> Έξοδος: **τουλάχιστον μία** τιμή. Αλγόριθμος που δεν παράγει τίποτα δεν λύνει κανένα πρόβλημα, οπότε δεν είναι αλγόριθμος.
>
> Δηλαδή: **μηδέν είσοδοι ναι, μηδέν έξοδοι όχι.**

> **Πρόσεχε**
>
> Η **περατότητα** αφορά **κάθε** δυνατή εκτέλεση, όχι μία.
>
> Μια διαδικασία που τερματίζει για τα δεδομένα που δοκίμασες αλλά βρόχεται για κάποια άλλα **δεν** ικανοποιεί το κριτήριο. Ένα αντιπαράδειγμα αρκεί για να πέσει ολόκληρο το κριτήριο.

## Πώς γράφεται ένας αλγόριθμος

Τέσσερις τρόποι αναπαράστασης, από τον πιο χαλαρό στον πιο αυστηρό:

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

Τα σχήματα του διαγράμματος ροής:

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

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

## Ο ίδιος αλγόριθμος με τρεις τρόπους

Πρόβλημα: διάβασε δύο αριθμούς και εμφάνισε τον μεγαλύτερο.

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

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

**Διάγραμμα ροής**, σχήμα προς σχήμα: έλλειψη «Αρχή» → πλάγιο παραλληλόγραμμο «Διάβασε α, β» → ρόμβος «α > β;». Από το «ναι» ένα ορθογώνιο «μεγ ← α», από το «όχι» ένα ορθογώνιο «μεγ ← β». Τα δύο βέλη ενώνονται → πλάγιο παραλληλόγραμμο «Εμφάνισε μεγ» → έλλειψη «Τέλος».

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

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

Αν δώσεις $12$ και $12$, η συνθήκη `α > β` βγαίνει ψευδής και εμφανίζεται το β. Η απάντηση είναι πάλι σωστή, γιατί οι δύο τιμές είναι ίσες. Αυτόν τον έλεγχο των ίσων τιμών κάνε τον πάντα σε κάθε σύγκριση.

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

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

| Δομή                | Τι κάνει                                       | Στον ψευδοκώδικα                  |
| ------------------- | ---------------------------------------------- | --------------------------------- |
| Ακολουθία           | εντολές η μία μετά την άλλη, όλες από μία φορά | εκχωρήσεις, `ΔΙΑΒΑΣΕ`, `ΕΜΦΑΝΙΣΕ` |
| Επιλογή             | εκτελείται κάτι μόνο αν ισχύει μια συνθήκη     | `ΑΝ … ΤΟΤΕ … ΑΛΛΙΩΣ`              |
| Επανάληψη           | κάτι εκτελείται πολλές φορές                   | `ΟΣΟ`, `ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ`, `ΓΙΑ`   |
| Κλήση υποαλγορίθμου | ένα κομμάτι γραμμένο αλλού εκτελείται εδώ      | κλήση με όνομα                    |

Οι δομές **φωλιάζουν** η μία μέσα στην άλλη: μια επιλογή μέσα σε επανάληψη, μια επανάληψη μέσα σε επιλογή. Δεν διασταυρώνονται ποτέ. Αυτό που ανοίγει τελευταίο κλείνει πρώτο.

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

## Η εκχώρηση

Το σύμβολο `←` **δεν** είναι ισότητα. Η εντολή διαβάζεται από δεξιά προς τα αριστερά: **υπολόγισε τη δεξιά πλευρά και βάλε το αποτέλεσμα στη μεταβλητή της αριστερής**.

*Διαδραστικό στη σελίδα: Εναλλαγή δύο τιμών, βήμα βήμα*

> **Θυμήσου**
>
> **Η εκχώρηση δεν είναι εξίσωση.**
>
> Η γραμμή `X <- X + 1` είναι απολύτως έγκυρη και σημαίνει «πάρε την τρέχουσα τιμή του X, πρόσθεσε ένα, ξαναβάλ' το στο X». Ως εξίσωση θα ήταν παράλογη.
>
> Αντίστροφα, το `5 <- X` είναι **συντακτικό λάθος**: στα αριστερά του βέλους μπαίνει μόνο μεταβλητή.

## Τύποι, σταθερές, μεταβλητές

| Έννοια    | Ορισμός                                                 |
| --------- | ------------------------------------------------------- |
| Σταθερά   | μέγεθος που **δεν** μεταβάλλεται κατά την εκτέλεση      |
| Μεταβλητή | θέση μνήμης με όνομα, της οποίας το περιεχόμενο αλλάζει |
| Τελεστές  | αριθμητικοί, συγκριτικοί, λογικοί                       |
| Έκφραση   | συνδυασμός σταθερών, μεταβλητών και τελεστών            |

Στην ψευδογλώσσα οι σταθερές και οι μεταβλητές είναι **αριθμητικές**, **αλφαριθμητικές** ή **λογικές**. Η ΓΛΩΣΣΑ, στο πρόγραμμα, τις χωρίζει σε τέσσερις τύπους: **ακέραιος**, **πραγματικός**, **χαρακτήρας**, **λογικός**.

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

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

1. Η λέξη «αρκετό» δεν ορίζει ποσότητα.
2. Δύο άνθρωποι θα εκτελέσουν την ίδια εντολή διαφορετικά, άρα η εντολή δεν έχει ένα μόνο νόημα.
3. Παραβιάζεται η **καθοριστικότητα**.
4. **Η διόρθωση είναι η ποσοτικοποίηση:** «πρόσθεσε $5$ γραμμάρια αλάτι».

   Δεν αρκεί να είναι η εντολή κατανοητή — πρέπει να είναι **μονοσήμαντη**.

### Παράδειγμα 2: Είναι αλγόριθμος μια διαδικασία που δεν δέχεται κανένα δεδομένο εισόδου;

1. **Ναι.** Το κριτήριο της εισόδου δέχεται **μηδέν** ή περισσότερες τιμές.
2. **Παράδειγμα:** αλγόριθμος που τυπώνει τους αριθμούς από $1$ έως $100$. Όλα όσα χρειάζεται είναι γραμμένα μέσα του.
3. **Αντίθετα, μηδενική έξοδος δεν επιτρέπεται:** χρειάζεται τουλάχιστον ένα αποτέλεσμα.
4. **Ο λόγος της ασυμμετρίας είναι πρακτικός:** αλγόριθμος χωρίς έξοδο δεν έχει λύσει τίποτα για κανέναν, όσο σωστά κι αν εκτελέστηκε.

### Παράδειγμα 3: Δίνεται A = 5 και B = 8. Ποιες είναι οι τιμές μετά τις εντολές A ← B και B ← A, με αυτή τη σειρά;

1. **Πρώτη εντολή:** $A \leftarrow B$, άρα το $A$ παίρνει την τιμή $8$.

   Τώρα $A = 8$, $B = 8$.
2. **Η τιμή $5$ χάθηκε.** Δεν υπάρχει πια πουθενά στη μνήμη.
3. **Δεύτερη εντολή:** $B \leftarrow A$, άρα το $B$ παίρνει την τιμή $8$.

   Τελικά $A = 8$, $B = 8$.
4. **Δεν έγινε εναλλαγή.** Και οι δύο μεταβλητές κατέληξαν με $8$.

   Γι' αυτό η εναλλαγή απαιτεί **τρίτη** μεταβλητή: κάπου πρέπει να φυλαχτεί η τιμή που πρόκειται να γραφτεί από πάνω.

### Παράδειγμα 4: Ποιο κριτήριο απειλεί η οδηγία «διαίρεσε το X με το Y»;

1. **Την καθοριστικότητα.** Αν το $Y$ μπορεί να πάρει την τιμή μηδέν, η εντολή δεν λέει τι πρέπει να γίνει τότε.
2. Η καθοριστικότητα απαιτεί κάθε εντολή να ορίζεται **χωρίς αμφιβολία για κάθε τιμή**. Αυτό ακριβώς το παράδειγμα δίνει και το σχολικό βιβλίο: μια διαίρεση πρέπει να προβλέπει και μηδενικό διαιρέτη.
3. **Η διόρθωση** είναι έλεγχος πριν τη διαίρεση: αν $Y \neq 0$ τότε γίνεται η διαίρεση, αλλιώς εμφανίζεται μήνυμα.
4. **Πρόσεξε ότι το ίδιο παράδειγμα απειλεί και την περατότητα** σε άλλη μορφή: βρόχος που περιμένει να μηδενιστεί ένας μετρητής που αυξάνεται δεν τερματίζει ποτέ.

   Ένα κριτήριο μπορεί να πέσει από δεδομένα που κανείς δεν σκέφτηκε να δοκιμάσει.

### Παράδειγμα 5: Θέμα Β: δίνεται ο αλγόριθμος με \`x ← 472\` και τις εντολές \`ε ← x DIV 100\`, \`δ ← (x MOD 100) DIV 10\`, \`μ ← x MOD 10\`, \`y ← μ \* 100 + δ \* 10 + ε\`. Να γράψεις τις τιμές όλων των μεταβλητών μετά από κάθε εντολή.

1. **Η μέθοδος:** μία γραμμή του πίνακα τιμών για κάθε εντολή. Γράφεις μόνο τη μεταβλητή που αλλάζει. Οι άλλες κρατούν την τιμή που είχαν.
2. `x DIV 100` είναι το ακέραιο πηλίκο: $472$ διά $100$ δίνει $4$. Άρα `ε = 4`, το ψηφίο των εκατοντάδων.
3. `x MOD 100` είναι το υπόλοιπο, $72$. Το `72 DIV 10` δίνει $7$. Άρα `δ = 7`, οι δεκάδες. Και `x MOD 10` δίνει `μ = 2`, οι μονάδες.
4. Η τελευταία εντολή χτίζει τον αριθμό ανάποδα: $2 \cdot 100 + 7 \cdot 10 + 4 = 274$.

   *Διαδραστικό στη σελίδα: Τα ψηφία του 472, ανάποδα*
5. **Ο έλεγχος:** το `x` δεν άλλαξε ποτέ, γιατί δεν βρέθηκε ποτέ αριστερά από βέλος. Μια μεταβλητή αλλάζει **μόνο** όταν δέχεται εκχώρηση ή διαβάζεται.

### Παράδειγμα 6: Θέμα Γ: ένα θέατρο χρεώνει εισιτήριο \$4\$ ευρώ για ηλικία κάτω από \$12\$, \$5\$ ευρώ για ηλικία από \$65\$ και πάνω, και \$8\$ ευρώ για όλους τους άλλους. Να γράψεις αλγόριθμο σε ψευδογλώσσα που διαβάζει την ηλικία και εμφανίζει την τιμή. Ποια κριτήρια ελέγχεις στο τέλος;

1. **Ανάλυση πρώτα.** Είσοδος: μία ηλικία. Έξοδος: μία τιμή. Επεξεργασία: τρεις περιπτώσεις που δεν επικαλύπτονται.
2. **Ο αλγόριθμος.** Τρεις περιπτώσεις θέλουν `ΑΝ` με `ΑΛΛΙΩΣ_ΑΝ`, ώστε να εκτελεστεί ακριβώς μία.

   *Διαδραστικό στη σελίδα: Η τιμή του εισιτηρίου*
3. **Τα όρια.** «Κάτω από $12$» σημαίνει `< 12`: το παιδί $12$ ετών πληρώνει $8$. «Από $65$ και πάνω» σημαίνει `>= 65`: ο $65$χρονος πληρώνει $5$. Ένα λάθος σύμβολο εδώ κοστίζει μονάδες, και δεν το βρίσκεις αν δοκιμάσεις μόνο ηλικίες στη μέση.
4. **Τα κριτήρια.** Είσοδος: μία τιμή. Έξοδος: μία τιμή, άρα τουλάχιστον μία. Καθοριστικότητα: κάθε ηλικία πέφτει σε ακριβώς έναν κλάδο. Περατότητα: δεν υπάρχει βρόχος, άρα τελειώνει πάντα. Αποτελεσματικότητα: κάθε εντολή γίνεται με χαρτί και μολύβι.

## Ερωτήσεις

1. Ως προς την είσοδο, ένας αλγόριθμος πρέπει να δέχεται:
   - καμία, μία ή περισσότερες τιμές
   - τουλάχιστον μία τιμή
   - ακριβώς μία τιμή
   - τουλάχιστον δύο τιμές
2. Ως προς την έξοδο, ένας αλγόριθμος πρέπει να παράγει:
   - τουλάχιστον ένα αποτέλεσμα
   - καμία ή περισσότερες τιμές
   - τόσα αποτελέσματα όσα και τα δεδομένα εισόδου
   - ακριβώς ένα αποτέλεσμα
3. Η οδηγία «πρόσθεσε αρκετό αλάτι» παραβιάζει:
   - την καθοριστικότητα
   - την περατότητα
   - την έξοδο
   - την είσοδο
4. Μια διαδικασία τερματίζει για τα περισσότερα δεδομένα αλλά όχι για όλα. Τότε:
   - δεν ικανοποιεί την περατότητα
   - ικανοποιεί την περατότητα, αφού συνήθως τερματίζει
   - παραβιάζει την καθοριστικότητα
   - παραβιάζει την είσοδο
5. Ποιος τρόπος αναπαράστασης θεωρείται ο πιο ανεπιθύμητος;
   - το ελεύθερο κείμενο
   - το διάγραμμα ροής
   - η κωδικοποίηση
   - η φυσική γλώσσα κατά βήματα
6. Στο διάγραμμα ροής, ο ρόμβος παριστάνει:
   - έλεγχο συνθήκης
   - είσοδο ή έξοδο δεδομένων
   - αρχή ή τέλος
   - εκχώρηση τιμής
7. Η εντολή $X \leftarrow X + 1$:
   - είναι έγκυρη και αυξάνει το X κατά ένα
   - είναι λάθος, γιατί ως εξίσωση δεν αληθεύει
   - δεν αλλάζει την τιμή του X
   - επιτρέπεται μόνο μέσα σε βρόχο
8. Με $A = 5$ και $B = 8$, οι εντολές $A \leftarrow B$ και μετά $B \leftarrow A$ δίνουν:
   - $A = 8$ και $B = 8$
   - $A = 8$ και $B = 5$
   - $A = 5$ και $B = 8$
   - $A = 5$ και $B = 5$
9. Ο υπολογισμός «για καθέναν από τους 25 μαθητές, διάβασε τον βαθμό του» χρειάζεται κυρίως τη δομή:
   - επανάληψης
   - επιλογής
   - ακολουθίας
   - εκχώρησης
10. Η σχέση αλγορίθμου και προγράμματος είναι ότι:
   - το πρόγραμμα είναι αλγόριθμος γραμμένος σε γλώσσα προγραμματισμού
   - ο αλγόριθμος είναι πρόγραμμα που έχει ήδη μεταγλωττιστεί
   - είναι δύο λέξεις για το ίδιο ακριβώς πράγμα
   - ο αλγόριθμος δεν χρειάζεται να τερματίζει, το πρόγραμμα ναι

## Ασκήσεις

1. Πόσα είναι τα κριτήρια που πρέπει να ικανοποιεί κάθε αλγόριθμος;
2. Ποιο σχήμα του διαγράμματος ροής παριστάνει την είσοδο και την έξοδο δεδομένων;
3. Ποιο κριτήριο παραβιάζει η οδηγία «υπολόγισε την τετραγωνική ρίζα του X», όταν δεν προβλέπει τι γίνεται αν το X είναι αρνητικό;
4. Μια διαδικασία διαβάζει δύο αριθμούς και υπολογίζει το άθροισμά τους, αλλά δεν το εμφανίζει πουθενά. Ποιο κριτήριο παραβιάζει;
5. Δίνονται $A = 3$ και $B = 7$ και εκτελούνται με τη σειρά οι εντολές $B \leftarrow A$ και $A \leftarrow B$. Ποιες είναι οι τελικές τιμές των $A$ και $B$;
6. Εκτελούνται με τη σειρά οι εντολές $X \leftarrow 4$, $Y \leftarrow X + 2$, $X \leftarrow X * Y$, $Y \leftarrow X - Y$ και $X \leftarrow X - Y$.
   α) Πόσο είναι το $X$ μετά την τρίτη εντολή;
   β) Ποια είναι η τελική τιμή του $Y$;
   γ) Ποια είναι η τελική τιμή του $X$;
7. Εκτελούνται με τη σειρά οι εντολές `X <- 47`, `Y <- X div 10`, `Z <- X mod 10` και `W <- Z * 10 + Y`.
   α) Πόσο είναι το $Y$;
   β) Πόσο είναι το $Z$;
   γ) Πόσο είναι το $W$;
8. Δίνονται $A = 5$ και $B = 8$ και εκτελούνται με τη σειρά οι εντολές $A \leftarrow A + B$, $B \leftarrow A - B$ και $A \leftarrow A - B$, χωρίς καμία τρίτη μεταβλητή.
   α) Πόσο είναι το $A$ μετά την πρώτη εντολή;
   β) Πόσο είναι το $B$ μετά τη δεύτερη εντολή;
   γ) Ποια είναι η τελική τιμή του $A$;
   δ) Έγινε εναλλαγή των αρχικών τιμών;

---

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