Αλγόριθμοι: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 53:
Συνήθως ασχολούμαστε με προβλήματα με υπολογίσιμη πολυπλοκότητα. Δηλαδή με προβλήματα
για τα οποία οι απαιτήσεις σε χρόνο και μνήμη δεν είναι απαγορευτικές και
αναπτύσουμε αλγορίθμους για να λύσουμε τα προβλήματα αυτά. Συνήθη ερωτήματα που τίθενται στη μελέτη και την ανάλυση των αλγορίθμων είναι :
Γραμμή 83 ⟶ 84 :
Αναλύουμε τους αλγόριθμους με το να βελτιώνουμε, αν είναι δυνατό, και με το να
διαλέγουμε τον καλύτερο για ένα πρόβλημα. Εξετάζουμε τα ακόλουθα κριτήρια : α) ορθότητα β) ποσότητα της δουλειάς που πρέπει να γίνει γ) ποσότητα της
μνήμης που απαιτείται δ) απλότητα ε) πότε ένας αλγόριθμος είναι βέλτιστος Θα αναπτύξουμε ορισμένα από αυτά.
Γραμμή 95 ⟶ 98 :
Πρώτον, πριν προσπαθήσουμε να διαπιστώσουμε αν ένας αλγόριθμος είναι σωστός, πρέπει
να ξεκαθαρίσουμε τι σημαίνει "σωστός". Μπορούμε να λέμε ότι ένας αλγόριθμος είναι
Πρέπει να εξετάσουμε προσεκτικά κάποιες λεπτομέρειες (όπως αρχικές και τελικές τιμές διαφόρων μετρητών των βρόχων) και να εκτελέσουμε με το χέρι τον αλγόριθμο για κάποια μικρά παραδείγματα. Τίποτα από αυτά δεν αποδεικνύει ότι είναι σωστός, αλλά για μικρά προγράμματα αρκούν άτυπες τεχνικές. Πολλά προγράμματα που γράφονται έξω από σχολικές τάξεις είναι πολύ μεγάλα και πολύ πολύπλοκα. Για να αποδείξουμε την ορθότητα ενός μεγάλου προγράμματος, μπορούμε να διασπάσουμε το πρόγραμμα σε μικρότερα τμήματα, να αποδείξουμε ότι το καθένα από αυτά κάνει σωστά τη δουλειά του, επομένως όλο το πρόγραμμα είναι σωστό. Αυτό γίνεται ευκολότερο αν οι αλγόριθμοι και τα προγράμματα γράφονταν έτσι ώστε να μπορούν να διασπαστούν σε κομμάτια που μπορούν να επιλυθούν ξεχωριστά. Αυτό είναι ένα από τα κυριότερα ζητήματα του δομημένου προγραμματισμού.▼
σωστός, αν, δοθείσης μιας έγκυρης εισόδου, υπολογίζει σε πεπερασμένο χρόνο τη σωστή
απάντηση. Είμαστε εντάξει, αν γνωρίζουμε τι είναι οι έγκυρες είσοδοι και τι είναι το
"σωστό αποτέλεσμα". Επομένως αποδεικνύοντας ότι ένας αλγόριθμος είναι σωστός σημαίνει
να διατυπώσουμε ακριβώς τι αποτέλεσμα πρόκειται να παράγει δοθείσης καλά διατυπωμένης
εισόδου, και μετά να αποδείξουμε την πρόταση. Υπάρχουν δύο ζητήματα σε έναν αλγόριθμο :
η μέθοδος λύσης του προβλήματος και η σειρά των εντολών που πρέπει να εκτελεστούν για
να το επιτύχουν. Το να ξεδιαλύνουμε την ορθότητα της μεθόδου και/ή των τύπων που χρησιμοποιούνται μπορεί να απαιτεί μια μεγάλη ακολουθία λημμάτων και θεωρημάτων για τα αντικείμενα που εμπλέκονται στον αλγόριθμο (όπως γράφοι, επαναλήψεις, πίνακες). Για παράδειγμα, η εγκυρότητα της μεθόδου απλοποίησης Gauss για την επίλυση συστημάτων
γραμμικών εξισώσεων, εξαρτάται από έναν αριθμό θεωρημάτων της γραμμικής άλγεβρας. Τέλος
έχουμε τις ίδιες τις εντολές. Αν ένας αλγόριθμος είναι δίκαια σύντομος και ξεκάθαρα διατυπωμένος, χρησιμοποιούμε γενικά κάποιους πολύ άτυπους τρόπους στο να πειστούμε ότι
τα διάφορα τμήματά του κάνουν αυτό που πρέπει.
▲ Πρέπει να εξετάσουμε προσεκτικά κάποιες λεπτομέρειες (όπως αρχικές και τελικές τιμές διαφόρων μετρητών των βρόχων) και να εκτελέσουμε με το χέρι τον αλγόριθμο για κάποια μικρά παραδείγματα. Τίποτα από αυτά δεν αποδεικνύει ότι είναι σωστός, αλλά για μικρά προγράμματα αρκούν άτυπες τεχνικές. Πολλά προγράμματα που γράφονται έξω από σχολικές τάξεις είναι πολύ μεγάλα και πολύ πολύπλοκα. Για να αποδείξουμε την ορθότητα ενός μεγάλου προγράμματος,
μπορούμε να διασπάσουμε το πρόγραμμα σε μικρότερα τμήματα, να αποδείξουμε ότι το καθένα
από αυτά κάνει σωστά τη δουλειά του, επομένως όλο το πρόγραμμα είναι σωστό. Αυτό γίνεται ευκολότερο αν οι αλγόριθμοι και τα προγράμματα γράφονταν έτσι ώστε να μπορούν να
διασπαστούν σε κομμάτια που μπορούν να επιλυθούν ξεχωριστά. Αυτό είναι ένα από τα
κυριότερα ζητήματα του δομημένου προγραμματισμού.
Μια από τις πιο χρήσιμες τεχνικές στην απόδειξη της ορθότητας, είναι η μαθηματική επαγωγή. Χρησιμοποιείται για να αποδείξει ότι οι βρόχοι σε έναν αλγόριθμο κάνουν ακριβώς
αυτό που πρέπει. Για κάθε βρόχο θέτουμε συνθήκες και σχέσεις για τις οποίες πιστεύουμε
ότι ικανοποιούνται από τις μεταβλητές και τις δομές δεδομένων που χρησιμοποιούνται, και
μετά να επαληθεύσουμε ότι αυτές οι συνθήκες ισχύουν, κάνοντας "περάσματα" στο βρόχο. Οι λεπτομέρειες της απόδειξης απαιτούν να ακολουθήσουμε προσεκτικά τις εντολές στον αλγόριθμο.
</nowiki></pre></td></tr>
| |||