Ένα απλό διάγραμμα ροής, το οποίο απεικονίζει τον αλγόριθμο ελέγχου και επισκευής μιας λάμπας η οποία δεν δουλεύει.
Ως αλγόριθμος (ετυμολογία: al-Ḵwārizmī, Abū Ja‘far Muhammad ibn Mūsa) ορίζεται μια πεπερασμένη σειρά ενεργειών, αυστηρά καθορισμένων και εκτελέσιμων σε πεπερασμένο χρόνο, που στοχεύουν στην επίλυση ενός προβλήματος. Πιο απλά (αλγόριθμο) ονομάζουμε μία σειρά από εντολές που έχουν αρχή και τέλος, είναι σαφείς και έχουν ως σκοπό την επίλυση κάποιου προβλήματος.[1][2]
Η λέξη αλγόριθμος προέρχεται από μία διατριβή του Πέρση μαθηματικού Μοχάμεντ ιμπν Μουσά αλ-Χουαρίζμι, η οποία περιείχε συστηματικές τυποποιημένες λύσεις αλγεβρικών προβλημάτων και αποτελεί ίσως την πρώτη πλήρη πραγματεία άλγεβρας. Έτσι η λέξη αλγόριθμος καθιερώθηκε αργά τα επόμενα χίλια χρόνια μετην έννοια «συστηματική διαδικασία αριθμητικών χειρισμών». Τη σημερινή της σημασία την οφείλει στη γρήγορη ανάπτυξη των ηλεκτρονικών υπολογιστών στα μέσα του 20ου αιώνα. Η έννοια του αλγορίθμου γίνεται ευκολότερα αντιληπτή μετο παρακάτω παράδειγμα. Αν κάποιος επιθυμεί να γευματίσει θα πρέπει να εκτελέσει κάποια συγκεκριμένα βήματα: να συγκεντρώσει τα υλικά, να προετοιμάσει τα σκεύη μαγειρικής, να παρασκευάσει το φαγητό, να στρώσει το τραπέζι, να ετοιμάσει τη σαλάτα, να γευματίσει, να καθαρίσει το τραπέζι καινα πλύνει τα πιάτα. Προφανώς, η προηγούμενη αλληλουχία οδηγεί στο επιθυμητό αποτέλεσμα. Δεν είναι όμως η μοναδική γιατην επίτευξη του σκοπού, αφού μπορεί να αλλάξει η σειρά των βημάτων (π.χ. πρώτα να ετοιμάσει τη σαλάτα και μετά να στρώσει το τραπέζι). Ωστόσο το νόημα είναι πως η κατάτμηση μιας σύνθετης εργασίας σε διακριτά βήματα που εκτελούνται διαδοχικά, είναι οπιο πρακτικός τρόπος επίλυσης πολλών προβλημάτων.
Οι αλγόριθμοι θα πρέπει να πληρούν κάποια πρότυπα καινα διατυπώνονται με συγκεκριμένο τρόπο. Έτσι ένας αλγόριθμος πρέπει να ικανοποιεί τα επόμενα κριτήρια:
Καθοριστικότητα
Περατότητα
Αποτελεσματικότητα
Επεκτασιμότητα
Να έχει είσοδο δεδομένων, επεξεργασία και έξοδο αποτελεσμάτων
Καθοριστικότητα - Definiteness
Κάθε κανόνας του ορίζεται επακριβώς καιη αντίστοιχη διεργασία είναι συγκεκριμένη. Κάθε εντολή πρέπει να καθορίζεται χωρίς καμία αμφιβολία γιατον τρόπο εκτέλεσής της. Π.χ. Σε μία διαίρεση να λαμβάνεται υπόψη καιη περίπτωση όπου ο διαιρετέος λαμβάνει μηδενική τιμή. Τυπικές περιπτώσεις η διαίρεση μετο μηδέν, υπόριζος ποσότητα αρνητική, κλπ. Προβλήματα καθοριστικότητας αντιμετωπίζονται συχνά μετη λογική της επιλογής, δηλ. Ανα>0 τότε ..... αλλιώς ......
Περατότητα - Finiteness
Κάθε εκτέλεση είναι πεπερασμένη, δηλαδή τελειώνει ύστερα από έναν πεπερασμένο αριθμό διεργασιών ή βημάτων. Μία διαδικασία πουδεν τελειώνει μετά από συγκεκριμένο/πεπερασμένο αριθμό βημάτων λέγεται απλά υπολογιστική διαδικασία.
Αποτελεσματικότητα - Effectiveness
Είναι μηχανιστικά αποτελεσματικός, δηλαδή όλες οι διαδικασίες που περιλαμβάνει μπορούν να πραγματοποιηθούν με ακρίβεια καισε πεπερασμένο χρόνο "με μολύβι και χαρτί". Κάθε μεμονωμένη εντολή του αλγορίθμου να είναι απλή (και όχι σύνθετη). Δηλαδή μία εντολή δεν αρκεί να έχει ορισθεί αλλά πρέπει να είναι και εκτελέσιμη.
Είσοδος δεδομένων - Input
Κατά την εκκίνηση εκτέλεσης του αλγορίθμου καμία, μία ή περισσότερες τιμές δεδομένων πρέπει να δίνονται ως είσοδοι στον αλγόριθμο. Η περίπτωση πουδε δίνονται τιμές δεδομένων εμφανίζεται όταν ο αλγόριθμος δημιουργεί και επεξεργάζεται κάποιες πρωτογενείς τιμές μετη βοήθεια συναρτήσεων παραγωγής τυχαίων αριθμών ή μετη βοήθεια άλλων απλών εντολών.
Έξοδος αποτελεσμάτων - Output
Δίδει τουλάχιστον ένα μέγεθος ως αποτέλεσμα που εξαρτάται κατά κάποιο τρόπο από τις αρχικές εισόδους. Ο αλγόριθμος πρέπει να δημιουργεί τουλάχιστον μία τιμή (δεδομένων) ως αποτέλεσμα προς το χρήστη ή προς ένα άλλο αλγόριθμο.
Τέσσερις είναι οι βασικοί τρόποι αναπαράστασης ενός αλγορίθμου:[3]
Ελεύθερο κείμενο, που αποτελεί τονπιο αδόμητο τρόπο παρουσίασης αλγορίθμου. Ελλοχεύει η δημιουργία μιας μη εκτελέσιμης κατάστασης παραβιάζοντας έτσι το κριτήριο της αποτελεσματικότητας.
Διάγραμμα ροής, που συνιστά έναν πιο γραφικό τρόπο παρουσίασης του αλγορίθμου. Η χρήση διαγραμμάτων ροής δεν είναι η πλέον ενδεδειγμένη λύση για ένα πρόβλημα καιγια αυτό χρησιμοποιούνται σπάνια στη βιβλιογραφία.
Φυσική γλώσσα που εκτελείται κατά βήματα. Σε αυτή την περίπτωση μπορεί να παραβιαστεί το κριτήριο του καθορισμού μεταξύ των βημάτων.
Κωδικοποίηση του αλγορίθμου σεψευδογλώσσα ή γλώσσα προγραμματισμού. Έτσι ο αλγόριθμος παρουσιάζεται πιο συνοπτικός, συμπαγής ενώ πληροί και τις προϋποθέσεις του δομημένου προγραμματισμού.
Η προγραμματιστική δομή που περικλείει τον έλεγχο μιας συνθήκης και μία ή δύο ομάδες εντολών. Από τις ομάδες των εντολών εκτελείται η πρώτη, αν ισχύει η συνθήκη, ή αν υπάρχει και δεύτερη ομάδα εντολών εκτελείται η δεύτερη ανδεν ισχύει η συνθήκη.
Μετον όρο συνθήκη εννοούμε δυο όρους ίδιου τύπου και ανάμεσα τους ένας τελεστής σύγκρισης.
Μετον όρο τελεστή σύγκρισης εννοούμε ένα από τα σύμβολα < , > , <> , <= , >= , =.
Το αποτέλεσμα της σύγκρισης των όρων (νοείται εφόσον οι όροι έχουν κάποια τιμή, δηλαδή δεν περιέχουν την τιμή null) είναι ηαλγεβρική τιμή Αληθής (True) ή Ψευδής (False).
Οι όροι μπορεί να είναι μεταβλητές ή σταθερές.[3]
Η προγραμματιστική δομή που περικλείει τον συνεχή έλεγχο μίας συνθήκης και μία ομάδα εντολών. Οι εντολές εκτελούνται ανάλογα μετην δομή της επανάληψης. Υπάρχουν τριών ειδών επαναλήψεις.[3]
Όσο ... επανάλαβε. Σε αυτή την δομή επανάληψης ελέγχεται πρώτα η συνθήκη και εφόσον ισχύει (δίνει τιμή αληθή) εκτελείται η ομάδα εντολών.
Επανάλαβε ... μέχρις ότου. Σε αυτή την δομή επανάληψης εκτελείται η ομάδα εντολών, στη συνέχεια ελέγχεται αν ισχύει η συνθήκη και εφόσον ΔΕΝ ισχύει (δίνει τιμή ψευδής) εκτελείται ξανά η ομάδα εντολών[4].
ΓιαΝ φορές επανάλαβε.Σε αυτή την δομή επανάληψης εκτελείται η ομάδα εντολών Ν φορές όπου Ν είναι αριθμός θετικός ακέραιος.
Δεσμεύσεις της εντολής Για:
ανη τιμή έναρξης της επανάληψης είναι μικρότερη ή το πολύ ίση μετην τιμή τέλους τότε αναγκαστικά το βήμα μεταβολής πρέπει να είναι θετικό.
ανη τιμή έναρξης είναι μεγαλύτερη ητο πολύ ίση μετην τιμή τέλους τότε αναγκαστικά το βήμα μεταβολής πρέπει να είναι αρνητικό.
σε καμία περίπτωση δεν πρέπει το βήμα να είναι όσο μετο μηδέν.
Οι αλγόριθμοι είναι σημαντικοί γιατί σχετίζονται άμεσα μετον τρόπο μετον οποίο οι υπολογιστές επεξεργάζονται δεδομένακαι παράγουν πληροφορίες. Ένα πρόγραμμα υπολογιστών είναι ουσιαστικά ένας αλγόριθμος που λέει στον υπολογιστή ποια συγκεκριμένα βήματα να εκτελέσει (σεποια συγκεκριμένη σειρά) προκειμένου να επιτευχθεί ένας συγκεκριμένος στόχος, όπως π.χ. ο υπολογισμός των μισθών των υπαλλήλων ή η εκτύπωση των ελέγχων των μαθητών. Κατά συνέπεια, ''ένας αλγόριθμος μπορεί να θεωρηθεί οποιαδήποτε ακολουθία εντολών που μπορεί να εκτελεσθεί από μια υπολογιστική μηχανή'' (Μηχανή Τιούρινγκ).[5][6] Αυτός ο ορισμός δόθηκε τον20ο αιώνα από τονΆλαν Τιούρινγκ.
Χαρακτηριστικά, όταν ένας αλγόριθμος συνδέεται μετην επεξεργασία πληροφοριών, τα δεδομένα διαβάζονται από μια συσκευή εισόδου, γράφονται σεμια συσκευή εξόδου, και / ή αποθηκεύονται γιατην περαιτέρω χρήση. Τα αποθηκευμένα στοιχεία θεωρούνται ως τμήμα της εσωτερικής κατάστασης του συστήματος που εκτελεί τον αλγόριθμο.
Για οποιαδήποτε τέτοια υπολογιστική διαδικασία, ο αλγόριθμος πρέπει να οριστεί αυστηρά: να είναι ορισμένος για όλες τις πιθανές περιστάσεις πουθα μπορούσαν να προκύψουν. Δηλαδή οποιαδήποτε υπό όρους βήματα πρέπει να εξεταστούν συστηματικά, καισε κάθε περίπτωση τα κριτήρια πρέπει να είναι σαφή (και υπολογίσιμα).
Επειδή ένας αλγόριθμος είναι ένας ακριβής κατάλογος βημάτων ακριβείας, η σειρά του υπολογισμού θα είναι σχεδόν πάντα κρίσιμη γιατη λειτουργία του αλγόριθμου. Οι εντολές συνήθως απαριθμούνται ρητά, και περιγράφονται σαννα ξεκινούν "από την κορυφή" και πηγαίνοντας "προς στο κατώτατο σημείο", μια ιδέα που περιγράφεται τυπικά μετον όρο της "ροής ελέγχου".
Μέχρι τώρα, σε αυτήν η συζήτηση γιατην τυποποίηση του αλγορίθμου, έχουμε δεχθεί ως βάση τονδιαδικαστικό προγραμματισμό. Αυτή είναι καιηπιο κοινή αντίληψη, η οποία προσπαθεί να περιγράψει ένα έργο με διακεκριμένα, "μηχανικά" μέσα. Μοναδικός σε αυτήν την αντίληψη των αλγόριθμων είναι ο ρόλος της λειτουργίας ανάθεσης (ο καθορισμός της τιμής μιας μεταβλητής) ο οποίος προέρχεται από τη ιδέα "της μνήμης" σαν πρόχειρο τετράδιο.
Δείτε ακόμα τολειτουργικό προγραμματισμόκαιτονλογικό προγραμματισμόγια εναλλακτικές αντιλήψεις γιατοτι αποτελεί έναν αλγόριθμο.
Οι αλγόριθμοι μπορούν να υλοποιηθούν από προγράμματα ηλεκτρονικών υπολογιστών, μολονότι συχνά σε περιορισμένες μορφές. Ένα λάθος στον σχεδιασμό ενός αλγόριθμου γιατην λύση ενός προβλήματος μπορεί να οδηγήσει σε αποτυχίες/βλάβες στο εφαρμοσμένο πρόγραμμα.
Οι αλγόριθμοι δεν υλοποιούνται μόνο ως προγράμματα υπολογιστών, αλλά συχνά επίσης καιμε άλλα μέσα, όπως π.χ. σε ένα βιολογικό νευρικό δίκτυο, ή σε ένα ηλεκτρονικό κύκλωμα, ή σεμια μηχανική συσκευή.
Η ανάλυση καιη μελέτη των αλγορίθμων είναι ένας τομέας τής επιστήμης της πληροφορικής, και ασκείται συχνά αφαιρετικά (χωρίς τη χρήση μιας συγκεκριμένης γλώσσας προγραμματισμού ή άλλη εφαρμογή). Από αυτή την άποψη, μοιάζει με άλλους μαθηματικούς τομείς, συγκεκριμένα στο ότι η εστίαση της ανάλυσης είναι πάνω στις βασικές αρχές του αλγορίθμου, και όχι σε οποιαδήποτε ιδιαίτερη εφαρμογή του. Ένας τρόπος απεικόνισης ένας αλγόριθμου είναι το γράψιμο τουψευδοκώδικα. Άλλοι τρόποι είναι: με ελεύθερο κείμενο, με φυσική γλώσσα περιγράφοντας τα βήματα καιμε λογικό διάγραμμα .
↑Σ. Ζάχος, Δ. Φωτάκης. «Μηχανές Turing και Υπολογισιμότητα»(PDF). Διαφάνειες μαθήματος στην Σχολή Ηλεκτρολόγων Μηχανικών & Μηχανικών Υπολογιστών, Εθνικό Μετσόβιο Πολυτεχνείο. Αρχειοθετήθηκε από το πρωτότυπο(PDF) στις 11 Μαΐου 2015. Ανακτήθηκε στις 6 Οκτωβρίου 2011.