«Διαίρει και Βασίλευε»: Από τα Σπαθιά στα Microchip

 

Πώς μια αρχαία πολεμική τακτική μετατράπηκε στο απόλυτο «cheat code» της Πληροφορικής; Η διαδρομή είναι γεμάτη αίμα, στρατηγική και... ανακατεμένα δεδομένα.

  Η ιδέα δεν γεννήθηκε σε εργαστήριο, αλλά στα πεδία των μαχών. Ο Φίλιππος Β' ο Μακεδόνας (πατέρας του Μ. Αλεξάνδρου) συνειδητοποίησε ότι αν κρατάς τους αντιπάλους σου απομονωμένους, διασπασμένους και σε διαρκή φαγωμάρα, τους εξουσιάζεις για πλάκα. Οι Ρωμαίοι το μετέφρασαν σε Divide et impera και το έκαναν το επίσημο manual της αυτοκρατορίας τους.

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

  Ο άνθρωπος που πήρε τη γεωπολιτική ίντριγκα και την κλείδωσε μέσα στα τσιπάκια ήταν ο θρυλικός Τζον φον Νόιμαν.

• Το χάος: Ο πρώιμος υπολογιστής EDVAC  προσπαθώντας να βάλει σε σειρά τεράστιους όγκους ανακατεμένων δεδομένων.

• Το χτύπημα: Το 1945, ο φον Νόιμαν εφηύρε τον αλγόριθμο Merge Sort. Ανάγκασε τον υπολογιστή να σταματήσει να πελαγώνει: να σπάει τις λίστες στη μέση ξανά και ξανά μέχρι να μείνουν μονά κομμάτια, να τα ταξινομεί ακαριαία και να τα επανασυνδέει.

Μια στρατιωτική τακτική 2.500 ετών έγινε ο λόγος που σήμερα το smartphone σου, η Google και το Netflix μπορούν να φιλτράρουν δισεκατομμύρια πληροφορίες σε κλάσματα του δευτερολέπτου.

Ένα παράδειγμα 

Το καλύτερο και πιο εύληπτο παράδειγμα από την καθημερινότητα για την κατανόηση της μεθόδου  «Διαίρει και Βασίλευε» είναι το φτιάξιμο ενός μεγάλου παζλ 1.000 κομματιών.

Αν προσπαθήσεις να πάρεις ένα τυχαίο κομμάτι και να το δοκιμάσεις ένα-ένα με τα υπόλοιπα 999 για να δεις πού ταιριάζει, θα τρελαθείς. Αυτός είναι ο «χρονοβόρος» τρόπος (στον προγραμματισμό τον λέμε Brute Force).

Αντίθετα,  εφαρμόζουμε τη μέθοδο Διαίρει και Βασίλευε:

1. Διαίρεση (Divide)

«Σπάμε» το τεράστιο πρόβλημα (των 1.000 κομματιών) σε μικρότερα, πιο εύκολα διαχειρίσιμα «υποπροβλήματα». Αδειάζουμε το κουτί και χωρίζουμε τα κομμάτια σε κατηγορίες:

• Ομάδα Α: Όλα τα κομμάτια με ίσιες άκρες (το περίγραμμα).

• Ομάδα Β: Όλα τα έντονα μπλε κομμάτια (ο ουρανός).

• Ομάδα Γ: Όλα τα πράσινα κομμάτια (το γρασίδι).

2. Βασίλευε (Conquer)

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

• Φτιάχνουμε πρώτα όλο το τετράγωνο πλαίσιο (το περίγραμμα).

• Συναρμολογούμε τα μπλε κομμάτια και σχηματίζουμε τον ουρανό.

• Συναρμολογούμε τα πράσινα κομμάτια και σχηματίζουμε το γρασίδι.

3. Συνδυασμός (Combine)

Παίρνουμε τα 3 έτοιμα κομμάτια που φτιαξαμε (το πλαίσιο, τον ουρανό, το γρασίδι), τα κουμπώνουμε  μεταξύ τους και ξαφνικά έχουμε μπροστά μας  έτοιμο ολόκληρο το παζλ!

Ένα ακόμα γρήγορο παράδειγμα: Το καθάρισμα του σπιτιού

Αν σκεφτείς «πρέπει να καθαρίσω ένα διώροφο σπίτι», μάλλον θα πάθεις πανικό και θα το αναβάλεις.

• Διαίρεση: Χωρίζεις το σπίτι σε δωμάτια (Κουζίνα, Μπάνιο, Σαλόνι).

• Βασίλευε: Μπαίνεις στην κουζίνα και καθαρίζεις μόνο αυτήν. Μετά πας στο μπάνιο. Μετά στο σαλόνι. κάθε δωμάτιο μόνο του είναι μια εύκολη, γρήγορη μάχη.

• Συνδυασμός: Μόλις τελειώσεις και το τελευταίο δωμάτιο, αυτόματα όλο το σπίτι είναι καθαρό.

Με λίγα λόγια: Παίρνεις κάτι που σε ξεπερνάει σε μέγεθος, το «τεμαχίζεις» σε μικρά κομμάτια που τα «έχεις» εύκολα, τα λύνεις ένα-ένα, και στο τέλος τα ενώνεις!

Το πλέον κλασικό και πανέμορφο πρόβλημα της ζυγαριάς, το οποίο αποτελεί την απόλυτη πρακτική εφαρμογή του «Διαίρει και Βασίλευε»!

  Ας υποθέσουμε ότι έχουμε 9 νομίσματα (το 9 είναι ο ιδανικός αριθμός για να καταλάβουμε τη δύναμη της μεθόδου). Τα 8 είναι γνήσια και έχουν το ίδιο βάρος, ενώ το 1 είναι κάλπικο και βαρύτερο.

Με μια ζυγαριά δύο σκελών, το ελάχιστο πλήθος ζυγίσεων που χρειαζόμαστε για να το βρούμε με 100% σιγουριά είναι μόνο 2 ζυγίσεις!

Αντί να χωρίσουμε τα νομίσματα στη μέση (στα 2), η βέλτιστη στρατηγική εδώ είναι να τα διαιρέσουμε στα 3.

1η Ζύγιση: Η πρώτη μεγάλη διαίρεση

Διαίρεση: Χωρίζουμε τα 9 νομίσματα σε 3 ίσες ομάδες των 3 νομισμάτων (Ομάδα Α, Ομάδα Β, Ομάδα Γ).

Βασίλευε: Παίρνουμε την Ομάδα Α και την Ομάδα Β και τις βάζουμε στα δύο σκέλη της ζυγαριάς (3 νομίσματα αριστερά, 3 δεξιά). Η Ομάδα Γ μένει στο τραπέζι.

Υπάρχουν δύο πιθανές περιπτώσεις:

• Περίπτωση 1 (Η ζυγαριά γέρνει): Αν ένα από τα δύο σκέλη κατεβεί, τότε το κάλπικο (το βαρύτερο) βρίσκεται προφανώς μέσα στην ομάδα που έγειρε τη ζυγαριά.

• Περίπτωση 2 (Η ζυγαριά ισορροπεί): Αν η ζυγαριά μείνει οριζόντια, σημαίνει ότι οι ομάδες Α και Β έχουν μόνο γνήσια νομίσματα. Άρα, το κάλπικο βρίσκεται σίγουρα στην Ομάδα Γ που αφήσαμε στο τραπέζι!

Το κέρδος: Με 1 και μόνο ζύγιση, αποκλείσαμε αμέσως τα 6 από τα 9 νομίσματα. Τώρα ξέρουμε με βεβαιότητα ότι το κάλπικο βρίσκεται σε μια συγκεκριμένη τριάδα.

2η Ζύγιση: Ο εντοπισμός

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

Διαίρεση: Χωρίζουμε τα 3 νομίσματα σε 3 ομάδες του 1 νομίσματος.

Βασίλευε & Συνδυασμός: Παίρνουμε 2 από τα νομίσματα και βάζουμε ένα στο αριστερό σκέλος και ένα στο δεξί. Το τρίτο νόμισμα μένει στο τραπέζι.

• Αν η ζυγαριά γέρνει: Το νόμισμα στο σκέλος που κατέβηκε είναι το κάλπικο.

• Αν η ζυγαριά ισορροπεί: Τα δύο νομίσματα στη ζυγαριά είναι γνήσια, άρα το κάλπικο είναι αυτό που αφήσαμε στο τραπέζι!

Η  Γενίκευση

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

Αν είχες περισσότερα νομίσματα, ο ελάχιστος αριθμός ζυγίσεων N για x νομίσματα καθορίζεται από τις δυνάμεις του 3 :

• Έως 3 νομίσματα: 1 ζύγιση (3^1)

• Έως 9 νομίσματα: 2 ζυγίσεις (3^2)

• Έως 27 νομίσματα: 3 ζυγίσεις (3^3)

• Έως 81 νομίσματα: 4 ζυγίσεις (3^4)

Έτσι, ακόμη και αν είχες 80 νομίσματα, με τη μέθοδο «Διαίρει και Βασίλευε» θα χρειαζόσουν το πολύ 4 κινήσεις για να βρεις το κάλπικο!

Να περάσουμε σε ένα αγαπημένο πρόβλημα 

                                            Ο Δαίδαλος και η Πρόκληση του Μίνωα

Όταν ο Δαίδαλος κατέφυγε στη Σικελία, ο βασιλιάς Μίνωας τον καταδίωξε. Για να προστατευτεί, ο Δαίδαλος πρότεινε μια πρόκληση: άφησε πίσω του ένα έγγραφο σκισμένο σε 100 κομμάτια. Κάθε κομμάτι τοποθετήθηκε μέσα σε ένα κλειδωμένο κουτί με το δικό του μοναδικό κλειδί.

Δεδομένα:

1. Υπάρχουν 100 κουτιά και 100 κλειδιά, αριθμημένα από το 1 έως το 100.

2. Ο κανόνας είναι ότι ο αριθμός του σωστού κλειδιού για κάθε κουτί μπορεί να διαφέρει από τον αριθμό του κουτιού το πολύ κατά 1. Για παράδειγμα, το κουτί 42 μπορεί να ανοίγει μόνο από το κλειδί 41, το 42 ή το 43.

3. Ο σκοπός είναι να βρεθεί ποιο κλειδί αντιστοιχεί σε ποιο κουτί με τις λιγότερες δυνατές δοκιμές.

Ποιος είναι ο μικρότερος αριθμός δοκιμών που απαιτείται για να εγγυηθούμε την πλήρη αντιστοίχιση όλων των κλειδιών με τα κουτιά, ακόμη και στη χειρότερη περίπτωση;

Για να βρούμε τη λύση, μπορούμε να ξεκινήσουμε απλοποιώντας το πρόβλημα:

2 Κουτιά: Αν έχουμε τα κουτιά 1 και 2, αρκεί 1 δοκιμή. Δοκιμάζουμε το κλειδί 1 στο κουτί 1. Αν ανοίξει, τότε το κλειδί 2 ανοίγει το κουτί 2. Αν δεν ανοίξει, τότε το κλειδί 1 ανοίγει το κουτί 2 και το κλειδί 2 το κουτί 1.

4 Κουτιά: για μια ομάδα 4 κουτιών (π.χ. 1, 2, 3, 4), υπάρχουν 5 πιθανά σενάρια αντιστοίχισης (όπως {1-1, 2-2, 3-3, 4-4} ή {2-1, 1-2, 4-3, 3-4}).(**) 

(Ο αριθμός των σεναρίων αυτών ακολουθεί την ακολουθία Fibonacci. Αν Sn είναι ο αριθμός των τρόπων για n κουτιά, τότε Sn = Sn-1 + Sn-2:

• Για 1 κουτί: 1 τρόπος.

• Για 2 κουτιά: 2 τρόποι.

• Για 3 κουτιά: 3 τρόποι (1+2).

• Για 4 κουτιά: 5 τρόποι (2+3).)

Με 3 δοκιμές μπορούμε να διακρίνουμε και τα 5 σενάρια (αφού 2^3 = 8, που είναι μεγαλύτερο από το 5).

Για παράδειγμα: Δοκιμάζουμε το κλειδί 3 στο κουτί 3. Αν πετύχει, μένουν οι συνδυασμοί των κουτιών 1 και 2 (1 δοκιμή) και το κουτί 4 είναι αναγκαστικά σωστό. Αν αποτύχει, προχωράμε σε στοχευμένες δοκιμές στα υπόλοιπα.

Γενίκευση για  100 Κουτιά:

Χωρίζουμε τα 100 κουτιά σε 25 ομάδες των 4 κουτιών η καθεμία.

Εφόσον κάθε ομάδα 4 κουτιών απαιτεί 3 δοκιμές για να λυθεί πλήρως, ο συνολικός αριθμός δοκιμών είναι 25 x3 = 75.

Συμπέρασμα: Απαιτούνται 75 δοκιμές για να είμαστε απόλυτα σίγουροι, ανεξάρτητα από το πόσο άτυχοι είμαστε στις επιλογές μας.

                     Aλγόριθμος Mergesort (Ταξινόμηση μέσω Συγχώνευσης)

 Η προσέγγιση «Διαίρει και Βασίλευε» (Divide and Conquer) δεν είναι απλώς μια στρατιωτική τακτική, αλλά ένας από τους πιο ισχυρούς και κομψούς τρόπους που έχουν οι υπολογιστές —και οι άνθρωποι— για να επιβάλλουν την τάξη στο χάος.

Ακολουθεί μια περιγραφή της μεθόδου, όπως αυτή αναλύεται μέσα από τον αλγόριθμο Mergesort (Ταξινόμηση μέσω Συγχώνευσης):

Η Παγίδα του Μεγέθους: Γιατί χρειαζόμαστε το «Διαίρει»

Φανταστείτε ότι έχετε μια βιβλιοθήκη με εκατοντάδες μπερδεμένα βιβλία. Η διαίσθησή μας λέει ότι αν διπλασιάσουμε τον αριθμό των βιβλίων, θα χρειαστούμε διπλάσιο χρόνο για να τα ταξινομήσουμε. Στην πραγματικότητα, η ταξινόμηση πάσχει από αυτό που οι επιστήμονες ονομάζουν «αντι-οικονομία κλίμακας»: όσο περισσότερα είναι τα αντικείμενα, τόσο πιο αργή και επίπονη γίνεται η διαδικασία ανά αντικείμενο, γιατί κάθε νέο βιβλίο πρέπει να συγκριθεί με όλο και περισσότερα άλλα. Το μέγεθος πονάει.

Η Λύση: Σπάστε το πρόβλημα στα δύο

Αντί να προσπαθήσετε να βάλετε σε τάξη ολόκληρο το βουνό των βιβλίων ταυτόχρονα, η στρατηγική «Διαίρει και Βασίλευε» σας προτείνει κάτι ριζοσπαστικό: χωρίστε το βουνό στη μέση.

• Μην σταματήσετε εκεί. Χωρίστε τα δύο μισά σε τέσσερα τέταρτα, μετά σε όγδοα, και συνεχίστε μέχρι να έχετε πολλά ζευγάρια βιβλίων.

• Η ταξινόμηση δύο μόνο βιβλίων είναι παιχνιδάκι: απλώς βάζετε το «μικρότερο» πάνω από το «μεγαλύτερο».

Η Μεγεθυσμένη Συγχώνευση: Το «Βασίλευε»

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

• Δεν χρειάζεται να ψάξετε παντού. Συγκρίνετε μόνο τα δύο πάνω-πάνω βιβλία των δύο στοιβών.

• Παίρνετε το μικρότερο, το βάζετε στη νέα στοίβα και επαναλαμβάνετε τη διαδικασία με τα επόμενα «κορυφαία» βιβλία.

Το Αποτέλεσμα: Μια «Έκρηξη» Αποδοτικότητας

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

• Μια απλή μέθοδος θα απαιτούσε 300 εκατομμύρια περάσματα από τα δεδομένα.

• Το Mergesort (Διαίρει και Βασίλευε) θα χρειαζόταν μόλις 29 περάσματα.

Πρακτική εφαρμογή: Το «Πάρτι της Ταξινόμησης»

Η καλύτερη περιγραφή για την καθημερινή ζωή είναι η εξής: Αν θέλετε να τακτοποιήσετε τη βιβλιοθήκη σας, παραγγείλτε μια πίτσα και καλέστε φίλους.

1. Μοιράστε τα βιβλία ισόποσα σε όλους.

2. Ο καθένας ταξινομεί τη δική του μικρή στοίβα.

3. Μετά, ανά ζευγάρια, συγχωνεύετε τις στοίβες σας μέχρι να μείνει μόνο μία, τέλεια ταξινομημένη, πάνω στο ράφι.

Το μόνο που πρέπει να προσέξετε είναι να μην λερώσετε τα βιβλία με σάλτσα πίτσας!

Ο αλγόριθμος Mergesort επινοήθηκε από τον σπουδαίο μαθηματικό John von Neumann το 1945.

Ο Von Neumann έγραψε τον κώδικα για αυτόν τον αλγόριθμο προκειμένου να καταδείξει τη δύναμη του υπολογιστή αποθηκευμένου προγράμματος (stored-program computer),.

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

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

Είναι ενδιαφέρον ότι το πρόγραμμα του von Neumann γράφτηκε με το χέρι το 1945, παρόλο που ο υπολογιστής για τον οποίο προοριζόταν απείχε ακόμη αρκετά χρόνια από την ολοκλήρωσή του.

=================================================================

(**) Για να βρούμε τα 5 πιθανά σενάρια αντιστοίχισης για μια ομάδα 4 κουτιών, βασιζόμαστε στον περιορισμό που θέτει το πρόβλημα: ο αριθμός του σωστού κλειδιού για κάθε κουτί μπορεί να διαφέρει από τον αριθμό του κουτιού το πολύ κατά 1.

Αυτό σημαίνει ότι το κουτί n μπορεί να ανοίξει μόνο από το κλειδί n-1, το n ή το n+1. Για 4 κουτιά (1, 2, 3, 4), η εύρεση των σεναρίων γίνεται μέσω της εξής ανάλυσης περιπτώσεων:

Ανάλυση Περιπτώσεων

Περίπτωση Α: Το Κουτί 1 έχει το Κλειδί 1 Αν το Κουτί 1 «πάρει» το σωστό του κλειδί, τότε μένουν τα κουτιά 2, 3 και 4 για να αντιστοιχιστούν με τα κλειδιά 2, 3 και 4.

1. Υπο-περίπτωση 1: Το Κουτί 2 έχει το Κλειδί 2. Τότε μένουν τα 3 και 4. 

o Σενάριο 1: Κουτί 3-Κλειδί 3, Κουτί 4-Κλειδί 4 ({1, 2, 3, 4}).

o Σενάριο 2: Κουτί 3-Κλειδί 4, Κουτί 4-Κλειδί 3 ({1, 2, 4, 3}).

2. Υπο-περίπτωση 2: Το Κουτί 2 έχει το Κλειδί 3. Τότε το Κουτί 3 πρέπει να έχει το Κλειδί 2 (γιατί το Κλειδί 2 δεν μπορεί να ανοίξει το Κουτί 4). 

o Σενάριο 3: Κουτί 3-Κλειδί 2, Κουτί 4-Κλειδί 4 ({1, 3, 2, 4}).

Περίπτωση Β: Το Κουτί 1 έχει το Κλειδί 2 Αν το Κουτί 1 έχει το Κλειδί 2, τότε το Κουτί 2 πρέπει υποχρεωτικά να έχει το Κλειδί 1. Αυτό συμβαίνει γιατί το Κλειδί 1 μπορεί να ανοίξει μόνο το Κουτί 1 ή το Κουτί 2, και αφού το Κουτί 1 έχει ήδη κλειδί, το Κλειδί 1 «εγκλωβίζεται» στο Κουτί 2. Τώρα μένουν μόνο τα κουτιά 3 και 4 για να αντιστοιχιστούν με τα κλειδιά 3 και 4.

1. Υπο-περίπτωση 1: Το Κουτί 3 έχει το Κλειδί 3. 

o Σενάριο 4: Κουτί 4-Κλειδί 4 ({2, 1, 3, 4}).

2. Υπο-περίπτωση 2: Το Κουτί 3 έχει το Κλειδί 4. 

o Σενάριο 5: Κουτί 4-Κλειδί 3 ({2, 1, 4, 3}).

Σύνοψη των 5 Σεναρίων 

Σενάριο Κουτί 1 Κουτί 2 Κουτί 3 Κουτί 4

1ο Κλειδί 1 Κλειδί 2 Κλειδί 3 Κλειδί 4

2ο Κλειδί 2 Κλειδί 1 Κλειδί 3 Κλειδί 4

3ο Κλειδί 1 Κλειδί 3 Κλειδί 2 Κλειδί 4

4ο Κλειδί 1 Κλειδί 2 Κλειδί 4 Κλειδί 3

5ο Κλειδί 2 Κλειδί 1 Κλειδί 4 Κλειδί 3