# Επίλυση προβλημάτων με υπολογιστή

> Κατανόηση, ανάλυση, σχεδίαση, έλεγχος: τα στάδια πριν από τον κώδικα.

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

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

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

## Τι είναι πρόβλημα

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

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

Γι' αυτό το μεγαλύτερο μέρος της επίλυσης γίνεται **πριν** από τον κώδικα.

## Δεδομένα, ζητούμενα, περιορισμοί

Το πρώτο που κάνεις με ένα πρόβλημα είναι να το διαβάσεις και να το χωρίσεις σε τρία κομμάτια:

| Κομμάτι         | Ερώτηση που απαντά               | Παράδειγμα (εκδρομή)                                    |
| --------------- | -------------------------------- | ------------------------------------------------------- |
| **Δεδομένα**    | τι ξέρω ήδη;                     | πλήθος μαθητών, θέσεις ανά λεωφορείο, κόστος λεωφορείου |
| **Ζητούμενα**   | τι πρέπει να βρω;                | πόσα λεωφορεία, πόσο πληρώνει ο καθένας                 |
| **Περιορισμοί** | ποιοι κανόνες δεν παραβιάζονται; | κανείς δεν μένει όρθιος, τα λεωφορεία είναι ακέραια     |

> **Δεδομένα και πληροφορία**
>
> **Δεδομένα** είναι ακατέργαστα στοιχεία, όπως ο αριθμός $17$. **Πληροφορία** είναι ό,τι προκύπτει από την επεξεργασία τους και έχει νόημα για κάποιον: «ο μέσος όρος της τάξης είναι $17$».

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

> **Κλειδί**
>
> **Ένα πρόβλημα που δεν έχει διατυπωθεί καθαρά δεν λύνεται σωστά, όσο καλός κι αν είναι ο κώδικας.**
>
> Πριν σκεφτείς «πώς», γράψε σε μια πρόταση **τι** ζητάς. Αν δεν μπορείς, δεν έχεις καταλάβει ακόμα το πρόβλημα, και ό,τι γράψεις θα λύνει κάτι άλλο.

## Τα στάδια της επίλυσης

Η επίλυση ενός προβλήματος με υπολογιστή περνά από πέντε στάδια. Δεν είναι αυστηρά γραμμικά: ο έλεγχος συχνά σε στέλνει πίσω.

| Στάδιο           | Τι κάνεις                                                | Τι παράγεις                                |
| ---------------- | -------------------------------------------------------- | ------------------------------------------ |
| **1. Κατανόηση** | διαβάζεις, ξεχωρίζεις δεδομένα, ζητούμενα, περιορισμούς  | σαφή διατύπωση του προβλήματος             |
| **2. Ανάλυση**   | σπας το πρόβλημα σε μικρότερα κομμάτια                   | λίστα υποπροβλημάτων                       |
| **3. Σχεδίαση**  | βρίσκεις τα βήματα που λύνουν κάθε κομμάτι               | **αλγόριθμο**                              |
| **4. Υλοποίηση** | γράφεις τον αλγόριθμο σε γλώσσα προγραμματισμού          | **πρόγραμμα**                              |
| **5. Έλεγχος**   | τρέχεις το πρόγραμμα με δεδομένα που ξέρεις την απάντηση | διορθώσεις, και εμπιστοσύνη στο αποτέλεσμα |

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

## Ανάλυση: από πάνω προς τα κάτω

Ένα μεγάλο πρόβλημα σπάνια λύνεται μονομιάς. Η **ανάλυση από πάνω προς τα κάτω** (top-down) το σπάει σε υποπροβλήματα, και όποιο υποπρόβλημα είναι ακόμα μεγάλο το σπάει ξανά, μέχρι κάθε κομμάτι να είναι τόσο μικρό που η λύση του να φαίνεται αμέσως.

Για την εκδρομή:

```text
Οργάνωση εκδρομής
├── Πόσα λεωφορεία;
│   ├── Πόσοι μαθητές δήλωσαν;
│   └── Πόσες θέσεις έχει κάθε λεωφορείο;
├── Πόσο κοστίζει συνολικά;
│   └── λεωφορεία × κόστος λεωφορείου
└── Πόσο πληρώνει κάθε μαθητής;
    └── συνολικό κόστος ÷ πλήθος μαθητών
```

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

## Η υπολογιστική σκέψη

Τα στάδια αυτά στηρίζονται σε τέσσερις τρόπους σκέψης, που μαζί λέγονται **υπολογιστική σκέψη** (computational thinking):

- **Αποσύνθεση**: σπάω το πρόβλημα σε μικρότερα. Είναι η ανάλυση που μόλις είδες.
- **Αναγνώριση προτύπων**: βλέπω ότι ένα κομμάτι μοιάζει με κάτι που έχω ήδη λύσει. Ο μέσος όρος βαθμών και ο μέσος όρος θερμοκρασιών είναι το ίδιο πρόβλημα.
- **Αφαίρεση** (abstraction): κρατάω μόνο ό,τι επηρεάζει τη λύση. Το χρώμα του λεωφορείου δεν αλλάζει πόσα χρειάζονται.
- **Αλγοριθμική σκέψη**: γράφω τη λύση ως σειρά σαφών βημάτων που μπορεί να εκτελέσει κάποιος άλλος.

## Ο έλεγχος: δεδομένα που ξέρεις την απάντηση

Ένα πρόγραμμα που «τρέχει» δεν είναι απαραίτητα σωστό. Το ελέγχεις δίνοντάς του δεδομένα για τα οποία **ξέρεις ήδη** τη σωστή απάντηση, και συγκρίνεις.

Τα πιο χρήσιμα δεδομένα ελέγχου είναι οι **οριακές περιπτώσεις**: οι τιμές στα άκρα, όπου τα προγράμματα σπάνε πιο συχνά. Για λεωφορεία των $50$ θέσεων, ενδιαφέρουν ιδιαίτερα οι $50$ και οι $51$ μαθητές, όχι οι $37$.

Να ένα πρόγραμμα σε Python που κάνει ακριβώς αυτό το λάθος. Δεν χρειάζεται να ξέρεις ακόμα Python: το `//` είναι η ακέραια διαίρεση, που πετάει το δεκαδικό μέρος.

```python
students = 120
buses = students // 50
print(buses)
```

```text
2
```

Δύο λεωφορεία των $50$ θέσεων χωράνε $100$ μαθητές, οπότε $20$ μένουν στην άκρη του δρόμου. Με $100$ μαθητές το πρόγραμμα θα έδινε σωστή απάντηση, και ένας έλεγχος μόνο με αυτή την τιμή δεν θα έβρισκε ποτέ το λάθος.

> **Πρόσεχε**
>
> **«Το δοκίμασα και δούλεψε» δεν σημαίνει «είναι σωστό».**
>
> Ο έλεγχος μπορεί να δείξει ότι υπάρχει λάθος, αλλά δεν μπορεί να αποδείξει ότι δεν υπάρχει. Γι' αυτό διαλέγεις τα δεδομένα ελέγχου **επίτηδες**: μια συνηθισμένη τιμή, τις οριακές, και μία που δεν θα έπρεπε να γίνει δεκτή (π.χ. $0$ ή αρνητικό πλήθος μαθητών).

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

### Παράδειγμα 1: Ένα κατάστημα κάνει έκπτωση 20% σε αγορές πάνω από 50 ευρώ. Ξεχώρισε δεδομένα, ζητούμενα και περιορισμούς για το πρόγραμμα του ταμείου.

1. **Δεδομένα:** το ποσό της αγοράς, το ποσοστό έκπτωσης ($20\%$) και το όριο ($50$ ευρώ).
2. **Ζητούμενο:** το ποσό που θα πληρώσει ο πελάτης.
3. **Περιορισμοί:** το ποσό δεν μπορεί να είναι αρνητικό· η έκπτωση ισχύει **μόνο** πάνω από το όριο.
4. **Το ερώτημα που η εκφώνηση αφήνει ανοιχτό:** τι γίνεται με αγορά ακριβώς $50$ ευρώ;

   Το «πάνω από» λέει ότι στα $50$ δεν γίνεται έκπτωση. Αυτό πρέπει να ξεκαθαριστεί **πριν** γραφτεί ο κώδικας, γιατί εκεί ακριβώς θα διαφωνούσαν δύο προγραμματιστές.

### Παράδειγμα 2: Για το πρόγραμμα του ταμείου, διάλεξε δεδομένα ελέγχου και γράψε τη σωστή απάντηση για το καθένα.

1. **Μια συνηθισμένη τιμή κάτω από το όριο:** $30$ ευρώ, χωρίς έκπτωση, πληρώνει $30$.
2. **Μια συνηθισμένη τιμή πάνω από το όριο:** $100$ ευρώ, έκπτωση $20$, πληρώνει $80$.
3. **Οι οριακές:** $50$ ευρώ πληρώνει $50$ (δεν είναι «πάνω από»). $50{,}01$ ευρώ παίρνει έκπτωση και πληρώνει $40{,}01$ περίπου.
4. **Μια άκυρη τιμή:** $-10$ ευρώ. Το πρόγραμμα πρέπει να βγάλει μήνυμα λάθους, όχι ποσό.

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

### Παράδειγμα 3: Ανάλυσε από πάνω προς τα κάτω το πρόβλημα «βγάλε τον μέσο όρο κάθε μαθητή της τάξης και βρες ποιος έχει τον καλύτερο».

1. **Πρώτο επίπεδο:** (α) για κάθε μαθητή, υπολόγισε τον μέσο όρο του· (β) βρες τον μεγαλύτερο μέσο όρο· (γ) εμφάνισε το όνομα.
2. **Το (α) είναι ακόμα μεγάλο:** διάβασε τους βαθμούς του μαθητή, πρόσθεσέ τους, διαίρεσε με το πλήθος τους.
3. **Αναγνώριση προτύπου:** το «πρόσθεσε και διαίρεσε με το πλήθος» είναι ο ίδιος υπολογισμός για κάθε μαθητή. Γράφεται μία φορά και επαναλαμβάνεται.
4. **Αφαίρεση:** το φύλο, η ηλικία και το τμήμα του μαθητή δεν χρειάζονται για τη λύση, οπότε δεν μπαίνουν στα δεδομένα.

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

## Ερωτήσεις

1. Ποιο είναι το πρώτο στάδιο στην επίλυση ενός προβλήματος με υπολογιστή;
   - Η κατανόηση του προβλήματος
   - Η συγγραφή του προγράμματος
   - Ο έλεγχος με δεδομένα
   - Η σχεδίαση του αλγορίθμου
2. Στο πρόβλημα «πόσα λεωφορεία των 50 θέσεων χρειάζονται για 120 μαθητές», το «τα λεωφορεία είναι ακέραιος αριθμός» είναι:
   - περιορισμός
   - δεδομένο
   - ζητούμενο
   - άσχετη λεπτομέρεια που αφαιρείται
3. Ποια πρόταση για τον αλγόριθμο και το πρόγραμμα είναι σωστή;
   - Το πρόγραμμα είναι ένας αλγόριθμος γραμμένος σε γλώσσα προγραμματισμού.
   - Αλγόριθμος και πρόγραμμα είναι δύο λέξεις για το ίδιο πράγμα.
   - Ο αλγόριθμος γράφεται πάντα μετά το πρόγραμμα, για τεκμηρίωση.
   - Αλγόριθμος υπάρχει μόνο για προβλήματα με αριθμούς.
4. Πότε σταματάς να σπας ένα πρόβλημα σε υποπροβλήματα στην ανάλυση από πάνω προς τα κάτω;
   - Όταν κάθε κομμάτι λύνεται άμεσα, με μία ή δύο ενέργειες
   - Πάντα μετά από τρία επίπεδα
   - Όταν έχεις γράψει τον κώδικα
   - Όταν τα υποπροβλήματα γίνουν όσα και τα δεδομένα εισόδου
5. Όταν για το πλήθος των λεωφορείων αγνοείς το χρώμα τους, εφαρμόζεις:
   - αφαίρεση
   - αποσύνθεση
   - αναγνώριση προτύπων
   - έλεγχο
6. Ένα πρόγραμμα δίνει έκπτωση σε αγορές «από 50 ευρώ και πάνω». Ποια τιμή ελέγχου είναι η πιο χρήσιμη;
   - 50 ευρώ
   - 200 ευρώ
   - 10 ευρώ
   - Όλες είναι εξίσου χρήσιμες
7. Ένα πρόγραμμα έδωσε σωστό αποτέλεσμα σε 5 δοκιμές. Τι μπορείς να πεις με βεβαιότητα;
   - Ότι δουλεύει σωστά για αυτά τα 5 σύνολα δεδομένων
   - Ότι δεν έχει κανένα λάθος
   - Ότι θα δουλεύει σωστά για οποιαδήποτε τιμή
   - Ότι ο αλγόριθμος είναι σωστός, αλλά ο κώδικας ίσως όχι
8. Βλέπεις ότι ο μέσος όρος βαθμών και ο μέσος όρος θερμοκρασιών υπολογίζονται με τον ίδιο τρόπο. Αυτό είναι:
   - αναγνώριση προτύπων
   - αφαίρεση
   - υλοποίηση
   - σύμπτωση χωρίς χρησιμότητα
9. Το πρόγραμμα υπολογίζει λεωφορεία ως «μαθητές // 50». Για ποιο πλήθος μαθητών δίνει λάθος απάντηση;
   - 51
   - 50
   - 100
   - Για καμία, αφού η πράξη είναι σωστή
10. Ο αριθμός 17, γραμμένος μόνος του σε ένα χαρτί, είναι:
   - δεδομένο
   - πληροφορία
   - αλγόριθμος
   - ζητούμενο

## Ασκήσεις

1. Ποιο στάδιο της επίλυσης παράγει τον αλγόριθμο;
2. Πόσα λεωφορεία των $50$ θέσεων χρειάζονται για $151$ μαθητές;
3. Ένα πρόγραμμα υπολογίζει το εισιτήριο: κάτω από $12$ ετών πληρώνεις $5$ ευρώ, αλλιώς $8$ ευρώ.
   α) Ποια ηλικία είναι η πιο κρίσιμη οριακή τιμή;
   β) Πόσα ευρώ πρέπει να βγάλει για αυτή την ηλικία;
   γ) Δώσε μια άκυρη τιμή ηλικίας για έλεγχο.
4. Για την εκδρομή: $120$ μαθητές, λεωφορεία των $50$ θέσεων, $300$ ευρώ το λεωφορείο.
   α) Πόσα λεωφορεία χρειάζονται;
   β) Πόσο είναι το συνολικό κόστος;
   γ) Πόσο πληρώνει κάθε μαθητής;

---

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