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

Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Tkirzoglou (συζήτηση | συνεισφορές)
Χωρίς σύνοψη επεξεργασίας
Tkirzoglou (συζήτηση | συνεισφορές)
Χωρίς σύνοψη επεξεργασίας
Γραμμή 1:
<nowiki> '''1.ΕΙΣΑΓΩΓΗ'''
Όταν λέμε ότι ένα πρόβλημα λύνεται αλγοριθμικά, εννοούμε, ότι υπάρχει ένα πρόγραμμα σε υπολογιστή που παράγει το σωστό αποτέλεσμα για κάθε είσοδο αν το τρέξουμε για όσο χρόνο χρειαστεί και του δώσουμε όση μνήμη χρειάζεται. Στη δεκαετία του 1930 πριν την εμφάνιση των υπολογιστών, οι μαθηματικοί δούλευαν εντατικά για να μελετήσουν τους αλγόριθμους, οι οποίοι μεταφράζονταν σε ένα ξεκάθαρο σύνολο εντολών που θα ακολουθούνταν για να λύσουν το πρόβλημα ή να υπολογίσουν μια συνάρτηση. Εξήχθησαν και διερευνήθηκαν διάφορα τυπικά μοντέλα υπολογισμού. Η πιο πολύ έμφαση σ' αυτή τη μελέτη, που ονομάστηκε θεωρία υπολογισμού, δόθηκε στην περιγραφή και τον χαρακτηρισμό τέτοιων προβλημάτων που μπορούσαν να λυθούν αλγοριθμικά και στο να εξαιρέσουν τα προβλήματα που δεν μπορούσαν να λυθούν. Ένα από τα πιο σημαντικά ζητήματα στην αρνητική περίπτωση ήταν το λεγόμενο "πρόβλημα τερματισμού" (halting problem). Το πρόβλημα τερματισμού είναι το να καθορίσεις πότε ένας τυχαίος δοθείς αλγόριθμος (ή πρόγραμμα υπολογιστή) θα μπεί σε ατέρμονα βρόχο, ενώ δουλεύει σε δοθείσα είσοδο. Στην περίπτωση αυτή δεν υπάρχει πρόγραμμα που να λύσει αυτό το πρόβλημα.</nowiki>
Όταν λέμε ότι ένα πρόβλημα λύνεται αλγοριθμικά, εννοούμε, ότι υπάρχει ένα πρόγραμμα σε υπολογιστή που παράγει το σωστό αποτέλεσμα για κάθε είσοδο αν το τρέξουμε για όσο χρόνο χρειαστεί και του δώσουμε όση μνήμη χρειάζεται. Στη δεκαετία του 1930 πριν την εμφάνιση των υπολογιστών, οι μαθηματικοί δούλευαν εντατικά για να μελετήσουν τους αλγόριθμους, οι οποίοι μεταφράζονταν σε ένα ξεκάθαρο σύνολο εντολών που θα ακολουθούνταν για να λύσουν το πρόβλημα ή να υπολογίσουν μια συνάρτηση. Εξήχθησαν και διερευνήθηκαν διάφορα τυπικά μοντέλα υπολογισμού. Η πιο πολύ έμφαση σ' αυτή τη μελέτη, που ονομάστηκε θεωρία υπολογισμού, δόθηκε στην περιγραφή και τον χαρακτηρισμό τέτοιων προβλημάτων που μπορούσαν να λυθούν αλγοριθμικά και στο να εξαιρέσουν τα προβλήματα που δεν μπορούσαν να λυθούν. Ένα από τα πιο σημαντικά ζητήματα στην αρνητική περίπτωση ήταν το λεγόμενο "πρόβλημα τερματισμού" (halting problem). Το πρόβλημα τερματισμού είναι το να καθορίσεις πότε ένας τυχαίος δοθείς αλγόριθμος (ή πρόγραμμα υπολογιστή) θα μπεί σε ατέρμονα βρόχο, ενώ δουλεύει σε δοθείσα είσοδο. Στην περίπτωση αυτή δεν υπάρχει πρόγραμμα που να λύσει αυτό το πρόβλημα.
Παρόλο που η θεωρία υπολογισμού είχε προφανείς και θεμελιώδεις εφαρμογές στην επιστήμη των υπολογιστών, η γνώση ότι ένα πρόβλημα μπορεί θεωρητικά να επιλυθεί σε υπολογιστή δεν είναι αρκετή αν αυτό δεν είναι πρακτικά εφαρμόσιμο. Για παράδειγμα, ένα πρόγραμμα που παίζει σκάκι, μπορεί θεωρητικά να γραφτεί και δεν είναι πολύ δύσκολο. Υπάρχει πεπερασμένος αριθμός διάταξης των κξομματιών του σκάκι και το παιχνίδι θα τερματίσει μετά από πεπερασμένο αριθμό κινήσεων αφού ακολουθηθούν συγκεκριμένοι κανόνες, με τις αντίστοιχες κινήσεις του άλλου παίκτη κοκ μέχρι τελικά το παιχνίδι να τελειώσει. Έτσι ο υπολογιστής αφού γνωρίζει τις δυνατές συνέπειες κάθε κίνησης διαλέγει την καλύτερη. Ένα τέτοιο πρόγραμμα δεν μπορεί να τρέξει γιατί ο αριθμός των δυνατών κινήσεων (προσεγγιστικά 10**19) είναι τόσο μεγάλος που το πρόγραμμα θα διαρκέσει χιλιάδες χρόνια.
Γραμμή 10 ⟶ 11 :
ε) Πόσο χρήσιμα είναι πρακτικά τα θεωρητικά αποτελέσματα και οι αυστηροί ορισμοί;
 
'''2. ΑΝΑΛΥΣΗ ΑΛΓΟΡΙΘΜΩΝ'''
Αναλύουμε τους αλγόριθμους με το να βελτιώνουμε, αν είναι δυνατό, και με το να διαλέγουμε τον καλύτερο για ένα πρόβλημα. Εξετάζουμε τα ακόλουθα κριτήρια :
α) ορθότητα β) ποσότητα της δουλειάς που πρέπει να γίνει γ) ποσότητα της μνήμης που απαιτείται δ) απλότητα ε) πότε ένας αλγόριθμος είναι βέλτιστος
Θα αναπτύξουμε ορισμένα από αυτά.
'''ΟΡΘΟΤΗΤΑ'''
Υπάρχουν τρία κύρια βήματα στην ταυτοποίηση της ορθότητας ενός αλγορίθμου.
Πρώτον, πριν προσπαθήσουμε να διαπιστώσουμε αν ένας αλγόριθμος είναι σωστός, πρέπει να ξεκαθαρίσουμε τι σημαίνει "σωστός". Μπορούμε να λέμε ότι ένας αλγόριθμος είναι σωστός, αν, δοθείσης μιας έγκυρης εισόδου, υπολογίζει σε πεπερασμένο χρόνο τη σωστή απάντηση. Είμαστε εντάξει, αν γνωρίζουμε τι είναι οι έγκυρες είσοδοι και τι είναι το "σωστό αποτέλεσμα". Επομένως αποδεικνύοντας ότι ένας αλγόριθμος είναι σωστός σημαίνει να διατυπώσουμε ακριβώς τι αποτέλεσμα πρόκειται να παράγει δοθείσης καλά διατυπωμένης εισόδου, και μετά να αποδείξουμε την πρόταση. Υπάρχουν δύο ζητήματα σε έναν αλγόριθμο : η μέθοδος λύσης του προβλήματος και η σειρά των εντολών που πρέπει να εκτελεστούν για να το επιτύχουν. Το να ξεδιαλύνουμε την ορθότητα της μεθόδου και/ή των τύπων που χρησιμοποιούνται μπορεί να απαιτεί μια μεγάλη ακολουθία λημμάτων και θεωρημάτων για τα αντικείμενα που εμπλέκονται στον αλγόριθμο (όπως γράφοι, επαναλήψεις, πίνακες). Για παράδειγμα, η εγκυρότητα της μεθόδου απλοποίησης Gauss για την επίλυση συστημάτων γραμμικών εξισώσεων, εξαρτάται από έναν αριθμό θεωρημάτων της γραμμικής άλγεβρας. Τέλος έχουμε τις ίδιες τις εντολές. Αν ένας αλγόριθμος είναι δίκαια σύντομος και ξεκάθαρα διατυπωμένος, χρησιμοποιούμε γενικά κάποιους πολύ άτυπους τρόπους στο να πειστούμε ότι τα διάφορα τμήματά του κάνουν αυτό που πρέπει.
Πρέπει να εξετάσουμε προσεκτικά κάποιες λεπτομέρειες (όπως αρχικές και τελικές τιμές διαφόρων μετρητών των βρόχων) και να εκτελέσουμε με το χέρι τον αλγόριθμο για κάποια μικρά παραδείγματα. Τίποτα από αυτά δεν αποδεικνύει ότι είναι σωστός, αλλά για μικρά προγράμματα αρκούν άτυπες τεχνικές. Πολλά προγράμματα που γράφονται έξω από σχολικές τάξεις είναι πολύ μεγάλα και πολύ πολύπλοκα. Για να αποδείξουμε την ορθότητα ενός μεγάλου προγράμματος, μπορούμε να διασπάσουμε το πρόγραμμα σε μικρότερα τμήματα, να αποδείξουμε ότι το καθένα από αυτά κάνει σωστά τη δουλειά του, επομένως όλο το πρόγραμμα είναι σωστό. Αυτό γίνεται ευκολότερο αν οι αλγόριθμοι και τα προγράμματα γράφονταν έτσι ώστε να μπορούν να διασπαστούν σε κομμάτια που μπορούν να επιλυθούν ξεχωριστά. Αυτό είναι ένα από τα κυριότερα ζητήματα του δομημένου προγραμματισμού.
Μια από τις πιο χρήσιμες τεχνικές στην απόδειξη της ορθότητας, είναι η μαθηματική επαγωγή. Χρησιμοποιείται για να αποδείξει ότι οι βρόχοι σε έναν αλγόριθμο κάνουν ακριβώς αυτό που πρέπει. Για κάθε βρόχο θέτουμε συνθήκες και σχέσεις για τις οποίες πιστεύουμε ότι ικανοποιούνται από τις μεταβλητές και τις δομές δεδομένων που χρησιμοποιούνται, και μετά να επαληθεύσουμε ότι αυτές οι συνθήκες ισχύουν, κάνοντας "περάσματα" στο βρόχο. Οι λεπτομέρειες της απόδειξης απαιτούν να ακολουθήσουμε προσεκτικά τις εντολές στον αλγόριθμο.
'''ΧΡΗΣΗ ΜΝΗΜΗΣ'''
Ο ορισμός των θέσεων μνήμης που χρησιμοποιεί ένα πρόγραμμα, όπως και ο αριθμός των δευτερολέπτων που απαιτούνται, εξαρτάται από την υλοποίηση που επιλέγουμε. Παρόλο αυτά μπορούμε να εξάγουμε κάποια συμπεράσματα, εξετάζοντας έναν αλγόριθμο. Ένα πρόγραμμα χρειάζεται μνήμη για τις εντολές, τις σταθερές και τις μεταβλητές και τα δεδομένα. Χρειάζεται επιπλέον χώρο για την επεξεργασία των δεδομένων, και για την αποθήκευση των ενδιάμεσων αποτελεσμάτων. Τα δεδομένα εισόδου μπορούν να παρασταθούν με διάφορες μορφές που έχουν διαφορετικές απιτήσεις σε μνήμη. Αν έχουν μια φυσική μορφή - όπως ένα αρραυ αριθμών ή έναν πίνακα - τότε αναλύουμε και τον επιπλέον χώρο που χρησιμοποιείται, εκτός από το πρόγραμμα και την είσοδό του. Αν η επιπλέον μνήμη είναι σταθερή ως προς το μέγεθος της εισόδου, τότε λέμε ότι ο αλγόριθμος δουλεύει in place. Αυτός ο όρος χρησιμοποιείται κυρίως σε αλγόριθμους διάταξης. Αν η είσοδος μπορεί να παρασταθεί με διάφορους τρόπους (πχ γράφους) τότε, φυσικά, θα υπολογίσουμε τη μνήμη για την ίδια την είσοδο καθώς και την επιπλέον μνήμη. Γενικά, θα αναφερόμαστε σε ποσότητα μνήμης χωρίς να προσδιορίζουμε ακριβώς τα KB. Πρέπει να θεωρούμε τη θέση μνήμης αρκετά μεγάλη για να χωρέσει έναν αριθμό. Αν το μέγεθος της μνήμης εξαρτάται από τη συγκεκριμένη είσοδο, μπορεί να γίνει η ανάλυση χειρότερης περίπτωσης (worst- case) και μέσης περίπτωσης (average - case).
 
'''ΑΠΛΟΤΗΤΑ'''
Συχνά, όχι πάντα, ο άμεσος τρόπος επίλυσης ενός προβλήματος δεν είναι και ο πιο αποδοτικός. Η απλότητα ενός αλγορίθμου είναι ένα επιθυμητό χαρακτηριστικό. Κάνει την απόδειξη της ορθότητας ευκολότερη, όπως επίσης ευκολότερο το γράψιμο, την εκσφαλμάτωση και τη μετατροπή ενός προγράμματος. ¨οταν διαλέγουμε έναν αλγόριθμο πρέπει να συνυπολογίσουμε το χρόνο που χρειάζεται η εκσφαλμάτωση, αλλά αν το πρόγραμμα χρησιμοποιείται πολύ συχνά, ο κρισιμότερος παράγοντας είναι η αποδοτικότητα.
 
'''ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ (OPTIMALITY)'''
Για να αναλύσουμε την πολυπλοκότητα ενός προβλήματος, όπως τίθεται από έναν συγκεκριμένο αλγόριθμο, διαλέγουμε μια κλάση αλγορίθμων (συχνά καθορίζοντας τον τύπο των πράξεων που επιτρέπεται να εκτελούν οι αλγόριθμοι) και ένα μέτρο της πολυπλοκότητας, όπως πχ τις μετρούμενες πράξεις. Τότε μπορούμε να ρωτήσουμε πόσες πράξεις χρειάζονται για να λυθεί ένα πρόβλημα. Υπάρχει ο "καλύτερος" δυνατός αλγόριθμος; Λέμε ότι ένας αλγόριθμος είναι βέλτιστος (στη χειρότερη περίπτωση), αν δεν υπάρχει άλλος αλγόριθμος στην κλάση που μελετάμε που να εκτελεί λιγότερες πράξεις (στη χειρότερη περίπτωση).
Πριν καταλήξουμε στο ποιος είναι ο βέλτιστος, μήπως πρέπει να εξετάσουμε καθέναν από την κλάση ξεχωριστά; Ευτυχώς όχι. Μπορούμε να αποδείξουμε θεωρήματα που καθορίζουν ένα κάτω όριο στον αριθμό των πράξεων που εκτελούνται. Τότε κάθε αλγόριθμος που εκτελεί αυτον τον αριθμό των πράξεων είναι βέλτιστος. Επομένως υπάρχουν δύο δουλειές που πρέπει να γίνουν για να βρούμε έναν καλό αλγόριθμο στην κλάση των αλγορίθμων που μελετάμε, ή αλλιώς, να παντήσουμε στη θεωρητική ερώτηση : Πόση δουλειά είναι απαραίτητη και αρκετή για να λυθεί ένα πρόβλημα;