⚙️ Κεφάλαιο 2: Βασικές Έννοιες Αλγορίθμων

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

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

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

2.2Ποια κριτήρια θα πρέπει να ικανοποιεί ένας αλγόριθμος;

Τα κριτήρια που πρέπει να ικανοποιεί ένας αλγόριθμος είναι:

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

2.3Από ποιες σκοπιές μελετάει η Πληροφορική τους αλγορίθμους;

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

Η Πληροφορική, λοιπόν, μπορεί να ορισθεί ως η επιστήμη που μελετά τους αλγορίθμους από τις ακόλουθες σκοπιές:

• Υλικού (hardware): Η ταχύτητα εκτέλεσης ενός αλγορίθμου επηρεάζεται από τις διάφορες τεχνολογίες υλικού, δηλαδή από τον τρόπο που είναι δομημένα σε μια ενιαία αρχιτεκτονική τα διάφορα συστατικά του υπολογιστή (ανάλογα με το αν ο υπολογιστής έχει κρυφή μνήμη και πόση, ανάλογα με την ταχύτητα της κύριας και δευτερεύουσας μνήμης κ.λπ.).
• Γλωσσών Προγραμματισμού: Το είδος της γλώσσας προγραμματισμού που χρησιμοποιείται (δηλαδή, χαμηλότερου ή υψηλότερου επιπέδου) αλλάζει τη δομή και τον αριθμό των εντολών ενός αλγορίθμου. Γενικά μια γλώσσα που είναι χαμηλότερου επιπέδου (όπως η assembly ή η C) είναι ταχύτερη από μια άλλη που είναι υψηλότερου επιπέδου (όπως η Basic ή Pascal). Ακόμη, σημειώνεται ότι διαφορές συναντώνται μεταξύ των γλωσσών σε σχέση με το πότε εμφανίσθηκαν.
• Θεωρητική: Το ερώτημα που συχνά τίθεται είναι, αν πράγματι υπάρχει ή όχι κάποιος αποδοτικός αλγόριθμος για την επίλυση ενός προβλήματος. Η εξέταση αυτού του ερωτήματος είναι δύσκολο να σχολιασθεί στα πλαίσια του βιβλίου αυτού, επειδή απαιτεί μεγάλη θεωρητική κατάρτιση. Ωστόσο η προσέγγιση αυτή είναι ιδιαίτερα σημαντική, γιατί προσδιορίζει τα όρια της λύσης που θα βρεθεί σε σχέση με ένα συγκεκριμένο πρόβλημα.
• Αναλυτική: Μελετώνται οι υπολογιστικοί πόροι (computer resources) που απαιτούνται από έναν αλγόριθμο, όπως για παράδειγμα το μέγεθος της κύριας και της δευτερεύουσας μνήμης, ο χρόνος για λειτουργίες CPU και για λειτουργίες εισόδου/εξόδου.

2.4Να αναφέρετε τους τρόπους αναπαράστασης ενός αλγορίθμου

Ένας αλγόριθμος μπορεί να αναπαρασταθεί με τους εξής τρόπους:

• Ελεύθερο κείμενο (free text): Ο πιο ανεπεξέργαστος και αδόμητος τρόπος παρουσίασης αλγορίθμου. Έτσι εγκυμονεί τον κίνδυνο ότι μπορεί εύκολα να οδηγήσει σε μη εκτελέσιμη παρουσίαση, παραβιάζοντας το τελευταίο χαρακτηριστικό των αλγορίθμων, δηλαδή την αποτελεσματικότητα.
• Διαγραμματικές τεχνικές: Συνιστούν ένα γραφικό τρόπο παρουσίασης του αλγορίθμου. Από τις διάφορες διαγραμματικές τεχνικές που έχουν επινοηθεί, η πιο παλιά και η πιο γνωστή ίσως, είναι το διάγραμμα ροής (flow chart). Ωστόσο η χρήση διαγραμμάτων ροής για την παρουσίαση αλγορίθμων δεν αποτελεί την καλύτερη λύση, γι' αυτό και εμφανίζονται όλο και σπανιότερα στη βιβλιογραφία και στην πράξη.
• Φυσική γλώσσα κατά βήματα: Στην περίπτωση αυτή χρειάζεται προσοχή, γιατί μπορεί να παραβιασθεί το τρίτο βασικό χαρακτηριστικό ενός αλγορίθμου, όπως προσδιορίσθηκε προηγουμένως, δηλαδή το κριτήριο της καθοριστικότητας.
• Κωδικοποίηση (coding): Ένα πρόγραμμα γραμμένο είτε σε μια ψευδογλώσσα είτε σε κάποια γλώσσα προγραμματισμού, που όταν εκτελεσθεί θα δώσει τα ίδια αποτελέσματα με τον αλγόριθμο.

2.5Από τι αποτελείται ένα διάγραμμα ροής και ποια τα σύμβολα;

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

Τα σύμβολα αυτά είναι:

2.6Τι είναι η μεταβλητή;

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

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

Είδη μεταβλητών:

• Αριθμητικές: Αποθηκεύουν αριθμητικές τιμές (π.χ. 70, -32, 5)
• Αλφαριθμητικές: Αποθηκεύουν κείμενο (π.χ. "Φροντιστήριο", "abc")
• Λογικές: Παίρνουν τιμή αληθής ή ψευδής

2.7Τι είναι οι σταθερές;

Σταθερές είναι προκαθορισμένες τιμές που παραμένουν αμετάβλητες κατά την εκτέλεση του αλγορίθμου.

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

Είδη σταθερών:

• Αριθμητικές: π.χ. 70, -32, 5
• Αλφαριθμητικές: π.χ. "Φροντιστήριο", "abc"
• Λογικές: με τιμή αληθής ή ψευδής

2.8Τι είναι οι τελεστές;

Τελεστές είναι τα γνωστά σύμβολα των πράξεων. Υπάρχουν τρία είδη τελεστών:

1. Αριθμητικοί

+, -, *, /, ^, div, mod

• div: Επιστρέφει το ακέραιο πηλίκο της διαίρεσης δύο αριθμών. Π.χ. 13 div 3 = 4
• mod: Επιστρέφει το υπόλοιπο της ακέραιας διαίρεσης. Π.χ. 13 mod 3 = 1

2. Συγκριτικοί

>, <, >=, <=, =, <>

3. Λογικοί

ΚΑΙ, Η, ΟΧΙ — συνδέουν συνθήκες. Το αποτέλεσμα είναι πάντα μια λογική τιμή: αληθής ή ψευδής.

2.9Τι είναι οι εκφράσεις;

Εκφράσεις είναι συνδυασμοί τελεστέων (μεταβλητών ή σταθερών) και τελεστών.

Το αποτέλεσμα μιας έκφρασης αποδίδεται σε μια μεταβλητή με εκχώρηση τιμής.

Π.χ. τιμή ← α + β — το αποτέλεσμα του αθροίσματος των τιμών των μεταβλητών α και β θα εκχωρηθεί στη μεταβλητή τιμή.

Η τελική τιμή μιας εκχώρησης εξαρτάται από την ιεραρχία των πράξεων (γνωστή από τα μαθηματικά) και τις παρενθέσεις.

2.10Λογικές πράξεις

Οι τρεις βασικές λογικές πράξεις:

• Η (OR): Αληθής όταν οποιαδήποτε από τις δύο προτάσεις είναι αληθής
• ΚΑΙ (AND): Αληθής όταν και οι δύο προτάσεις είναι αληθείς
• ΟΧΙ (NOT): Αληθής όταν η πρόταση που την ακολουθεί είναι ψευδής

Το αποτέλεσμα είναι πάντα μια λογική τιμή: αληθής ή ψευδής.

Πίνακας Αλήθειας

2.11Τι εννοούμε με τον όρο Δομή ακολουθίας;

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

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