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

Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Tkirzoglou (συζήτηση | συνεισφορές)
Χωρίς σύνοψη επεξεργασίας
Tkirzoglou (συζήτηση | συνεισφορές)
Χωρίς σύνοψη επεξεργασίας
Γραμμή 19:
Πρέπει να εξετάσουμε προσεκτικά κάποιες λεπτομέρειες (όπως αρχικές και τελικές τιμές διαφόρων μετρητών των βρόχων) και να εκτελέσουμε με το χέρι τον αλγόριθμο για κάποια μικρά παραδείγματα. Τίποτα από αυτά δεν αποδεικνύει ότι είναι σωστός, αλλά για μικρά προγράμματα αρκούν άτυπες τεχνικές. Πολλά προγράμματα που γράφονται έξω από σχολικές τάξεις είναι πολύ μεγάλα και πολύ πολύπλοκα. Για να αποδείξουμε την ορθότητα ενός μεγάλου προγράμματος, μπορούμε να διασπάσουμε το πρόγραμμα σε μικρότερα τμήματα, να αποδείξουμε ότι το καθένα από αυτά κάνει σωστά τη δουλειά του, επομένως όλο το πρόγραμμα είναι σωστό. Αυτό γίνεται ευκολότερο αν οι αλγόριθμοι και τα προγράμματα γράφονταν έτσι ώστε να μπορούν να διασπαστούν σε κομμάτια που μπορούν να επιλυθούν ξεχωριστά. Αυτό είναι ένα από τα κυριότερα ζητήματα του δομημένου προγραμματισμού.
Μια από τις πιο χρήσιμες τεχνικές στην απόδειξη της ορθότητας, είναι η μαθηματική επαγωγή. Χρησιμοποιείται για να αποδείξει ότι οι βρόχοι σε έναν αλγόριθμο κάνουν ακριβώς αυτό που πρέπει. Για κάθε βρόχο θέτουμε συνθήκες και σχέσεις για τις οποίες πιστεύουμε ότι ικανοποιούνται από τις μεταβλητές και τις δομές δεδομένων που χρησιμοποιούνται, και μετά να επαληθεύσουμε ότι αυτές οι συνθήκες ισχύουν, κάνοντας "περάσματα" στο βρόχο. Οι λεπτομέρειες της απόδειξης απαιτούν να ακολουθήσουμε προσεκτικά τις εντολές στον αλγόριθμο.
ΧΡΗΣΗ ΜΝΗΜΗΣ
Ο ορισμός των θέσεων μνήμης που χρησιμοποιεί ένα πρόγραμμα, όπως και ο αριθμός των δευτερολέπτων που απαιτούνται, εξαρτάται από την υλοποίηση που επιλέγουμε. Παρόλο αυτά μπορούμε να εξάγουμε κάποια συμπεράσματα, εξετάζοντας έναν αλγόριθμο. Ένα πρόγραμμα χρειάζεται μνήμη για τις εντολές, τις σταθερές και τις μεταβλητές και τα δεδομένα. Χρειάζεται επιπλέον χώρο για την επεξεργασία των δεδομένων, και για την αποθήκευση των ενδιάμεσων αποτελεσμάτων. Τα δεδομένα εισόδου μπορούν να παρασταθούν με διάφορες μορφές που έχουν διαφορετικές απιτήσεις σε μνήμη. Αν έχουν μια φυσική μορφή - όπως ένα αρραυ αριθμών ή έναν πίνακα - τότε αναλύουμε και τον επιπλέον χώρο που χρησιμοποιείται, εκτός από το πρόγραμμα και την είσοδό του. Αν η επιπλέον μνήμη είναι σταθερή ως προς το μέγεθος της εισόδου, τότε λέμε ότι ο αλγόριθμος δουλεύει in place. Αυτός ο όρος χρησιμοποιείται κυρίως σε αλγόριθμους διάταξης. Αν η είσοδος μπορεί να παρασταθεί με διάφορους τρόπους (πχ γράφους) τότε, φυσικά, θα υπολογίσουμε τη μνήμη για την ίδια την είσοδο καθώς και την επιπλέον μνήμη. Γενικά, θα αναφερόμαστε σε ποσότητα μνήμης χωρίς να προσδιορίζουμε ακριβώς τα KB. Πρέπει να θεωρούμε τη θέση μνήμης αρκετά μεγάλη για να χωρέσει έναν αριθμό. Αν το μέγεθος της μνήμης εξαρτάται από τη συγκεκριμένη είσοδο, μπορεί να γίνει η ανάλυση χειρότερης περίπτωσης (worst- case) και μέσης περίπτωσης (average - case).
 
ΑΠΛΟΤΗΤΑ
Συχνά, όχι πάντα, ο άμεσος τρόπος επίλυσης ενός προβλήματος δεν είναι και ο πιο αποδοτικός. Η απλότητα ενός αλγορίθμου είναι ένα επιθυμητό χαρακτηριστικό. Κάνει την απόδειξη της ορθότητας ευκολότερη, όπως επίσης ευκολότερο το γράψιμο, την εκσφαλμάτωση και τη μετατροπή ενός προγράμματος. ¨οταν διαλέγουμε έναν αλγόριθμο πρέπει να συνυπολογίσουμε το χρόνο που χρειάζεται η εκσφαλμάτωση, αλλά αν το πρόγραμμα χρησιμοποιείται πολύ συχνά, ο κρισιμότερος παράγοντας είναι η αποδοτικότητα.
 
ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ (OPTIMALITY)