# Η επιστήμη των υπολογιστών

> Τι μελετά, και πώς φτάσαμε από τον Turing ως σήμερα.

Πληροφορική, Β΄ Λυκείου. https://www.akademio.gr/el/lyk-b/informatics/what-is-computer-science

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

- Να περιγράφεις τι μελετά η επιστήμη των υπολογιστών και γιατί δεν ταυτίζεται με τον προγραμματισμό.
- Να ελέγχεις αν μια διαδικασία είναι αλγόριθμος με τα πέντε κριτήρια.
- Να κατατάσσεις ένα ερώτημα στον κλάδο της πληροφορικής που το μελετά.
- Να τοποθετείς στον χρόνο τους σταθμούς από τον Turing ως τον Παγκόσμιο Ιστό.

## Τι μελετά

Η **επιστήμη των υπολογιστών** (computer science) μελετά τον **υπολογισμό**: τι μπορεί να υπολογιστεί, με πόσο κόστος, πώς αναπαρίσταται η πληροφορία και πώς χτίζονται τα συστήματα που κάνουν τη δουλειά στην πράξη.

Ο υπολογιστής είναι το εργαλείο της, όχι το αντικείμενό της. Μια φράση που αποδίδεται συχνά στον Edsger Dijkstra το λέει έτσι: η πληροφορική δεν αφορά τους υπολογιστές περισσότερο απ' όσο η αστρονομία αφορά τα τηλεσκόπια.

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

## Ο αλγόριθμος

Η λέξη προέρχεται από το όνομα του Πέρση μαθηματικού **al-Khwarizmi** (9ος αιώνας), του οποίου τα βιβλία έμαθαν στην Ευρώπη το δεκαδικό σύστημα αρίθμησης.

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

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

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

## Οι κλάδοι

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

| Κλάδος                         | Το ερώτημα που θέτει                                            | Σε αυτή την ενότητα            |
| ------------------------------ | --------------------------------------------------------------- | ------------------------------ |
| Θεωρία υπολογισμού             | Τι μπορεί να υπολογιστεί και με πόσο κόστος;                    | υπολογισιμότητα, πολυπλοκότητα |
| Αλγόριθμοι και δομές δεδομένων | Ποιος είναι ο καλύτερος τρόπος να λυθεί ένα πρόβλημα;           | πολυπλοκότητα, αναδρομή        |
| Αρχιτεκτονική υπολογιστών      | Πώς είναι φτιαγμένη η μηχανή που εκτελεί τις εντολές;           | αρχιτεκτονική, αναπαράσταση    |
| Λειτουργικά συστήματα          | Πώς μοιράζονται πολλά προγράμματα μία μηχανή;                   | λειτουργικά                    |
| Δίκτυα υπολογιστών             | Πώς μιλούν δύο υπολογιστές που δεν γνωρίζονται;                 | δίκτυα σε επίπεδα              |
| Γλώσσες προγραμματισμού        | Πώς περιγράφουμε έναν αλγόριθμο σε μηχανή;                      | γλώσσες και υποδείγματα        |
| Βάσεις δεδομένων               | Πώς οργανώνονται και ανακτώνται μεγάλοι όγκοι δεδομένων;        | βάσεις δεδομένων               |
| Τεχνητή νοημοσύνη              | Μπορεί μια μηχανή να μαθαίνει από παραδείγματα;                 | —                              |
| Ασφάλεια και κρυπτογραφία      | Πώς προστατεύεται η πληροφορία από όποιον δεν πρέπει να τη δει; | —                              |

## Δεδομένα και πληροφορία

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

- **Δεδομένα** (data) είναι ακατέργαστα στοιχεία: οι βαθμοί όλων των μαθητών ενός σχολείου, οι θερμοκρασίες κάθε ώρας ενός μήνα.
- **Πληροφορία** (information) είναι ό,τι προκύπτει όταν τα δεδομένα επεξεργαστούν ώστε να απαντούν σε ένα ερώτημα: «ο μέσος όρος του τμήματος ανέβηκε», «ο Ιούλιος ήταν ο θερμότερος των τελευταίων δέκα ετών».

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

## Από τον Turing ως σήμερα

| Χρονιά    | Σταθμός                                                                                                                         |
| --------- | ------------------------------------------------------------------------------------------------------------------------------- |
| περ. 825  | Ο al-Khwarizmi γράφει για τον υπολογισμό με το δεκαδικό σύστημα                                                                 |
| 1843      | Η Ada Lovelace δημοσιεύει σημειώσεις για την Αναλυτική Μηχανή του Charles Babbage, με ένα πρόγραμμα για τους αριθμούς Bernoulli |
| 1854      | Ο George Boole δημοσιεύει την άλγεβρα της λογικής, που θα γίνει η γλώσσα των κυκλωμάτων                                         |
| 1936      | Ο Alan Turing ορίζει με ακρίβεια τι είναι «υπολογισμός», με τη μηχανή που φέρει το όνομά του                                    |
| 1945      | Ο John von Neumann περιγράφει τον υπολογιστή με αποθηκευμένο πρόγραμμα                                                          |
| 1946      | Παρουσιάζεται δημόσια ο ENIAC, ένας από τους πρώτους ηλεκτρονικούς υπολογιστές γενικής χρήσης                                   |
| 1947      | Εφεύρεση του τρανζίστορ                                                                                                         |
| 1958      | Πρώτο ολοκληρωμένο κύκλωμα                                                                                                      |
| 1969      | Το ARPANET, πρόγονος του Διαδικτύου, συνδέει τους πρώτους κόμβους                                                               |
| 1971      | Ο πρώτος εμπορικός μικροεπεξεργαστής χωράει ολόκληρη την κεντρική μονάδα σε ένα τσιπ                                            |
| 1989–1991 | Ο Tim Berners-Lee προτείνει και υλοποιεί στο CERN τον Παγκόσμιο Ιστό                                                            |

*Η Ada Lovelace σε υδατογραφία γύρω στο 1840, λίγα χρόνια πριν από τις σημειώσεις του 1843. Σε αυτές περιέγραψε βήμα βήμα πώς η Αναλυτική Μηχανή θα υπολόγιζε τους αριθμούς Bernoulli, γι' αυτό το κείμενό της θεωρείται συχνά το πρώτο δημοσιευμένο πρόγραμμα.*

*Δοκιμαστικό κομμάτι της Αναλυτικής Μηχανής του Babbage, στο Μουσείο Επιστημών του Λονδίνου. Ολόκληρη η μηχανή δεν κατασκευάστηκε ποτέ· ο Babbage έφτιαξε μόνο τμήματα σαν αυτό. Οι στήλες από γρανάζια κρατούσαν αριθμούς, και η μηχανή του δούλευε στο δεκαδικό σύστημα, όχι στο δυαδικό.*

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

> **Θυμήσου**
>
> Ο **Turing** (1936) απάντησε στο «τι μπορεί να υπολογιστεί». Ο **von Neumann** (1945) στο «πώς χτίζεται μια μηχανή που το υπολογίζει». Το πρώτο είναι θεωρία, το δεύτερο αρχιτεκτονική, και θα τα δούμε σε χωριστές ενότητες.

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

Ο τρόπος που ένας επιστήμονας της πληροφορικής πλησιάζει ένα πρόβλημα λέγεται **υπολογιστική σκέψη** (computational thinking). Έχει τέσσερα συστατικά:

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

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

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

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

### Παράδειγμα 1: Είναι αλγόριθμος η διαδικασία: «Ξεκίνα με x = 1. Όσο το x είναι θετικό, αύξησε το x κατά 1. Στο τέλος τύπωσε το x»;

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

### Παράδειγμα 2: Μια συνταγή λέει: «Βάλε 500 g αλεύρι, αλάτι όσο θέλεις και ψήσε μέχρι να γίνει». Ποιο κριτήριο παραβιάζει;

1. **Το «500 g αλεύρι»** είναι σαφές και εκτελέσιμο.
2. **Το «αλάτι όσο θέλεις»** δεν ορίζει ποσότητα. Δύο άνθρωποι που το εκτελούν παίρνουν διαφορετικό αποτέλεσμα.
3. **Το «μέχρι να γίνει»** δεν λέει πώς ελέγχεται το «έγινε».
4. **Παραβιάζεται η καθοριστικότητα.** Η συνταγή είναι καλή οδηγία για άνθρωπο με εμπειρία, όχι αλγόριθμος. Για να γίνει, χρειάζεται π.χ. «5 g αλάτι» και «ψήσε 40 λεπτά στους 180 βαθμούς».

### Παράδειγμα 3: Σε ποιον κλάδο ανήκει το ερώτημα «γιατί η σελίδα φορτώνει αργά όταν πολλοί χρήστες μπαίνουν ταυτόχρονα;»

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

### Παράδειγμα 4: Ο αλγόριθμος του Ευκλείδη λέει: «Όσο ο b δεν είναι 0, αντικατάστησε το ζεύγος (a, b) με το (b, υπόλοιπο της διαίρεσης a με b). Στο τέλος τύπωσε το a». Εκτέλεσέ τον για \$a = 48\$, \$b = 18\$ και έλεγξε την περατότητα.

1. **Πρώτο βήμα:** $48 = 2 \cdot 18 + 12$, το ζεύγος γίνεται $(18, 12)$.
2. **Δεύτερο και τρίτο βήμα:** $18 = 1 \cdot 12 + 6$ δίνει $(12, 6)$, και $12 = 2 \cdot 6 + 0$ δίνει $(6, 0)$. Τυπώνεται $6$, ο μέγιστος κοινός διαιρέτης.
3. **Περατότητα:** το υπόλοιπο είναι πάντα μικρότερο από τον διαιρέτη, άρα ο b μικραίνει αυστηρά σε κάθε βήμα. Ένας φυσικός αριθμός δεν μπορεί να μικραίνει για πάντα, άρα κάποτε γίνεται $0$ και ο αλγόριθμος τελειώνει. Αυτό ισχύει για **κάθε** είσοδο, όχι μόνο για αυτή που δοκιμάσαμε.

## Ερωτήσεις

1. Ποιο είναι το κεντρικό αντικείμενο μελέτης της επιστήμης των υπολογιστών;
   - ο αλγόριθμος και ο υπολογισμός
   - το υλικό των υπολογιστών
   - η εκμάθηση γλωσσών προγραμματισμού
   - η σωστή χρήση των εφαρμογών γραφείου
2. Ποιο από τα κριτήρια ενός αλγορίθμου επιτρέπει να υπάρχουν μηδέν δεδομένα;
   - η είσοδος
   - η έξοδος
   - η περατότητα
   - κανένα, όλα απαιτούν τουλάχιστον ένα στοιχείο
3. Μια διαδικασία αυξάνει έναν θετικό αριθμό κατά $1$ όσο είναι θετικός. Ποιο κριτήριο παραβιάζει;
   - την περατότητα
   - την καθοριστικότητα
   - την αποτελεσματικότητα
   - κανένα, είναι σωστός αλγόριθμος
4. Η οδηγία «ρίξε αλάτι όσο θέλεις» παραβιάζει κυρίως:
   - την καθοριστικότητα
   - την περατότητα
   - την είσοδο
   - την έξοδο
5. Τι έκανε ο Alan Turing το $1936$;
   - όρισε με μαθηματική ακρίβεια τι σημαίνει «υπολογισμός»
   - κατασκεύασε τον πρώτο ηλεκτρονικό υπολογιστή
   - περιέγραψε την αρχιτεκτονική με αποθηκευμένο πρόγραμμα
   - εφηύρε το τρανζίστορ
6. Ποια σειρά είναι η σωστή χρονολογικά;
   - Boole, Turing, τρανζίστορ, Παγκόσμιος Ιστός
   - Turing, Boole, τρανζίστορ, Παγκόσμιος Ιστός
   - Boole, τρανζίστορ, Turing, Παγκόσμιος Ιστός
   - Boole, Turing, Παγκόσμιος Ιστός, τρανζίστορ
7. Ο χάρτης του μετρό δείχνει μόνο σταθμούς και συνδέσεις, με λάθος αποστάσεις. Ποια δεξιότητα της υπολογιστικής σκέψης δείχνει;
   - την αφαίρεση
   - την αποσύνθεση
   - την αναγνώριση προτύπων
   - τον αλγοριθμικό σχεδιασμό
8. Το ερώτημα «πώς μοιράζεται ένας επεξεργαστής ανάμεσα σε δέκα ανοιχτά προγράμματα;» ανήκει στον κλάδο:
   - των λειτουργικών συστημάτων
   - της αρχιτεκτονικής υπολογιστών
   - των δικτύων υπολογιστών
   - της θεωρίας υπολογισμού
9. Από πού προέρχεται η λέξη «αλγόριθμος»;
   - από το όνομα του μαθηματικού al-Khwarizmi
   - από τις ελληνικές λέξεις «άλγος» και «αριθμός»
   - από το όνομα του Alan Turing
   - από ένα αγγλικό αρκτικόλεξο της δεκαετίας του $1950$
10. Ποια δραστηριότητα είναι επιστήμη των υπολογιστών χωρίς να είναι προγραμματισμός;
   - η απόδειξη ότι κανένα πρόγραμμα δεν λύνει ένα συγκεκριμένο πρόβλημα
   - η συγγραφή μιας εφαρμογής για κινητό, από την ανάλυση ως τον έλεγχο
   - η μορφοποίηση ενός εγγράφου σε επεξεργαστή κειμένου
   - η εγκατάσταση ενός λειτουργικού συστήματος

## Ασκήσεις

1. Ποια δύο κριτήρια ενός αλγορίθμου αφορούν τα δεδομένα που μπαίνουν και τα αποτελέσματα που βγαίνουν;
2. Μια οδηγία λέει «ανακάτευε για λίγο». Ποιο κριτήριο αλγορίθμου παραβιάζει;
3. Ταξινόμησε χρονολογικά: ARPANET, μηχανή Turing, άλγεβρα Boole, πρώτος μικροεπεξεργαστής.
4. Δίνεται η διαδικασία: «Διάβασε έναν θετικό ακέραιο n. Όσο το n είναι διάφορο του $1$, αν είναι άρτιο διαίρεσέ το με $2$, αλλιώς πάρε $3n + 1$. Τύπωσε τη λέξη τέλος.»
   α) Πόσες αλλαγές κάνει το n ξεκινώντας από το $6$ μέχρι να γίνει $1$;
   β) Ποιο κριτήριο αλγορίθμου δεν έχει αποδειχθεί ότι ισχύει για κάθε n;

---

Οι απαντήσεις, τα διαδραστικά και τα παιχνίδια είναι στη σελίδα της ενότητας: https://www.akademio.gr/el/lyk-b/informatics/what-is-computer-science
