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

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

Για ανανέωση (ή προσθήκη νέου) avatar, πρέπει η μεγαλύτερη διάσταση της εικόνας να είναι 110 pixels.

[TED]

ναι, server based είναι, η php υπολογίζει τα αποτελέσματα, αλλά οι λύσεις πάλι υπάρχουν (who knows why...)

tested

[SolidSNK]

δε βλέπω τπτ τέτοιο. Για ρίξε κώδικα...

και δεν ίναι php , είναι jsp

[TED]

Δίνεται ταξινομημένος πίνακας με τα εξής στοιχεία: 3, 5, 6, 10, 18, 19, 20, 23, 27, 74, 99 Να βρείτε το συνολικό αριθμό των συγκρίσεων που απαιτούνται για την εύρεση του 99 με γραμμική αναζήτηση.

Code:

<input type="hidden" value="11" name="qstAnswer1"/>

[constantinos]

diavazw diavazw diavazw posts k den vlepw tpt gia ton algoruthmo KMP k mia teliki apantisi gia tous array pinakes k tis lekseis..kserei kaneis??pls

[SolidSNK]

yeah όντως έτσι είναι , στις υπολογιστικές! Στις πολλαπλής όπως βλέπω δεν...

[TED]

KMP αλγόριθμος ταξινόμισης

Εξετάζει το πρότυπο που έχουμε, ωστε να βρεί κάποια κομμάτια που επαναλαμβάνονται. Πιο συγκεκριμένα:

a b a b a c
0 0 1 2 3 0

ξεκινάει από το 2ο χαρακτήρα, και όταν βρεί τον ίδιο με τον πρώτο ξεκινάει να μετράει. Όσο οι επόμενοι χαρακτήρες ακολουθούν την ίδια σειρά με τους αρχικούς ανεβαίνει στο μέτρημα. Άν όχι, κατα κάποιον τρόπο μηδενίζει.

Παράδειγμα από το ethmmy:
χ α χ ο χ α
0 0 1 0 1 2


Αφού το κάνει αυτό, εξετάζει το string που θέλουμε να ψάξουμε ώς εξής:

τοποθετεί την αρχή του προτύπου στην αρχή του string, και εξετάζει ένα προς ένα τα γράμματα. άν τα βρεί όλα σταματάει την αναζήτηση.

Άν κάποιο από τα γράμματα δεν είναι ίδιο, τότε τοποθετεί τον πρώτο χαρακτήρα του προτύπου ΠΟΥ ΕΙΝΑΙ ΙΔΙΟΣ με αυτόν στον οποίο είχε σταματήσει στο string. Αν δεν υπάρχει, τότε ξεκινάει από την αρχή.

Ο αλγόριθμος στη σελίδα 7-6 βοηθάει πολύ...

[TED]

yeah όντως έτσι είναι , στις υπολογιστικές! Στις πολλαπλής όπως βλέπω δεν...

Ελπίζω να μην ισχύει, αλλά νομίζω πως βλέπω αρκετά λάθη στις απαντήσεις τους...

[TED]

Για τους array πίνακες και τις λέξεις:

στο ethmmy στις απαντήσεις λέει για το 6χ6 οτι το Ν πρέπει να είναι 11. Ωστόσο αυτό είμαι σίγουρος πως είναι λάθος, καθώς στους 11 χαρακτήρες η μορφή με τις συντεταγμένες χρειάζεται 3Ν = 33 byte ενώ η μορφή με τον πίνακα bit χρειάζεται Ν + 6*6/4 = N + 9 = 20 byte...

Νομίζω ότι τα αποτελέσματα τα βγάζουνε μόνο από το 6*6...

ps:
ισχύουν οι τύποι:

για την κανονική αποθήκευση:   n*m (είναι όλα χαρακτήρες)
για την αποθήκευση με πίνακα bit: Ν + n*m/w (ένας πίνακας με χαρακτήρες μεγέθους Ν και ένας με bits μεγέθοθς n*m)
για την αποθήκευση με συντεταγμένες: 3Ν (3 χαρακτήρες για κάθε μη μηδενικό στοιχείο)

[megapixel]

Γιατι μου το βγαζει λαθος??????????

3Ν*4 < Ν*4 + 6*6 =>  12Ν<4Ν+36 => 8Ν<36 => Ν<4,5 Αρα Ν=4!

[TED]

Γιατι μου το βγαζει λαθος??????????

3Ν*4 < Ν*4 + 6*6 =>  12Ν<4Ν+36 => 8Ν<36 => Ν<4,5 Αρα Ν=4!

τα γράφεις πολύ σωστά, έτσι πρέπει να βγαίνει. Αυτοί υπολογιζουν από το n x m...

[megapixel]

Εδω το O(n) δεν ειναι το σωστο?
Αφου στο 2ο βροχο θα κανει απο 1 εως n αλλα με βηαμα j^2 αρα λιγοτερες φορες απο n
                                                        n
αρα συνολο=n*(κατι λιγοτερο απο n)=/  ή
                                                       \n^2

[MARIOS]

re seis ta dentra AVL einai simantika????Den ta polikatalaba

[megapixel]

Εδω ποιο ειναι το σωστο? (αλγοριθμος ευθειας επιλογης)

Πηρα 0,38/1 δλδ 3 σωστα.

???

[TED]

Μήπως θα έπρεπε να είναι:

χ α χ ο χ α
0 0 1 0 2 1     ????

Κάτσε να το κάνουμε αναλυτικά...

χ α χ ο χ α

   1   2   3   4   5   6   7  
i | 1  2   3   3   4   5   6
j | 0  0   1   0   0   1   2

1: f(1) = 0; i=2
2: f(2) = 1; i=3; j=1
3: j=0;
4: f(3)=0; i=4;
5: f(4)=1; i=5; j=1;
6: f(5)=2; i=6; j=2;

το f(0) μπαίνει από την αρχή 0 απ' ότι κατάλαβα...
ενδέχεται βέβαια να μην το έχω καταλάβει καλά, οπότε διορθώστε με :p

[ippocrates9]

Γιατι μου το βγαζει λαθος??????????

3Ν*4 < Ν*4 + 6*6 =>  12Ν<4Ν+36 => 8Ν<36 => Ν<4,5 Αρα Ν=4!

τα γράφεις πολύ σωστά, έτσι πρέπει να βγαίνει. Αυτοί υπολογιζουν από το n x m...

Ρε παίδες ο πίνακας που έχει μόνο 0 και 1 μέσα γιατί να μην μετριέται όπως και οι άλλοι? Το 0 και το 1 δεν είναι ακέραιοι? Γιατί να μην πιάνουν και αυτοί 4 bits?
Με αυτή τη λογική η εξίσωση είναι 3Ν*4 < Ν*4 + 6*6*4