Πλανόδιοι πωλητές, ταχυδρόμοι και μυρμήγκια.

Ένα από τα πιο διάσημα προβλήματα των μαθηματικών, αλλά και της πληροφορικής, είναι το πρόβλημα του πλανόδιου πωλητή:

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

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

Travelling salesman movie

Όπως θα δείτε και στο παραπάνω άρθρο το πρόβλημα του πλανόδιου πωλητή είναι τρομερά δύσκολο να επιλυθεί με τις ως τώρα υπάρχουσες μεθόδους. Ένας υπάλληλος της UPS με 25 πακέτα προς παράδοση έχει 15 τρισεκατομμύρια διαδρομές! Το πρόβλημα αυτό ανήκει σε μια κατηγορία προβλημάτων, τα λεγόμενα πλήρη NP προβλήματα, για τα οποία εικάζεται ότι δεν υπάρχει "γρήγορος" αλγόριθμος που να τα επιλύει. Η εικασία αυτή είναι μια από τις πιο διάσημες εικασίες των μαθηματικών και ίσως η πιο διάσημη εικασία της πληροφορικής. Είναι δε επικυρηγμένη για 1 εκατομμύριο δολάρια από το Clay math institute! Επίσης, υπάρχει και μια ταινία με το τίτλο "Travelling salesman" η οποία διηγείται την ιστορία μιας ομάδας μαθηματικών που έχει προσλάβει η αμερικανική κυβέρνηση για να λύσουν το πρόβλημα αυτό.

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

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

Υ.Γ. Και μια ερώτηση. Άραγε στην Ελλάδα υπάρχει κάποιος (δημόσιος οργανισμός, ιδιωτική εταιρεία ή άλλος) που να ασχολείται με το πρόβλημα της εύρεσης της μικρότερης διαδρομής; για παράδειγμα, τα ΕΛΤΑ και τα συνεργεία καθαριότητας κάθε δήμου θα είχαν άμεσα οφέλη από την ελαχιστοποίηση των διαδρομών που κάνουν. Φοβάμαι, όμως, ότι στη χώρα είναι η εφαρμογή των μεθόδων μαθηματικής βελτιστοποίησης απέχει έτη φωτός. Κι ας διδάσκεται στα ελληνικά πανεπιστήμια εδώ και δεκαετίες...

Παραπομπές:

1. Το άρθρο του περιοδικού wired  για τη UPS.
2. Η σελίδα της wikipedia  για το πρόβλημα του πλανόδιου πωλητή (στα αγγλικά). Εκεί θα βρείτε και παραπομπή στη μέθοδο επίλυσης του με την αποικία μυρμηγκιών.
3. Η επίσημη σελίδα της ταινίας "Travelling salesman".

Η χρήση της θεωρίας των πρώτων αριθμών στην κωδικοποίηση

Σίγουρα όλοι μας έχουμε ακούσει για τους πρώτους αριθμούς και για το πως στη σημερινή εποχή χρησιμοποιούμε πανίσχυρους υπολογιστές για να μεγαλώσουμε το “κατάλογο” με τους ήδη γνωστούς πρώτους αριθμούς. Επίσης σίγουρα αρκετοί από εμάς θα σκεφτήκαμε ότι αν και αυτή η αναζήτηση είναι ενδιαφέρουσα δεν έχει καμία πρακτική εφαρμογή. ’Όμως τα πράγματα δεν είναι έτσι. Η αναζήτηση πρώτων αριθμών (και η ανάλυση ενός αριθμού σε γινόμενο πρώτων παραγόντων) έχει εφαρμογή στην κρυπτογραφία.

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

στο Α τον αριθμό 1

στο Γ τον αριθμό 2

στο Τ τον αριθμό 3

Έτσι η λέξη ΓΑΤΑ μεταφράζεται στην ακολουθία αριθμών 2,1,3,1

Επιλέγουμε έναν αριθμό n (με n>m) και ένα αριθμό r σχετικά πρώτο με το n (εδώ επιλέγουμε η=5,r=3).’Έστω a ένας όρος της ακολουθίας, πολλαπλασιάζουμε τον a με τον r και παίρνουμε το υπόλοιπο του γινομένου αr ως προς n. ’Έτσι στο συγκεκριμένο παράδειγμα η ακολουθία γίνεται 6,3,9,3 αν πολλαπλασιαστεί με το 3 και αν πάρουμε το υπόλοιπο ως προς 5 έχουμε 1,3,4,3

Αν θέλουμε να αποκωδικοποιήσουμε το μήνυμα αρκεί να βρούμε έναν αριθμό p τέτοιο που το γινόμενο pr να έχει υπόλοιπο ένα όταν διαιρεθεί με το n (επειδή (n,r)=1 δηλ. είναι σχετικά πρώτοι ένας τέτοιος αριθμός σίγουρα υπάρχει).

Για το παράδειγμα μας είναι p=2 αφού pr=23=6=5+1.

Τώρα αν πολλαπλασιάσουμε κάθε όρο της κωδικοποιημένης ακολουθίας με το p και πάρουμε το υπόλοιπο το γινομένου ως προς n έχουμε την αρχική ακολουθία.

Έτσι η ακολουθία 1,3,4,3 γίνεται 2,6,8,6 όταν πολλαπλασιαστεί με το 2 και παίρνοντας τα υπόλοιπα ως προς 5 έχουμε 2,1,3,1 που αντιστοιχεί στη λέξη ΓΑΤΑ.

Το πρόβλημα είναι όμως ότι αυτός που κάνει την κωδικοποίηση ξέρει αυτόματα πως να αποκωδικοποιήσει τα μηνύματα.Το πρόβλημα αυτό αντιμετωπίζεται με τη χρήση μιας μεθόδου χάρη στην οποία είναι πρακτικά αδύνατα σε όποιον κάνει την κωδικοποίηση να κάνει και την αποκωδικοποίηση.Τη μέθοδο αυτή επινόησαν οι Ronald L.Rivest,Adi Shamip,Leonard Adleman και παρουσιάστηκε σε μια εργασία τους το 1977.

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

• Επιλέγουμε 2 πρώτους αριθμούς p,q και υπολογίζουμε το γινόμενό τους m=pq και εδώ θέλουμε το m να είναι μεγαλύτερο από το πλήθος των γραμμάτων που έχουμε (για το ίδιο παράδειγμα επιλέγουμε p=3, q=5)

• Μετά βρίσκουμε 2 αριθμούς c,d τέτοιους ώστε το γινόμενο τους να αφήνει υπόλοιπο 1 όταν διαιρεθεί με τον (p-1)(q-1)

{εδώ (p-1)(q-1)=(3-1)(5-1)=8 άρα αν c=d=3 τότε cd= q= 8+1= (p-1)(q-1)+1}

Τώρα μπορούμε να ανακοινώσουμε τους αριθμούς m και c . Όποιος θέλει να κωδικοποιήσει ένα μήνυμα αρκεί να το μετατρέψει σε μαι ακολουθία αριθμών , κάθε όρο της να τον υψώσει στην c και να πάρει το υπόλοιπο του ως προς m.

Για το συγκεκριμένο παράδειγμα έχουμε την ακολουθία: 2,1,3,1

υψώνοντας κάθε φορά στην 3 παίρνουμε: 8,1,27,1

και άρα τα υπόλοιπα ως προς 15 είναι η ακολουθία: 8,1,12,1

• Για την αποκωδικοποίηση αρκεί να υψώσουμε κάθε όρο της κωδικοποιημένης ακολουθίας στην d=3 και αν πάρουμε το υπόλοιπο του ως προς n=15 έτσι έχουμε διαδοχικά :

512, 1, 1758, 1 αν υψώσουμε στην 3 και

2, 1, 3, 1 αν πάρουμε το υπόλοιπο ως προς 15.

Το σημαντικό στην παραπάνω διαδικασία είναι ότι αν τα p,q είναι μεγάλα τότε είναι πολύ δύσκολο να βρεθούν αν γνωρίζουμε μόνο το n και επομένως είναι πολύ δύσκολο να υπολογιστεί και ο αριθμός d που είναι απαραίτητος για την αποκωδικοποίηση. Ο Rivest υπολόγισε ότι αν ο n είναι ένας αριθμός με 125 ή 126 ψηφία ο οποίος προέκυψε από 2 πρώτους με 63 ψηφία τότε για να αναλυθεί ο n σε γινόμενο πρώτων παραγόντων θα χρειαζόντουσαν περίπου 10 τετράκις εκατομμύρια χρόνια.

Σχεδιάγραμα κρυπτογράφησης δημοσίου κλειδειού. Εικόνα από το wikimedia commons.

Παράρτημα

Ορισμός: γράφοντας a =b modn εννοούμε ότι ο a όταν διαιρεθεί με το n αφήνει το ίδιο υπόλοιπο με τον b

Ισχύει ότι αν (r,n)=1 δηλαδή είναι σχετικά πρώτοι τότε υπάρχει k ώστε : rk=1 modn

Άρα αν a είναι ένας αριθμός που αντιστοιχεί σ’ ένα γράμμα μιας λέξης για να τον κωδικοποιήσουμε τον πολλαπλασιάζουμε μ’ έναν αριθμό r τέτοιο ώστε (r,n)=1. Για να κάνουμε την αποκωδικοποίηση αρκεί να πολλαπλασιάσουμε με τον αντίστοιχο αριθμό k έτσι έχουμε:

(ar) k=a(rk)=a1=amodn 

Επίσης από το θ.Fermat έχουμε ότι αν (a,n)=1 τότε a^φ(n)=1modn, όπου φ(n) η συνάρτηση του Euler (αν n=pq όπου p,q πρώτοι τότε φ(n)= (p-1)(q-1))

Επομένως αν n=pq και cd=λφ(n)+1 τότε για να κωδικοποιήσουμε τον όρο a τον υψώνουμε στην c και παίρνουμε b=a^cmod, ενώ για να τον αποκωδικοποιήσουμε υψώνουμε τον b στην d:

 b^d=(a^c)^d= a^cd =a^λφ(n)+1=a^λφ(n) a=(a^φ(n))^λa=1^λa=1a=amodn

Πανελλήνιες 2013 - Ανακοίνωση εισακτέων

Ανακοινώθηκε ο αριθμός των εισακτέων σε κάθε σχολή. Η σχετική ανακοίνωση στη σελίδα του υπουργείου είναι εδώ. Να σας ενημερώσω ότι και φέτος θα δοκιμάσω να προβλέψω την μεταβολή των βάσεων για διάφορες σχολές. Αυτό θα γίνει αφού ανακοινωθούν και τα στοιχεία για τη βαθμολογία των υποψηφίων.

Το σχετικό άρθρο του in.gr ξεκινά ως εξής:
"Μειωμένος κατά 6.806 ο αριθμός των εισακτέων σε ΑΕΙ και ΤΕΙ

Μειωμένοι κατά 8,94% είναι οι εισακτέοι στα ΑΕΙ και στα ΤΕΙ, στην Ανώτατη Σχολή Παιδαγωγικής και Τεχνολογικής Εκπαίδευσης (ΑΣΠΑΙΤΕ) και στις ΑΣΤΕ, όπως ανακοίνωσε την Τρίτη το μεσημέρι το υπουργείο Παιδείας.
Συγκεκριμένα, θα εισαχθούν 69.288 υποψήφιοι, ενώ το ακαδημαϊκό έτος 2012-2013 είχαν εισαχθεί 76.094..."