5.4 Είδη αλγορίθμων

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

Είναι γενικά γνωστό ότι, υπάρχουν σήμερα ακριβοί υπολογιστές με δυνατότητες που ξεπερνούν τα όρια των προσωπικών/ οικιακών υπολογιστών. Οι υπολογιστές αυτοί χρησιμοποιούνται από μεγάλες επιχειρήσεις, οργανισμούς και ιδρύματα, και διακρίνονται από τη συνθετότητά τους, αφού αποτελούνται από πολλούς επεξεργαστές, πολλές κύριες μνήμες και πολλές δευτερεύουσες μνήμες (μαγνητικούς δίσκους). Στους υπολογιστές αυτούς είναι δυνατόν ένας αλγόριθμος να κατατμηθεί σε μικρότερα κομμάτια που εκτελούνται παράλληλα, αφού απαιτούν διαφορετικούς υπολογιστικούς πόρους. Σε αυτά τα υπολογιστικά συστήματα ο χρόνος που απαιτείται από έναν αλγόριθμο, είναι κλάσμα του απαιτούμενου χρόνου από τον ίδιο αλγόριθμο σε έναν προσωπικό υπολογιστή, που τυπικά διαθέτει έναν επεξεργαστή, μία κύρια μνήμη και μία δευτερεύουσα μνήμη. Η ανάπτυξη παράλληλων (parallel) αλγορίθμων για περιβάλλοντα, όπως αυτό που προαναφέρθηκε, είναι μία σημαντική περιοχή που απασχολεί πλήθος επιστημόνων, καθώς διαφαίνεται ότι στο μέλλον οι υπολογιστές αυτοί θα γίνουν φθηνότεροι και θα επεκταθεί η χρήση τους. Ωστόσο, στα πλαίσια του μαθήματος αυτού δεν θα μας απασχολήσει η σχεδίαση και η ανάλυση παράλληλων αλγορίθμων.

Για να γίνει καλύτερα κατανοητή η έννοια του παράλληλου αλγόριθμου, ας θεωρήσουμε και πάλι το αρχικό παράδειγμα του 2ου κεφαλαίου, όπου πρέπει να δρομολογήσουμε τις ενέργειές μας, ώστε να γευματίσουμε. Όμως τώρα θα θεωρήσουμε ότι εργάζονται δύο άτομα. Έτσι, ο επόμενος πίνακας δίνει τις ενέργειες του κάθε ατόμου.

Πρώτο άτομο Δεύτερο άτομο Προετοιμασία σκευών μαγειρικής Ετοιμασία σαλάτας Παρασκευή φαγητού Στρώσιμο τραπεζιού Γεύμα Γεύμα Καθαριότητα τραπεζιού Πλύσιμο πιάτων και κουζινικών

Παρατηρούμε ότι τώρα η διαδικασία ολοκληρώνεται σε λιγότερο χρόνο, αφού σε κάθε άτομο αναλογούν μόνο τέσσερις εργασίες.

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

Επειδή η βελτίωση των αλγορίθμων είναι ζωτικής σημασίας, μία ιδιαίτερη περιοχή της Πληροφορικής, η Υπολογιστική Πολυπλοκότητα (Computa tional Complexity), διερευνά από την αναλυτική άποψη τους αλγορίθμους και τους ταξινομεί ανάλογα με την επίδοσή τους. Έτσι συνεχώς νέοι καλύτεροι αλγόριθμοι αναπτύσσονται, ενώ άλλοι εγκαταλείπονται ως μη αποτελεσματικοί. Ένας αλγόριθμος λέγεται άριστος (optimal), αν αποδειχθεί ότι είναι τόσο αποτελεσματικός, ώστε δεν μπορεί να κατασκευασθεί καλύτερος.

Πολυωνυμικοί (polynomial) λέγονται οι αλγόριθμοι με πολυπλοκότητα που φράσσεται από επάνω με μία πολυωνυμική έκφραση. Για παράδειγμα, πολυωνυμικοί είναι οι αλγόριθμοι τάξης Ο(n), O[pic], O[pic] κ.λπ. Συνήθως αυτοί δεν απαιτούν μεγάλη υπολογιστική προσπάθεια σε αντίθεση με τους αλγορίθμους πολυπλοκότητας τάξης O[pic], O[pic] ή O[pic], που ονομάζονται μη πολυωνυμικοί ή εκθετικοί.

Πολλές φορές μερικά προβλήματα σε πρώτη εξέταση μοιάζουν παρόμοια, αλλά στη συνέχεια μπορεί να αποδειχθεί ότι έχουν εξαιρετικά διαφορετικό βαθμό δυσκολίας ως προς την εύρεση αποτελεσματικής λύσης. Για παράδειγμα, έστω τα εξής δύο προβλήματα: - Δίδεται ένα σύνολο διαφορετικών θετικών αριθμών x1, x2, …, xn (όπου το n άρτιος αριθμός). Να βρεθούν δύο υποσύνολα από n/2 αριθμούς, όπου η διαφορά των αθροισμάτων κάθε υποσυνόλου να είναι μέγιστη, - Δίδεται ένα σύνολο διαφορετικών θετικών αριθμών x1, x2, …, xn (όπου το n άρτιος αριθμός). Να βρεθούν δύο υποσύνολα από n/2 αριθμούς, όπου η διαφορά των αθροισμάτων κάθε υποσυνόλου να είναι ελάχιστη.

Σε σχέση με το πρώτο πρόβλημα, εύκολα μπορούμε να προτείνουμε αποτελεσματικούς αλγορίθμους. Για παράδειγμα, μπορούμε να ταξινομήσουμε τους n αριθμούς και να τους χωρίσουμε σε δύο ομάδες, τους μικρούς και τους μεγάλους. Η λύση αυτή έχει πολυπλοκότητα Ο[pic], αν χρησιμοποιηθεί η ταξινόμηση φυσσαλίδας. Μάλιστα σημειώνεται ότι, μπορεί να προταθεί και ακόμη πιο αποτελεσματικός αλγόριθμος γραμμικής πολυπλοκότητας. Ωστόσο, σε σχέση με το δεύτερο πρόβλημα δεν υπάρχει αποτελεσματικός αλγόριθμος. Η μοναδική λύση στηρίζεται στην εξαντλητική δοκιμή όλων των δυνατών τρόπων. Ένας τέτοιος αλγόριθμος είναι πολυπλοκότητας Ο[pic].

Κατά παρόμοιο τρόπο υπάρχουν πολλά προβλήματα που δεν μπορούν να επιλυθούν με κάποιο αποτελεσματικό (δηλαδή πολυωνυμικό) αλγόριθμο, αλλά πρέπει να δοκιμασθούν όλες οι δυνατές περιπτώσεις ώστε να επιλεχθεί η καλύτερη. Τα προβλήματα αυτά ονομάζονται δυσχείριστα (intractable). Ευρύτατα γνωστό ως δυσχείριστο πρόβλημα είναι το πρόβλημα της συντομότερης διαδρομής που πρέπει ένας περιοδεύων πωλητής να ακολουθήσει, ώστε να περάσει μία και μόνο μία φορά από κάθε πόλη και να επιστρέψει στην αρχική. Το πρόβλημα αυτό αναφέρθηκε ως παράδειγμα στην αρχή του κεφαλαίου. Ένα άλλο γνωστό δυσχείριστο πρόβλημα είναι ο χρωματισμός ενός γράφου. Σύμφωνα με το πρόβλημα αυτό, πρέπει να χρωματίσουμε τις κορυφές ενός γράφου χρησιμοποιώντας ένα συγκεκριμένο αριθμό χρωμάτων, έτσι ώστε δύο γειτονικές κορυφές ή περιοχές να μην έχουν το ίδιο χρώμα. Δυσχείριστο επίσης είναι το πρόβλημα του χρωματισμού των συνδέσεων μεταξύ των ακμών ενός γράφου, έτσι ώστε οι συνδέσεις που καταλήγουν σε μία συγκεκριμένη κορυφή να είναι διαφορετικού χρώματος.

Τα δυσχείριστα αυτά προβλήματα, που αποκαλούνται και ανοικτά προβλήματα, λέγεται ότι ανήκουν στην κατηγορία των προβλημάτων NP-πλήρων προβλημάτων από τα αρχικά των αγγλικών όρων Nondeterministic Polynomial. Για κάθε πρόβλημα της κατηγορίας αυτής δεν υπάρχει ή τουλάχιστον δεν έχει βρεθεί ακόμη αλγόριθμος επίλυσής τους σε πολυωνυμικό χρόνο.

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

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