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

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

[12:00-13:30]

Η γραμματεία είναι ανοιχτή καθημερινά 12:00-13:30

[ampoulog]

Δίνεται το παρακάτω τμήμα ενός αλγορίθμου.
For i=1 To n Do
    For j=1 To i Do
        For k=1 To j*j Do
            S = S + 1
Ποια είναι και γιατί η  O(g(n))  του παραπάνω τμήματος αλγορίθμου;

[SolidSNK]

Είναι παραπάνω η τάξη. Η πρώτη επανάληψη ναι μεν σου λέει, το εσωτερικό θα γίνει ν φορές, αλλά οι άλλες 2 είναι εξαρτόμενες από τη τιμή του n. Εποπτικά, βλέπω θα ναι n^4 (ή με λιγότερες πιθανότητες ν^3 ).

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

[SolidSNK]

Α και έχω μια απορία στις σημειώσεις. Αυτές οι σημειώσεις τι είναι? Έχει μέσα για πολυπλοκότητα? Είναι ΜΟΝΑΧΑ αποκλειστικά αυτά που είναι στο ethmmy?

[ampoulog]

Είναι παραπάνω η τάξη. Η πρώτη επανάληψη ναι μεν σου λέει, το εσωτερικό θα γίνει ν φορές, αλλά οι άλλες 2 είναι εξαρτόμενες από τη τιμή του n. Εποπτικά, βλέπω θα ναι n^4 (ή με λιγότερες πιθανότητες ν^3 ).

Αυτό έλεγα και εγώ αλλά όταν το β΄ζω στην αυτοαξιολόγηση το μετράει ως λάθος .

[SolidSNK]

Βρε μπας και είναι n^5    Γενικά πρέπει να το πάρεις μαθηματικά ...

[SolidSNK]

Αν δεν είχαμε το μέσα-μέσα βρόχο θα μιλούσαμε για τάξη ν^2 πάντως, αυτό είναι σίγουρο.

[ampoulog]

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

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

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

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

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

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

[2bleDooR]

ampoulog ωραιος φιλε,εγω το καταλαβα οπως το εγραψες!
Επισης στα ιδια θεματα μπορειτε να εξηγηστε το θεμα με την ΔΙΑΠΛΟΚΗ ?? Plz    (καπου στη μεση τη διαδρομης το χανω  )

[ampoulog]

Στο θέμα 10 β όταν λέει ότι η Array χρησιμοποιεί την Element τι εννοεί ?

[~GiA~]

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

n*(1+2+3...+n)*(1^2+2^2+...+n^2)

????

ετσι το σκεφτικα

[ampoulog]

Αυτό κάνω και εγώ και η τάξη μου βγαίνει Ο(n^4) . Αλλά μου το μετράει ως λάθος .

[ampoulog]

Κάτι άλλο
Μπορεί κάποιος να μου εξηγήσει τον αλγόριθμο ΚΜP και ΚΜP match .
Τι ακριβώς κάνουμε εκεί , πως λειτουργεί ??

[gerdi]

Λοιπόν αλγόριθμος Boyer-Moore ακριβώς πριν τον κατακερματισμό.Γιατί στο παράδειγμα που έχει στις σημειώσεις του Μήτκα τελειώνει στα 15 βήματα? Κανονικά δεν θα έπρεπε πολύ πιο νωρίς??

[ampoulog]

Δεν κατάλαβα τι εννοείς .
Σε πόσα βήματα θα έπρεπε να τελειώνει ???

[gerdi]

Αν παρατηρήσεις μετά το 3ο τα εξετάζει 1-1 δλδ 3+12=15
Κανονικά θα έπρεπε σε πολ'ύ λιγότερα βήματα να τελιώνει αφού κάθε φορά που ένα στοιχείο του Τ δεν εμπεριέχεται στο πατερν όλο το πατερν μεταφέρεται 1 στοιχειο μετά από αυτό.Οπως γίνεται αν δεις στα παραπάνω βήματα με το Η(2-3)