Προβλήματα Μαθηματικών

Απρίλιος 10, 2009

Τελωνειακός έλεγχος

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 11:54 μμ

douane

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

Για λόγους νομικούς η διοίκηση ζητά να κρατούνται για έλεγχο κάθε μέρα «100 αντικείμενα επιλεγμένα απολύτως τυχαία από τα αντικείμενα της ημέρας«.

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

Όμως δεν ξέρει. Κατά τη διάρκεια της ημέρας φθάνουν αντικείμενα για επεξεργασία στην υπηρεσία του απροειδοποίητα και δεν έχει χώρο να κρατήσει πάνω από 100 αντικείμενα στην αποθήκη του.

Τι θα πρέπει να κάνει;

Advertisements

4 Σχόλια »

  1. Υπόδειξη: Κάνει το μόνο πράγμα που θα μπορούσε να κάνει!

    Μου αρέσει!

    Σχόλιο από Δημήτρης — Απρίλιος 18, 2009 @ 12:51 μμ

  2. Υπόδειξη:

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

    Τι θα πρέπει να κάνει ο διευθυντής του τελωνείου ώστε να έχει 100 αντικείμενα που έχουν επιλεγεί τυχαία από τα N+1 της ημέρας;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Απρίλιος 19, 2009 @ 12:38 μμ

  3. Μπορεί να κάνει το εξής, να βάλει τα 100 πρώτα αντικείμενα που θα έρθουν στην αποθήκη του και για κάθε επόμενο να κάνει την εξής διαδικασία:
    αν αυτό που έρχεται είναι το ν-ιοστό τότε θα το βάλει στην αποθήκη με πιθανότητα 100/ν και σε περίπτωση που το βάλει θα βγάλει τυχαία ένα από τα 100 που βρίσκονται ήδη μέσα στην αποθήκη.
    Επαγωγικά τώρα αποδεικνύεται ότι αν έχουμε τυχαίο δείγμα από 100 αντικείμενα για τα ν πρώτα τότε με αυτή τη μέθοδο και για τα ν+1 πρώτα αντικείμενα θα έχουμε τυχαίο δείγμα από 100. Άρα και στο τέλος της διαδικασίας θα έχει 100 αντικείμενα επιλεγμένα με ίδια πιθανότητα το καθένα.
    Από την πρακτική πλευρά τώρα του ζητήματος, για να αποφασίσει αν το ν-ισοστό αντικείμενο θα το κρατήσει ή όχι μπορεί να βάλει μέσα σε ένα κουτί ν χαρτάκια από τα οποία τα 100 αντιπροσωπεύουν την απόφαση του να το κρατήσει και να διαλέξει τυχαία 1 χαρτάκι. Όμοια για να αποφασίσει ποιο θα βγάλει από την αποθήκη θα τραβήξει κλήρο ανάμεσα σε 100 χαρτάκια.

    Μου αρέσει!

    Σχόλιο από stedes — Απρίλιος 23, 2009 @ 7:21 μμ

  4. Πολύ σωστά.

    Η μέθοδος αυτή ονομάζεται reservoir sampling.

    Μ’αρέσει ιδιαίτερα που περιέγραψες με λεπτομέρεια το πώς θα υλοποιηθεί η μέθοδος (χαρτάκια σε κουτάκια).

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Απρίλιος 23, 2009 @ 8:40 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: