Αλγόριθμος, συστηματική διαδικασία που παράγει - σε περιορισμένο αριθμό βημάτων - την απάντηση σε μια ερώτηση ή τη λύση ενός προβλήματος. Το όνομα προέρχεται από τη λατινική μετάφραση, Algoritmi de numero Indorum, της αριθμητικής πραγματείας του Al-Khwarizmi του Μουσουλμάνου του 9ου αιώνα «Al-Khwarizmi σχετικά με την Ινδουιστική Τέχνη του Ρεκόνγκν».
επιστήμη υπολογιστών: Αλγόριθμοι και πολυπλοκότητα
Ένας αλγόριθμος είναι μια συγκεκριμένη διαδικασία για την επίλυση ενός καλά καθορισμένου υπολογιστικού προβλήματος. Η ανάπτυξη και ανάλυση αλγορίθμων είναι θεμελιώδης
Για ερωτήσεις ή προβλήματα με μόνο ένα πεπερασμένο σύνολο περιπτώσεων ή τιμών υπάρχει πάντα ένας αλγόριθμος (τουλάχιστον κατ 'αρχήν). αποτελείται από έναν πίνακα τιμών των απαντήσεων. Σε γενικές γραμμές, δεν είναι μια τόσο ασήμαντη διαδικασία για την απάντηση ερωτήσεων ή προβλημάτων που έχουν έναν άπειρο αριθμό περιπτώσεων ή αξιών που πρέπει να ληφθούν υπόψη, όπως "Είναι ο φυσικός αριθμός (1, 2, 3,…) Πρωταρχικός;" ή "Ποιος είναι ο μεγαλύτερος κοινός διαιρέτης των φυσικών αριθμών a και b;" Η πρώτη από αυτές τις ερωτήσεις ανήκει σε μια τάξη που ονομάζεται decidable. Ένας αλγόριθμος που παράγει μια απάντηση ναι ή όχι ονομάζεται διαδικασία απόφασης. Η δεύτερη ερώτηση ανήκει σε μια κλάση που ονομάζεται υπολογιστική. ένας αλγόριθμος που οδηγεί σε συγκεκριμένη απάντηση αριθμού ονομάζεται διαδικασία υπολογισμού.
Υπάρχουν αλγόριθμοι για πολλές τέτοιες άπειρες κατηγορίες ερωτήσεων. Το Euclid's Elements, που δημοσιεύθηκε περίπου 300 π.Χ., περιείχε ένα για την εύρεση του μεγαλύτερου κοινού διαιρέτη δύο φυσικών αριθμών. Κάθε μαθητής του δημοτικού σχολείου τρυπάται σε μακρά διαίρεση, ο οποίος είναι ένας αλγόριθμος για την ερώτηση "Κατά τη διαίρεση ενός φυσικού αριθμού α με έναν άλλο φυσικό αριθμό β, ποιος είναι ο πηλίκος και το υπόλοιπο;" Η χρήση αυτής της υπολογιστικής διαδικασίας οδηγεί στην απάντηση στην αποφασιστική ερώτηση "Το b διαιρεί a;" (η απάντηση είναι ναι αν το υπόλοιπο είναι μηδέν). Η επανειλημμένη εφαρμογή αυτών των αλγορίθμων παράγει τελικά την απάντηση στην αποφασιστική ερώτηση "Είναι ένα πρωταρχικό;" (η απάντηση είναι όχι αν το a διαιρείται με μικρότερο φυσικό αριθμό εκτός από το 1).
Μερικές φορές δεν μπορεί να υπάρχει αλγόριθμος για την επίλυση μιας άπειρης κατηγορίας προβλημάτων, ειδικά όταν γίνεται κάποιος περαιτέρω περιορισμός στην αποδεκτή μέθοδο. Για παράδειγμα, δύο προβλήματα από την εποχή του Ευκλείδη που απαιτούν τη χρήση μόνο μιας πυξίδας και μιας ευθείας (χωρίς χάρακα χάρακα) - ανίχνευση μιας γωνίας και κατασκευή ενός τετραγώνου με μια περιοχή ίση με έναν δεδομένο κύκλο - συνεχίστηκαν για αιώνες πριν αποδειχθούν αδύνατο. Στα τέλη του 20ου αιώνα, ο Γερμανός μαθηματικός David Hilbert πρότεινε 23 προβλήματα για τους μαθηματικούς για επίλυση τον επόμενο αιώνα. Το δεύτερο πρόβλημα στη λίστα του ζήτησε διερεύνηση της συνέπειας των αξιωματικών της αριθμητικής. Οι περισσότεροι μαθηματικοί είχαν μικρή αμφιβολία για την τελική επίτευξη αυτού του στόχου μέχρι το 1931, όταν ο γεννημένος στην Αυστρία λογικός Kurt Gödel έδειξε το εκπληκτικό αποτέλεσμα ότι πρέπει να υπάρχουν αριθμητικές προτάσεις (ή ερωτήσεις) που δεν μπορούν να αποδειχθούν ή να απορριφθούν. Ουσιαστικά, οποιαδήποτε τέτοια πρόταση οδηγεί σε μια διαδικασία προσδιορισμού που δεν τελειώνει ποτέ (μια κατάσταση γνωστή ως πρόβλημα διακοπής). Σε μια ανεπιτυχή προσπάθεια να εξακριβωθεί τουλάχιστον ποιες προτάσεις δεν είναι επιλύσιμες, ο Άγγλος μαθηματικός και λογικός Alan Turing καθόρισε αυστηρά την χαλαρά κατανοητή έννοια ενός αλγορίθμου. Παρόλο που ο Turing κατέληξε να αποδεικνύει ότι πρέπει να υπάρχουν αναποφάσιστες προτάσεις, η περιγραφή του για τα βασικά χαρακτηριστικά κάθε μηχανής αλγόριθμου γενικής χρήσης, ή της μηχανής Turing, έγινε το θεμέλιο της επιστήμης των υπολογιστών. Σήμερα, τα ζητήματα της δυνατότητας υπολογισμού και υπολογιστικότητας είναι κεντρικά στο σχεδιασμό ενός προγράμματος υπολογιστή - ενός ειδικού τύπου αλγορίθμου.
