[Δομές δεδομένων]Απορίες στις ασκήσεις 2011/12

[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 με προσοχή στα ονόματα των αρχείων!

[Πληροφορίες Καθηγητών]

Πληροφορίες Καθηγητών

[Lampros]

Α οκ...ένιωσα τώρα..

[afroditeschild]

Υπάρχει κάποιος καλός άνθρωπος που να έλυσε το 3ο θέμα του 2011?

Παλέυω τόσην ώρα και ακόμα τίποτα

οταν εισαγουμε τα κλειδια χωρις να παρουμε υποψιν την προταιρεοτητα το δεντρο θα ειναι ετσι οπως το δειχνει μονο που στα αριστερα του
(4,11)ως παιδι του  θα μπει το (3,5) ,στα αριστερα του (9,14) σαν παιδι του θα μπει το (8,21) και αριστερα απο το (16,7) θα μπει το (12,9)
οκ με αυτο?

Γιατί τους νέους κόμβους τους βάζεις έτσι?Γιατί ας πούμε το [8,21] να μην μπεί αριστερά απο το (16,7)?

Aρχικα το 8,21 θα μπει και θα παει απο τα αριστερα γτ ειναι μικροτερο του 11,4 μετα κατεβαινει και τσουπ βλεπει το 6,6 απε που να παει???θα παει απο τα δεξα του 6,6 γτ ειναι μεγαλυτερο απο 6,6!!!!!!!!!!!!!!!!

[afroditeschild]

ποτε η πολυπλοκοτητα εκφραζετε με το log(n) δεν μπορω να το καταλαβω?
δλδ σε ποιες περιπτωσεις ο κωδικας μας δειχνει τετοια πολυπλοκοτητα????

[NXSnow]

Για υπολογισμό πολυπλοκότητας ξέρει κανείς πως να το γράψω αυτό σε σειρά?

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

[NXSnow]

ποτε η πολυπλοκοτητα εκφραζετε με το log(n) δεν μπορω να το καταλαβω?
δλδ σε ποιες περιπτωσεις ο κωδικας μας δειχνει τετοια πολυπλοκοτητα????

Μαλλον σε αυτό που πόσταρα από πάνω. Μου το εβγαλε σωστό οτι ειναι O(logn) αλλα δεν ξερω πως να το αποδείξω.

[NXSnow]

Εγω το εχω βγαλει ετσι...


                                              (11,4)
                                            /            \
                                      (3,5)              (16,7)
                                            \             /
                                            (6,6)      (12,8)
                                            /     \
                                     (4,11)      (9,14)
                                                   /
                                             (8,21)

Ελπιζω να ειναι σωστο...

και εγω αυτο ακριβως εβγαλα

Εγώ το 4,11 το άφησα κάτω από το 3,5 και νομίζω έτσι είναι σωστό. δεν χρειάζετε να πάει από την άλλη.

[Lampros]

Εγώ το 4,11 το άφησα κάτω από το 3,5 και νομίζω έτσι είναι σωστό. δεν χρειάζετε να πάει από την άλλη.

Μα δεν γίνεται να μείνει εκεί το 4,11 αφού όταν το περιστρέψεις πάει στο 6,6 αναγκαστικά.

Είναι ιδιότητα της περιστροφής

[NXSnow]

Εγώ το 4,11 το άφησα κάτω από το 3,5 και νομίζω έτσι είναι σωστό. δεν χρειάζετε να πάει από την άλλη.

Μα δεν γίνεται να μείνει εκεί το 4,11 αφού όταν το περιστρέψεις πάει στο 6,6 αναγκαστικά.

Είναι ιδιότητα της περιστροφής

Το εσωτερικό παιδί αλλάζει, όχι το εξωτερικο. Κάνει μια περιστροφή το 4 με το 5 και το 4 είναι πλέον εξωτερικο. Αρα δεν αλλάζει.

[afroditeschild]

το 4,11 το εβαλες αριστερα του 3,5 δλδ???αν εκανες  αυτο ειναι λαθος γτ απο τα αιστερα του 3,5 πρεπει να εχουμε τιμες μικροτερες του 3

[NXSnow]

το 4,11 το εβαλες αριστερα του 3,5 δλδ???αν εκανες  αυτο ειναι λαθος γτ απο τα αιστερα του 3,5 πρεπει να εχουμε τιμες μικροτερες του 3

Καλα λες εκεί έκανα το λάθος και το συνέχισα γιατί δεν κοιτούσα τους αριθμούς.  
Όταν έβαλα το 3,5 το έβαλα δεξιά του 4,11.

[nikos912000]

Για υπολογισμό πολυπλοκότητας ξέρει κανείς πως να το γράψω αυτό σε σειρά?

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

Για το συγκεκριμένο, δεν μπορείς να χρησιμοποιήσεις σειρά...Αλλά κατευθείαν μπορείς να πεις ότι ο βρόχος έχει logn πολυπλοκότητα...Αυτό συμβαίνει γιατί εσύ εκτελείς "κομμάτια" της ακολουθίας (1,2,...,n) και όχι ολόκληρη...πχ θα εκτελεστεί για j=1,2,4,8,16...Άρα διαμερίζεις κατά κάποιο τρόπο την ακολουθία που έχεις (κατ' αυτόν τον τρόπο βγαίνει συνήθως η λογαριθμική πολυπλοκότητα)...Ρώτησα τον Αντώνη και μου 'πε πως όντως έτσι βγαίνει...!

[afroditeschild]

στα θεματα του 2008 στο 6ο ερωτημα με το σωρο τι διαγραμμα θελει ακριβως ??????

[afroditeschild]

και κατι ακομα τι πολυπλοκοτητα εχει το παρακατω??
for i=1 to n
  for j=1 to i
   for k=1 to j*j
     S=S+1

[Lampros]

και κατι ακομα τι πολυπλοκοτητα εχει το παρακατω??
for i=1 to n
  for j=1 to i
   for k=1 to j*j
     S=S+1

n^4

[elen//]

Βρειτε την πολυπλοκοτητα
x=1;
for i=0: <10
for j=n: >=0: j--
for k=0: <n
x+=n;
(Απ:n ^2)

Σ' αυτό το παράδειγμα δεν θα πρεπε να είναι η πολυπλοκότητα 10n² και όχι n² σκέτο;

αυτή η πολυπλοκότητα με βάση ποιά αθροίσματα βγαίνει?