Επαγωγή σε δέντρα

Συντονιστής: Σεραφείμ

Σίλης
Δημοσιεύσεις: 64
Εγγραφή: Δευ Δεκ 01, 2014 6:50 pm

Επαγωγή σε δέντρα

#1

Μη αναγνωσμένη δημοσίευση από Σίλης » Πέμ Φεβ 19, 2015 2:56 pm

Έπεσα πάνω σ' αυτό το πρόβλημα κάποια στιγμή αναπάντεχα, και αν μή τι άλλο καθότι σκουριασμένος με τέτοια «στοιχειώδη», μου πήρε κάμποσο να το λύσω. Δέν το ξέρω το φόρουμ καλά, και δέν είμαι σίγουρος σε ποιά κατηγορία ταιριάζει. Μπορεί να τεθεί με όρους κατηγορηματικής λογικής ή θεωρητικής πληροφορικής: «ποιές ακολουθίες συμβόλων φτιάχνουν έναν επιτρεπτό όρο;». Εγώ το συνάντησα συγκεκριμένα σε συμφραζόμενα συντακτικής ανάλυσης, ψάχνοντας να βρώ στα πρόχειρα έναν γρήγορο αλγόριθμο για ν' αναγνωρίζω συμβολοσειρές πάνω σε δοσμένο αλφάβητο, χωρίς να πρέπει πρώτα να μάθω πάρσιν θίορι και δέ συμμαζεύεται. Τον τρόπο τον βρήκα σχετικά γρήγορα και ευχάριστα, παίζοντας απο δώ κι' απο κεί στο Μαθεμάτικα (του Γούλφραμ, όχι το φόρουμ), αλλα όταν είπα να τη δώ μαθηματικός και να δείξω οτι ο αλγόριθμος πράγματι κάνει αυτό που τον θέλω, έπεσ' η αυτοεκτίμησή μου εκεί που της έπρεπε ξανά (...όχι που θα μου σηκώσεις κεφάλι!).

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


Τα προκαταρκτικά. Ας είναι A ένα πεπερασμένο σύνολο και r : A \to \mathbb{N} μία συνάρτηση (υπόψιν οτι εδώ συμπεριλαμβάνω το μηδέν στους φυσικούς). Θεωρούμε το σύνολο S_A των πεπερασμένων ακολουθιών απο στοιχεία του A: για παράδειγμα, άν A = \{a, b, c\} τότε (a, a, c, b, a, b) \in S_A αλλα και () \in S_Aκενή ακολουθία). Αυτό το σύνολο μπορούμε να το περιγράψουμε επαγωγικά ξεκινώντας απ' την κενή ακολουθία και προθέτοντας στοιχεία του A:
  • () \in S_A·
  • άν a \in A και (a_1, \ldots, a_m) \in S_A τότε και (a, a_1, \ldots, a_m) \in S_A.
Είπα «πρόθέτοντας», αλλα φυσικά γίνεται να το ορίσουμε και χώνοντας κάθε νέο στοιχείο ώς επίθημα· η επιλογή να το κάνουμε με προθήματα βοηθάει στη λύση καθώς συνάδει με τον επόμενο ορισμό. Ορίζουμε λοιπόν και το σύνολο T_A ώς εξής:
  • για κάθε a \in A με r(a) = 0 είναι (a) \in T_A (η ακολουθία με μόνο στοιχείο το a
  • άν a \in A με r(a) = m και (a_{10}, a_{11}, \ldots, a_{1n_1}), \ldots, (a_{m0}, a_{m1}, \ldots, a_{mn_m}) \in T_A, τότε και (a, a_{10}, a_{11}, \ldots, a_{1n_1}, \ldots, a_{m0}, a_{m1}, \ldots, a_{mn_m}) \in T_A.
Σά να λέμε, οι ακολουθίες του T_A λαμβάνουν υπόψη τη συνάρτηση r: άν φερειπείν r(a) = 0, r(b) = 1, r(c) = 3 για το σύνολο επάνω, τότε έχουμε

() \not\in T_A, (a) \in T_A, (b) \not\in T_A, (b, a) \in T_A, (c, a, a, a) \in T_A, (c, b, a, a, b, a) \in T_A

και τα λοιπά. Βοηθάει ίσως να το μαρτυρήσουμε οτι μπορούμε να φανταστούμε αυτές τις ακολουθίες σά δέντρα: πιχί η τελευταία αντιστοιχεί στην παράσταση

\begin{array}{ccc} 
 & c & \\ 
\quad / & \mid & \backslash\quad \\ 
 b & a & b \\ 
 \mid &  & \mid \\ 
 a &  & a \\ 
\end{array}

Ίσως βέβαια και να μή βοηθάει. Εντάξει.

Τώρα, το πρόβλημα. Ισχύει T_A \subseteq S_A. Ανάποδα, ας είναι (a_0, a_1, \ldots, a_m) \in S_A μιά οποιαδήποτε περατή ακολουθία· πώς μπορούμε να μάθουμε άν (a_0, a_1, \ldots, a_m) \in T_A χρησιμοποιώντας το πολύ προσθαφαιρέσεις;

Για να το φέρω πιό πολύ σε άσκηση, να δώσω μία κατεύθυνση προς τη λύση που είχα βρεί προσωπικά. Θεωρήστε τη συνάρτηση tr: S_A \to \mathbb{Z} με
  • tr() := 1,
  • tr(a_0, a_1, \ldots, a_m) := r(a_0) + tr (a_1, \ldots, a_m) - 1,
και δείξτε ότι

(a_0, a_1, \ldots, a_m) \in T_A άν και μόνο άν tr(a_0, a_1, \ldots, a_m) = 0 και tr(a_0, \ldots, a_{m'}) > 0 για κάθε m' < m.

Κάτι που ξέχασα επάνω: για να βγάζουν όλ' αυτά νόημα, είναι καλό να απαιτήσουμε απο την r να απεικονίζει ένα τουλάχιστον στοιχείο του A στο 0.


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7751
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Επαγωγή σε δέντρα

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Φεβ 19, 2015 8:49 pm

Η επιβεβαίωση της λύσης δεν είναι τόσο δύσκολη. (Άλλη κουβέντα το πόσο δύσκολα βρέθηκε.)

Δίνω μια διαφορετική αντιμετώπιση:

Για κάθε ακολουθία (a_0,a_1,\ldots,a_m) ορίζω μια λέξη στα R,U (σκεφτείτε "RIGHT" και "UP") ως εξής: Το στοιχείο a με r(a) = k αντιστοιχεί στην λέξη

\underbrace{RR\cdots R}_{k\, R's}U.

Σε κάθε λέξη στα R,U αντιστοιχώ ένα μονοπάτι στο πλέγμα το οποίο ξεκινάει από το (0,0) και κατασκευάζεται ως εξής: Ξεκινώντας την λέξη από τα αριστερά, αν δω R πάω από το (x,y) στο (x+1,y), αν δω U πάω από το (x,y) στο (x,y+1).

Οπότε σε κάθε ακολουθία (a_0,a_1,\ldots,a_m) μπορώ να αντιστοιχίσω ένα μονοπάτι μέσω της ενδιάμεσης λέξης.

Τότε έχω το εξής: (a_0,a_1,\ldots,a_m) \in T_A αν και μόνο αν r(a_m)=0 και το μονοπάτι που αντιστοιχεί στην ακολουθία (a_0,a_1,\ldots,a_{m-1}) [Προσοχή! Σταματώ στο m-1.] ξεκινάει από το (0,0), τελειώνει στο (m,m) και δεν περνάει ποτέ πάνω από την ευθεία y=x.

Η απόδειξη είναι της ίδιας δυσκολίας με την απόδειξη της άσκησης του Σίλη (της οποίας δεν έδωσα λύση). Μάλιστα δεν είναι δύσκολο να δείξουμε ότι οι δυο συνθήκες (η δική μου και του Σίλη) είναι ισοδύναμες χωρίς να αποδείξουμε καμία από αυτές.

Ο λόγος που έγραψα αυτήν την συνθήκη είναι ο εξής: Αν η ακολουθία (a_0,\ldots,a_m) ανήκει στο T_A ή όχι εξαρτάται αποκλειστικά και μόνο από την ακολουθία (r(a_0),\ldots,r(a_m)). Για κάθε m ο αριθμός αυτών των ακολουθιών που μας κάνουν είναι ο αριθμός Catalan \displaystyle{C_m = \frac{1}{m+1}\binom{2m}{m}.} Δείτε π.χ. εδώ.


Σίλης
Δημοσιεύσεις: 64
Εγγραφή: Δευ Δεκ 01, 2014 6:50 pm

Re: Επαγωγή σε δέντρα

#3

Μη αναγνωσμένη δημοσίευση από Σίλης » Παρ Φεβ 20, 2015 11:47 am

Αριθμοί Καταλάν λοιπόν... Άρα έχουμε διάβασμα. Νά 'σαι καλά Δημήτρη, χτύπησες νεύρο.


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7751
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Επαγωγή σε δέντρα

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Φεβ 21, 2015 10:37 am

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


Απάντηση

Επιστροφή σε “ΑΝΩΤΕΡΑ ΜΑΘΗΜΑΤΙΚΑ”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης