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

<nowiki> '''1.ΕΙΣΑΓΩΓΗ'''

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

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

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

γ) Ποια κριτήρια χρησιμοποιούνται στην επιλογή του καταλληλότερου αλγόριθμου για μια συγκεκριμένη εφαρμογή;

δ) Με ποιο τρόπο μπορεί να αποδειχθεί ότι ένας αλγόριθμος είναι βέλτιστος;

 

 

<nowiki>'''2. ΑΝΑΛΥΣΗ ΑΛΓΟΡΙΘΜΩΝ'''