Δομές Δεδομένων - Εξετάσεις Σεπτεμβρίου 2007

THMMY.gr > Forum > Μαθήματα Βασικού Κύκλου > 3ο Εξάμηνο > Δομές Δεδομένων (Moderators: chatzikys, Tasos Bot, tzortzis) > Δομές Δεδομένων - Εξετάσεις Σεπτεμβρίου 2007

0 Members and 1 Guest are viewing this topic.

Pages: 1 [2] 3 4 5

Author

Topic: Δομές Δεδομένων - Εξετάσεις Σεπτεμβρίου 2007 (Read 12200 times)

emmanuel

Veteran
Αbsolute ΤΗΜΜΥ.gr

Gender:

Posts: 3830

πλάκα με κανεις?

Re: Δομές Δεδομένων - Εξετάσεις Σεπτεμβρίου 2007

« Reply #15 on: August 29, 2007, 15:19:54 pm »

ρε παιδια τι κατι πηρε το αυτι μου...
εχει γεμισει το φορουμ με ανακοινωσεις..
αν πραγματιακ σας ενδιαφερει λιγο ψαξτε,μη γεμιζουμε τα τοπικ με τα ιδια και τα ιδια.


	Logged

tu/e

akis

Veteran
Αbsolute ΤΗΜΜΥ.gr

Gender:

Posts: 4005

Re: Δομές Δεδομένων - Εξετάσεις Σεπτεμβρίου 2007

« Reply #16 on: August 29, 2007, 15:47:25 pm »

ενταξει Μανόλη
εχεις δίκιο
μη μας μαλώνεις

Tongue


	Logged

solid_snake

Νεούλης/Νεούλα

Posts: 37

Do not underestimate your Power and Potentials

Re: Δομές Δεδομένων - Εξετάσεις Σεπτεμβρίου 2007

« Reply #17 on: August 29, 2007, 19:05:11 pm »

sorry...


	Logged

kORTAS

Εθισμένος στο ΤΗΜΜΥ.gr

Gender:

Posts: 769

Jijikas

Re: Δομές Δεδομένων - Εξετάσεις Σεπτεμβρίου 2007

« Reply #18 on: August 29, 2007, 19:22:20 pm »

Quote from: ikoufis on August 20, 2007, 17:12:02 pm

Ο αραιός πίνακας μπορεί να αποθηκευτεί ως τριάδες αριθμών και μάλιστα τόσες τριάδες όσα και τα μη μηδενικά στοιχεία Ν.Αρα για κάθε μη μηδενικό στοιχείο χρειάζεται να αποθηκεύσουμε 3 ακεραίους,δηάδή 3*4=12 βιτ.Συνολικά 12Ν βιτ για όλο τον πίνακα.
Η αμέσως λιγότερη συμφέρουσα αποθήκευση αραιών πιθνάκων για μικρά Ν είναι στη διαφάνεια 9 σελ2-4.
Εκεί χρειαζόμαστε n*m(5*6 ή 6*6) βιτς για την αποθήκευση του δυαδικού πίνακα συν 4Ν βιτς για την αποθήκευση του πίνακα των ακεραίων.
Αρα λύνοιυμε την ανίσωση 12Ν<n*m+4Ν και βάζουμε το μεγαλύτερο Ν που ικανοποιεί την ανίσωση,όχι την ισότητα.

E, ναι βγαίνει 5*6/8=3,75 και 6*6/8=4,5. Την ισότητα ικανοποιούν τα 3,75 και 4,5 εγώ έβαλα την αμέσως μικρότερη ακέραι ποσότητα δηλ 3 και 4. Γιατί αυτό είναι λάθος;


	Logged

MIMIRU

Ανερχόμενος/Ανερχόμενη

Posts: 75

Είμαι ηλεκτρολόγος, συμβαίνει κάτι;

Re: Δομές Δεδομένων - Εξετάσεις Σεπτεμβρίου 2007

« Reply #19 on: August 29, 2007, 23:12:41 pm »

Quote from: kORTAS on August 29, 2007, 19:22:20 pm

Quote from: ikoufis on August 20, 2007, 17:12:02 pm

Και γω βάζω αυτα ακριβώς και είναι λαθος..Ας απαντήσει κάποιος..


	Logged

filmst_r

Ανερχόμενος/Ανερχόμενη

Gender:

Posts: 83

Great Googly Moogly.

Re: Δομές Δεδομένων - Εξετάσεις Σεπτεμβρίου 2007

« Reply #20 on: August 29, 2007, 23:47:00 pm »

Quote from: MIMIRU on August 29, 2007, 23:12:41 pm

Quote from: kORTAS on August 29, 2007, 19:22:20 pm

Quote from: ikoufis on August 20, 2007, 17:12:02 pm

Και γω βάζω αυτα ακριβώς και είναι λαθος..Ας απαντήσει κάποιος..

Σε σχετικό μέιλ προς κο Ψωμόπουλο, μου απάντησε το εξής:
Από την θεωρία έχουμε ότι για Ν μη μηδενικά στοιχεία χρειαζομαστε 3Ν λέξεις
(σελ.2-5, διαφάνεια 11). Έτσι εάν δεσμεύουμε στην μνήμη έναν πίνακα 6x6 κάποιου
τύπου μεταβλητής τότε αυτόματα δεσμεύουμε μνήμη 6x6x(αριθμό των λέξεων που
καταλαμβάνει η μεταβλητή).

Για παράδειγμα εάν η μεταβλητή ακέραιος αντιστοιχεί σε μία λέξη μνήμης τότε ένας
πίνακας ακεραίων 6x6 θα δεσμεύσει 36 λέξεις μνήμης. Εάν για κάθε μη μηδενικό
στοιχείο χρειάζονται 3 λέξεις μνήμης τότε ο μέγιστος αριθμός μη μηδενικών
στοιχείων Ν που μπορεί να αποθηκευτεί σε αυτήν την δεσμευμένη μνήμη είναι 11
(για Ν=12 έχουμε ακριβώς την ίδια κατανάλωση μνήμης, και άρα δεν μιλάμε για
βέλτιστη λύση).

Στη συνέχεια, καθώς κι εγώ είχα μείνει με την εντύπωση ότι για την υλοποίηση του πίνακα της διαφάνειας 9 δεσμεύεται 1bit/κελλί, ρώτησα και πάλι σχετικά και πήρα την εξής απάντηση:
(...)και ο πίνακας απαιτεί για κάθε στοιχείο του χώρο
ίσο με w (δηλαδή δεν ισχύει το ένα bit ανά κελί).

...Κι επειδή παρόλαυτά εξακολούθησα να μην καταλαβαίνω σε τι στο καλό χρησιμεύει τότε η (notorious) μέθοδος της διαφάνειας 9, ξαναρώτησα και η απορία μου λύθηκε ως εξής:

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

Αυτά λοιπόν Wink

Καλό διάβασμα σε όλους(μας)


	Logged

kotsos_ee

Ανερχόμενος/Ανερχόμενη

Gender:

Posts: 62

Re: Δομές Δεδομένων - Εξετάσεις Σεπτεμβρίου 2007

« Reply #21 on: August 30, 2007, 12:25:43 pm »

εγώ ουτε τώρα κατάλαβα. Αν κάποιος καταλαβε ας γραψει την εξίσωση παρακαλώ
(η ειναι η (x*y)>3N? και αν ειναι το 4bits τι το δινει?)


« Last Edit: August 30, 2007, 12:40:23 pm by kotsos_ee »	Logged

jeffaldo

Εθισμένος στο ΤΗΜΜΥ.gr

Gender:

Posts: 803

Re: Δομές Δεδομένων - Εξετάσεις Σεπτεμβρίου 2007

« Reply #22 on: August 30, 2007, 13:30:31 pm »

κανονικα πρεπει να γραψεις

3*Ν*4 < 6*6*4
οποτε το 4 απλοποιείται κ εχουμε 3*Ν<6*6 -> Ν<12,αρα Ν=11


	Logged

Larry_Flynt

Καταστραμμένος

Gender:

Posts: 5403

Re: Δομές Δεδομένων - Εξετάσεις Σεπτεμβρίου 2007

« Reply #23 on: August 30, 2007, 14:14:11 pm »

Ο κώδικας που θα ζητηθεί σε τι επίπεδα δυσκολίας θα κινηθεί;

Δλδ πίνακες και κανένα bublesort ή μπορεί να φτάσουμε σε υλοποίηση κανενός δέντρου;


	Logged

void DrawShadow()
{
shadow = Matrix.CreateShadow(-directionalLight0Direction, game.functions.GetPlane(ref game.player.position, 5));
Matrix[] bones = game.heroPlayer.GetSkinTransforms();
Matrix[] shadowBones = new Matrix[bones.Length];

for (int i = 0; i < shadowBones.Length; i++)
{
shadowBones = bones * shadow;
}

foreach (ModelMesh mesh in game.heroModel.Meshes)
{
foreach (Effect effect in mesh.Effects)
{
effect.CurrentTechnique = effect.Techniques["Shadow"];
effect.Parameters["Bones"].SetValue(shadowBones); effect.Parameters["View"].SetValue(game.viewMatrix);
effect.Parameters["Projection"].SetValue(game.projectionMatrix);
}
mesh.Draw();
}

}

fpsom

Καταξιωμένος/Καταξιωμένη

Gender:

Posts: 119

I am not antisocial. Society is anti-me...

Re: Δομές Δεδομένων - Εξετάσεις Σεπτεμβρίου 2007

« Reply #24 on: August 30, 2007, 15:23:02 pm »

Quote from: Larry_Flynt on August 30, 2007, 14:14:11 pm

Είπαμε ότι είμαστε βάρβαροι, αλλά όχι και σε βαθμό να σας βάλουμε να υλοποιήσετε δένδρο σε java...! Wink

Κατά τα άλλα, καλά τα λες...

Φώτης


	Logged

Sed quis custodiet ipsos custodes?

Tsieki

Καταξιωμένος/Καταξιωμένη

Posts: 175

Re: Δομές Δεδομένων - Εξετάσεις Σεπτεμβρίου 2007

« Reply #25 on: August 30, 2007, 15:27:35 pm »

Θα ήθελα να αναφέρω 2 απορίες που έχω, αν μπορεί κάποιος να βοηθήσει...

Στις σημειώσεις σελ.4α-29 στη διαγραφη σε δυαδικό δέντρο, αντικαθιστά το στοιχείο προς διαγραφή 88 με το 82. Δεν θα έπρεπε να το αντικαταστήσει με το στοιχείο 97 που είναι το αμέσως επόμενο του 88; Sad

Γιατί στο βιβλίο των δομών σελ.393 λέει πως για κάθε κόμβο, ο κόμβος με το επόμενο υψηλότερο κλειδί είναι ο διάδοχός του και τον αντικαθιστά σε περίπτωση διαγραφής του...Δηλαδή εδώ στο συγκεκριμένο παράδειγμα είναι το 97. Ε; Υπάρχει μήπως λάθος στις σημειώσεις;

Επίσης κατά τη διαγραφή κλειδιού από β-δέντρο σελ. 4b-12 που διαγράφεται το στοιχείο 112 της προηγούμενης σελίδας δεν θα έπρεπε το 112 που βρίσκεται σε εσωτερικό κόμβο να εγκατασταθεί από το επόμενό του, δηλ.το 131 και στη συνέχεια ο κόμβος φύλλο στον οποίο απομένει μόνο το κλειδι 158 να ενσωματηθεί με το δεξί του υπόδεντρο(231 283);

Ας απαντήσει κάποιος αν ξέρει... beg


	Logged

igna

Καταξιωμένος/Καταξιωμένη

Gender:

Posts: 102

Re: Δομές Δεδομένων - Εξετάσεις Σεπτεμβρίου 2007

« Reply #26 on: August 30, 2007, 16:11:00 pm »

Υπαρχουν καπου παραδειγματα για εξασκηση στην java?


	Logged

Nessa NetMonster

Καταστραμμένος

Posts: 7044

Ιούνιος 1999 - 19/7/2009

Re: Δομές Δεδομένων - Εξετάσεις Σεπτεμβρίου 2007

« Reply #27 on: August 30, 2007, 16:29:00 pm »

Διευκρινιστική ερώτηση: Οι σημειώσεις που επιτρέπεται να έχουμε είναι αυτές στο site που λένε "Δομές Δεδομένων - Σημειώσεις Διδάσκοντος" ή και αυτές που λένε "Java: Οδηγός Java - Σημειώσεις Διδάσκοντος "; Ή είναι μέσα και οι ψευδοκώδικες αλγορίθμων;

Από τη γραμματεία ποιες μοιράζονταν;