Αλγόριθμοι

Εισαγωγή

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

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

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

Συνήθως ασχολούμαστε με προβλήματα με υπολογίσιμη πολυπλοκότητα. Δηλαδή με προβλήματα για τα οποία οι απαιτήσεις σε χρόνο και μνήμη δεν είναι απαγορευτικές και αναπτύσσουμε αλγορίθμους για να λύσουμε τα προβλήματα αυτά. Συνήθη ερωτήματα που τίθενται στη μελέτη και την ανάλυση των αλγορίθμων είναι :

• Πως μπορεί να βελτιωθεί ένας αλγόριθμος;
• Πως μπορεί να αναλυθεί μαθηματικά η αποδοτικότητα των αλγορίθμων;
• Ποια κριτήρια χρησιμοποιούνται στην επιλογή του καταλληλότερου αλγόριθμου για μια συγκεκριμένη εφαρμογή;
• Με ποιο τρόπο μπορεί να αποδειχθεί ότι ένας αλγόριθμος είναι βέλτιστος;
• Πόσο χρήσιμα είναι πρακτικά τα θεωρητικά αποτελέσματα και οι αυστηροί ορισμοί;

Ανάλυση αλγορίθμων

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

• Ορθότητα
• Ποσότητα της δουλειάς που πρέπει να γίνει
• Ποσότητα της μνήμης που απαιτείται
• Απλότητα
• Πότε ένας αλγόριθμος είναι βέλτιστος Θα αναπτύξουμε ορισμένα από αυτά.

Ορθότητα

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

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

Μια από τις πιο χρήσιμες τεχνικές στην απόδειξη της ορθότητας, είναι η μαθηματική επαγωγή. Χρησιμοποιείται για να αποδείξει ότι οι βρόχοι σε έναν αλγόριθμο κάνουν ακριβώς αυτό που πρέπει. Για κάθε βρόχο θέτουμε συνθήκες και σχέσεις για τις οποίες πιστεύουμε ότι ικανοποιούνται από τις μεταβλητές και τις δομές δεδομένων που χρησιμοποιούνται, και μετά να επαληθεύσουμε ότι αυτές οι συνθήκες ισχύουν, κάνοντας "περάσματα" στο βρόχο. Οι λεπτομέρειες της απόδειξης απαιτούν να ακολουθήσουμε προσεκτικά τις εντολές στον αλγόριθμο.

Χρήση μνήμης

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

Απλότητα

Συχνά, όχι πάντα, ο άμεσος τρόπος επίλυσης ενός προβλήματος δεν είναι και ο πιο αποδοτικός. Η απλότητα ενός αλγορίθμου είναι ένα επιθυμητό χαρακτηριστικό. Κάνει την απόδειξη της ορθότητας ευκολότερη, όπως επίσης ευκολότερο το γράψιμο, την εκσφαλμάτωση και τη μετατροπή ενός προγράμματος. Όταν διαλέγουμε έναν αλγόριθμο πρέπει να συνυπολογίσουμε το χρόνο που χρειάζεται η εκσφαλμάτωση, αλλά αν το πρόγραμμα χρησιμοποιείται πολύ συχνά, ο κρισιμότερος παράγοντας είναι η αποδοτικότητα.

Βελτιστοποίηση(Optimization)

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

Πριν καταλήξουμε στο ποιος είναι ο βέλτιστος, μήπως πρέπει να εξετάσουμε καθέναν από την κλάση ξεχωριστά; Ευτυχώς όχι. Μπορούμε να αποδείξουμε θεωρήματα που καθορίζουν ένα κάτω όριο στον αριθμό των πράξεων που εκτελούνται. Τότε κάθε αλγόριθμος που εκτελεί αυτόν τον αριθμό των πράξεων είναι βέλτιστος. Επομένως υπάρχουν δύο δουλειές που πρέπει να γίνουν για να βρούμε έναν καλό αλγόριθμο στην κλάση των αλγορίθμων που μελετάμε, ή αλλιώς, να απαντήσουμε στη θεωρητική ερώτηση: Πόση δουλειά είναι απαραίτητη και αρκετή για να λυθεί ένα πρόβλημα;

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

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

Η έννοια του κάτω ορίου για τη συμπεριφορά της χειρότερης περίπτωσης των αλγορίθμων στη συγκεκριμένη κλάση, είναι πολύ σημαντική στην υπολογιστική πολυπλοκότητα. Πρέπει να κρατήσουμε καλά στο μυαλό μας ότι: "Η F είναι ένα κάτω όριο για μια κλάση αλγορίθμων", σημαίνει ότι για κάθε αλγόριθμο στην κλάση και για κάθε είσοδο τάξης n, υπάρχει κάποια είσοδος τάξης n, για την οποία ο αλγόριθμος πρέπει να εκτελέσει τουλάχιστον F(n) βασικές πράξεις.