PDE - Η κοινότητα των εκπαιδευτικών

Καλημέρα! Να ρωτήσω..με βάση την άποψη ότι το O(n/k) είναι απλοϊκή απάντηση, τότε αυτό δεν περιλαμβάνει και το εξής΄ ναι μεν για k=1, το n/k=n αλλά αυτό θυμίζει τις πιθανότητες Λυκείου: Δηλαδή αν ρίξουμε ένα ζάρι πάρα πολλές φορές (n) τότε "ξέρουμε"-αναμένουμε να έρθουν τις ίδιες φορές τα k αποτελέσματα(n/k). Προσωπικά όμως το πρώτο που απέκλησα ήταν το n/k, γιατί για μεγάλο n αν θεωρήσουμε ότι "στο ζάρι" μας προστείθενται παραπάνω πλευρές(μεγαλύτερο k) για τις ίδιες n ρίψεις και το k πλησιάζει το n τότε παύει να ισχύει το πιθανοτικά ισοδύναμο μεταξύ των αποτελεσμάτων των ρίψεων, αφού είναι σαν να ρίχνουμε ένα κοινό ζάρι π.χ. 8 φορές και αναμένουμε να φέρουμε σίγουρα τα 1,2,3,4,5,6 (ή αλλιώς ρίχνω 100 φορές ζάρι με πλευρές 1-40 και τα 1-40 θα έρθουν σίγουρα από 2 φορές) Δηλαδή, για να ισχύει το n/k  πρέπει πιθανοτικά να ισχύει ότι το n πάρα πολύ μεγάλο και το k πάρα πολύ μικρό,πάντα με τη λογική ότι τα n στοιχεία έχουν την ίδια πιθανότητα εισόδου.Ωστόσο, αν είχαν την ίδια πιθανότητα εισόδου τότε ποιός ο λόγος να χρησιμοποιήσουμε hashing και δεν δεσμεύουμε εξαρχής n/k χώρο για κάθε ομάδα στοιχείων με το χαρακτηριστικό k; Eπίσης είναι αυτό δυνατό να συμβεί σε προβλήματα πρακτικά-υπολογιστικά-καθημερινά; Τέλος για να γίνει αυτό πιο αντιληπτό, με το n/k έχουμε ότι και 1000n/1000k=n/k=10000000n/10000000k, εν ολίγοις συμπεραίνω ότι αν δοκιμάζω να αυξάνω και το n και το k τότε η συνάρτηση hash έχει πάντα με βάση την πολυπλοκότητα το ίδιο αποτέλεσμα κάτι που μπορεί να ισχύεί, Πιθανοτικά πάντα, με n και με κ=2 κέρμα ,με 3n και κ=6 ζάρι, αλλά σίγουρα όχι π.χ. με 100n για κ=100 βαθμούς (όπως στον Ασεπ).Πληροφοριακά να πώ ότι δεν αναφέρομαι στα παραπάνω γιατί έτσι μου βγήκε το αντιδραστικό. Την κατάσταση που επικρατεί την γνωρίζει ο καθένας!! Θέλω να τεκμηριώσω την ένστασή μου γιατί έχω 31-32 "ορθώς σωστές"(δεν θυμάμαι για μία!!) και άρα 29-28 "ορθώς λάθος". Ελπίζω να μη δημιουργώ αρνητικό κλίμα σε άλλους με 10,20..60 ορθές απαντήσεις!!Αυτό που με απαχολεί επίσης είναι η απάντηση που δώθηκε στην ερώτηση 4(χρησιμοποιεί τη λέξη ΓΛΩΣΣΑ) ΣΕ ΣΧΕΣΗ με την απάντηση που δώθηκε στην ερώτηση 57 η οποία δεν περιλαμβάνει το δ(Άρα συμπεραίνω...ότι τα σενάρια πμορούν να γραφούν σε οποιαδήποτε γλώσσα!!!!Και μιας και προηγούμενα κάποιος συνάδελφος μίλησε περί βιβλίων αλγορίθμων, ψάχνωντας περαιτέρω για την ερώτηση 4 όλοι οι όροι που αναφέρονται περί γραμματικές χωρίς συμφραζόμενα...τους έχει δώσει-ορίσει ο "γνωστός άγνωστος" για τους αλγορίθμους τσόμσκι!.Παρόλα αυτά χρησιμοποιούνται και με το κόμμα που λέμε,άρα στην 17 που χρησιμοποιείταi το μαθηματικό-κοινώς αποδεκτό άθροισμα δεν έπρεπε να αναφέρει τουλάχιστον! για κάθε n>1;;;; Σύμφωνα λοιπόν με το διαχωρισμό των γλωσσων από τον προαναφερόμενο υπάρχουν και οι κανονικές γλώσσες π.χ.αρβανίτικα. Ωραία τότε με βάση την 57 θα μπορώ να φτιάξω και σενάριο με αυτά!!:-)

Το n/k είναι η απλοϊκή απάντηση γιατί για να την απαντήσεις θα πρέπει κάποιος να σε πληροφορήσει ότι ισχύει το uniformity assumption δηλαδή χοντρικά ότι η συνάρτηση κατακερματισμού κατανέμει ομοιόμορφα το σύνολο στις θέσεις του πίνακα, κάτι το οποίο δεν δόθηκε σαν εκφώνηση, και επίσης σε αυτή την περίπτωση μιλάμε για μέση πολυπλοκότητα και όχι για πολυπλοκότητα χειρότερης περίπτωσης (πάλι καμία αναφορά στην εκφώνηση). Τώρα το k μπορεί να είναι ο,τιδήποτε σε σχέση με το n. Πχ. O(logn). Απο κει και πέρα προφανώς ισχύει αυτό που αναφέρεις ότι όταν μεταβάλλεις κατα μια σταθερά κ το n και το k, η μέση πολυπλοκότητα παραμένει ίδια. Τώρα άμα προαποθηκεύσεις τα n στοιχεία κατά k είσαι οκ όταν το σύνολο που αποθηκεύεις είναι σταθερό, δλδ δεν έχεις ενθέσεις διαγραφές. Εκεί που είναι χρήσιμο το hashing είναι μεταξύ άλλων εκεί που ξέρεις από τη φύση του προβλήματος ότι πρέπει να αποθηκεύσεις αριθμούς πχ στο [1, 1.000.000] αλλά δεν ξέρεις πόσους... 50, 100, 200; το μέγεθος δηλαδή του προς αποθήκευση συνόλου μεταβάλλεται δυναμικά κατά το χρόνο ζωής του πίνακα. Αν δέσμευες εξαρχής χώρο μεγέθους 1.000.000 στοιχείων θα ταν σπατάλη, οπότε χρησιμοποιείς hashing έχοντας κατά νου την περίπτωση σύγκρουσης.

Στο 17 ξαναλέω ότι θα πρεπε κατα τη γνώμη μου να λέει ότι τα αριστερά μέλη είναι συναρτήσεις πολυπλοκότητας, όπως το λέει σε όλα τα βιβλία αλγορίθμων όπου υπάρχουν ανάλογες ασκήσεις. Το για κάθε n>1 δεν είναι τόσο σωστό, το ακριβές είναι για κάθε n>n0, όπου n0 κατάλληλη κ οσοδήποτε μεγάλη σταθερά.