THMMY.gr

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


2013-2014

Θα ήταν εύκολο να ανεβάσει κάποιος τις ασκήσεις που έχουν γίνει μέχρι τώρα στο 1ωρο της παρασκευής?συμπίπτει με άλλο μάθημα και δεν έχω την ευχέρεια να το παρακολουθήσω. :)

Βασικα δεν γινονται ασκησεις οπως πχ στο δομημενο. Μεχρι τωρα γινεται μια παρουσιαση των βασικων στοιχειων της java τα οποια τα βλεπεις μετα καλυτερα στο εργαστηριο. Αν θελεις ριξε μια ματια στο e-thmmy. Νομιζω εχουν ανεβασει τις διαφανειες των μαθηματων ασκησεων.

nice  ;)

Έστω πινακας 10 θέσεων i=0,1....9 και κάνουμε αναζήτηση αλματος με αλμα πχ α=2 . Θα αρχίσουμε από το i=0 (1η συκγριση) και μετά θα πάμε στο i=2(2η σύγκριση) κ.ο.κ ?  (αυτοαξιολογιση 2 και τα θέματα 2 κ 3 ήταν έτσι . )

Ναι, έτσι δουλεύει η αναζήτηση άλματος όπως μας την έμαθαν.

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

Για τους πινακες κατακερματισμου:

Παιρνουμε τα στοιχεία που δίνονται και τα περναμε μεσα απο την συναρτηση h(k). Τα αποτελεσματα (θετικοι ακεραιοι) τοποθετουνται στον πινακα (απο 0 εως n) στην θέση που έχει τιμή ίση με το αποτελεσμα της h(k).
Σε περίπτωση συγκρουσεων:
i)h'(k)=c (c-> σταθερα θετικη ή αρνητικη)...Μετακίνουμε το στοιχειο "συγκρουσης" c θεσεις προς τα δεξια (αν c θετικο) ή c θέσεις αριστερα (αν c αρητικο). Αν στην νεα θέση υπαρχει κ παλι συγκρουση συνεχιζουμε την "μετακινηση" μεχρι να βρεθει ελευθερη θεση.

ii)h'(k)=ci²...Μετακίνουμε το στοιχειο "συγκρουσης"  ci² θεσεις προς τα δεξια (οπου i=1).Αν στην νεα θέση υπαρχει κ παλι συγκρουση αναζητουμε ελευθερη θεση  ci² (για i=2) ...επαναλαμβανουμε για i=3,4... μεχρι να βρεθει κενη θεση.

iii)h'(k)=(kmodc)-c οπου c σταθερα...και παλι μετακινουμε το στοιχειο τοσες θεσεις οσο η τιμη που δινει η h'(k)....

Μπορει καποιος να εξηγησει την επιλυση με μεθοδο συνδεδεμενων λιστων (θεμα 2 αυγουστος του '07)

Να ρωτήσω και εγώ κάτι στον κατακερματισμό που είναι βασικό πέρα αυτού για τις συνδεδεμένες λίστες.  Όταν για παράδειγμα, έχω h'(k)=2i^2, όπως στο παράδειγμα στην τάξη, και έστω ότι έχω μια σύγκρουση. Η νέα θέση χ΄ είναι χ+1. Αν έχω και εκεί μετά ποια θα είναι η νέα θέση η (χ+2*2^2)=(χ+8)  ή  χ'+8. Εννοώ αρχίζω να μετράω από την αρχική θέση κατακερματισμού ή αναδρομικά, δηλαδή εκεί που σταμάτησα στην χ', δηλαδή (χ'+8)=(χ+2)+8. Ρωτάω γιατί στο βιβλίο του lafore σελίδα 543 δείχνει απλά ότι μετράει τα τετράγωνα από την αρχή , ενώ αν θυμάμαι καλά είχαμε πει το άλλο και επίσης δεν βγαίνει και η θέση του 12 στο παράδειγμα στην τάξη, με τον τρόπο του βιβλίου , εκτός και αν κάνω λάθος στο μέτρημα των κουτιών. Γενικά απλά είναι συνηθισμένη άσκηση και είναι κρίμα να χάσεις εδώ.   

Επίσης, αν γίνεται να πει κάποιος με σιγουριά τις πολυπλοκότητες στα θέματα τα παλιά που είναι στο ethmmy , θέμα 1ο , ερώτημα α και στα δύο για να τα συγκρίνω.

και τέλος μια ιδέα στις συνδεδεμένες λίστες που ρωτήθηκε πιο πάνω

Παίδες καλημέρα! Στα θεματα φεβ 2008 στο θεμα της javas πως περνάμε το μέγεθος του πινακα στην μεθοδο printArray το μεγεθος του πινακα array στοιχείων Element;

Κατω κατω λέει να ΜΗΝ βάλουμε αλλα ορίσματα αρα μεγεθος πίνακα μεσω ορισματος αποκλείεται.

array.length ;)

THX! 2 ακόμη προβλήματα.

Φεβ 2008 Java:

την μεθοδο printArray της  κλασης Array πως την καλούμε μέσα στην main της Array?
(ο eclipse λέει να την κάνω static); Ειναι σωστό;

επισης, δεν μπορώ να καλέσω μέσα στην Array μεσω του πινακα κ των element τους setters και getters της κλασης element.

Γραφω κ [ ι ] .getValue(); και μου εμφανίζει πρόβλημα.

σωστο ειναι να το κανεις στατικ
αλλα γενικα η λογικη για να χρησιμοποιησεις μεθοδους μιας κλασης μεσα στη μαιν
πρεπει πρωτα να δημιουργησεις ενα αντικειμενο Αρραυ και μετα μεσω αυτου να καλεσεις την πριντΑρραυ

το αλλο σου προβλημα δεν το πολυκαταλαβα (δεν εχω δει ακομη το θεμα αυτο)

Τη συνάρτηση getValue() πως την έχεις ορίσει ως private;

Οχι ειναι public  :-\ :-\  Δες το μια και πες με

Το i που χρησιμοποιείς, δεν το έχεις ορίσει!

Κλαίω με τα ηλίθια λάθη! Χρωστάω μπυρονια και στους 2  :) :) :)

Παιδιά μία μικρή βοήθεια με το θέμα 1ο δ) από τον Αύγουστο του 2007. Με έχει μπερδέψει κάπως ενώ φαίνεται απλό! thanks :)

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

H ταξινόμηση quicksort πως δουλεύει γιατι δεν βγάζω νόημα!  >:( >:( >:(

Αυγ. 07.->Θεμα 1
1)Δ
2)Ε
3)Β
4)Α

Φεβ. 08->Θεμα 1
1)Α
2)Γ
3)Β
4)Ε

Συμφωνειτε;

Ρε μην τρολλάρεις τον κόσμο  :-\

Για το 1) μου φαίνεται ότι είναι n*n*(1+2+3+...+n)=n*n*n(n+1)/2=O(n⁴) (όποιος το ξέρει σίγουρα, ας το επαληθεύσει)
Για το 2) έχουμε περίπτωση RL, οπότε θα χρειαστεί διπλή στο 27.
Τα υπόλοιπα σωστά

Στα θέματα του Αυγούστου του 2007, στο θέμα 2β), για τη μέθοδο συνδεδεμένων λιστών, θα υποθέσουμε ότι η περιοχή υπερχείλησης είναι από τη θέση 16 του πίνακα και μετά (δηλαδη 16->0->1->2 κτλ)?

thank u!κ εγώ αυτό βρήκα απλά κάπως αυθαίρετα!tnx anyway!

Offtopic : Σημειώσεις δικες μας και ασκήσεις που κάναμε δεν μπορούμε να τις έχουμε μαζι μας έτσι ?

οχι

Ρε μαλακες δεν τρολαρω πειτε με λιγο την μεθοδολογια με το pivot και την ταξινομηση

Αρχικά διαλέγεις ένα στοιχείο σύγκρισης (Pivot) από τον πίνακα με κάποια μέθοδο. Συνήθως αυτή η μέθοδος είναι το μεσσαίο στοιχείο του πίνακα. Αφού το βρεις, το ανταλλάσεις με το πρώτο στοιχείο του πίνακα για να αρχίσεις τη σύγκριση.
Έπειτα ορίζεις τις μεταβλητές left και right και βάζεις την μία στην αρχή του πίνακα (Left) και την άλλη στο τέλος (right). Ξεκινώντας με την Left, την μετακινείς δεξιά μέχρι να συναντήσεις στοιχείο μεγαλύτερο του Pivot. Στη συνέχεια μετακινείς την right αριστερά μέχρι να συναντησεις στοιχείο μικρότερο του pivot. Αφού έχουν σταματήσει και οι 2 μεταβλητές σε καποια στοιχεία και δεν έχουν προσπεράσει η μία την άλλη, ανταλλάσεις μεταξύ τους τα δύο αυτά στοιχεία (χωρίς να πειράξεις τις θέσεις των Left και right) και συνεχίζεις με την ίδια λογική.
Όταν προσπεράσει η μία μεταβλητή την άλλη, ανταλλάσεις το Pivot με το στοιχείο που είναι στη θέση right, χωρίσοντας έτσι τον πίνακα σου σε δύο μέρη: ένα με στοιχεία μεγαλύτερα του pivot και ένα με στοιχεία μικρότερα του pivot.
Τέλος, εφαρμόζεις τον ίδιο αλγόριθμο σε κάθε ένα από τα καινούρια κομμάτια, χωρίς το Pivot.

Μπορεί κάποιος ρε παιδιά να μου δώσει τα φώτα του με τον αλγόριθμο Knuth-Morris-Pratt...πως βγάζουμε την συνάρτηση αποτυχίας και γενικά πως δουλεύουμε στην αναζήτηση του προτύπου??

το εξηγεις λιγο το 2)??

Στην quicksort εχω δυο δεικτες r και l. Εστω οτι σαν pivot επιλεγω το πρωτο στοιχειο του πινακα.
Μετα ο δεικτης r θα αρχισει να σκαναρει προς τα αριστερα μεχρι να βρει στοιχειο μικροτερο απο το πιβοτ. Θα σταματησει μολις βρει.
Μετα ο δεικτης l θα αρχισει να σκαναρει προς τα δεξια μεχρι να βρει στοιχειο μεγαλυτερο του πιβοτ. Θα σταματησει και αυτος και μετα οι δυο δεικτες θα ανταλλαξουν στοιχεια. Νομιζω μεχρι εδω ειμαι καλα. Αφου γινει η ανταλλαγη, ο δεικτης l προχωραει ενα στοιχειο προς τα δεξια και μετα αρχιζει παλι ο r να σκαναρει μεχρι να βρεθει αριστερα του l;; Βασικα με ενδιαφερει το τι γινεται μετα την ανταλλαγη. Συγγνωμη για τον μεγαλο προλογο.

Αν δεις εδώ (http://alexander.ee.auth.gr:8083/eTHMMY/archive/46/downloadFile/93/Data%20Structures%20-%20Lecture%205%20-%20Searching%20color.pdf) στη σελίδα 12 (σελίδα 45-46) λέει αναλυτικά τον αλγόριθμο.

Τελικά λάθος το έχω απαντήσει. Η περίπτωση είναι LL στον κόμβο 27 και θα χρειαστεί μια απλή περιστροφή του 27. Αφού δεν υπάρχει τέτοια επιλογή, είναι όντως το Ε.

Αφού γίνει η αναταλλαγή, ξεκινάει πάλι ο left να προχωράει μέχρι να βρει μεγαλύτερο του pivot. Όταν βρει, σταματάει αυτός και αρχίζει ο right μέχρι να βρει μικρότερο. Αν σταματήσει και αυτός αλλά έχουν προσπεράσει ο ένας τον άλλο, σημαίνει ότι ο left συνάντησε το πρώτο στοιχείο του πίνακα με τα μεγαλύτερα από το πιβοτ στοιχεία και ο right συνλαντησε το πρώτο στοιχείο του πίνακα με τα μικρότερα από το πίβοτ στοιχεία. Εφόσον ο πίνακας είναι συνεχής, τα δύο αυτά στοιχεία θα είναι γειτονικά και άρα και οι δείκτες Left και right θα είναι δίπλα δίπλα. Ο right θα είναι σε στοιχείο μικρότερο του πίβοτ. Άρα ανταλλάζεις το πιβοτ με αυτό το στοιχείο και τώρα ο πίνακας σου είναι χωρισμένος σε δύο, με σύνορο το πίβοτ. Τους παίρνεις έναν έναν και ξανα εκτελείς τον αλγόριθμο.

Ευχαριστω πολυ!  :)
Το εχω λαθος πανω btw ο l ξεκιναει πρωτος!  :-X

εστειλα στον αντωνη και με ειπε το Β

Όντως. Έχω μπερδέψει τους κόμβους στους οποίους γίνονται οι διπλές και οι απλές περιστροφές.

Φεβ. 11 θεμα 1
Συμφωνειτε;
1)Β
2)Γ
3)Α
4)ξερεις κανεις να το εξηγησει

Επισης απο την ιδια χρονια στον πινακα κατακερματισμου για h'(k)=-1 παω προς τα αριστερα αλλα δεν υπαρχει καμια κενη θεση ...τι κανω σ αυτη την περιπτωση;;; (ή μηπως εχω κανει κατι αλλο λαθος; )...το ιδιο συμβαινει κ για την h'(k)=(kmod9)-9....

Στο 4, όπως είναι το δέντο χωρίς αλλαγή ισχύει ότι:
Σ=00 (2 ψηφία)
Ο=01(2 ψηφία)
Ε=0 (1 ψηφίο)
Α=1 (1 ψηφίο)
Άρα το κόστος έιναι ίσο με Κ=130*2( για το Σ) + 150*2 (για το Ο) + 1*250 (για το Α)=810
Αν αλλάξουν θέση, το Ο θα θέλει 1 ψηφίο και το Α θα θέλει 2. Άρα το νέο κόστος θα είναι:
Κ'=130*2+150*1+250*2=810
Άρα το κόστος θα μείνει το ίδιο. Ετσι νομίζω ότι βγαίνει. Όποιος μπορεί, ας το επαληθεύσει.



Το Γ) ερώτημα σωστό είναι το γ).Το 16 (leftChild) είναι μεγαλύτερο από το δεξί παιδί του πατέρα του 4 (δηλαδή το 4). Άρα θα μπει με το rightChild του 4, δηλαδή το 1. Μόλις μπει να εκτελέσει την Traverse για 1 και εκτυπώσει το 1, δεν θα μπει στην if και θα ξαναεκτυπώσει το 1. Έπειτα θα βγει από τη traverse(1) και τότε θα πάει να εκτελέσει την επόμενη εντολή της Traverse(4), η οποία είναι να εκτυπώσει το 4. Τέλος θα βγει και από την Traverse(4) και θα εκτελέσει την τελευταία εντολή της Traverse(10) Που είναι να εκτυπώσει το 10.
Αρα θα εκτυπώσει 10411410

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

Φεβρουάριος 2008 στο Θέμα 4 η κλάση Array κληρονομεί την Element?

ωραια σε ευχαριστω

οχι

Έκανε κανεις το β-δενδρο του 2007 2α) ; πως βγαίνει;

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

Σωστός! Τουλάχιστον δεν επηρρεάζει την άσκηση.

H κλαση Array θα κληρονομει την  Element στα θεματα Φεβ2008?

χαχαχα το ρωτησα και εγω αυτο..οχι

Μπορεί κάποιος να βοηθήσει στο θεμα 2β του Φεβρουαρίου 2008?

Ουπς! Δεν το βρηκα! Sorry!

ο αλγόριθμος επίλυσης συγκρούσεων είναι φιξ ? Απλα αλλάζουμε το h' ανάλογα με το αν θέλουμε γραμμική , τετραγωνική κτλ ?

άμα γράψετε κάτω απο 9 κόψτε το

 8))

Εχει κανει καποιος το θεμα της java του 11'?

Feb2008 το θεμα 1 η πρωτη που ζηταει πολυπλοκοτητα ειναι το Δ η το Ε?

O(n)

Σε ArrayList μπορουμε να αποθηκευσουμε συμβολοσειρες?

τα παντα ολα μπορεις να αποθηκευσεις

Αρα τη συμβολοσειρα θα την αποθηκευσουμε σε αρειλιστ?Μιλαω για το θεμα της τζαβα του 11'

δεν το ειδα
βαρεθηκα :P
αυριο
ας απαντησει κανεις αλλος...

Γραμμικη γιατι ειναι? Αφου εχει  λουπες μεσα?

Στο θεμα 4ο 11' στη δομη Treap πρεπει να ειναι και ισοσταθμισμενο το τελικο δεντρο μας?

Παίρνεις το worst case scenario της κάθε λουπας

στο 1ο for wcs =10
στο 2ο wcs = 10 όταν ι=9
στο 3ο wcs =n
Αρα 10*10*n = 100n σε ενδιαφέρει το n και ο εκθετης του και αν έχει log

To treap δεν χρειάζεται να είναι AVL , αν κάνω λάθος ας διορθώσει κάποιος

επειδη αυτα με τις πολυπλοκοτητες με μπερδευουν λιγο
ποτε θα εμφανιζονταν ενα Log;

Τι όφελος έχουμε με τη 3-δική μορφή έναντι της δυαδικής; Φεβ 08 θέμα 3β ii

+1, γιατι εμενα με μπερδευουν πολυ.  :-\

+1 :P Ίσως αυτό βοηθήσει http://programmers.stackexchange.com/questions/146021/determining-if-an-algorithm-is-o-log-n

τελικά αύριο από σημειώσεις μπορούμε να έχουμε μόνο τις διαφάνειες εκτυπωμένες ή γίνεται και δικές μας χειρόγραφες?

Βιβλιο, διαλεξεις θεωριας, διαλεξεις εργαστηριων. Εννοειται χωρις χειρογραφες σημειωσεις πανω σ'αυτα!  :P

java 11 κανεις?

Ισως το οτι το υψος του δενδρου ειναι μικροτερο και οτι χρειαζονται λιγοτερες ανταλλαγες για να δημιουργηθει ο σωρος ελαχιστων? Δεν ειμαι σιγουρος, ειδικα τετοια ωρα. Πειτε καμια αλλη γνωμη!   :-\

Φεβρουαριος 08 Θεμα 2 β. Το εχει κανει στις παραδοσεις αυτο; Ενα μαθημα ελειψα αυτο βρηκε να κανει? Παιζει να μπορει καποιος να ανεβασει λυση?

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

παιζει καποιος να εξηγησει λιγο τη διασχιση (ενδοδιατεταγμενη προδιαεταγμενη μεταδιατεταγμενη)
καταλαβαινω πως ενα δεντρο το μετατρεπουμε στο αντιστοιχο στρινγκ
αλλα με μπερδευει το αναποδο
δηλαδη πως ενα στρινγκ το κανουμε δεντρο
ποια ειναι η διαδικασια που ακολουθουμε;
(ρωταω με βαση τα θεματα του 07 κ 08)

Αυτό που κανεις αρχικά είναι ένα πλήρες δυαδικό δεντρο με κενά στοιχεια . Πχ βλέπεις ότι έχεις 18 γράμματα  , κανεις ένα πλήρες δυαδικό με 18 αδεια στοιχεια .
Τώρα για τον τρόπο διασχισης πας στο pdf 4α και τσεκάρεις τα πχ . Τα βελάκια βοηθάνε πολύ και επίσης τσέκαρε και εδώ το applet

http://www.qmatica.com/DataStructures/Trees/AVL/AVLTree.html

βγάλε από τα options το AVL και το traverse είναι η διάσχιση  και διαλέγεις

Μπορεί να μου εξηγήσει κάποιος πως γίνεται η επίλυση συγκρούσεων με τη μέθοδο των συνδεδεμένων λιστών..?

σε ευχαριστω παρα πολυ φιλε
με ξεμπλοκαρες απειρα

επισης να ρωτησω κατι ακομη
αν μας λεει να φτιαξουμε ενα δυαδικο δεντρο με καποια στοιχει που μας δινονται
εμει θα πρεπει να το κανουμε και ισορροπημενο ή αν το θελει θα μας λεει ξεκαθαρα AVL;

θα πρεπει να λεει AVL

ξερει κανεις αν υπαρχουν πουθενα οι απαντησεις απο τα τεστ αξιολογησης που ειναι στο e-thmmy?

λίγο ηλίθια ερώτηση αλλά όταν μας δίνει μια σειρά από αριθμούς όπως 3α Φεβ-2008 πώς σχηματίζουμε το δυαδικό δέντρο;

στην ενότητα 6-αναζήτηση-στον αλγόριθμο boyer moore γιατί κάνει 15 αναζητήσεις μέχρι να ευθυγραμμίσει τον τζίτζι;
γενικά αν πχ στο τελευταίο γράμμα του P(πχ εδώ το τζιτζι) βρουμε διαφορά,τότε ψάχνουμε από το πρότελευταίο αντίστοιχο του Τ και προς τα πίσω(έστω δηλαδή ότι το τζιτζι αντιστοιχεί στο ιτζηρας,τότε θα ευθυγραμμίσουμε το ζ του ίτζηρα με το τελευταίο ζ του τζιτζι;;)  ή από το πρώτο για να κάνουμε τη σύγκριση+ευθυγράμμιση για τα υπόλοιπα γράμματα του P;