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

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

 

</nowiki>

 

Αναλύουμε τους αλγόριθμους με το να βελτιώνουμε, αν είναι δυνατό, και με το να διαλέγουμε τον καλύτερο για ένα πρόβλημα. Εξετάζουμε τα ακόλουθα κριτήρια :

α) ορθότητα β) ποσότητα της δουλειάς που πρέπει να γίνει γ) ποσότητα της μνήμης που απαιτείται δ) απλότητα ε) πότε ένας αλγόριθμος είναι βέλτιστος

 

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

Πρώτον, πριν προσπαθήσουμε να διαπιστώσουμε αν ένας αλγόριθμος είναι σωστός, πρέπει να ξεκαθαρίσουμε τι σημαίνει "σωστός". Μπορούμε να λέμε ότι ένας αλγόριθμος είναι σωστός, αν, δοθείσης μιας έγκυρης εισόδου, υπολογίζει σε πεπερασμένο χρόνο τη σωστή απάντηση. Είμαστε εντάξει, αν γνωρίζουμε τι είναι οι έγκυρες είσοδοι και τι είναι το "σωστό αποτέλεσμα". Επομένως αποδεικνύοντας ότι ένας αλγόριθμος είναι σωστός σημαίνει να διατυπώσουμε ακριβώς τι αποτέλεσμα πρόκειται να παράγει δοθείσης καλά διατυπωμένης εισόδου, και μετά να αποδείξουμε την πρόταση. Υπάρχουν δύο ζητήματα σε έναν αλγόριθμο : η μέθοδος λύσης του προβλήματος και η σειρά των εντολών που πρέπει να εκτελεστούν για να το επιτύχουν. Το να ξεδιαλύνουμε την ορθότητα της μεθόδου και/ή των τύπων που χρησιμοποιούνται μπορεί να απαιτεί μια μεγάλη ακολουθία λημμάτων και θεωρημάτων για τα αντικείμενα που εμπλέκονται στον αλγόριθμο (όπως γράφοι, επαναλήψεις, πίνακες). Για παράδειγμα, η εγκυρότητα της μεθόδου απλοποίησης Gauss για την επίλυση συστημάτων γραμμικών εξισώσεων, εξαρτάται από έναν αριθμό θεωρημάτων της γραμμικής άλγεβρας. Τέλος έχουμε τις ίδιες τις εντολές. Αν ένας αλγόριθμος είναι δίκαια σύντομος και ξεκάθαρα διατυπωμένος, χρησιμοποιούμε γενικά κάποιους πολύ άτυπους τρόπους στο να πειστούμε ότι τα διάφορα τμήματά του κάνουν αυτό που πρέπει.

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

 

<nowiki>'''ΧΡΗΣΗ ΜΝΗΜΗΣ'''

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