Αλγόριθμοι: Διαφορά μεταξύ των αναθεωρήσεων

<nowiki>

Όταν λέμε ότι ένα πρόβλημα λύνεται αλγοριθμικά, εννοούμε, ότι υπάρχει ένα πρόγραμμα σε υπολογιστή που παράγει το σωστό αποτέλεσμα για κάθε είσοδο αν το τρέξουμε για όσο χρόνο χρειαστεί και του δώσουμε όση μνήμη χρειάζεται. Στη δεκαετία του 1930 πριν την εμφάνιση των υπολογιστών, οι μαθηματικοί δούλευαν εντατικά για να μελετήσουν τους αλγόριθμους, οι οποίοι μεταφράζονταν σε ένα ξεκάθαρο σύνολο εντολών που θα ακολουθούνταν για να λύσουν το πρόβλημα ή να υπολογίσουν μια συνάρτηση. Εξήχθησαν και διερευνήθηκαν διάφορα τυπικά μοντέλα υπολογισμού. Η πιο πολύ έμφαση σ' αυτή τη μελέτη, που ονομάστηκε θεωρία υπολογισμού, δόθηκε στην περιγραφή και τον χαρακτηρισμό τέτοιων προβλημάτων που μπορούσαν να λυθούν αλγοριθμικά και στο να εξαιρέσουν τα προβλήματα που δεν μπορούσαν να λυθούν. Ένα από τα πιο σημαντικά ζητήματα στην αρνητική περίπτωση ήταν το λεγόμενο "πρόβλημα τερματισμού" (halting problem). Το πρόβλημα τερματισμού είναι το να καθορίσεις πότε ένας τυχαίος δοθείς αλγόριθμος (ή πρόγραμμα υπολογιστή) θα μπεί σε ατέρμονα βρόχο, ενώ δουλεύει σε δοθείσα είσοδο. Στην περίπτωση αυτή δεν υπάρχει πρόγραμμα που να λύσει αυτό το πρόβλημα.</nowiki>

 

Θα αναπτύξουμε ορισμένα από αυτά.

</nowiki>

 

<nowiki>'''ΟΡΘΟΤΗΤΑ'''

 

</nowiki>

<nowiki>

Ο ορισμός των θέσεων μνήμης που χρησιμοποιεί ένα πρόγραμμα, όπως και ο αριθμός των δευτερολέπτων που απαιτούνται, εξαρτάται από την υλοποίηση που επιλέγουμε. Παρόλο αυτά μπορούμε να εξάγουμε κάποια συμπεράσματα, εξετάζοντας έναν αλγόριθμο. Ένα πρόγραμμα χρειάζεται μνήμη για τις εντολές, τις σταθερές και τις μεταβλητές και τα δεδομένα. Χρειάζεται επιπλέον χώρο για την επεξεργασία των δεδομένων, και για την αποθήκευση των ενδιάμεσων αποτελεσμάτων. Τα δεδομένα εισόδου μπορούν να παρασταθούν με διάφορες μορφές που έχουν διαφορετικές απιτήσεις σε μνήμη. Αν έχουν μια φυσική μορφή - όπως ένα αρραυ αριθμών ή έναν πίνακα - τότε αναλύουμε και τον επιπλέον χώρο που χρησιμοποιείται, εκτός από το πρόγραμμα και την είσοδό του. Αν η επιπλέον μνήμη είναι σταθερή ως προς το μέγεθος της εισόδου, τότε λέμε ότι ο αλγόριθμος δουλεύει in place. Αυτός ο όρος χρησιμοποιείται κυρίως σε αλγόριθμους διάταξης. Αν η είσοδος μπορεί να παρασταθεί με διάφορους τρόπους (πχ γράφους) τότε, φυσικά, θα υπολογίσουμε τη μνήμη για την ίδια την είσοδο καθώς και την επιπλέον μνήμη. Γενικά, θα αναφερόμαστε σε ποσότητα μνήμης χωρίς να προσδιορίζουμε ακριβώς τα KB. Πρέπει να θεωρούμε τη θέση μνήμης αρκετά μεγάλη για να χωρέσει έναν αριθμό. Αν το μέγεθος της μνήμης εξαρτάται από τη συγκεκριμένη είσοδο, μπορεί να γίνει η ανάλυση χειρότερης περίπτωσης (worst- case) και μέσης περίπτωσης (average - case).

</nowiki>

<nowiki>

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

</nowiki>

<nowiki>