Εισαγωγή στις Αρχές της Επιστήμης των Η/Υ

Κεφάλαιο 2.2 – Αλγόριθμοι   Ορισμός και Αναπαράσταση Αλγορίθμου

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

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

Για παράδειγμα:

·        για να φτιάξουμε έναν καφέ, ακολουθούμε συγκεκριμένα βήματα,

·        για να υπολογίσουμε τον μέσο όρο δύο αριθμών, κάνουμε συγκεκριμένες πράξεις,

·        για να βρούμε τον μεγαλύτερο από δύο αριθμούς, ακολουθούμε μια συγκεκριμένη διαδικασία.

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

Ορισμός

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

Με απλά λόγια:

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

Ο αλγόριθμος πρέπει να περιγράφει με σαφήνεια τι πρέπει να γίνει και με ποια σειρά.

Παράδειγμα

Πρόβλημα:

Να υπολογιστεί το άθροισμα δύο αριθμών.

Μια απλή διαδικασία είναι:

1.     Να δοθούν οι δύο αριθμοί.

2.     Να προστεθούν οι δύο αριθμοί.

3.     Να εμφανιστεί το αποτέλεσμα.

Αυτή η διαδικασία αποτελεί έναν απλό αλγόριθμο.

2. Γιατί πρέπει να αναπαριστούμε έναν αλγόριθμο;

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

Η αναπαράσταση του αλγορίθμου μας βοηθά:

·        να κατανοήσουμε τη διαδικασία επίλυσης,

·        να ελέγξουμε αν τα βήματα είναι σωστά,

·        να επικοινωνήσουμε τον αλγόριθμο σε άλλους,

·        και αργότερα να μπορέσουμε να τον μετατρέψουμε σε πρόγραμμα.

3. Οι 4 τρόποι αναπαράστασης ενός αλγορίθμου

Σύμφωνα με το βιβλίο, η αναπαράσταση των αλγορίθμων μπορεί να πραγματοποιηθεί με τέσσερις τρόπους:

1.     Φυσική γλώσσα

2.     Ψευδοκώδικα ή ψευδογλώσσα

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

4.     Διαγραμματική αναπαράσταση – διάγραμμα ροής

3.1 Φυσική γλώσσα

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

Με τη φυσική γλώσσα περιγράφουμε τα βήματα επίλυσης του προβλήματος.

Παράδειγμα

Πρόβλημα:

Να υπολογιστεί το άθροισμα δύο αριθμών.

Με φυσική γλώσσα:

Διάβασε δύο αριθμούς.
Πρόσθεσε τους δύο αριθμούς.
Εμφάνισε το άθροισμά τους.

Πλεονέκτημα

Είναι εύκολη στην κατανόηση από τον άνθρωπο.

Μειονέκτημα

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

3.2 Ψευδοκώδικας ή ψευδογλώσσα

Ο ψευδοκώδικας ή ψευδογλώσσα είναι μια υποθετική γλώσσα που χρησιμοποιείται για την αναπαράσταση αλγορίθμων.

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

Παράδειγμα

Αλγόριθμος Άθροισμα

Διάβασε α, β

s ← α + β

Εμφάνισε s

Τέλος Άθροισμα

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

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

Η γλώσσα προγραμματισμού είναι μια τεχνητή γλώσσα που έχει αναπτυχθεί για να δημιουργεί ή να εκφράζει προγράμματα για τον υπολογιστή.

Η αναπαράσταση αλγορίθμων με γλώσσα προγραμματισμού μπορεί να γίνει:

·        με οπτικές γλώσσες προγραμματισμού, όπου χρησιμοποιείται γραφικός χειρισμός προγραμματιστικών στοιχείων,

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

Παράδειγμα σε Python

a = int(input())

b = int(input())

s = a + b

print(s)

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

3.4 Διαγραμματική αναπαράσταση – Διάγραμμα ροής

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

Από τις διάφορες μεθοδολογίες, η πιο διαδεδομένη είναι το διάγραμμα ροής.

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

4. Βασικά σύμβολα διαγράμματος ροής

4.1 Έλλειψη – Αρχή / Τέλος

Η έλλειψη χρησιμοποιείται για να δηλώσει:

·        την αρχή του αλγορίθμου,

·        το τέλος του αλγορίθμου.

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

4.2 Πλάγιο παραλληλόγραμμο – Είσοδος / Έξοδος

Το πλάγιο παραλληλόγραμμο δηλώνει:

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

4.3 Ορθογώνιο παραλληλόγραμμο – Πράξη

Το ορθογώνιο παραλληλόγραμμο δηλώνει την εκτέλεση μίας ή περισσότερων πράξεων.

Παράδειγμα:

4.4 Ρόμβος – Ερώτηση / Συνθήκη

Ο ρόμβος δηλώνει μία ερώτηση με δύο εξόδους για απάντηση.

Άρα ο ρόμβος χρησιμοποιείται όταν ο αλγόριθμος πρέπει να επιλέξει μεταξύ δύο διαφορετικών διαδρομών.

4.5 Βέλος – Ροή εκτέλεσης

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

5. Παράδειγμα 2.7 του βιβλίου – Αντιμετάθεση δύο μεταβλητών

Το βιβλίο ζητά να αναπτυχθεί αλγόριθμος ο οποίος:

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

α = 8

β = 12

α = 12

β = 8

Το βιβλίο παρουσιάζει το παράδειγμα με φυσική γλώσσα, διάγραμμα ροής και ψευδογλώσσα.

Φυσική γλώσσα

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

Αλγόριθμος Αντιμετάθεση

Διάβασε α, β

temp ← α

α ← β

β ← temp

Εμφάνισε α, β

Τέλος Αντιμετάθεση

Άρα: α = 12    β = 8

6. Τρία λυμένα παραδείγματα

Παράδειγμα 1 – Υπολογισμός αθροίσματος

Πρόβλημα

Να αναπτυχθεί αλγόριθμος που διαβάζει δύο αριθμούς και εμφανίζει το άθροισμά τους.

Λύση με φυσική γλώσσα

1.     Διάβασε δύο αριθμούς.

2.     Πρόσθεσε τους δύο αριθμούς.

3.     Εμφάνισε το άθροισμα.

Λύση με ψευδογλώσσα

Αλγόριθμος Άθροισμα

Διάβασε α, β

s ← α + β

Εμφάνισε s

Τέλος Άθροισμα

Παράδειγμα 2 – Υπολογισμός εμβαδού ορθογωνίου

Πρόβλημα

Να αναπτυχθεί αλγόριθμος που διαβάζει το μήκος και το πλάτος ενός ορθογωνίου και εμφανίζει το εμβαδόν του.

Λύση με φυσική γλώσσα

1.     Διάβασε το μήκος.

2.     Διάβασε το πλάτος.

3.     Υπολόγισε το εμβαδόν πολλαπλασιάζοντας μήκος × πλάτος.

4.     Εμφάνισε το εμβαδόν.

Ψευδογλώσσα

Αλγόριθμος Εμβαδόν

Διάβασε μήκος, πλάτος

Ε ← μήκος * πλάτος

Εμφάνισε Ε

Τέλος Εμβαδόν

Για μήκος = 8 και πλάτος = 5:

Ε = 8 * 5 = 40

Παράδειγμα 3 – Υπολογισμός μέσου όρου

Πρόβλημα

Να αναπτυχθεί αλγόριθμος που διαβάζει τρεις βαθμούς και εμφανίζει τον μέσο όρο τους.

Λύση

1.     Διάβασε τους τρεις βαθμούς.

2.     Πρόσθεσέ τους.

3.     Διαίρεσε το άθροισμα με το 3.

4.     Εμφάνισε τον μέσο όρο.

Ψευδογλώσσα

Αλγόριθμος Μέσος_Όρος

Διάβασε α, β, γ

ΜΟ ← (α + β + γ) / 3

Εμφάνισε ΜΟ

Τέλος Μέσος_Όρος

Για βαθμούς:

α = 12

β = 15

γ = 18

έχουμε:

ΜΟ = (12 + 15 + 18) / 3

ΜΟ = 45 / 3

ΜΟ = 15

7. Πώς βρίσκουμε έναν αλγόριθμο;

Όταν μας δίνεται ένα πρόβλημα, δεν ξεκινάμε αμέσως γράφοντας ψευδογλώσσα.

Πρώτα σκεφτόμαστε:

1. Τι δεδομένα έχω;

Ποια στοιχεία θα πρέπει να εισαχθούν;

2. Τι πρέπει να υπολογίσω ή να κάνω;

Ποια πράξη ή διαδικασία απαιτείται;

3. Τι αποτέλεσμα θέλω;

Τι πρέπει να εμφανίσει ο αλγόριθμος;

4. Ποια είναι η σωστή σειρά των βημάτων;

Τα βήματα πρέπει να μπουν στη σωστή σειρά.

Παράδειγμα

Για το εμβαδόν ορθογωνίου:   

Διάβασε μήκος, πλάτος

Ε ← μήκος * πλάτος

Εμφάνισε Ε

8. Ασκήσεις – Βρες τον αλγόριθμο

Στις παρακάτω ασκήσεις ζητείται να σκεφτείς και να γράψεις τα βήματα του αλγορίθμου.

Άσκηση 1

Να αναπτυχθεί αλγόριθμος που διαβάζει την ηλικία ενός ατόμου και εμφανίζει την ηλικία του.

Άσκηση 2

Να αναπτυχθεί αλγόριθμος που διαβάζει δύο αριθμούς και εμφανίζει το γινόμενό τους.

Άσκηση 3

Να αναπτυχθεί αλγόριθμος που διαβάζει την τιμή ενός προϊόντος και εμφανίζει την τιμή του μετά από έκπτωση 10%.

Άσκηση 4

Να αναπτυχθεί αλγόριθμος που διαβάζει τη βάση και το ύψος ενός τριγώνου και εμφανίζει το εμβαδόν του.

Άσκηση 5

Να αναπτυχθεί αλγόριθμος που διαβάζει δύο αριθμούς και εμφανίζει το άθροισμα και τη διαφορά τους.

Άσκηση 6

Να αναπτυχθεί αλγόριθμος που διαβάζει έναν αριθμό και εμφανίζει το διπλάσιό του.

Άσκηση 7

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

Άσκηση 8

Να αναπτυχθεί αλγόριθμος που διαβάζει τους βαθμούς ενός μαθητή σε τέσσερα μαθήματα και υπολογίζει τον μέσο όρο.

Άσκηση 9

Να αναπτυχθεί αλγόριθμος που διαβάζει έναν αριθμό και εμφανίζει το τετράγωνό του.

Άσκηση 10

Να αναπτυχθεί αλγόριθμος που διαβάζει την απόσταση που διένυσε ένα αυτοκίνητο και την ποσότητα καυσίμου που κατανάλωσε και υπολογίζει την κατανάλωση σε λίτρα ανά 100 km.