Απορίες στις Δομές Δεδομένων

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[Δείτε περισσότερα εδώ...]

Συμβουλές καλής χρήσης του φόρουμ: Youtube embed code and links, Shoutbox, Notify, ...

Δείτε περισσότερα εδώ...

[megapixel]

με 4 bit λεξεις.

αν αποθηκευσουμε κανονικα τα στοιχεια του πινακα
θελουμε 30*4=120 bit.

αν τα αποθηκευσουμε σαν τριαδες αριθμων(γραμη στηλη στοιχειο)
θελουμε 3*4*Ν bit

αν τα αποθηκευσουμε ως πινακα απο bit +πινακα με τα στοιχεια
θελουμε Ν*4+30 bit

για να ειναι βελτιστη η δευτερη μεθοδος πρεπει Ν*4+30> 3*4*Ν
αρα Νmax=3.

για Ν=2 εχουμε για τη δευτερη μεθοδο 24bit και με την τριτη 38.
για Ν=5 εχουμε για τη δευτερη μεθοδο 60bit και με την τριτη 50.

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

Αν αποθηκευσουμε σαν πινακα nxm , πινακα με μη μηδενικες τιμες, πινακα με στοιχεια οσα και οι γραμμες του αρχικου πινακα , τα οποια αντιστοιχουν αθροιστικα στο πληθος των ασσων ανα γραμμη
βγαζει
N+n+(nxm)/w. Πως βγαινει αυτο?

[Grecs]

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

[Social_waste]

megapixel
1 λεξη για καθε στοιχειο
1 λεξη για τον  αριθμο των στοιχειων σε καθε γραμη
και (n*m)/w λεξεις για τον πινακα απο bit
(n*m bit που αντιστοιχουν σε τοσες λεξεις) .

[ampoulog]

Δίνεται ο παρακάτω πίνακας. Επιλέξτε όσα κλειδιά μπορεί να βρεθούν αν εξεταστούν το πολύ δύο στοιχεία του πίνακα με τη μέθοδο της δυαδικής αναζήτησης. 1 2 3 4 5 6 7
1.   1
2.   2
3.   3
4.   4
5.   5
6.   6
7.   7


Σε αυτό τι ακριβώς ζητάει ?????????????????

[megapixel]

Δίνεται ο παρακάτω πίνακας. Επιλέξτε όσα κλειδιά μπορεί να βρεθούν αν εξεταστούν το πολύ δύο στοιχεία του πίνακα με τη μέθοδο της δυαδικής αναζήτησης. 1 2 3 4 5 6 7
1.   1
2.   2
3.   3
4.   4
5.   5
6.   6
7.   7


Σε αυτό τι ακριβώς ζητάει ?????????????????

1 2 3 4 5 6 7

1 2 3 4 5 6 7
         |

1 2 3 4 5 6 7         ή         1 2 3 4 5 6 7
   |                                                 |
 
δυαδικη: διαιρουμε στα 2 και συγκρινουμε με μια συγκριση μονο μπορουμε να βρουμε το 4
ενω με δυο συγκρισεις  μπορουμε το 2 και το 6
αρα σωστο ειναι το 2,4,6

[testiculos]

Ερώτηση:  Δίνεται το παρακάτω τμήμα ενός αλγορίθμου:

int i = 1;
while ( i <= n ) {
    for (int j = 1; j <= n; j = j * 2 ){
        x = x - 2 ;
}
            i++;
}

και η απάντηση δεν είναι n²...

[megapixel]

Στις σημειωσεις λεει οτι το δυαδικο δεντρο ειναι αυτο που εχει καθε κομβοσ 2 παιδια
ενω στο βιβλιο (σελ370) λεει οτι εχει το πολυ 2 παιδια. τελικα τι ειναι σωστο?

[ampoulog]

Έχει το πολύ δύο είναι το σωστό .

[george88thess]

@ megapixel : το πολυ 2 παιδια .

πωπω θα αυτοκτονησω με αυτη την αναζητηση αλματος. γιατι το αλμα να μετραει μετα το πρωτο στοιχειο???αφου η πρωτη διερευνηση ειναι μετα το πρωτο αλμα!!!!!
σκεφτηκα το αλλο.αφου το ιδανικο βημα αλματος ειναι ριζα n,εστω οτι εχουμε 9 στοιχεια. αν ξεκινησουμε κατευθειαν απο την τριτη θεση μετα απο 3 διερευνησεις φτανει στο τελος του πινακα ακριβως στο τελευταιο στοιχειο.αν ωστοσο κανουμε το αλμα μετα απο το πρωτο στοιχειο, δηλαδη παμε στην θεση 4 για την πρωτη διερευνηση, μετα απο 3 αλματα ξεπερνιεται το μεγεθος του πινακα -.-
οποτε......

[ampoulog]

Από τις διαφάνειες φαίνεται ότι η πρώτη διερεύνηση γίνεται στο p[a] και όχι στο πρώτο στοιχείο ....

[megapixel]

To πρωτο άλμα θα είναι απο :
6-20
το δευτερο απο 20-55
το τριτο απο 55-99
Αρα τρεις  βγάζω εγώ

Και μου λέει οτι είναι λανθασμενη στην αυτοαξιολόγηση
Μάλλον κάτι δεν καταλαβαίνω καλά ή είναι λάθος της βάσης δεδομένων .

Αν κάποιος το βγάζει αλλιώς ας πει

Γιατί η αναζήτηση από 55-99 να είναι σειριακή ???

Δειτε σελ 6-5 απο σημειωσεις:
Για αλμα α παει απο την 1η θεση στην S(α) που ειναι η 5η
Αρα το αλμα ειναι 4 θεσεις μετα καθε ελεγχο  αλλα το αλμα το εχει σαν α που ειναι το 5 (S(a)=5o
νουμερο)
Δλδ απο οτι καταλαβα μετακινηση θεσεων= αλμα-1


ΓΙΑ ΟΣΟΥΣ ΕΧΟΥΝ ΤΙΣ ΚΑΙΝΟΥΡΓΙΕΣ ΣΗΜΕΙΩΣΕΙΣ ΝΑ ΔΟΥΝ ΑΝΑΖΗΤΗΣΗ ΑΛΜΑΤΟΣ ΑΠΛΑ

Με αυτο συμφωνειτε?

[megapixel]

Τι να σου πω με έχει μπερδέψει πάρα πολύ .

Πάντως σχετικά με το NEOΣΑΡΧΙΕΠΙΣΚΟΠΟΣ που ρώτησες παραπάνω  μόλις το έκανα και βγαίνει κανονικά.

Η μέθοδος που ακολούθησα ήταν :
 1. μετρησα τα γράμματα της συμβολοσειράς και εφτιαξα δυαδικό δένδρο τόσων θέσεων.
 2.Έκανα προδιατεταγμένη διάσχιση για να τοποθετήσω τα γράμματα ¨
- επισκεψη στη ρίζα (Βάζεις το Ν)
-Επισκεψη του αριστερού υποδένδρου (βάζεις το Ε)
---Μετα θεωρείς ότι το Ε είναι ριζα του υποδένδρου
---και επισκέφτεσαι το αριστερο υποδένδρο όπου βάζεις το Ο
Αφού τελείωσεις με τα υποδενδρα αυτά
επισκέφτεσαι τα δεξια υποδένδρα
οπότε προκύπτει το παρακάτω :
            

                                                   Ν
                                 Ε                                  Ι
                      Ο                  Ι                Σ               Π
             Σ              Χ      Ε       Π       Κ    Ο        Ο     Σ
          Α  Ρ
(Σορρυ που δεν το κάνω σε κάποιο πρόγραμμα για να φανεί καλύτερα άλλα δεν έχω πολύ χρόνο . αν δεν το καταλάβεις πες μου και θα το φτιάζω σε κανένα word το βράδυ , απλά προσπάθησε να τα βάλεις στο χαρτί όπως στα δίνω).

Μετά κάνεις μεταδιατεταγμένη Διάσχιση
δηλαδή επισκέπτεσαι πρώτα το αριστερό παιδί μετά το δεξί και τέλος την ρίζα .

Αρχικά λοιπόν πας στο κάτω αριστερά παιδί και παίνεις το :   Α
Μετά στο κάτω αριστερά υποδένδρο και στο δεξί παιδί και παίρνεις το : Ρ
Επισκέπτεσαι την ρίζα του υποδένδρου αυτού και παίρνει το :  Σ
Θεωρείς την ρίζα του παραπάνω υποδέδρου σαν αριστερό παιδί του υποδένδου με ρίζα το Ο (ενα επίπεδο παραπάνω δλδ)
Εφόσον έχεις λάβει το αριστερό παιδί πας στο δεξί και αφού είναι φύλο το παίρνει δλδ το :Χ
Επισκέπτεσαι την ρίζα του υποδένδρου και παιρνεις το : Ο
Και στη συνέχεια επισκέφτεσαι το διξί παιδί -υποδένδρο  :
            Ι
       Ε      Π
Επειδή το  πας πρώτα αριστερά και παίρνεις το : Ε
μετά δεξιά και παίρνει το : Π
και μετά στη ρίζα και παίρνεις το : Ι
κ.ο.κ

Αυτο που κανω εγω γιατι ειναι λαθος?
Μηπως δεν ειναι πληρες?
Τι φταιει?

[Ariel]

Ερώτηση:  Δίνεται το παρακάτω τμήμα ενός αλγορίθμου:

int i = 1;
while ( i <= n ) {
    for (int j = 1; j <= n; j = j * 2 ){
        x = x - 2 ;
}
            i++;
}

και η απάντηση δεν είναι n²...

Μήπως θυμάσαι τις άλλες επιλογές???
Νομίζω θα πρέπει να είναι n*logn λόγω του δεύτερου βρόχου


Ερώτηση:

Δίνεται το παρακάτω τμήμα ενός αλγορίθμου:

int x = 1;
for (int i = 1; i <= n; i++) {
    for (int j = n; j >=i; j--){
        x /= n;
    }
}

Ποια τάξη O(g(n)) χαρακτηρίζει πιο πιστά την πολυπλοκότητα του παραπάνω τμήματος αλγορίθμου;

Ο(n²) ????

[cordou4]

ρε παιδιά πως κανουμε επανεξεταση στην αυτοαξιολογηση?
αν παρεις πανω απο 5 λεει "Η εξέταση έχει ολοκληρωθεί επιτυχώς" και δεν μπορω να κανω αυτοαξιολογηση
αν παρεις κατω απο 5 και πατησεις επανεξεταση γραφει προσπαθειες για επανεξεταση : 1 αλλα και παλι δεν μπορω να κανω επανεξεταση

[ampoulog]

Τι να σου πω με έχει μπερδέψει πάρα πολύ .

Πάντως σχετικά με το NEOΣΑΡΧΙΕΠΙΣΚΟΠΟΣ που ρώτησες παραπάνω  μόλις το έκανα και βγαίνει κανονικά.

Η μέθοδος που ακολούθησα ήταν :
 1. μετρησα τα γράμματα της συμβολοσειράς και εφτιαξα δυαδικό δένδρο τόσων θέσεων.
 2.Έκανα προδιατεταγμένη διάσχιση για να τοποθετήσω τα γράμματα ¨
- επισκεψη στη ρίζα (Βάζεις το Ν)
-Επισκεψη του αριστερού υποδένδρου (βάζεις το Ε)
---Μετα θεωρείς ότι το Ε είναι ριζα του υποδένδρου
---και επισκέφτεσαι το αριστερο υποδένδρο όπου βάζεις το Ο
Αφού τελείωσεις με τα υποδενδρα αυτά
επισκέφτεσαι τα δεξια υποδένδρα
οπότε προκύπτει το παρακάτω :
            

                                                   Ν
                                 Ε                                  Ι
                      Ο                  Ι                Σ               Π
             Σ              Χ      Ε       Π       Κ    Ο        Ο     Σ
          Α  Ρ
(Σορρυ που δεν το κάνω σε κάποιο πρόγραμμα για να φανεί καλύτερα άλλα δεν έχω πολύ χρόνο . αν δεν το καταλάβεις πες μου και θα το φτιάζω σε κανένα word το βράδυ , απλά προσπάθησε να τα βάλεις στο χαρτί όπως στα δίνω).

Μετά κάνεις μεταδιατεταγμένη Διάσχιση
δηλαδή επισκέπτεσαι πρώτα το αριστερό παιδί μετά το δεξί και τέλος την ρίζα .

Αρχικά λοιπόν πας στο κάτω αριστερά παιδί και παίνεις το :   Α
Μετά στο κάτω αριστερά υποδένδρο και στο δεξί παιδί και παίρνεις το : Ρ
Επισκέπτεσαι την ρίζα του υποδένδρου αυτού και παίρνει το :  Σ
Θεωρείς την ρίζα του παραπάνω υποδέδρου σαν αριστερό παιδί του υποδένδου με ρίζα το Ο (ενα επίπεδο παραπάνω δλδ)
Εφόσον έχεις λάβει το αριστερό παιδί πας στο δεξί και αφού είναι φύλο το παίρνει δλδ το :Χ
Επισκέπτεσαι την ρίζα του υποδένδρου και παιρνεις το : Ο
Και στη συνέχεια επισκέφτεσαι το διξί παιδί -υποδένδρο  :
            Ι
       Ε      Π
Επειδή το  πας πρώτα αριστερά και παίρνεις το : Ε
μετά δεξιά και παίρνει το : Π
και μετά στη ρίζα και παίρνεις το : Ι
κ.ο.κ

Αυτο που κανω εγω γιατι ειναι λαθος?
Μηπως δεν ειναι πληρες?
Τι φταιει?

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