Αλγόριθμοι και γλώσσες προγραμματισμού
Η έννοια του αλγορίθμου είναι θεμελειώδης στην επιστήμη των υπολογιστών. Ένας αλγόριθμος είναι μια στρατηγική για την επίλυση ενός προβλήματος η οποία έχει τις ακόλουθες ιδιότητες: (α) Είναι σαφώς ορισμένη (β) Τα βήματά της είναι εκτελέσιμα (γ) Είναι πεπερασμένη, δηλαδή τερματίζεται μετά από ένα ορισμένο πλήθος βημάτων. Ας δούμε, για παράδειγμα, κατά πόσο ο «αλγόριθμος» του Ευκλείδη για την εύρεση του μέγιστου κοινού διαιρέτη δύο ακεραίων ικανοποιεί τις παραπάνω ιδιότητες:
Αλγόριθμος του Ευκλείδη: Δεδομένων δύο θετικών ακεραίων m και n, να βρεθεί ο μέγιστος
κοινός διαιρέτης τους, δηλαδή ο μεγαλύτερος ακέραιος ο οποίος διαιρεί τον m και τον n.
Βήμα 1: Διαίρεσε το m με το n και έστω r το υπόλοιπο της διαίρεσης (προφανώς
0 ≤ r < n).
Βήμα 2: Αν το r είναι μηδέν, σταμάτα. Ο μέγιστος κοινός διαιρέτης είναι o n.
Βήμα 3: Αντικατέστησε τον m με τον n, τον n με τον r και επέστρεψε στο Βήμα 1.
Προτού δείξουμε ότι η παραπάνω διαδικασία είναι όντως αλγόριθμος, ας προσπαθήσουμε να ακολουθήσουμε τα βήματά του σε ένα απλό παράδειγμα. Έστω λοιπόν ότι μας δίδεται m = 133 και n = 456. Στο πρώτο βήμα διαιρούμε τον m με τον n και παίρνουμε r = 133. Στο δεύτερο βήμα αφού το r δεν είναι μηδέν δεν γίνεται τίποτα. Στο τρίτο βήμα θέτουμε m = 456 και n = 133. Επιστρέφουμε στο βήμα 1 και υπολογίζουμε τώρα r = 57. Στο δεύτερο βήμα πάλι δεν γίνεται τίποτα οπότε στο τρίτο βήμα θέτουμε m = 133, n = 57. Επιστρέφοντας ξανά στο πρώτο βήμα έχουμε r = 19. Για άλλη μια φορά δεν γίνεται κάτι στο δεύτερο βήμα ενώ το τρίτο βήμα θέτει m = 57 και n = 19. Τώρα όμως το υπόλοιπο της διαίρεσης του 57 με το 19 είναι μηδέν, επομένως ο αλγόριθμος σταματάει στο δεύτερο βήμα και ο μέγιστος κοινός διαρέτης είναι το 19.
Ας δούμε κατ' αρχήν ότι ο παραπάνω αλγόριθμος όντως τερματίζει. Μετά από το πρώτο βήμα η τιμή του r είναι μικρότερη από το n, επομένως αν το r δεν είναι μηδέν η τιμή του μειώνεται κάθε φορά που εκτελείται αυτό το βήμα. Επειδή μια φθίνουσα ακολουθία θετικών ακεραίων είναι αναγκαστικά πεπερασμένη, το Βήμα 1 θα εκτελεστεί πεπερασμένο αριθμό φορών. Για το αν τα βήματα του αλγορίθμου είναι καλά ορισμένα είναι αρκετό να δούμε ότι οι m και n είναι θετικοί ακέραιοι όποτε εκτελείται το Βήμα 1. Αυτό προφανώς ισχύει την πρώτη φορά, εξ υποθέσεως. Μετά την εκτέλεση του βήματος 1 ο r είναι ένας μη αρνητικός ακέραιος ο οποίος είναι επιπλέον διάφορος του μηδενός αν φτάσουμε στο τρίτο βήμα. Επομένως οι m και n είναι θετικοί ακέραιοι. Τέλος, τα βήματα του αλγορίθμου είναι εκτελέσιμα μια και το μόνο που χρησιμοποιείται είναι διαίρεση ακεραίων αριθμών η οποία προφανώς μπορεί να γίνει ακριβώς με τουλάχιστον ένα τρόπο.
Μένει λοιπόν να αποδείξουμε ότι αυτό που υπολογίζει ο παραπάνω αλγόριθμος είναι όντως ο μέγιστος κοινός διαιρέτης των m και n. Και αυτό είναι εύκολο: μετά το πρώτο βήμα έχουμε m = qn + r, για κάποιο ακέραιο q. Αν το r είναι μηδέν τότε το n είναι προφανώς ο μέγιστος κοινός διαιρέτης των m και n. Διαφορετικά, κάθε διαιρέτης των m και n είναι διαιρέτης και του m - qn = r. Επομένως το σύνολο των διαιρετών των m και n είναι ίσο με το σύνολο των διαιρετών των n και r. Ειδικότερα, ο μέγιστος κοινός διαρέτης των m και n είναι ο ίδιος με τον μέγιστο κοινό διαιρέτη των n και r. Άρα το τρίτο βήμα δεν αλλάζει την απάντηση του αρχικού προβλήματος.
Έχοντας στη διάθεσή μας τώρα τον αλγόριθμο για τη λύση του προβλήματος, απομένει να τον εκφράσουμε
ως πρόγραμμα σε κάποια γλώσσα προγραμματισμού, δηλαδή να τον κωδικοποιήσουμε. Η γλώσσα προγραμματισμού
C, την οποία θα χρησιμοποιούμε για να υλοποιούμε τους αλγορίθμους που σχεδιάζουμε, είναι παράδειγμα γλώσσας
υψηλού επιπέδου, με την έννοια ότι είναι ανεξάρτητη από τα χαρακτηριστικά του υπολογιστή στον οποίο εκτελούνται
τα προγράμματά της. Φυσικά, ένα πρόγραμμα το οποίο είναι γραμμένο σε μια γλώσσα υψηλού επιπέδου πρέπει
πρώτα να μεταφραστεί στην λεγόμενη γλώσσα μηχανής, που είναι κατάλληλη για το συγκεκριμένο υπολογιστή στον
οποίο θα εκτελεστεί το πρόγραμμα. Η διαδικασία αυτή λέγεται μεταγλώττιση (compilation) και
εκτελείται από προγράμματα που ονομάζονται μεταγλωττιστές (compilers). Το κείμενο του προγράμματος που θελουμε να
εκτελέσουμε καταχωρείται σε ένα αρχείο (file). Το όνομα ενός αρχείου στα περισσότερα υπολογιστικά συστήματα
αποτελείται από δύο μέρη που χωρίζονται με μια τελεία. Το κομμάτι του ονόματος αριστερά της τελείας ονομάζεται
βασικό όνομα (root name) και το υπόλοιπο προέκταση (extension). Η προέκταση υποδηλώνει τον σκοπό για τον
οποίο χρησιμοποείται το αρχείο ή τα περιεχόμενα του. Η προέκταση .c έχει προκαθορισμένη σημασία
και δηλώνει ένα αρχείο που περιέχει κώδικα C. Για παράδειγμα, αν κωδικοποιούσαμε τον αλγόριθμο του Ευκλείδη
για την εύρεση του μέγιστου κοινού διαιρέτη δύο ακεραίων ίσως διαλέγαμε το όνομα gcd.c ή
myprog.c.
Κάθε αρχείο που περιέχει κώδικα ονομάζεται πηγαίο αρχείο (source file). Ο μεταγλωττιστής μετατρέπει το πηγαίο αρχείο στο λεγόμενο αρχείο-αντικείμενο (object file) και στη συνέχεια ένα δεύτερο πρόγραμμα, το πρόγραμμα σύνδεσης (linker) παράγει το εκτελέσιμο αρχείο (executable file) το οποίο μπορεί να εκτελεστεί στο συγκεκριμένο υπολογιστικό σύστημα. Ευτυχώς, στα περισσότερα υπολογιστικά συστήματα η διαδικασία της παραγωγής ενός εκτελέσιμου αρχείου από ένα πηγαίο αρχείο είναι όχι μόνο γρήγορη αλλά και εύκολη.
Αξίζει τέλος να σημειώσουμε ότι οι μεταγλωττιστές, πέρα από την μετάφραση του πηγαίου κώδικα σε γλώσσα μηχανής εκτελούν και μια άλλη σημαντική λειτουργία, αυτή του ελέγχου του πηγαίου κώδικα για συντακτικά λάθη. Όπως η γλώσσα που μιλάμε, έτσι και κάθε γλώσσα προγραμματισμού έχει τους δικούς της συντακτικούς κανόνες τους οποίους πρέπει να σέβεται το πηγαίο αρχείο. Κάθε μεταγλωττιστής επισημαίνει τυχόν συντακτικά λάθη (syntax errors) τα οποία πρέπει να διορθωθούν προτού ολοκληρωθεί η μεταγλώττιση. Ακόμα και αν η μεταγλώττιση ενός προγράμματος ολοκληρωθεί χωρίς σφάλματα δεν σημαίνει ότι το πρόγραμμα όταν εκτελεστεί θα δίνει σωστά αποτελέσματα. Αυτό μπορεί να συμβαίνει για διάφορους λόγους, με τον συνηθέστερο να είναι η λάθος κωδικοποίηση του αλγορίθμου που χρησιμοποιούμε για την επίλυση του συγκεκριμένου προβλήματος. Λέμε σε αυτή την περίπτωση ότι το πρόγραμμά μας έχει "bug" (στα Αγγλικά bug σημαίνει έντομο, και αυτά ήταν πηγές προβλημάτων την εποχή που οι υπολογιστές χρησιμοποιούσαν λυχνίες κενού).