Δίκαιη μοιρασιά

Παρασκευή, 26/04/2024 by igaviotis Επιλεγμένα

During the EU CodeWeek 2023 Hackathon award ceremony the fair division algorithms were introduced as examples of practical application of algorithms in everyday life. EU CodeWeek strives to introduce algorithmic thinking and coding in schools.

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

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

Το πρόβλημα

Τώρα που είδαμε τη λύση, ας περιγράψουμε τι προσπαθούμε να πετύχουμε. Έχουμε να διαιρέσουμε ένα αγαθό, πχ. τις τηγανητές πατάτες ή ένα κέικ. Υπάρχουν οι συνδαιτημόνες που επιθυμούν να αποκτήσουν όσο το δυνατόν περισσότερο, αλλά θα συμβιβαστούν αν μπορέσουν να αποκτήσουν τουλάχιστον το κομμάτι που τους αναλογεί. Για $n$ ανθρώπους, αυτό σημαίνει ότι μετά τη μοιρασιά, καθένας τους πρέπει να έχει την αίσθηση ότι απέκτησε για τον εαυτό του ποσότητα τουλάχιστον $1/n$ του αγαθού. Αυτή είναι η αρχή της Αναλογικότητας.

Σα να μην έφτανε αυτό, οι δικαιούχοι του αγαθού θα ήθελαν κανείς άλλος να μην πάρει κομμάτι μεγαλύτερο από το δικό τους. Δηλαδή, δεν μου αρκεί να πάρω (αυτό που κρίνω ως) δίκαιο μερτικό για πάρτη μου, αλλά δεν θέλω και κάποιος άλλος να πάρει κάτι περισσότερο από εμένα – ακόμη κι αν το στερεί από κάποιον τρίτο, γιατί θα τον ζηλεύω. Αυτή είναι η αρχή Δίχως-Φθόνο.

Ιδανικά, καθώς καταλαβαίνετε, μια δίκαιη μοιρασιά που σέβεται τις δυο αυτές αρχές θα αποδώσει ποσότητα ακριβώς $1/n$ σε όλους τους $n$ δικαιούχους.

Σημείωση: Μια μοιρασιά μπορεί να είναι αναλογική και ωστόσο φθονερή (για $n \ge 3$ ). Αντίθετα, μια μοιρασιά Δίχως-Φθόνο δεν μπορεί παρά να είναι Αναλογική.

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

Κινούμενο μαχαίρι

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

Για τις περιπτώσεις όπου $n \ge 3$ μια έξυπνη λύση είναι το ‘κινούμενο μαχαίρι‘: κάποιος τοποθετεί ένα μαχαίρι πάνω στο ένα άκρο του κέικ και αρχίζει να το κινεί αργά και σταθερά κατά μήκος του μεγαλώνοντας σταδιακά το τμήμα του κέικ που έχει προσπεράσει. Όποτε κάποιος από τους δικαιούχους θεωρήσει ότι το τμήμα είναι αρκετό, φωνάζει ‘κόψε’, και υποχρεωτικά το παίρνει. Η διαδικασία συνεχίζεται για τους υπόλοιπους. Έτσι όλοι είναι ικανοποιημένοι με το κομμάτι που πήραν – κατ’ επιλογή τους. Ακόμη κι ο τελευταίος, που δεν είπε ‘κόψε’ (θεωρώντας ότι κανένα από τα $n-1$ κομμάτια των προηγούμενων δεν ήταν αρκετά μεγάλο), πρέπει να είναι ικανοποιημένος με το εναπομείναν τμήμα του κέικ που κατά την εκτίμησή του είναι μεγαλύτερο από $1- \frac{n-1}{n}$ , δηλαδή $\frac{1}{n}$ .

Ένα κινούμενο μαχαίρι μοιράζει δίκαια το κέικ σε τρεις

Το κινούμενο μαχαίρι (Dubins και Spanier, 1961) εξασφαλίζει αναλογική μοιρασιά. Ωστόσο, ένας ζηλιάρης που έχει ήδη πάρει το κομμάτι του, κατά την περαιτέρω εξέλιξη της κατάτμησης πρέπει να απόσχει: ακόμη κι αν θεωρήσει ότι ένα κομμάτι είναι μεγαλύτερο από αυτό που έχει ήδη πάρει, δεν μπορεί να το διεκδικήσει. Άρα ο αλγόριθμος δεν εξασφαλίζει την αρχή Δίχως-Φθόνο.

Μοιρασιά στα τρία Δίχως-Φθόνο

Μπορούμε να μοιράσουμε σε τρεις καλύτερα από το κινούμενο μαχαίρι; Οι Selfridge και Conway ανακάλυψαν έναν τρόπο ήδη το 1960, αλλά δεν έκριναν ότι αξίζει να τον δημοσιεύσουν! Πάει ως εξής:

Ο Α τεμαχίζει το κέικ σε 3 ίσα, κατά την εκτίμησή του, κομμάτια.
Ο Β εκτιμά ποιο είναι μεγαλύτερο και αποκόπτει το υπερβάλλον τμήμα του, τόσο όσο να μην είναι μικρότερο από τα άλλα δύο κομμάτια.
Ο Γ επιλέγει ένα από τα τρία κομμάτια – όποιο γουστάρει.
Αν ο Γ επέλεξε το κομμάτι που μίκρυνε στο βήμα (2), τότε ο Β επιλέγει ανάμεσα στα άλλα δύο κομμάτια. Διαφορετικά, ο Β παίρνει υποχρεωτικά το κομμάτι που μίκρυνε ο ίδιος στο βήμα (2).
Ο Α παίρνει το (ακέραιο) κομμάτι που έχει απομείνει.

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

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

Δεν είναι προφανές, αλλά και σε αυτό το στάδιο η μοιρασιά είναι αναλογική και δίχως φθόνο, ακόμη και για τον παίκτη Α στο βήμα (8). Παρότι πληροί τις προδιαγραφές που θέσαμε στην αρχή, ο αλγόριθμος δεν είναι προφανής – άσε που οι παίκτες θα φάνε τρίμματα αφού το κέικ μπορεί να κοπεί σε 6 κομμάτια. Δυστυχώς, ο αλγόριθμος δεν γενικεύεται για περισσότερους από 3 ανθρώπους.

Επίλογος

Μόλις το 1995 οι Brams και Taylor κατασκεύασαν τον πρώτο αλγόριθμο για οσουσδήποτε παίκτες που είναι και Δίχως-Φθόνο. Ωστόσο, είναι πολύπλοκος και απαιτεί πολλά βήματα, π.χ. για μοίρασμα σε 4 παίκτες απαιτεί 20 βήματα. Το χειρότερο είναι ότι δεν έχει άνω φράγμα για το πλήθος των βημάτων. Ακόμη χειρότερα, το καλύτερο όριο πολυπλοκότητας που έχει βρεθεί μέχρι τώρα για το πρόβλημα της δίκαιης μοιρασιάς ανάμεσα σε $n$ παίκτες είναι, κρατηθείτε..

$n^{n^{n^{n^{n^n}}}} = n \uparrow \uparrow 6$

Ευχαριστώ, δεν θα πάρω.

Για κλείσιμο –δεν κρατιέμαι– ποιος άραγε πρότεινε τον συμβολισμό με τα πάνω βελάκια για την επαναλαμβανόμενη ύψωση σε δυνάμεις; Knuth, 1976

Αναφορές

Subhash Suri, Fair Division and Cake Cutting, February 27, 2020
Ulle Endriss, Lecture Notes on Fair Division, Institute for Logic, Language and Computation, University of Amsterdam, 7 April 2010
Fair cake-cutting – Wikipedia

Παραγοντικό και Γάμμα

Τετάρτη, 23/08/2023 by igaviotis

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

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

Ακέραιοι

Με πόσους διαφορετικούς τρόπους μπορούν να τερματίσουν 4 ποδηλάτες Α, Β, Γ, Δ; Πρώτος μπορεί να είναι καθένας από τους τέσσερις, και θα ακολουθούν οι υπόλοιποι τρεις. Έτσι αναγουμε το αρχικό ερώτημα στο ίδιο μικρότερου μεγέθους. Για 1 ποδηλάτη, υπάρχει 1 τρόπος τερματισμού· για 2 ποδηλάτες είναι 2, ΑΒ ή ΒΑ· για 3 ποδηλάτες είναι 6 οι τρόποι τερματισμού, ΑΒΓ, ΑΓΒ, ΒΑΓ, ΒΓΑ, ΓΑΒ, ΓΒΑ. Άρα για τους 4 ποδηλάτες, έχουμε 4*6 = 12 αναδιατάξεις, όπως τις λέμε στα διακριτά μαθηματικά. Για $n$ ποδηλάτες είναι τόσες αναδιατάξεις ώστε οποιοσδήποτε από τους $n$ να είναι πρώτος, ακολουθούμενος από τους υπόλοιπους $n-1$ .

Ως σύμβολο του παραγοντικού, το θαυμαστικό $n!$ πρωτοχρησιμοποιήθηκε το 1808:

$4!=4 \cdot 3! = 4 \cdot 3 \cdot 2! = 4 \cdot 3 \cdot 2 \cdot 1! = 4 \cdot 3 \cdot 2 \cdot 1 =24$

Γενικά, για τους θετικούς ακέραιους, το παραγοντικό ορίζεται

$n! = \left\{ \begin{array}{ll} n \cdot (n-1)!, & n \geq 1\\ 1, &n=0 \end{array} \right. , n \in \mathbb{N}$

και στη μη αναδρομική εκδοχή του

$n! = n \cdot (n-1) \cdot (n-2) \cdots 1 = \prod_{i=1}^{n}i$

Πραγματικοί

Θα θέλαμε να επεκτείνουμε το παραγοντικό στους πραγματικούς αριθμούς! Δηλαδή θα θέλαμε μια συνάρτηση $f(x) = x \cdot f(x-1)!$ , για κάθε $x \in \mathbb{R}$ . Όταν το $x$ τυχαίνει να είναι ακέραιος, η τιμή αυτής της συνάρτησης ιδανικά θα ταυτίζεται με το ‘κανονικό’ παραγοντικό που ορίσαμε παραπάνω.

Είναι καταπληκτικό ότι υπάρχει μια τέτοια συνάρτηση! Λέγεται συνάρτηση Γάμμα

$\Gamma(x) = \int_0^\infty {t^{x - 1} e^{ - t} dt}$

Πατέρας της $\Gamma (x)$ είναι ο Euler γύρω στα 1730, αν και βρίσκουμε ανακατεμένα στην ιστορία τα μεγάλα ονόματα, όπως Bernoulli, Goldbach, Gauss.

Υπάρχει μια ενοχλητική μετατόπιση κατά +1, αλλά ισχύει $\Gamma (n+1) = n!$ για τους θετικούς, όπως (δια)φαίνεται στο διάγραμμα Matlab

Πράγματι βλέπουμε Γ(1)=1=0!, Γ(2)=1=1!, Γ(3)=2=2!, Γ(4)=6=3!. Και αναλυτικά, για πχ $x=2$ με παραγώγιση κατά μέλη και εφαρμογή του κανόνα de l’Hôpital

$\Gamma( 2) = \int_0^\infty {t^{2 - 1} e^{ - t} dt} = \int_0^\infty {t e^{ - t} dt} = - e^{-t}(1+t)\big|_0^\infty = - \frac{t+1}{e^{t}}\big|_{0}^\infty = - \frac{1}{e^{t}}\big|_{0}^\infty = 1$

Αλλά το πιο σημαντικό είναι ότι

$\Gamma (x+1) = \int_0^\infty {t^{x} e^{ - t} dt} = -t^x e^{-t} \big|_0^\infty + x \int_0^\infty t^{x-1} e^{-t} dt = x \cdot \Gamma(x)$

υπό την προϋπόθεση ότι το $x$ είναι θετικό (για να μηδενιστεί ο πρώτος όρος του αθροίσματος).

Στις ενδιάμεσες πραγματικές μη-ακέραιες τιμές, η συνάρτηση συμπεριφέρεται φυσιολογικά (συνεχής). Το τοπικό ελάχιστο είναι στο σημείο [1.461632, 0.885603].

Μπορεί να φαίνεται ουρανοκατέβατο ότι από το ολοκλήρωμα της συνάρτησης Γάμμα προκύπτουν τιμές παραγοντικών – μια λογική και συνεπής εξήγηση στο Unraveling the Mystery Behind This Math Miracle – YouTube. Ως υπόδειξη, η νιοστή παράγωγος του μονωνύμου $x^n$ είναι

$\frac{d^n}{dx^n}(x^n) = n(n-1)(n-2) \cdots 2 \cdot 1 = n!$

Παραγοντικό αρνητικών ακεραίων

Αφού $0!=1$ και $n!=n(n-1)!$ , άρα $0! = 0 \cdot (-1)! = 1$ , δηλαδή το (-1)! πρέπει πολλαπλασιαζόμενο με το 0 να δίνει 1, που αναδίνει μια αίσθηση άπειρου. Με τους αρνητικούς ακέραιους θα πρέπει να περιμένουμε εκπλήξεις και από τη συνάρτηση Γάμμα, αφού αυτή ακολουθεί με συνέπεια τη συμπεριφορά του παραγοντικού.

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

Η συνάρτηση Γάμμα στους πραγματικούς (αρνητικούς και θετικούς)

Για παράδειγμα, στις ακέραιες αρνητικές τιμές -1, -2, .., όχι μόνο είναι ασυνεχής, αλλά πηδάει από το $-\infty$ στο $+\infty$ , ή πιο ορθά η συνάρτηση Γάμμα έχει singularities (or “simple poles”).

Πάντως η Γάμμα παραμένει πραγματική για στους πραγματικούς – θετικούς κι αρνητικούς, εκτός πόλων. Και το λέω αυτό γιατί τώρα θα προχωρήσουμε στην..

Επέκταση στους μιγαδικούς

Ας γίνουμε πιο τολμηροί. Γιατί να μην επεκτείνουμε το πεδίο ορισμού της συνάρτησης Γάμμα στους μιγαδικούς;

$\Gamma(z) = \int_0^\infty {t^{z - 1} e^{ - t} dt}, z \in \mathbb{C}$

Στα σημεία όπου $\Re(z) \in \mathbb{Z}^{-}, \Im(z)=0$ έχει τους πόλους που είδαμε παραπάνω και απεικονίζονται ξεκάθαρα στην γραφική παράσταση του μέτρου $| \Gamma(z) |$ , δηλ. της απόστασης από την αρχή των αξόνων:

Στους δύο άξονες το πραγματικό και το φανταστικό μέρος του πεδίου ορισμού και στον ‘κατακόρυφο’ άξονα το μέτρο της $\Gamma(z)$

Τιμές και τύποι της συνάρτησης Γάμμα

Για τους θετικούς ακέραιους, η συνάρτηση Γάμμα ταυτίζεται με το παραγοντικό

$\Gamma(n+1) = n!, \; n \in \mathbb{N}$

Στους μιγαδικούς ο καθοριστικός τύπος είναι

$\Gamma(z+1) = z \cdot \Gamma(z)$

Ένας εντυπωσιακός ανακλαστικός τύπος για τη συνάρτηση Γάμμα είναι

$\Gamma(z) \cdot \Gamma(1-z) = \frac{\pi}{sin(\pi z)}, \; z \notin \mathbb{Z}$

από όπου προκύπτει

$\Gamma(\frac{1}{2}) \cdot \Gamma(1-\frac{1}{2}) = (\Gamma(\frac{1}{2}))^2 = \frac{\pi}{sin(\pi / 2)} = \pi \Rightarrow \Gamma(\frac{1}{2}) = \sqrt{\pi}$

Γουστάρω που ανακακατεύονται παραγοντικό, μιγαδικοί, ολοκληρώματα και ξεπηδάνε ρίζα, τριγωνομετρική συνάρτηση και το $\pi$ .

Γενικεύοντας, για τα μισά των θετικών ακεραίων παίρνουμε κατηφορικά την αναδρομή και σταματάμε στο $\Gamma(1/2)$

= (\frac{1}{2}+n-1) \cdot \Gamma(\frac{1}{2}+n-1)

Οι τιμές αυτές αυξάνουν μονότονα απειριζόμενες, αφού το γινόμενο των $n$ μονών όρων του αριθμητή άνετα νικά το $2^n$ του παρονομαστή, και σωστά, αφού οι τιμές πρέπει να κινούνται μέσα στο $[n!, (n+1)!]$

Τώρα, τα μισά των αρνητικών ακεραίων ξεκινούν με

$\Gamma(- \frac{1}{2}) = \frac{ \Gamma(\frac{1}{2})} {- \frac{1}{2}} = -2 \sqrt{\pi}$

και κατηφορίζουν ως

$\Gamma(-\frac{1}{2}-n) = \frac{\Gamma(-\frac{1}{2} -n+1)}{-\frac{1}{2}-n} = \cdots = \frac{\Gamma(-\frac{1}{2}-n+n)}{(-\frac{1}{2}-n) \cdot (-\frac{1}{2}-n+1) \cdots (-\frac{1}{2}-n+n-1)} = \frac{\Gamma(-\frac{1}{2})}{(-1)^n \cdot \frac{2n+1}{2} \cdot \frac{2n-1}{2} \cdots \frac{3}{2}}$

που αντικαθιστώντας κάνει

$\Gamma(-\frac{1}{2}-n) = \frac{(-2)^{n+1}}{ (2n+1) \cdots 5 \cdot 3 \cdot 1} \cdot \sqrt \pi = (-1)^{n+1} \cdot \frac{2^{2n+1} \cdot n!}{(2n+1)!} \cdot \sqrt \pi$

Οι τιμές της Γάμμα για τα αρνητικά μισά εναλλάσσουν πρόσημο και τείνουν στο 0 όσο κατεβαίνουμε προς το $-\infty$ .

Ανακεφαλαιώνοντας, για τα σημεία ±X.5

Ας ψαχουλέψουμε λίγο τις μιγαδικές τιμές που παίρνει η $\Gamma(z)$ όταν το $\Im(z) \ne 0$ . Για παράδειγμα, μπορούμε να υπολογίσουμε αριθμητικά

$i! = \Gamma(i+1) = 0.49802 - 0.15495i$

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

Για αρνητικά, όχι ακέραια $\Re (z)$ , όσο το $\Im (z)$ απομακρύνεται από το 0, η συνάρτηση παίρνει μικρές τιμές, τόσο κατά το πραγματικό, όσο και κατά το φανταστικό της μέρος, ενώ ξεσαλώνει κοντά στα ακέραια πραγματικά μέρη και η κατάσταση οξύνεται όσο μικραίνει το φανταστικό μέρος.

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

Εναλλακτική μορφή

Αυτοί που έχουν αλλεργία στα ολοκληρώματα, μπορεί να εκτιμήσουν έναν εναλλακτικό τύπο για το παραγοντικό. Ο Euler τον δημοσίευσε στις 13 Οκτωβρίου 1729, αλλά επειδή δεν του άρεσε το γινόμενο, προχώρησε και βρήκε στις 8 Ιανουαρίου 1730 τον τύπο με το ολοκλήρωμα που είδαμε παραπάνω.

Σκιαγράφοντας πώς προκύπτει, από το How to Take the Factorial of Any Number – YouTube, με λογαρίθμηση του γενικευμένου παραγοντικού τα γινόμενα μετατρέπονται σε αθροίσματα και επιτρέπεται μια γραμμική προσέγγιση επειδή ο λογάριθμος έχει κόψει τη φόρα του παραγοντικού

$(x+n)! = x! \cdot (x+1)(x+2) \cdots (x+n) \Rightarrow$

$\ln((x+n)!) = \ln(x!) + \sum_{i=1}^n \ln(x+i) \approx \ln(x!) + x \ln n$

Σουτάροντας τα όρια στο άπειρο, η προσέγγιση γίνεται ισότητα

$\ln(x!) = \lim\limits_{n \to \infty}\bigl\{ \sum_{i=1}^n \ln i - \sum_{i=1}^n \ln(x+i) + x\ln n \bigl\}$

$= \lim\limits_{n \to \infty}\bigl\{ \sum_{i=1}^n \ln\frac{i}{x+i} + x \ln n \bigl\}$

Τέλος, ύψωση σε δύναμη για να ξεφορτωθούμε το λογάριθμο

$x! = \lim\limits_{n \to \infty}\bigl\{ e^{x\ln n + \sum_{i=1}^n ln \frac{i}{x+i} } \bigl\} = \lim\limits_{n \to \infty}\bigl\{n^x \cdot \prod_{i=1}^n \frac{i}{x+i} \bigl\}$

Για λόγους ιστορικής ακρίβειας, πρώτος ο Bernoulli, μία εβδομάδα νωρίτερα από τον Euler, στις 6 Οκτωβρίου 1729, είχε δημοσιεύσει έναν παρόμοιο τύπο με γινόμενο

$\lim\limits_{n \to \infty}\{(n+\frac{x}{2})^{x-1} \cdot \prod_{i=1}^{n-1}\frac{i+1}{x+i}\}$

Για το τέλος, απολαύστε μια χειροποίητη απεικόνιση του μέτρου της συνάρτησης Γάμμα από το 1909:

A hand-drawn graph of the absolute value of the complex gamma function, from Tables of Higher Functions by Jahnke and Emde.

Αντίστροφο παραγοντικό

Και ενώ το είχα κλείσει το blogpost, βγάζει ο Michael Penn το Do you know about the «reciprocal gamma function»?? – YouTube, όπου εξετάζει μια ειδική μορφή του ολοκληρώματος που χρησιμοποιείται στο μετασχηματισμό Laplace.

Το ολοκλήρωμα

$L(s) = \frac{1}{2\pi} \int_{-\infty}^{\infty}\frac{e^{1+it}}{(i+it)^s}dt$

με ολοκλήρωση κατά μέλη πάνω στην $(1+it)^{-n}$ , δίνει την αναδρομή

$L(n+1) = \frac{1}{n} L(n)$

και αφού μετά κόπων και βασάνων αποδεικνύεται $L(2)=1$ , προκύπτει ότι

$L(3)=\frac{1}{2}, L(4)=\frac{1}{3 \cdot 2}, L(5)=\frac{1}{4!}, \cdots L(n+1)= \frac{1}{n!}, \; n \in \mathbb{N}$

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

Διάγραμμα των αντίστροφων παραγοντικών και άλλες σχετικές συναρτήσεις

Calendar appointments

Δευτέρα, 08/05/2023 by igaviotis

Updated on 3/1/2024

Should you be using the Outlook calendar, this script extracts useful information about your appointments, which you can analyze to gain insight on how you spent your time by project, time period, the persons you interact most, etc.

Specifically, it scans your calendar entries and assembles the list of all your appointments.

By the way, there is a relevant article that extracts information about your Outlook mails.

For each appointment, it will accumulate a variety of properties, such as start, end, duration, subject, category, attendees, etc. There’s the full list of all properties:

AllDayEvent, AutoResolvedWinner, BillingInformation, BusyStatus, Categories, Class, Companies, ConversationIndex, ConversationTopic, CreationTime, DownloadState, Duration, End, EndInEndTimeZone, EndTimeZone, EndUTC, EntryID, ForceUpdateToAllAttendees, FormDescription, GlobalAppointmentID, Importance, InternetCodepage, IsConflict, IsRecurring, LastModificationTime, Location, MarkForDownload, MeetingStatus, MeetingWorkspaceURL, MessageClass, Mileage, NoAging, OptionalAttendees, Organizer, OutlookInternalVersion, OutlookVersion, RecurrenceState, ReminderMinutesBeforeStart, ReminderOverrideDefault, ReminderPlaySound, ReminderSet, ReminderSoundFile, ReplyTime, RequiredAttendees, Resources, ResponseRequested, ResponseStatus, Saved, Sensitivity, Size, Start, StartTimeZone, StartUTC, Subject, UnRead

The information for the appointments is stored in a Comma Separated File, ready to be fed to your Excel, or favorite data analytics tool (mine was Power BI, but now I reverted back to MS Access). A sample is shown below, where I have left visible the most important properties.

You can press Alt-F11 in Outlook to open the VBA and Insert | Module for a clean editor window. Then copy and paste the code below into an empty Outlook module. Place your cursor anywhere into the CalendarAppointments subroutine and press F5 to run it.

Option Explicit

' CalendarAppointments() gets all appointments with their detailed field properties
'                        from Outlook Calendar and saves them in a CSV file
' Code originates from http://www.GregThatcher.com
' Edited by I Gaviotis, igaviotis.wordpress.com

' Version 2023-07-06 added explanatory comments on use
' Version 2024-01-03 added explanatory comments and edited for easy read

' Paste the VBA code in an Outlook module (to open new module, Alt-F11).
' Run CalendarAppointments() by pressing F5 on its body. 
' Outputs CSV file, saved on Desktop to find easily.
' Observe results in Excel.

Public Sub CalendarAppointments()
    On Error GoTo ErrorHandler
    
    Dim objSession As Outlook.NameSpace
    Dim objAppointmentsFolder As Outlook.Folder
    Set objSession = Application.Session
    Set objAppointmentsFolder = objSession.GetDefaultFolder(olFolderCalendar)
    

    Dim strOutputFilename As String, outFile As Integer
    strOutputFilename = "CalendarAppointments.csv" 'creates file in Desktop folder
    outFile = FreeFile
    Open strOutputFilename For Output As #outFile
    
    Debug.Print "CalendarAppointments Start " & Now
    Debug.Print "Appointments will be saved in " & strOutputFilename & ".."
    
    Dim arrFields As Variant
    arrFields = Array( _
		"AllDayEvent", "AutoResolvedWinner", "BillingInformation", "BusyStatus", _
		"Categories", "Class", "Companies", "ConversationIndex", "ConversationTopic", _
		"CreationTime", "DownloadState", "Duration", "End", "EndInEndTimeZone", _
		"EndTimeZone", "EndUTC", "EntryID", "ForceUpdateToAllAttendees", _
		"FormDescription", "GlobalAppointmentID", "Importance", "InternetCodepage", _
		"IsConflict", "IsRecurring", "LastModificationTime", "Location", _
		"MarkForDownload", "MeetingStatus", "MeetingWorkspaceURL", "MessageClass", _
		"Mileage", "NoAging", "OptionalAttendees", "Organizer", "OutlookInternalVersion", _
		"OutlookVersion", "RecurrenceState", "ReminderMinutesBeforeStart", _
        "ReminderOverrideDefault", "ReminderPlaySound", "ReminderSet", _
		"ReminderSoundFile", "ReplyTime", "RequiredAttendees", "Resources", _
		"ResponseRequested", "ResponseStatus", "Saved", "Sensitivity", "Size", _
		"Start", "StartTimeZone", "StartUTC", "Subject", "UnRead")
    
    Dim strLine As String, i As Integer
    strLine = ""
    For i = LBound(arrFields) To UBound(arrFields) 'traverse array with appointments fields
        strLine = strLine & arrFields(i) & ", " 'first line of CSV contains field names
    Next i
    strLine = Left(strLine, Len(strLine) - 2)
    Print #outFile, strLine ' CSV header
    
    Dim objItem As Object
    For Each objItem In objAppointmentsFolder.Items ' for each Outlook item 
        If (objItem.Class = olAppointment) Then     ' if it is an appointment
            strLine = ""
            With objItem
                For i = LBound(arrFields) To UBound(arrFields) 'assemble all fields of one appointment
                    strLine = strLine & Sanitize(CallByName(objItem, arrFields(i), VbGet)) & ", "
                Next i
            End With
            strLine = Left(strLine, Len(strLine) - 2)
            Print #outFile, strLine
        End If
    Next objItem
    Close #outFile
    Debug.Print "CalendarAppointments End " & Now

Exiting:
    Set objSession = Nothing
    Set objAppointmentsFolder = Nothing
    Exit Sub
ErrorHandler:
    Debug.Print Err.Number, Err.Description
    Resume Exiting
End Sub

Function Sanitize(ByVal str As String) As String
  ' get rid of single & double quotes, commas, carriage returns and semicolons, to maintain intact the CSV structure
  Sanitize = Replace(Replace(Replace(Replace(Replace(Replace(str, _
             "'", " "), """", " "), ",", ""), vbCrLf, " "), vbCr, " "), ";", " ")
End Function

On your Desktop you’ll find the CalendarAppointments.csv file that you can readily open with Excel to purview the entries fields and filter / sort as needed.

For the more inclined, I would suggest to import the CSV file into MS Access (First Row Contains Field Names; if truncation occurs for RequiredAttendees or OptionalAttendees, change Short Text -> Long Text). Then query extensively, like:

SELECT Year([Start]) AS StartYear, Month([Start]) AS StartMonth, 
       Count(EntryID) AS AppointmentCount
FROM CalendarAppointments
GROUP BY Year([Start]), Month([Start])
ORDER BY Count(EntryID) DESC;

TRANSFORM Sum(Duration/60) AS DurationInHours
SELECT Month(Start) AS StartMonth
FROM CalendarAppointments
WHERE AllDayEvent="False" AND BusyStatus=2
GROUP BY Month(Start)
PIVOT Year(Start);

Note: in the query above I included only accepted appointments (BusyStatus=2); I do not follow those that I mark as tentative and Outlook deletes those declined (in newer version that changes – at last). I also excluded full day events (usually holidays, etc.); each would contribute 24 hours to duration. Originally, duration is in minutes, so dividing by 60 gets it in hours. I pivoted by year and totals are actually average monthly durations for each year, so 2023 was busier than 2022.

Count emails in Outlook

Παρασκευή, 20/01/2023 by igaviotis

In my former jobs, I spent some time trying to come up with productivity figures. Some years ago, I was working for a shipyard company and workers were assigned tasks on ship repairs. Their working time was recorded (entry – exit from the yard) to be used for their wages. Their supervisors also recorded the time on tasks carried out on the ships or, for example, when they were just standing by because there was no (productive) task to carry out. Taking into consideration hourly pay, insurance costs, indirect costs, etc, we could analytically (not statistically) compute the actual cost of the ship’s repair work, which was then subtracted from the invoiced amount to the ship-owner, leaving the net profit for the yard. Straightforward, eh?

How could someone do some analogous calculation (not estimation) for office work? How could an office worker find out whether he worked more or less for a specific month?

Nowadays, more and more office work is carried out by exchanging email messages. I thought, let’s experiment with this and see where it leads.

The basic idea

I would need to count the email messages exchanged daily. With those arriving in my Inbox, I need to spend some time to have an initial look at them. Some of them, I delete immediately. Some of them need my attention, so I need to carefully read them and, out of those, for some I need to carry out some work and reply back.

So, I need to count all incoming emails grouped by day, which is tedious to do, because at the end of the day, some of them are placed in the Deleted Emails and the rest are stacked in sub-folders.

Calendar appointments may also be of interest to you: instead on collecting email info, that collects calendar info.

I also need to count the Sent emails, because they require extra effort to be carried out and some time to write them.

So, I will use these two figures as KPIs for my job done. Other interesting info is further found, such as high/low volume time of day.

The implementation

A VBA script runs inside Outlook and collects all the necessary information about the emails, without me needing to count them.

The outputs of this scripts, which are CSV files, you can analyze them using some spreadsheet or database application to get useful results. I chose to use Microsoft Power BI, because it is easy to update its input datasets, it has some fancy visualizations, and offers handy slicing (filtering).

From time to time, you need to re-run the VBA script to get fresher mail counts for the most recent dates. In my case, the mail retention policy for the Deleted Items is 6 months, so after that period the older, deleted emails will disappear, therefore only the last 6 months mail counts are valid (in my case). After updating the CSV files, you Refresh the data sources in Power BI to see the statistics.

Step 1 Producing the data

At the end of this page, you will find The EmailCount VBA source code, which you can Copy as text. While in Outlook, you press Alt-F11 to open the Microsoft Visual Basic for Applications environment. You insert a new Module and inside you Paste the copied code.

Before running it, you need to change lines 17-18, where you should edit with your own email address.

Then place your cursor somewhere in the body of the EmailCount() subroutine and press Run (the green arrow in the menu).

This will create two files, prefixed by the current date, on your Desktop:

CountMails.csv gives the total count of emails, sent & received, for each day

LogMails.csv contains lines for each email found in all Outlook folders. Columns hold the datetime of the email, the folder the mail is currently placed in, 0 if it is an incoming email or -1 if it is a Sent Item.

BTW, the VBA code also logs some informative facts in the Immediate window (press Ctrl-G to open) in the environment. It will also report if something goes wrong, so you’d better have a look at it, before proceeding with the data in the CSV files.

Step 2 Getting the information

Ok, now that the raw data is in place, let’s deduce useful information out of them. I will sketch my approach using Power BI, but you can get similar outputs with Excel, Access, or whichever tool you are familiar with.

Step 2a Ingesting data

Files with Comma Separated Values are easily handled by any spreadsheet application. I fed them into Power BI promoting the first line in header and changing dates to the proper data type. I even added a computed column ReceivedHour = Format([ReceivedOn],"hh").

Step 2b Reporting

For reporting you can select the data to drill into by year and month.

I created some charts, which may seem a bit dull, but the nice part is that they respond to slicing, justto get the idea.

November 2022 was by far the worst month.

One can do nice things with the collected data. A next project I have in mind is to collect the appointments data from Outlook calendar and report the time spent in meetings. One can also combine email and calendar data to calculate interesting work KPIs.

Enjoy and let me know how much you torture your mail servers!

The EmailCount VBA source code

 

Option Explicit

' EmailCount() scans Outlook folders counting how many email messages were sent/received every day.
' The daily email count is then stored as a CSV file at your Desktop.
' Moreover, a log file contains for every message the sent timestamp, folder stored and if the message was sent.

' Version 2022-12-19 minor changes in Debug.Print
'         2022-12-05 running ok, producing CSV file at Desktop which is fed to Power BI for analysis.
'         2022-12-08 added second email


' When run at work, keep in mind that the detention policy for the Deleted folder is 183 days (6 months).

' To reset policy and allow the script to run, just delete file C:\Users\XXXusernameXXX\AppData\Roaming\Microsoft\Outlook\VbaProject.OTM
' and copy in a new module the script code. Otherwise, message "The macros in this project are disabled..." appears.

Const cstrMyEmail = "XXXgaviotisXXX@Xmail.com"  ' to find the emails that I sent
Const cstrMyEmail2 = "YYYgaviotisYYY@Ymail.com" ' an alternative email																											

Dim objDictionary As Object ' the data structure to store the collected data
Dim objLogFile As Object    ' the handle for the log file
    
Private Sub EmailCount()
On Error GoTo ErrorHandler

'traverses all mail in default mail account and outputs info in CSV files at desktop folder

    Dim objOutlookApplication As Object
    Dim objNameSpace As Object
    Debug.Print "EmailCount Start " & Now
    Set objOutlookApplication = CreateObject("Outlook.Application")
    Set objNameSpace = objOutlookApplication.GetNamespace("MAPI")
    
    Dim objFolder As Object
    ' Set objFolder = Application.ActiveExplorer.CurrentFolder ' This option allows to select a folder and count in it al all its subfolders'
    Set objFolder = objNameSpace.GetDefaultFolder(olFolderInbox).Parent ' This option gets all current mailbox folders
    
    Set objDictionary = CreateObject("Scripting.Dictionary") ' global variable to be accessible by the recursive routine
    
    Dim strLogFilename As String ' the filename where useful email data are logged
    strLogFilename = GetDesktop & "\" & cstrMyEmail & " " & GetDate(Now) & " LogMails.csv" ' You may change the log folder and filename here
    Dim fso As Object
    Set fso = CreateObject("Scripting.FileSystemObject")
    Set objLogFile = fso.CreateTextFile(strLogFilename) ' global var to be accessible by the recursive routine
    objLogFile.WriteLine "ReceivedOn;InFolder;SentByMe" 'header of log file

    Call ProcessCurrentFolder(objFolder)
    
    Dim strOutputFilename As String
 
    strOutputFilename = GetDesktop & "\" & cstrMyEmail & " " & GetDate(Now) & " CountEmails.csv" ' You may change the output folder and filename here
    
    Call OutputResult(strOutputFilename)
    
    objLogFile.Close: Set fso = Nothing: Set objLogFile = Nothing ' log file garbage
    Set objDictionary = Nothing
    Set objFolder = Nothing
    Set objNameSpace = Nothing
    Set objOutlookApplication = Nothing
    Debug.Print "EmailCount End " & Now
    Exit Sub

ErrorHandler:
    Debug.Print Err.Number, Err.Description
    Resume Next
End Sub
 
Private Sub ProcessCurrentFolder(ByVal objFolder As Outlook.MAPIFolder)
On Error GoTo ErrorHandler

    ' process emails in the folder
    Dim intEmailCount As Integer
    intEmailCount = 0
    Debug.Print "Folder: " & objFolder & " Items: " & objFolder.Items.Count;
        
    ' When new items are created in the Contacts folder or the Recipient Cache folder (a hidden folder under the Contacts folder), related items are created in the PersonMetadata folder.
    If objFolder = "PersonMetadata" Then
        Debug.Print " SKIPPED" ' ignore this folder - it contains garbage anyways
        Exit Sub
    End If
        
    Dim objItem As Object, objItems As Outlook.Items
    Set objItems = objFolder.Items
    ' The SetColumns method is useful for iterating through an Items collection. If you don't use this method, Microsoft Outlook must open each item to access the property.
    ' With the SetColumns method, Outlook only checks the properties that you have cached, and provides fast, read-only access to these properties.
    ' objItems.SetColumns ("ReceivedTime")
    
    Dim strDate As String
    For Each objItem In objItems
        If TypeName(objItem) = "MailItem" Then
         intEmailCount = intEmailCount + 1
            strDate = GetDate(objItem.ReceivedTime)
            
            If Not objDictionary.Exists(strDate) Then
                objDictionary(strDate) = 0
            End If
            objDictionary(strDate) = CLng(objDictionary(strDate)) + 1
            
            objLogFile.WriteLine objItem.ReceivedTime & "; " & objFolder & "; " & _
                IIf(objItem.SenderEmailAddress = cstrMyEmail Or objItem.SenderEmailAddress = cstrMyEmail2, vbTrue, vbFalse)
        End If
    Next objItem
    Debug.Print " Mails:" & intEmailCount
    
    ' process subfolders in the folder recursively
    Dim objCurFolder As Outlook.MAPIFolder
    If (objFolder.Folders.Count > 0) Then
        For Each objCurFolder In objFolder.Folders
            Call ProcessCurrentFolder(objCurFolder)
        Next objCurFolder
    End If
    Exit Sub

ErrorHandler:
    Debug.Print Err.Number, Err.Description
    Resume Next
End Sub

Function OutputResult(ByVal strFileName As String) As String
    Dim strMessage As String
    Dim varKey As Variant
    
    Dim fso As Object
    Set fso = CreateObject("Scripting.FileSystemObject")
    Dim oFile As Object
    Set oFile = fso.CreateTextFile(strFileName)
    
    oFile.WriteLine "ReceivedDate;EmailCount" 'header
    For Each varKey In objDictionary.Keys
        oFile.WriteLine varKey & "; " & objDictionary(varKey)
    Next
    
    oFile.Close
    Set fso = Nothing
    Set oFile = Nothing
End Function

Function GetDate(dt As Date) As String
    GetDate = Year(dt) & "-" & Format(Month(dt), "00") & "-" & Format(Day(dt), "00") 'just the date
End Function

Function GetDesktop() As String
    Dim oWSHShell As Object
    Set oWSHShell = CreateObject("WScript.Shell")
    GetDesktop = oWSHShell.SpecialFolders("Desktop")
    Set oWSHShell = Nothing
End Function

Παπούτσια στη σειρά

Πέμπτη, 08/04/2021 by igaviotis

Γιατί άραγε χρειάζεται τόση προσπάθεια για να κρατηθεί το σπίτι σε τάξη; Αυτό το θεμελιώδες ζήτημα με απασχόλησε στο «Καπάκι της οδοντόπαστας» και το προσεγγίζω κι εδώ με ένα άλλο παράδειγμα.

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

Ερώτημα

Έχετε τρία διαφορετικά ζευγάρια παπούτσια. Ποια είναι η πιθανότητα να είναι σωστά τοποθετημένα στη σειρά (δηλαδή αριστερό-δεξί πλάι-πλάι);

Απάντηση

Όλα τα ζευγάρια είναι διαφορετικά και τα δυο παπούτσια του ίδιου ζευγαριού είναι αριστερό και δεξί, άρα διαφορετικά μεταξύ τους. Άρα έχουμε 6 διαφορετικά παπούτσια και υπάρχουν $6!=6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1=720$ δυνατοί τρόποι τοποθέτησής τους (αναδιατάξεις). Σε αυτούς τους τυχαίους τρόπους διάταξης, στους περισσότερους τα παπούτσια είναι ανακατωμένα.

Ας μετρήσουμε σε ποιες διατάξεις είναι τακτοποιημένα σωστά τα παπούτσια: πρέπει να είναι αριστερά το αριστερό παπούτσι και δεξιά το δεξί του ίδιου ζευγαριού. Επειδή έχουμε 3 ζευγάρια παπούτσια και δεν έχει σημασία η σειρά των ζευγαριών μεταξύ τους, υπάρχουν $3!=3 \cdot 2 \cdot 1$ διατάξεις ζευγαριών.

Άρα η πιθανότητα να είναι τακτοποιημένα τα παπούτσια είναι $3!/6!= 6/720=1/120=0,0083$ , δηλαδή λίγο κάτω από 1%. Γι αυτό αν δεν τακτοποιήσω εγώ τα παπούτσια στη σειρά, μόνο 3 φορές το χρόνο θα είναι τακτοποιημένα από μόνα τους κατά τύχη.

Γενίκευση

Στη γενική περίπτωση που έχω $n$ ζευγάρια παπούτσια, η πιθανότητα να είναι στη σειρά είναι $n!/(2n)!$ Ο πίνακας δείχνει ότι οι πιθανότητες για αυτούς που έχουν μεγάλη παπουτσοθήκη είναι απογοητευτικές..

Πίνακας για $1,2, \cdots , n$ ζευγάρια παπουτσιών

Πρόγραμμα

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

import itertools, random
def sostaTopothetimena(stiSeira):
  for i in range(0, len(stiSeira), 2):
    enaPap, dyoPap = stiSeira[i], stiSeira[i+1]
    if not ((enaPap[0] == dyoPap[0]) and (enaPap[1] == 'Αριστερό') and (dyoPap[1] == 'Δεξί')):
      return False
    #print(stiSeira)
  return True

zevgariaPapoutsia = {'Αθλητικά', 'Μπότες', 'Μοκασίνι', 'Πέδιλα'}
zevgari = {'Αριστερό', 'Δεξί'}
papoutsia = list(itertools.product(zevgariaPapoutsia, zevgari))
sosta = 0
epanal = 1000000
for j in range(1, epanal):
  random.shuffle(papoutsia)
  if sostaTopothetimena(papoutsia):
    sosta += 1
print("Σχετική συχνότητα σωστών", sosta / epanal)

Ορίζω σε ένα σύνολο zevgariPapoutsia που έχω. Χρησιμοποιώ Python set για να επιβάλλω ότι όλα τα ζευγάρια είναι διαφορετικά, όπως στα κανονικά μαθηματικά σύνολα. Έτσι αν βάλεις δυο ίδια ζευγάρια ‘Αθλητικά’ θα τα αποθηκεύσει (ορθώς) μια φορά, διότι τα σύνολα δεν επιτρέπουν διπλότυπα στοιχεία. Θα μπορούσα να χρησιμοποιήσω εναλλακτικά Python list, αλλά δεν μου αρέσει γιατί στην επόμενη γραμμή παίρνω το καρτεσιανό γινόμενο των δυο συνόλων zevgariaPapoutsia και zevgari και κανονικά το καρτεσιανό γινόμενο εφαρμόζεται επί συνόλων, άσχετα πως στην Python θα μπορούσαν να είναι και λίστες. Το αποτέλεσμα της μεθόδου itertools.product το αποθηκεύω στη λίστα papoutsia και όχι σε σύνολο, διότι θέλω να την αναδιατάσσω και τα μαθηματικά σύνολα δεν ενέχουν διάταξη. Ορθώς η Python μπορεί να κάνει random.shuffle() σε list αλλά όχι σε set.

Μετά επαναλαμβάνω το πείραμα ένα εκατομμύριο φορές ώστε τα (στατιστικά) αποτελέσματά του να τείνουν προς το αναμενόμενο αποτέλεσμα (Νόμος των μεγάλων αριθμών).

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

Μια εκτέλεση του παραπάνω κώδικα για τέσσερα ζευγάρια παπούτσια δίνει:

Σχετική συχνότητα σωστών 0.000601

ή 0.0601% που είναι αρκετά κοντά στο αποτέλεσμα του παραπάνω πίνακα.

Διερεύνηση

Η πιθανότητα να είναι σωστά τοποθετημένα $n$ ζευγάρια παπουτσιών στη σειρά είναι

\frac{n!}{(2n)!} — Λίγες πράξεις δεν βλάπτουν..

= \frac{n!}{1 \cdot 2 \cdot 3 \dotsb (n-1) \cdot n \cdot (n+1) \dotsb (2n-1) \cdot(2n)} — Λίγες πράξεις δεν βλάπτουν..

Παραλλαγή

Αν μπαίνοντας στο σπίτι πετάω πιο προσεκτικά τα παπούτσια μου στην παπουτσοθήκη έτσι ώστε τα δυο παπούτσια του κάθε ζευγαριού να παραμένουν δίπλα-δίπλα, τότε αρκεί το αριστερό να είναι αριστερά και το δεξί να είναι δεξιά και τότε όλα τα ζευγάρια της παπουτσοθήκης θα είναι τακτοποιημένα. Ξεκάθαρα, η πιθανότητα να είναι τακτοποιημένο ένα ζευγάρι είναι $P(Z)=1/2$ (δηλαδή αριστερό-δεξί και όχι δεξί-αριστερό).

Άρα υπό την προϋπόθεση ότι τα παπούτσια κάθε ζευγαριού παραμένουν δίπλα-δίπλα, για να είναι τακτοποιημένη η παπουτσοθήκη μου, αρκεί καθένα από τα $n$ ζευγάρια να έχει το αριστερό του παπούτσι αριστερά και το δεξί δεξιά. Μιας και η διάταξη του κάθε ζευγαριού είναι ανεξάρτητη από τη διάταξη όλων των υπόλοιπων,

$P(Z_1 \cap Z_2 \cap \cdots \cap Z_n) =P(Z_1) \cdot P(Z_2) \dots P(Z_n) = \frac{1}{2^n}$

Έτσι για 3 ζευγάρια παπούτσια, αν τα παρατάω κάπως προσεκτικά, η παπουτσοθήκη θα είναι τακτοποιημένη με πιθανότητα $\frac{1}{2^3}=\frac{1}{8}=12,5\%$ , ενώ στην ορίτζιναλ εκδοχή η πιθανότητα ήταν $\frac{1}{120} =0,8\overline{3}\%$ . Με λίγη προσοχή βέλτιωσα τις πιθανότητες κατά $1 \cdot 3 \cdot 5 = 15$ φορές, ή στη γενική περίπτωση κατά $1 \cdot 3 \cdot 5 \dotsb (2n-1)$ φορές.

Το πρότυπο Παρατηρητής (Observer pattern)

Δευτέρα, 25/01/2021 by igaviotis

Το πρότυπο Παρατηρητής (Observer pattern ονομάστηκε στη Smalltalk τη δεκαετία του 80) εφαρμόζεται όταν ένα συμβάν, π.χ. μια αλλαγή στην κατάσταση μιας οντότητας, επιβάλει την εκτέλεση κάποιας ενέργειας από τα αντικείμενα που έχουν εγγραφεί συνδρομητές. Παράβαλε με μια συνδρομητική υπηρεσία, όπως τη διανομή ενός περιοδικού: όποτε εκδίδεται νέο τεύχος, αποστέλλεται σε όλους τους συνδρομητές…

Ένα σενάριο-παράδειγμα υλοποιείται σε διάφορες εκδόσεις:

Ορίζονται οι κλάσεις που αναπαριστούν τις οντότητες, τα χαρακτηριστικά και τις λειτουργίες τους και με απλοϊκό τρόπο ενημερώνονται όλες οι οθόνες μετά από κάθε αλλαγή.
Εφαρμόζει τη βασική ιδέα του προτύπου Παρατηρητής πάνω στον κώδικα του (1)
Μια πιο «καθαρή» προσέγγιση που δεν έχει τόσο γενική εφαρμογή όπως η (2)
Μια βελτιστοποιημένη και πιο γενική προσέγγιση που αναπόφευκτα είναι πιο περίπλοκη

Όλες οι εκδόσεις είναι πλήρως λειτουργικές και (υπερ)καλύπτουν το σενάριο του προβλήματος.

Η αναφορά είναι 6 σελίδες και περιλαμβάνει και τον κώδικα.

Σκέτος ο κώδικας για να τον δοκιμάσεις περιέχεται σε 4 φακέλους.

Παιχνίδια στο Powerpoint

Παρασκευή, 17/04/2020 by igaviotis

Αυτή την εποχή αρκετοί δάσκαλοι πήραν την πρωτοβουλία να φτιάξουν εκπαιδευτικό υλικό με τη μορφή παρουσιάσεων ή απλών παιχνιδιών χρησιμοποιώντας το PowerPoint.

Ψάχνοντας γύρω-γύρω βρήκα το παιχνίδι ‘Κρεμάλα’ ως παρουσίαση PPTX, δίχως κώδικα. Είναι τραγικά εκνευριστικό και δύσκολο να το φτιάξεις, άσε που είχε και σφάλματα.

Προκύπτει ότι ακόμη και το απλούστερο παιχνίδι να θέλεις να φτιάξεις, από τη στιγμή που θα χρειαστεί να επιδεικνύει κάποια ‘συμπεριφορά’ ανάλογα με τις ενέργειες / επιλογές του μαθητή, ΔΕΝ επαρκεί μια απλή παρουσίαση του PowerPoint και χρειάζεται κώδικας VBA. Αυτό (δυστυχώς) δεν είναι απλό για τον τυπικό χρήστη του PowerPoint.

Σε αυτή την ανάρτηση έχω μια προσπάθεια για ένα απλό παιχνίδι λέξεων που ξεκίνησε η Ράνια ως παρουσίαση του PowerPoint. Σε αυτήν συμπεριέλαβα κώδικα που έχει τις απαραίτητες εντολές και μπορεί εύκολα να προσαρμοστεί, δίχως γνώσεις προγραμματισμού. Είναι ένα αρχείο του PowerPoint με κατάληξη PPTM, καθώς περιέχει κώδικα VBA.

Μπορείς να το κατεβάσεις, να το δεις και να το δοκιμάσεις ή να το προσαρμόσεις με δικές σου λέξεις.

Προϋποθέτει ότι θα έχεις κάνει από τα μενού του PowerPoint: Αρχείο | Επιλογές | Κέντρο Αξιοπιστίας | Ρυθμίσεις Κέντρου Αξιοπιστίας | Ενεργοποίηση όλων των μακροεντολών.

Οδηγίες για προσαρμογή

Μπορείς να διαμορφώσεις τους ήχους και τις κινήσεις των υπαρχόντων γραμμάτων.
Το αρχείο περιέχει αρχικά 1 διαφάνεια. Αν θέλεις κι άλλες διαφάνειες, μπορείς να αντιγράψεις τη μοναδική διαφάνεια, να επικολλήσεις και να τροποποιήσεις τις κόπιες της (μέχρι 4).
Μην χρησιμοποιείς τονισμένα γράμματα.
Αν χρειάζονται και άλλα (ίδια) γράμματα, όπως τα 3 ‘α’ στο πρώτο παιχνίδι με την κατσαρόλα, μπορείς να κάνεις αντιγραφή & επικόλληση από τα υπάρχοντα γράμματα.
Με Alt + F11 μπαίνεις στον κώδικα και στις γραμμές 24-27 γράφεις για κάθε διαφάνεια:
1. τις λάθος απαντήσεις που επιτρέπονται, π.χ. για τη δεύτερη διαφάνεια apotyxies(2)=7, κ.ο.κ
2. τη σωστή απάντηση, π.χ. sostes_lexeis(2) = "παραθρο" , αν στους μαθητές έχεις δώσει το ‘υ’ και ψάχνουν να βρουν τα υπόλοιπα γράμματα της λέξης «παραθυρο».
Αν δεν σου φτάνουν 5 διαφάνειες στον κώδικα διορθώσεις στη γραμμή 5 το πλήθος των διαφανειών.

Παρατηρήσεις

Τα παρακάτω χρειάζεται να τα ξέρει ο προγραμματιστής – δεν χρειάζονται για την προσαρμογή των λέξεων από το δάσκαλο.

Για να εκτελείται ο κώδικας VBA πρέπει να υπάρχει σε μια διαφάνεια, ένα (οποιοδήποτε) στοιχείο ελέγχου! Εχω βάλει ένα στην πρώτη διαφάνεια (στο κέντρο κάτω). Θα μπορούσε και να είναι κρυφό, αλλά το άφησα έτσι για να (μισο)φαίνεται.
Το τρέχον μοντέλο συμβάντων του PowerPoint απαιτεί μια κλάση και την κατασκευή ενός αντικειμένου της εφαρμογής που είναι πιο μεγάλη και δυσνόητη. Έτσι κατέφυγα στην παλιά, μη αντικειμενοστραφή προσέγγιση.

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

Παραθέτω χύμα τον κώδικα που χρειάστηκε για το παράδειγμα με τις λέξεις για να δείτε πόσο δύσκολο / άσχημο / μη προφανές είναι:

Option Explicit
'Αν κατι παει στραβα στην εκτελεση μιας ρουτινας, απλως κρεμαει χωρις καποιο μηνυμα
Const myDEBUG As Boolean = False 'ο debugger της VBA στο PowerPoint δεν δουλευει

Const diafaneies As Integer = 5 'ΑΛΛΑΞΕ

Dim sostes_lexeis(diafaneies) As String
Dim apotyxies(diafaneies) As Integer

Dim diafaneia As Integer    'αριθμος τρεχουσας διαφανειας
Dim apotyxia As Integer     'ποσες αποτυχιες επιτρεπονται στην τρεχουσα διαφανεια
Dim sosti_lexi As String    'η λεξη που ψαχνεις στη διαφανεια αυτη
Dim exei_meinei As String   'τι εχει απομεινει που δεν βρηκες
Dim prospatheies As Integer 'ποσες προσπαθειες εκανες στην τρεχουσα διαφανεια
Dim lathi As Integer        'ποσα λαθος γραμματα εχεις επιλεξει στην τρεχουσα διαφανεια
Dim kerdises As Boolean     'αν κερδισες το παιχνιδι
Dim exases As Boolean       'αν εχασες το παιχνιδι
Dim strDebLin As String     'πληροφοριακη γραμμή

Sub Arxikopoiisi()
  'οι αποτυχιες που επιτρεπονται μεχρι να σταματησει το παιχνιδι
                    'τα γράμματα της λέξης που ψάχνεις να βρεις σε καθε διαφανεια
  apotyxies(1) = 6: sostes_lexeis(1) = "ατσαρολα" 'ΑΛΛΑΞΕ
  apotyxies(2) = 6: sostes_lexeis(2) = ""         'ΑΛΛΑΞΕ
  apotyxies(3) = 6: sostes_lexeis(3) = ""         'ΑΛΛΑΞΕ
  apotyxies(4) = 6: sostes_lexeis(4) = ""         'ΑΛΛΑΞΕ
  apotyxies(5) = 6: sostes_lexeis(5) = ""         'ΑΛΛΑΞΕ

End Sub

Sub OnSlideShowPageChange()
  diafaneia = ActivePresentation.SlideShowWindow.View.CurrentShowPosition
  If diafaneia = 1 Then Arxikopoiisi
  'μολις μπαινεις σε κάθε διαφανεια
  apotyxia = apotyxies(diafaneia)
  sosti_lexi = sostes_lexeis(diafaneia)
  exei_meinei = sosti_lexi
  prospatheies = 0
  lathi = 0
  kerdises = False
  exases = False
  ActivePresentation.Slides(diafaneia).Shapes("Κέρδισες").Visible = False
  ActivePresentation.Slides(diafaneia).Shapes("Εχασες").Visible = False
  ActivePresentation.Slides(diafaneia).Shapes("DebLin").Visible = myDEBUG

  'Επαναφορα διαφανειας
  ActivePresentation.Slides(diafaneia).Shapes("Προσπάθειες").TextFrame.TextRange.Characters.Text = prospatheies &amp; " προσπάθειες"
  ActivePresentation.Slides(diafaneia).Shapes("DebLin").TextFrame.TextRange.Characters.Text = "Διαφάνεια:" &amp; diafaneia
  If Not myDEBUG Then ActivePresentation.Saved = True 'μην αποθηκευεις
End Sub

Sub kane(oSh As Shape) 'οταν πατιεται ενα γραμμα
  Dim gramma As String, thesi As Integer, i As Integer, epityxia As Boolean
  gramma = oSh.TextFrame.TextRange.Characters.Text
  thesi = InStr(exei_meinei, gramma)
  If thesi  0 Then
    Mid(exei_meinei, thesi, 1) = "#"
    epityxia = True
  Else
    lathi = lathi + 1
    epityxia = False
  End If
  prospatheies = prospatheies + 1
  kerdises = (exei_meinei = String(Len(sosti_lexi), "#"))
  exases = (lathi &gt;= apotyxia)

  ActivePresentation.Slides(diafaneia).Shapes("Προσπάθειες").TextFrame.TextRange.Characters.Text = prospatheies &amp; " προσπάθειες"
  If kerdises Then
    ActivePresentation.Slides(diafaneia).Shapes("Κέρδισες").Visible = True
  End If
  If exases Then
    ActivePresentation.Slides(diafaneia).Shapes("Εχασες").Visible = True
  End If

  strDebLin = " Διαφάνεια:" &amp; diafaneia &amp; " Σωστή λέξη:" &amp; sosti_lexi &amp; " Απομένει:" &amp; exei_meinei &amp; _
              " Γράμμα:" &amp; gramma &amp; " Θέση:" &amp; thesi &amp; " Επιτυχία:" &amp; epityxia &amp; _
              " Προσπάθειες:" &amp; prospatheies &amp; " Λάθη:" &amp; lathi &amp; " Νίκη:" &amp; kerdises &amp; " Ήττα:" &amp; exases
  ActivePresentation.Slides(diafaneia).Shapes("DebLin").TextFrame.TextRange.Characters.Text = strDebLin
  If Not myDEBUG Then ActivePresentation.Saved = True 'μην αποθηκευεις
End Sub
<span id="mce_SELREST_start" style="overflow:hidden;line-height:0;"></span>

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

Ανάπτυξη web apps με Django

Τετάρτη, 15/04/2020 by igaviotis

Θέλουμε να δούμε μια λύση που διαχειρίζεται όγκο δεδομένων (data-intensive) και λειτουργεί στο Διαδίκτυο, γιατί στην πλειοψηφία των επιχειρησιακών σεναρίων τέτοιες λύσεις χρειάζονται. Μια λύση που αποτελεί μετεξέλιξη της κλασικής client-server αρχιτεκτονικής που έχει ένα database server στο πίσω μέρος και μια front-end εφαρμογή που εκτελείται στο PC απλωμένη σε ένα τοπικό δίκτυο.

Το Django είναι ένα δημοφιλές framework που βοηθάει στην υλοποίηση ενός τέτοιου σεναρίου. Α, και δεν περιλαμβάνει JavaScript (σπυράκια και καντήλες).

Στο Ανάπτυξη Web apps με Django θα υλοποιήσουμε μια απλή λύση, που μέσω ιστοσελίδων δυναμικού περιεχομένου ο χρήστης σε περιβάλλον web θα αλληλεπιδρά με τη βάση δεδομένων. Για να καταλάβετε τι γίνεται, θα φτάσουμε εκεί μετά από δυο παραδείγματα, τα κλασικά «Γεια σου κόσμε» και «1+1 κάνει 2».

Θα εκτιμήσω απερίγραπτα αν επικοινωνήσετε στο igaviotis@gmail.com για να κρίνετε το παρόν κείμενο για σφάλματα, παραλείψεις, νοητικά άλματα, δυσνόητα σημεία που χρήζουν αναλυτικότερης εξήγησης, υπερβολές, κακές διατυπώσεις, εμπειρίες από τη χρήση του κειμένου για να μάθετε Django. Εκτιμώνται ιδιαίτερα τα αρνητικά σχόλια.

Εισαγωγή στην Python για προγραμματιστές

Πέμπτη, 19/03/2020 by igaviotis

Είναι της μόδας (καλά, και η Java ήταν πριν είκοσι χρόνια..).

Είναι όμορφη και απλή (και αργή, αλλά who cares).

Εντάξει, είναι καλύτερη από την (εξαποδώ) JavaScript (σιγά, και ποια γλώσσα δεν θα ήταν καλύτερη;) για web programming (Django, Flask).

Εδώ έχουμε μια συνοπτική εισαγωγή στη γλώσσα. Μετά πετάξου στα γρήγορα στην Ανάπτυξη web apps με Django για τα περαιτέρω.

Είμαι μεγάλος για Arduino;

Δευτέρα, 23/04/2018 by igaviotis

Μάλλον. Πάντως με υπερηφάνεια παρουσιάζω ένα ηλεκτρονικό κύκλωμα που συναρμολόγησα. Είναι άχρηστο, αλλά who cares.

Αποτελείται από έναν αισθητήρα φωτός (photo-resistor), μια φωτοδίοδο (LED) και ένα μεγαφωνάκι (buzzer).

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

Αν η τιμή της είναι πάνω από ένα κατώφλι, ανάβει το ενδεικτικό LED, αλλιώς το σβήνει.

Για λόγους debugging η τιμή αυτή τυπώνεται στη σειριακή έξοδο.

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

Ακολουθεί ο κώδικας, περίπου C στη σύνταξη. Η συνάρτηση setup() εκτελείται άπαξ με την ενεργοποίηση του κυκλώματος και η συνάρτηση loop() συνέχεια εφεξής.

int inPin = A0; //εδώ συνδέεται ο αισθητήρας φωτός
int sensorVal = 0; //ένδειξη του αισθητήρα 0->σκοτάδι, 1023->φως
int outPin = 13; //εδώ συνδέεται το ενδεικτικό LED
int loudPin = 8;

int sensorPin = A0; //εδώ συνδέεται ο αισθητήρας φωτός
int ledPin = 13; //εδώ συνδέεται το ενδεικτικό LED
int loudPin = 8; //εδώ συνδέεται το buzzer

int sensorVal; //για την ένδειξη του αισθητήρα 0->σκοτάδι, 1023->φως

void setup() {
  pinMode(sensorPin, INPUT); //είσοδος από αισθητήρα
  pinMode(ledPin, OUTPUT); //έξοδος για LED
  pinMode(loudPin, OUTPUT); //έξοδος για buzzer
  Serial.begin(9600); //για την σειριακή έξοδο
}

void loop() {
  sensorVal = analogRead(sensorPin); //διάβασμα της τιμής του αισθητήρα
  if (sensorVal > 500) { //τιμή κατώφλι - αυθαίρετη
    digitalWrite(ledPin, HIGH); //άναψε LED
  } else {
    digitalWrite(ledPin, LOW); //σβήσε LED
  }

  Serial.println(sensorVal); //τύπωνε την τιμή
  tone(loudPin, sensorVal); //παίξε ήχο με τη συχνότητα
}

Αριστούργημα, ε;

Πλάκα-πλάκα, η πλατφόρμα Arduino είναι ένα έξυπνο, ενδιαφέρον και χρήσιμο παιχνίδι, γιατί συνδυάζει φυσική (φυσικά μεγέθη, μονάδες μέτρησης), ηλεκτρονικά (κυκλώματα) και προγραμματισμό με εποπτικό τρόπο. Είναι οικονομικό (€19), δεν χαλάει, δεν είναι επικίνδυνο (5V) και άρεσε στην Ελπίδα (12 ετών).

$n \in \mathbb{N}$	$-\infty$	$-\frac{1}{2}-n$	$-1/2$	$1/2$	$\frac{1}{2}+n$	$\infty$
$\Gamma(n)$	$0$	$(-1)^{n+1} \cdot \frac{2^{2n+1} \cdot n!}{(2n+1)!} \cdot \sqrt \pi$	$-2 \sqrt \pi$	$\sqrt \pi$	$\frac{(2n)!}{4^n \cdot n!} \cdot \sqrt \pi$	$\infty$

Ζευγάρια παπουτσιών	$1$	$2$	$3$	$4$	$5$	$n$
Σωστές αναδιατάξεις	$1$	$2$	$6$	$24$	$120$	$n!$
Δυνατές αναδιατάξεις	$2$	$24$	$720$	$40.320$	$3.628.800$	$(2n)!$
Πιθανότητα	$50\%$	$8,\overline{3}\%$	$0,8\overline{3}\%$	$0,0595\dots\%$	$0,0033\dots\%$	$n!/(2n)!$

$\frac{n!}{(2n)!}$	$= \frac{n!}{1 \cdot 2 \cdot 3 \dotsb (n-1) \cdot n \cdot (n+1) \dotsb (2n-1) \cdot(2n)}$
	$=\frac{n!}{ \underbrace{1 \cdot 3 \cdot 5 \dotsb (2n-1)}_\text{odd} \cdot \underbrace{2 \cdot 4 \cdot 6 \dotsb (2n)}_\text{even} }$
	$= \frac{n!}{[1 \cdot 3 \cdot 5 \dotsb (2n-1)] \cdot 2^n \cdot [1 \cdot 2 \cdot 3 \dotsb n]}$
	$= \frac{n!}{[1 \cdot 3 \cdot 5 \dotsb (2n-1)] \cdot 2^n \cdot n!}$
	$= \frac{1}{[1 \cdot 3 \cdot 5 \dotsb (2n-1)] \cdot 2^n} = \frac{1}{2^n \cdot \prod_{k=0}^{n-1}(2k+1)}$