THMMY.gr

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

ναι γενικά κάθε κουτάκι/κυκλάκι σε ένα δέντρο είτε ρίζα είτε φύλλο θεωρείται κόμβος! Οι γραμμές ονομάζονται ακμές

παιδια εχει λύσει κανεις αναλυτικα απο τα θεματα Φεβρουαριου του 16, το 2o θεμα - Β;

μπορει καποιος να ανεβασει λυση φεβ.2016 θεμα 2ο το Β ερωτημα ??? ειτε απο την Α ειτε απο την Β ομαδα

 ;D ;D ;D ;D ;D ;D ;D ;D

Θενκ γιου!  ;)

τελειο!   ;D

θενξ!  8))

Κάποιος να λύσει αναλυτικό παράδειγμα με χρήση : αναζήτηση άλματος,δυαδική αναζήτηση (βλέπε πολλαπλής το 16) και με ΚΜΠ αλγόριθμο BF, ΒΜ κτλπ κάποιο help Σε αυτά αν γίνεται!! (πχ Αύγουστος το 2007 3ο θέμα)

αυτα μηπως ειναι εκτος; γιατι ο ψωμοπουλος στις παραδοσεις φετος θυμαμαι να τις περνουσε αυτες τις διαφανειες χωρις να δινει σημασια.. ας επιβεβαιωσει και καποιος

οπως επισης και με τη μεθοδο των συνδεδεμενων λιστων στον κατακερματισμο δεν νομιζω να εκανε ασκησεις..  :(

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

Τώρα για το πολλαπλής του 2016. Γενικά η δυαδική αναζήτη τρέχει σε O(logn) ενώ η αναζήτηση άλματος (αν κατάλαβα καλά τι είναι) τρεχει σε χρόνο O(log logn) αν επιλεγεί σωστά το άλμα και τα στοιχεία έχουν ομοιόμορφη κατανομή, ενώ τρέχει σε χείριστο χρόνο O(sqrt(n)) αν δεν υπάρχει η παραπάνω κατανομή αλλά γίνει σωστά η επιλογή του βήματος. Για το συγκεκριμένο παράδειγμα μπορείς να δεις ότι η δυαδική αναζήτη θα τσεκάρει αρχικα το 15 με το στοιχείο που ψάχνεις. Μετά το low θα γίνει ίσο με το index του 18, δηλαδή 6 και στον επόμενο έλεγχο θα βρει το 24.
Η αναζήτηση με άλμα αυτό που θα κάνει είναι κάθε φορά να ξεκινάει από την αρχή και να ψάχνει ανα τόσο στοιχεία όσο είναι το άλμα. Αν πέσει σε μεγαλύτερο στοιχείο γυρνάει πίσω μέχρι να πετύχει το σωστό, που αν το τρέξεις με το χέρι θα δεις ότι θέλει παραπάνω πράξεις.

Για τον KMP μπορεις να δεις αυτό (https://www.youtube.com/watch?v=GTJr8OvyEVQ) και μετά αυτό (https://www.youtube.com/watch?v=KG44VoDtsAA) το βιντεο. Επειδή δίνω αύριο δεν προλαβαίνω σήμερα να κάνω το θέμα του 2007 που ζήτας. Αν μπορέσω αύριο θα το κοιτάξω και θα το ανεβάσω.

Στα θεματα που εχουν ανεβασει Φεβρουαριος 2016 ομαδα Β

Στο θεμα με τον κατακερματισμο στο 2ο ερωτημα ο φιλος γραφει για i=13 ομως εγω βρισκω οτι μπαινει σε εκεινη τη θεση για i=3

Αν καταλαβαινω καλα προσθετουμε 1-4-9-16 απο την αρχη καθε φορα και οχι απο εκει που σταματησαμε... διορθωστε με αν εχω λαθος

Νομίζω υπάρχουν πολλά λάθη στις λυμένες του downloads...Στου Φεβρουαρίου 2016Β για παράδειγμα Θέμα 1ο γ) βρίσκω Β)2 και στο δ) το Β)Δυαδική μιας και το βρίσκει στον 1ο έλεγχο αφού mid=13...

Σύμφωνα με τις διαφάνειες:h'(x)=c*(i^2) στην τετραγωνική εξέταση.Αφού ο κώδικας του κατακερματισμού λέει index=index+h'(x) ,όπου i ο αριθμός συνεχώμενων συγκρούσεων.Τότε κάθε φορά που επαναλαμβάνεται η λούπα του κώδικα αυξάνει i ΑΛΛΑΖΕΙ όμως και το index,οπότε μάλλον το α+c,α+4c κτλπ από το νέο index.Αυτό κατάλαβα εγώ τουλάχιστον δεν είμαι και σίγουρος :(

Ετσι ακριβώς δουλευει. Και όντως το i δεν είναι 13 αλλά 3

Το αρχείο είναι φώτο του μεθόδου επίλυσης των γ και Δ του 1ου θέματος Φλεβάρη 2016 Β που προανέφερα.Αν βρίσκετε άλλη λύση σχολιάστε...

Εγώ ναί μεν βγάζω ι=13 αλλά στο γ βρίσκω άλλο πίνακα στο αρχείο φαίνεται αναλυτικά πως το έκανα τσέκαρε αν έχω κάνει λάθος..

Ναι αλλά στις διαφάνειες γράφει και το
«– Όλα τα κλειδιά που συγκρούονται στην h(x) ακολουθούν
την ίδια διαδρομή:
• Αρχικά: a = h(j) = h(k)
• Στη συνέχεια: a + c, a + 4c, a + 9c, α + 16c, ....»

δηλαδή το a είναι αυτό που βρίσκεις στην αρχή και κάθε φορά προσθέτεις σε αυτό το c*i² (το ίδιο λέει και στη Wikipedia (https://en.wikipedia.org/wiki/Quadratic_probing)), και θυμάμαι να το λέει και όταν έκανε ασκήσεις αν και δεν είμαι πολύ σίγουρος για αυτό.

Έχει λύσει κάποιος το θέμα 3.Β(ΟΜΑΔΑ Α) με τη σωρό του 2016;

https://www.thmmy.gr/smf/index.php?action=tpmod;dl=item3061 (https://www.thmmy.gr/smf/index.php?action=tpmod;dl=item3061)

Νομιζω οτι τελικα το index στο β ερωτημα δεν το αλλαζεις και κρατας αυτο που βρηκες στην αρχη για α βλεπε και παραδειγμα στο βιβλιο σελ 262... σχετικα με το γ εχεις δικιο και εγω τοσο το βρηκα

Σε ευχαριστώ πολύ για το κόπο σου! Πολύ βοηθητικό και το λινκ και το comment για το άλμα!

Στην περίπτωση ταξινόμησης σωρού που μας δίνονται κάποιοι αριθμοί για να εισαχθούν ( πχ. 10) , ξεκινάμε την εισαγωγή από κάτω αριστερό φύλλο της σωρού προς τα δεξιά ανεβαίνοντας επίπεδα κατά πάνω? Το ίδιο ισχύει έιτε έχουμε σωρό ελαχίστων είτε μεγίστων?
Δείτε θέμα 3ο 2016 .

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

Oκ ευχαριστω για την επιβεβαιωση!