THMMY.gr

Τις σωστές απαντήσεις από την αυτοαξιολόγηση πού μπορούμε να τις δούμε;

+1?

Ποια αυτοαξιολογηση ρε?

@hatzf: Υπάρχει ένα πεδίο στο eTHMMY αν κάνεις join στο μάθημα με το νέο πρόγραμμα σπουδών (5ο εξάμηνο δηλαδή) που είναι η αυτοαξιολόγηση! :)


Επίσης, δεν νομίζω να μπορούμε να δούμε τις απαντήσεις..
Αλλά αφού είναι ανακυκλώμενα τα θέματα, μπορείς εύκολα να βρεις ποιο είναι το σωστό και μετά να σπαζοκεφαλιαστείς γιατί είναι αυτό... :P

Σε μένα δε γίνεται επανεξέταση, μου βγάζει "απαγορεύεται η πρόσβαση".

      Καταρχάς, νομίζω πως ο τύπος υπολογισμού του μέγιστου αριθμού κόμβων στις σημειώσεις (4a-6) είναι λάθος. Μάλλον θα έπρεπε να είναι: n=(d^h+1-1)/(d-1) και όχι n=(d^h-1-1)/(d-1). Κάνω λάθος σε αυτό;

στις δικες μυο σημειωσεις βλεπω  n=(d^h-1)/(d-1)

Που και πάλι είναι λάθος, γιατί αν πάρουμε ένα τετραδικό δένδρο με ύψος h=2, θα έχει το πολύ 1 ρίζα, 4 παιδιά και 16 εγγόνια, αυτό μας κάνει 21 κόμβους. Ενώ (4²-1)/(4-1)=5. Από την άλλη (4²⁺¹-1)/(4-1)=21. Η σωστή σχέση λοιπόν πρέπει να είναι: n=(d^h+1-1)/(d-1).

Περασα και τις 2 εξετασεις και δε μπορω να επαναεξεταστω...Θελω να απαντησω και σε αυτες που εκανα λαθος! >:(

Για τουσ αραιούς πίνακες π.χ. 5*6 πως θα βρούμε τη μέγιστη τιμή του Ν????
Εγω πήρα τις ανισώτητες 3Ν<Ν+30/4 και την 3Ν<Ν+6+30/4 και βγαίμει η τιμή 3. αλλα δεν μου το βγάζει σωστό η αυτοαξιολόγηση.
 :-\ :-\ :-\

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

Ναι μπράβο κι εγώ το ίδιο!!!!!
Ξέρει κανείς το σωστό;;;;;

Αυτά είναι από τα φυλλάδια;

εγώ πατεντιάρικα

3*Ν < Χ*Υ

http://www.thmmy.gr/smf/index.php?topic=17081.msg342249#msg342249 (http://www.thmmy.gr/smf/index.php?topic=17081.msg342249#msg342249)

      N=3 και Ν=4 είναι τα σωστά, εμένα μου τα πήρε και τα δυο για σωστά. Σε κάτι άλλα υπήρχε πρόβλημα.
      Διευκρινίζει στην ερώτηση ότι η ρίζα είναι στο επίπεδο μηδέν. Αφού λοιπόν το επίπεδο είναι και το ύψος άρα το ύψος δένδρου με μόνο τη ρίζα είναι h=0. Δεν μπορούμε κατά τη γνώμη μου να την πάρουμε ίση με 1. Και άντε σε μια ερώτηση δικαιολόγησης δεν παίζει ρόλο αυτό αλλά σε πολλαπλής επιλογής υπάρχει πρόβλημα.

Κιεγώ αυτά βάζω αλλα δεν μου τα παίρνει για σωστα...
Στο ΑΘΛΟΣ η σωστή απάντηση είναι το Σ????

Αnmavrid μήπως με αντέγραφες; ;)

Λες??? Μάλλον εσυ με αντέγραφες!! :P :P
 Η εχουμε κοινή λογική πορεία..
Τελικά το Σ είναι το σωστό???? 8)

Δεν τα δέχεται ως σωστά..Αυτα βάζω και γω..

      Σου λέω ότι σε μένα τα δέχτηκε. Αν θέλεις μπορώ να προσκομίσω και στοιχεία.  ;D

Βρε το θέμα ειναι οτι όταν τα απαντάω μου τα βγάζει λάθος..και τρελαίνομαι...Πιστεύω και γω οτί αυτά είναι τα σωστά.

Μήπως έχει κανένα bug το σύστημα? Grin

Το ίδιο έπαθα και εγώ

       Σύμφωνα με νεότερες πληροφορίες οι σωστές απαντήσεις είναι Ν=9 και Ν=11, 3Ν<30 και 3Ν<36, για να συμφέρει η αποθήκευση αυτή σε σχέση με την απλή αποθήκευση ολόκληρου του αραιού πίνακα.

Ξέρει κανείς ποία είναι η λύση της άσκησης με τα αστεράκια??

Αν θυμάμαι καλά το καμία από τις παραπάνω είναι η απάντηση
βρίσκεις το Α(4), Α(3), Α(2) και Α(1)
και βλέπεις οτι δεν ισχύει καμία σχέση

Ξερει κανεις την απαντηση με τα δυαδικα δεντρα και τον τροπο διασχισης και για το μεταδιατεταγμενο και για το προδιατεταγμενο???

http://en.wikipedia.org/wiki/Postorder

 
Τα μεγάλα πνεύματα συναντιώνται. Ναι το Σ είναι το σωστό.

Ευχαριστω!

Οταν εννοουμε διαφανειες τι εννοουμε ρε παιδια ?
τις σημειωσεις του μιτκα ή εκεινες στο αλεχαντερ που ειναι ιδιες με τις σημειωσεις..ΔιαΦΩΤΗστε με!!!!

KAI ασκηση με τα αστερακια στην αυτοαξιολογηση πως βγαινει????
πλζζζζζζζζζζζζζζζζζζ

Μπορει να μου πει καποιος τι σημαινει αυτη η εντολη σε μια λιστα?
L.next.next.next ← L.next.next

Ο τέταρτος κόμβος παίρνει την τιμή του τρίτου κόμβου...νομίζω... :???:

Σε ένα δυαδικό δέντρο αναζήτησης, όταν διαγράφουμε ένα κλειδί που έχει δύο παιδιά, ποιος είναι ο διάδοχος?

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

Να θέσω κι εγώ την ερώτηση μου: Ποιος είναι ο ελάχιστος αριθμός κόμβων που μπορεί να έχει ένα πλήρες τετραδικό δέντρο ύψους 6. Θεωρούμε πως η ρίζα είναι το επίπεδο 0...ποιά είναι η απάντηση?γίνεται ένα πλήρες δέντρο να έχει ελάχιστο αριθμό κόμβων και μέγιστο ή εγω εχω καταλάβει κάτι λάθος??

Στο βιβλίο λέει οτι πας στο δεξί παιδι και συνεχίζεις στο αριστερό παιδί,πάλι στο αριστερό παιδί και συνέχεια στο αριστερά παιδιά εαν υπάρχουν, μέχρι το τελευταίο αριστερό και βάζεις αυτό.έαν δεν εχει αριστερό παιδί το πρώτο δεξι, βάζεις το δεξί.
καταλαβεσ???? ;)
δεν μπορούσα να το εξηγήσω καλύτερα... :-[

Εφόσον είναι πλήρες θα είναι ο μέγιστος αριθμός κόμβων νομίζω...και το βρίσκεις από τον τύπο. ;)

 Αυτός ο παλιο-χούφμαν με τα Β Α Λ Ε Ν Τ Ι πώς γίνεται;
100 φορές τον έκανα και όλο λάθος μου το βγάζει!!!! >:( >:( >:( >:(

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

Ρε παιδια με τις πολυπλοκοτητες τι γινεται τελικα,βρισκω τις απαντησεις σε ολα εκτος απο τις ερωτησεις για πολυπλοκοτητες!

1)

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


2)

For i=1 To n Do
    For j=1 To i Do
        For k=1 To j*j Do
            S = S + 1

Το 2 ειδικα το αναλυσαμε παρα πολυ και πολλοι αλλα δε βρηκαμε λυση, ξερει κανεις στα σιγουρα να πει?

Παιδιά, μήπως γνωρίζει(έχει καταλάβει κανείς) πώς στην σελίδα 8-7 υπολογίζεται η f(j) (συνάρτηση αποτυχίας) ???? Επίσης στην σελίδα 10-2 δεν μπορώ να καταλάβω απ' το σχηματάκι την Ταξινόμηση Εισαγωγής..Πώς δουλεύει? Με ποιά λογική???

Αυτα ακριβως τα 2 ειναι μεγαλα ταμπου και για μενα αλλα τετοια ωρα!

Το δευτερο μου φαινεται ειναι n^4

έχουμε γράψει σχετικά με αυτό στο topic με link  http://www.thmmy.gr/smf/index.php?topic=17604.0

Αν υπάρχουν παρατηρήσεις είναι ευπρόσδεκτες

Κάποιος?????????? :???:

Ξέρει κανείς την απαντηση?     ----->
 Ερώτηση: Δίνεται ένας αραιός πίνακας ακεραίων διάστασης 4 x 10. Αν Ν είναι ο αριθμός των μη μηδενικών στοιχείων του πίνακα, πόση θα είναι η διαφορά σε λέξεις της καλύτερης με τη χειρότερη μέθοδο αποθήκευσης του πίνακα; Θεωρείστε ότι για την αποθήκευση ενός ακεραίου χρησιμοποιούνται 8 bits.

drfeelgood η ερώτηση πρέπει να είναι λάθος. Δε μιλάει για ποιο Ν θέλει να γίνει η δουλεία. Για διαφορετικά Ν βρίσκουμε διαφορετική καλύτερη μέθοδο. Πρέπει να δωθεί το Ν για να μπορέσουμε να δώσουμε απάντηση. Η τουλάχιστον αυτό κατάλαβα εγώ.

Επίσης το σύστημα αξιολόγησης έχει λάθος στην παρακάτω ερώτηση :

Ερώτηση:

Δίνεται το παρακάτω τμήμα ενός αλγορίθμου.
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)) χαρακτηρίζει πιο πιστά την πολυπλοκότητα του παραπάνω τμήματος αλγορίθμου;


Δε δέχεται ως σωστή καμία από τις απαντήσεις που μας προτίνει.
Νομίζω πως έχει Ο (n^4). Κάνω λάθος????

Πρεπει τελικα να ειναι Ο(n^4)

Συμφωνα με το παραδειγμα των σημειωσεων:

For i=1 To n Do==>θα εκτελεστει n φορες

For j=1 To i Do==>θα εκτελεστει  1+2+3+4...+n φορες..Αυτη η σειρα ισουται με (n^2+n)/2

For k=1 To j*j Do θα εκτελεστει 1+4+9+...+n*n..Aυτη η σειρα ισουται με [n*(n+1)(2n+1)]/6

S = S + 1==>θα εκτελεστει μια φορα

Εμεις κραταμε μονο το τελευταιο πολυωνυμο [n*(n+1)(2n+1)]/6 που θα ειναι ο συνολικος αριθμος των εκτελεσςων της S=S+1.Aρα O(n^3) το σωστό!


Αλλα αυτος λεει δεν θελει την ακριβη πολυπλοκοτητα αλλα αυτη που αντιπροσωπευει  πιο σωστα τον αλγοριθμο!Συνεπως θα ναι η Ο(n^4) η οποια προσεγγιζει πιο πολυ απ τις αλλες την Ο(n^3)!

O(n³) είναι...

Η εξήγηση είναι όπως λέει ο Bo@rD-RiDeR απλά κρατάς μόνο το τελευταίο

Στην ανάλυση συμπεριλαμβάνονται και οι βρόγχοι i,j...

Το δίνει σε πολλαπλή επιλογή. Για  Ν = 2 δεν ισχύει αυτό που λες. Ο καλύτερος τρόπος αποθήκευσης είναι σε τριάδες αριθμών.

Ξέρει κανείς τi μπορούμε να έχουμε ανοιχτό στις εξετάσεις?????

http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm

Check και αυτό για όσους δεν κατάλαβαν τα δέντρα. Είναι κορυφή. Έχει και animation  :)

Πάντως σχετικά με την ερώτηση που αφορούσε αραιούς πίνακες υπήρχε λάθος στην αυτοαξιολόγηση. Για παράδειγμα στην ερώτηση που τέθηκε για το ΄΄Για τουσ αραιούς πίνακες π.χ. 5*6 πως θα βρούμε τη μέγιστη τιμή του Ν????
Εγω πήρα τις ανισώτητες 3Ν<Ν+30/4 και την 3Ν<Ν+6+30/4 και βγαίμει η τιμή 3. αλλα δεν μου το βγάζει σωστό η αυτοαξιολόγηση.΄΄ το σωστό είναι το 3, απλά ήταν λάθος περασμένο στην αυτοαξιολόγηση. Έστειλα mail στους μεταπτυχιακούς και με ενημέρωσαν για το πρόβλημα.Οπότε δεν υπάρχει λόγος ανησυχίας.

Εισαι σιγουρος?Οι περσινοι οταν προσπαθουσαν να το λυσουν οπως το λυσες ο ψωμοπουλος τους ειπε οτι δεν ειναι αυτος ο σωστος τροπος σκέψης!!παραθετω..



δλδ δεν λυνεις την εξισωση 3Ν<Ν +(n*m)/w  αλλα την 3N<(n*m)
εν προκειμένω στον 5*6 η σωστη απαντηση ειναι N<10 αρα N=9

Σε mail μου η κα Νικολαΐδου Παρασκευή μου απάντησε ότι υπήρχε λάθος στην αυτοαξιολόγηση και μετά από την επισύμανση θα το διόρθωναν. Οπότε μάλλον για αυτόν το λόγο σε κάποιους έβγαζε ότι είναι σωστό και σε κάποιους άλλους ότι είναι λάθος. Πάντως αν παρακολουθεί τη συζήτηση κάποιος από τους μεταπτυχιακούς ας μας δώσει και μια πιο σίγουρη απάντηση. Δεν θέλω να πάρω κανέναν στο λαιμό μου.

καποιος που να ξερει?

1)Ερώτηση: Έστω ότι θέλουμε να αναζητήσουμε το πρότυπο P = χαχοχα στη συμβολοσειρά S = χαχοχχαχοοχαχοχα Χρησιμοποιώντας τον αλγόριθμο KMP (Knuth-Morris-Pratt). Ποιος είναι ο συνολικός αριθμός των συγκρίσεων που θα χρειαστεί να εκτελεστούν; Θεωρείστε ότι ο αλγόριθμος σταματάει την πρώτη φορά που ανακαλύπτει το πρότυπο P.

Βαζω 19 και βγαζει λαθος


2)Ερώτηση: η την συνάρτηση , να αποθηκεύσετε σε πίνακα κατακερματισμού 11 θέσεων τα παρακάτω κλειδιά με τη σειρά που δίνονται: Το πρώτο στοιχείο του πίνακα θεωρείται ότι έχει δείκτη 0. Η επίλυση των συγκρούσεων να γίνει με τη μέθοδο της τετραγωνικής εξέτασης με c = 1. 

Γενικώς οταν δινει τετραγωνική εξεταση και μια διευθυνση(adress) ειναι καλλυμενη τοτε παμε  στην (adress+c) kai an ειναι κ αυτη στην (adress +4c)υστερα?  Πως λειτουργει ο αλγοριμοθς? στη γραμμικη ξερουμε οτι το adress ειναι μεταβλητο και το h'(k) σταθερο..εδω ειναι αναποδα?

Γιατι οταν παω να επανεξεταστω μου βγαζει δεν επιτρεπεται η πρόσβαση?Σας βγαζει εσας τπτ?...τι μονο 2 εξετασεις κ ξεμπερδεψαμε? :P

Απλά πρέπει να στείλεις mail στον Ψωμόπουλο για να στο ανοίξει και να μπορέσεις να ξανακάνεις το τεστ.Οι ερωτήσεις θα είναι διαφορετικές από τα πρώτα τεστ που έκανες.

α μάλιστα thanks!

Ερώτηση: Δίνεται ένας αραιός πίνακας ακεραίων διάστασης 4 x 10. Αν Ν είναι ο αριθμός των μη μηδενικών στοιχείων του πίνακα, πόση θα είναι η διαφορά σε λέξεις της καλύτερης με τη χειρότερη μέθοδο αποθήκευσης του πίνακα; Θεωρείστε ότι για την αποθήκευση ενός ακεραίου χρησιμοποιούνται 8 bits.

ξερει κανεις πως γινεται το παραπανω???????????????????????

Λογικά η χειρότερη είναι να αποθηκευθεί ο πίνακας σε 4*10=40 λέξεις, δηλαδή ακόμα και τα μηδενικά να πιάνουν από μία λέξη, και ο καλύτερος θα είναι 3*Ν λέξεις ή (Ν+ 40/8) =(Ν+5) λέξεις, Άρα, εξαρτάται από το Ν. Αν Ν>2,5, δηλαδή Ν>=3, τότε συμφέρει ο 2ος καλύτερος τρόπος, αλλιώς ο 1ος (3*Ν λέξεις).
Η διαφορά θα βρίσκεται αφαιρώντας τα

thanks

ΑΑΑΑΑΑΑΑ
και κατι ακομα......Ερώτηση:

Παρακάτω δίνεται ένας πίνακας χαρακτήρων μαζί με τη συχνότητα εμφάνισής τους. Αν δημιουργήσουμε τον βέλτιστο κώδικα Huffman για τους παραπάνω χαρακτήρες, τότε ποιο θα είναι το μήκος (σε bits) της αναπαράστασης του χαρακτήρα “Α” στον κώδικα Huffman;

Χαρακτήρας:
   Χαρακτήρας:
   

Β   Α   Λ   Ε   Ν   Τ   
1    1   2   3    11  12

ΒΟΗΘΕΙΑ
PLEASE!!!!!!!!!!!!!!!!!!!!!!!!!!Ι
οταν εχουμε στον κωδικα huffman 2 ιδιους κομβους ( με τον ιδιο αριθμο!!!)....τι κανουμε???????

προσθετεις τα μικροτερα κ αν ειναι ιδια παλι τα προσθετεις. οποτε τωρα παιρνει 1+1=2 μετα 2+2=4 κ το μετακινεις μετα το 3. υστερα 3+4=7,7+11=18 κ παει μετα το 12 κ τελος 12+18=30 οποτε πλεον εχεις το δεντρο. βρηκα οτι θα ειναι 5.

thanx
ετσι οπως λες πρεπει να ειναι και εχεισ δικαιο
ΝΟΤΕ:
εργραψα λαθος στην εκφωνιση........
Β   Α   Λ   Ε   Ν   Τ     Ι
1    1   2   3     3     11  12
ειναι το σωστο......
αλλα με την μεθοδολογια που λες το καταλαβα... Να σαι καλα!!!!!!!!!!!
με την σωστη εκφωνιση πρεπει το rout του δεντρου να ειναι 33...και το Α να θελει 5 ψηφια.....
ας το επιβεβαιωσει καποιος που εκανε την αξιολογηση...(εμενα εχει κωλησει και δεν μπορω να δωσω αλλη απαντηση)

για οσους θελουνα να δουν πως δουλευει.......http://en.wikipedia.org/wiki/Huffman_coding

ναι 5 παλι βγαινει

παιδια στο ερωτιμα με το δεντρο αναζητησης οπου διαγραφουμε τιμες 50,35,20.........(http://img104.imageshack.us/img104/3225/200409a1ayl5.gif) (http://imageshack.us)

λεει ποιος αριθμος θα ειναι στον κομβο με το *........
απ οτι ειδα.....στο τεστ δεχεται σωστο το 40....αν το κανεισ ομως στο http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm
δοκιμη βγαινει το 25.....................
ποιο ειναι σωστο τελικα...???????

Οσο αφορα την ταξινομηση επιλογης λεει οτι παιρνουμε το πρωτο στοιχειο κ μετα βρισκουμε το μικροτερο στοιχειο του πινακα κ ανταλλασσουμε. ομως για να βρουμε το μικροτερο θα πρεπει να σαρωσουμε ολο τον πινακα η οταν ας πουμε βρουμε το 0 θα πουμε ειναι το μικροτερο κ τελος? πχ αν εχουμε 6 5 9 1 2 ποσες συγκρισεις θα κανω για να αλλαξω το 6 με το 1, τρεις η τεσσερις?

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

Αυτό για την ταξινόμηση σωρού δεν το έχω καταλάβει ούτε εγώ. Μήπως μπορεί κάποιος να εξηγήσει πώς γίνεται η ταξινόμηση σωρού για κάποιον πίνακα?????????

 Όσο για την ταξινόηση επιλογής λογικά θα σαρώνεις όλο τον πίνακα,γιατί πρέπει να βρείς το μικρότερο στοιχειο. Αν όμως στον παραπάνω πίνακα θες να κάνεις πχ 3 συγκρίσεις (με δεδομένο ότι για να αλλάξεις το 6 με το 1 θες 4 συγκρίσεις)
ο τελικός πίνακας θα είναι  1 5 9 6 2 ή  θα παραμείνει 6 5 9 1 2 επειδή δεν έχεις ελέγξει όλο τον πίνακα??

Έστω ότι θέλουμε να αναζητήσουμε το πρότυπο P = χαχοχα στη συμβολοσειρά S = χαχοχχαχοοχαχοχα Χρησιμοποιώντας τον αλγόριθμο KMP (Knuth-Morris-Pratt). Ποιος είναι ο συνολικός αριθμός των συγκρίσεων που θα χρειαστεί να εκτελεστούν; Θεωρείστε ότι ο αλγόριθμος σταματάει την πρώτη φορά που ανακαλύπτει το πρότυπο P.


ρε παιδια πως γινεται τουτο???????????

ΤΟ σωστο αποτελεσμα παντως ειναι 20! :)

εμενα στο χαρτι μου βγαινουν 19 !!!!  :D :D :D
αλλα δεν το δεχεται....
γιατι ειναι 20????? 8) 8) :???: :???: :???: :???:

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

19 βγαινει αν δεν μετρησουμε τις συγκρισεις για τα γραμματα που συμπιπτουν μετα την πρωτη μετακινηση οπως λεει στην διαφανεια 15. κγω 20 εβαλα μετρωντας ολες τις συγκρισεις κ το πηρε σωστο.

παντως για να βγαλεις ακρη βρες την f συμφωνα με τον αλγοριθμο διαφανεια 10 κ για τις συγκρισεις διαφ 11

για την  μια απο βαριαντα η απαντηση ειναι 20 και για την αλλη....19
εγω απλα δεν το προσεξα πως υπαρχουν 2 εκδωσεις και ελυσα στο χαρτι την αλλη απ αυτη που ειχα... ¨)

σόρρυ που δεν απαντάω στο παραπάνω, δεν έχω προχωρήσει στην ύλη ακόμα.

Πόσες διασπάσεις κόμβων θα πραγματοποιηθούν αν επιχειρήσουμε να τοποθετήσουμε, με τη σειρά που δίνονται, τα παρακάτω κλειδιά:

59, 13, 58, 124, 21, 60, 15, 22, 99, 20, 14

σε ένα B-δένδρο βαθμού d = 1;

ξέρει την απάντηση κανείς? έβαλα 6 και είναι λάθος.

κατάλαβα το λάθος μου, για βοήθεια δείτε:    http://slady.net/java/bt/view.php

λογικά τώρα θα πρέπει να είναι 5 διασπάσεις, σωστά?

Σίγουρα υπάρχει κάποια με αποτέλεσμα 19, γιατί εμένα μου το έχει πάρει 4 φορές σωστό. Να κάνω μια ερώτηση, οι ταξινομήσεις σας βγαίνουν σωστά στην αξιολόγηση; Εγώ τις έχω τρέξει και με JAVA applet και καμία φορά δε  μου έδωσε όλη την απάντηση σωστή. Το μέγιστο που πήρα ήταν 0,5.

Επίσης, έχει συναντήσει κανείς την παρακάτω?

Ερώτηση:
Έστω A(n) ο αριθμός των αστερίσκων (“*”) που εκτυπώνονται στην κονσόλα, για δεδομένο n>=2 , από την παρακάτω μέθοδο σε Java:

void stardust(int n) {
    if (n >= 2) {
        int k = n – 1;
        System.out.print(“*”);
        stardust(k);
        System.out.print(“*”);
        stardust(k-2);
        System.out.print(“*”);
    }
}
Ποια από τις παρακάτω συναρτήσεις υπολογίζει την τιμή του A(n), όταν n>=2 ;
(n) = 2A(n-1) + 3       
2.    A(n) = 3A(n-1) + 2    
3.    A(n) = A(n-1) + A(n-2) + 3    
4.    A(n) = A(n-1) + 2A(n-2) + 2    
5.    Καμία από τις παραπάνω


η σωστή απάντηση είναι "καμία από τις παραπάνω"?

νομιζω πως ναι.

κγω σε μερικες δεν μπορω να βρω που εχω λαθος  :P.

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

Θα το πυροβολήσω δεν εξηγείται αλλιώς.  ^banghead^ Λοιπόν έχουμε σε κώδικα huffman να κάνουμε τα εξής:
Π    Α    Γ    Ε    Τ    Ο    Σ
1     1    2    2    4    15   16

Λέει πόσα ψηφία θέλει το Α για να παρασταθεί με τον βέλτιστο κώδικα huffman. Και με το χέρι που το υπολόγισα αλλά και με java applet από αυτή την σελίδα
http://www.cs.sfu.ca/CC/365/li/squeeze/Huffman.html
μου βγάζει ότι θέλει 6 ψηφία... Όμως η αυτοαξιολόγηση το βγάζει για λάθος  :o

 >:(
Τι συμβαίνει?

κι εγώ ακριβώς το ίδιο. έστειλα μαιλ και στον ψωμόπουλο, αλλά δεν απάντησε.(προφανώς γιατί το έστειλα μετα τις 8)

Εγω που το κανα προχειρα τωρα βρηκα 5,βαλατε 5??Δεν μου ετυχε κ αυτη η ερωτηση,αλλα ειχαμε πει οτι σε περιπτωση ισοτητας συχνοτητων αυτη που βρηκαμε αθροιστικα,η τρεχουσα δηλαδη,παει στα δεξια...δλδ το  πρωτο αθροισμα Π+Α=2,το παμε στα δεξια του Ε και κοκ

και γω το εκανα τωρα στο χαρτι και θελει 6 ψηφια.......ισως υπαρχει ακποιο προβλημα στο τεστ.....

να ρωτησω κατι....
στις συναρτησεις κατακερματισμου......εχει ενα παραδειγμα 2πλου κατακερματισμου.....και λεει στον αλγοριθμο....
address={address + offfset}mod M


και ποιο ειναι το Μ οεο????????

Θα προσπερασει δλδ κ το Γ και το Ε???

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

 εμένα γιατί μου λέει απαγορεύεται η πρόσβαση????????????

Οχι το Γ μενει εκει που ειναι!Απλως το Π+Α προσπερναει και το Γ και το Ε!

Έτσι δεν γίνεται το δένδρο?

Cyber για την ταξινομηση που παρεθεσες παρολο που δεν μπορω να καταλαβω απολυτα τον αλγοριθμο,ειδα οτι εβαλες το 4 στη θεση 0,ενω επρεπε στη θεση 4 καθοτι 4/9..πηλικο 0 και υπόλοιπο 4

και γω 5 διασπασεισ βγαζω

συμφωνω μαζι σου ..
ακι γω ετσι το εκανα!!!!!!  8) 8)

xmmmmmmmm οκ τερμα το διαβασμα για σημερα αν ειναι να κανω τετοια λαθη.

Προφανώς το σωστό με τον παγετό είναι 5, έτσι? άρα κάθε φορά προσθέτουμε? ακόμα και τα τελευταία 2 που μένουν?

6 ειναι!!!!!!!!!
ετσι νομιζω
δες οπως στην εικονα με το δεντρο που παρατεθηκε πιο πριν......

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


πάντως, καθώς το έψαξα λίγο και σε άλλες σελίδες και applets, όπως το http://www.beluga.ch/code/applets/huffman
δεν τα πηγαίνουν δεξιά, αλλά τα αφήνουν εκεί που είναι. τα μετακινούν μόνο σε περίπτωση μεγαλύτερου, όχι και ίσου.

5 είναι...
Τα δύο τελευταία έχουν μικρότερη συχνότητα από το άθροισμα όλων των άλλων...

παιδια εχω τελειωσει επιτυχως και τα δυο τεστ και δεν με αφηνει να τα επαναεξετασω >:( >:(

βγαζει κατι. δεν επιτρεπεται η προσβαση...

ξερει κανεις τι παιζει???

Σ' όλους το κάνει...

Νομίζω οτι πρέπει να στείλεις μέιλ να στο ξεκλειδώσουν

ναι, ζητάς να σου διαγράψουν το ήδη υπάρχον γραπτό σου και να μπορείς να ξαναεξεταστείς.

Μπορεί να με βοηθήσει κάποιος στην ερώτηση: έχουμε τους αροθμούς 1 2 3 4 5 6 7 ,ποιά κλειδιά μπορούν να εξεταστούν με δυαδική αναζήτηση που θα εκτελεστεί δύο φορές;

4,6 νομιζω...

να ρωτησω και εγω κατι, στον αλγοριθμο ευθειας επιλογης, αν εχεις τον πινακα 88, 127, 38, 19, 71, 63, 5, 1 μετα απο 10 συγκρισεις, το μονο που θα εχει αλλαξει δεν θα ειναι ο ασσος που θα εχει μετακινηθει στην αρχη? αφου ο αριθμος των συγκρισεων δεν ειναι ιδιος με τον αριθμο των μεταθεσεων...

εγώ θα έλεγα 2 και 6.

Μάλλον η σωστή εκφώνηση είναι η εξής: "Επιλέξτε όσα κλειδιά μπορεί να βρεθούν αν εξεταστούν το πολύ δύο στοιχεία του πίνακα με τη μέθοδο της δυαδικής αναζήτησης. 1 2 3 4 5 6 7". Βάζω το 4 και το 6 που θα είναι τα 2 mid και δε μου δίνει όλες τις μονάδες. ΄΅χω δοκιμάσει επίσης τα 3,4,6 και 4,5,6 και πάλι δε μου τα δίνει σωστά.

Για τη ερώτηση με την ταξινόμηση νομίχω πως έχεις δίκιο.
Νομίζω ότι έχεις δίκιο. Και εγώ έτσι το έκανα με βάση τις συγκρίσεις ,αλλά στην αυτοαξιολόγηση δεν το δίνει σωστό.Αλλά πρέπει να είναι έτσι ,γιατί προλαβαίνεις με 10 συγκρίσεις να σαρώσεις μια φορά ολόκληρο τον πίνακα και μια φορά το μισό.

πρωτα θα εξετασει το 4 καθως ειναι το μεσαιο στοιχειο του πινακα, μετααπο την ατυχη εξεταση θα παει στο (4+1)+7/2=6 και θα τερματισει.

88, 127, 38, 19, 71, 63, 5, 1
ετσι οπως το σκεφτομαι: οι πρωτες 7 συκγισεις θα γινουν και θα επιλεξουν το 1 ως min και μετα θα το τοποθετησουν στην αρχη.
μενουν 3 συγκρισεις.
θα συγκριθουν τα:5-63,5-71,5-19 και μας τελειωνουν οι συγκρισεις..
στυο μεταξυ δεν εχουν γινει αλλες μεταθεσεις, αρα ο πινακας ειναι ως εξης:
1, 127, 38, 19, 71, 63, 5, 88

Λοιπον μολις το εκανα οπως λες και ετσι βγαινει 5 ψηφια.......
οποτε 5 ειναι τελικα.....

Συμφωνώ απολύτως και με τα δύο που έχεις γράψει. Αν τα βάλεις όμως στην αυτοαξιολόγηση βγάζει λάθος. Προφανώς πρέπει να υπάρχει λάθος στην αυτοαξιολόγηση ,γιατ΄μου βγάζει και άλλα "κουλά"!!!!

τότε θα έλεγα 2,4,6

αφου δεν μας λεει αν ψαχνει μεγαλυτερο ή μικροτερο απο 4, μαλλον ετσι ειναι...

Ρε παιδιά σχετικά με το θέμα του Χούφμαν...Πως είναι δυνατόν να βγαίνει 5?Είπατε ότι όταν έχω ίδιες συχνότητες αυτή που βγαίνει αθροιστικά πάει δεξιά...Σίγουρα είναι 5 και όχι 6 και που είναι η διαφορά αυτού του ενός ψηφίου?

Δεν έχει σημασία αν θα βάλεις τις συχνότητες αριστερά ή δεξιά εφόσον είναι ίσες. Αυτό που πρέπει να προσέξεις είναι να προσθέτεις πάντα τις 2 μικρότερες και το άθροισμά τους να το βάζεις στη σωστή θέση (δλδ ταξινομημένο). Αν το κάνεις έτσι θα δεις ότι βγαίνει 5.(Σημασία έχει το από πόσα bit θα αποτελείται το Α και όχι από ποια, άρα είτε μπει αριστερά είτε δεξιά είναι το ίδιο.

Ευχαριστώ φίλε....άντε καλά μυαλά και υπομονή.

Βασικά μία τελευταία ερώτηση τώρα που κοιτάω τον Χούφμαν...Μπορεί η τιμή ενός παιδιού ενός κόμβου, να είναι μεγαλύτερη από την τιμή ενός αδερφού του παραπάνω κόμβου?

Ρε παιδιά θα τρελαθώ..όταν ρωτάει για τα δέντρα.. ποιο είναι το μέγιστο Ν δε συγκρίνουμε το 3Ν με Ν+n+(n*m)/w και/ή το 3N με το Ν+(n*m)/w??? Υπάρχει κι άλλος τρόπος?

Πόσες διασπάσεις κόμβων θα πραγματοποιηθούν αν επιχειρήσουμε να τοποθετήσουμε, με τη σειρά που δίνονται, τα παρακάτω κλειδιά:

59, 13, 58, 124, 21, 60, 15, 22, 99, 20, 14

σε ένα B-δένδρο βαθμού d = 1;

......Σύμφωνα με τις σημειώσεις αν το δέντρο είναι βαθμού 1, η ρίζα έχει το πολύ 2 κλειδιά και 3 κόμβους, από 2 το πολύ κλειδιά ο καθένας, έτσι? άρα χωράει 8 κλειδιά συνολικά..εμείς πώς θα τα χωρέσουμε τα 10??

:D

ΕΚΤΟΣ και αν βάζουμε μόνο τα 8... πάσο!

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

Αν ρωτησει ποιο ειναι το μεγιστο Ν για να εχουμε εναν αραιο πινακα κανουμε 3Ν<(n*m)

Αν ρωτησει ποιο ειναι το μεγιστο Ν για το οποιο η καλυτερη υλοποιηση ειναι με τριαδες,τοτε κανουμε 3Ν<Ν+(n*m)

θα με τρελάνετε.. γιατί εμένα στο

Χαρακτήρας:    π    α   γ   ε   τ    ο    ς
 Συχνότητα:     1    1   2   2   4   15   16

μου βγαίνουν διαφορετικά δέντρα ανάλογα με την περίπτωση (πού βάζω τα ισόβαθμα δηλαδή..)?



και επίσης....


στην αξιολόγηση, έβαλα και στις δύο περιπτώσεις 3Ν<Ν+(n*m)/w  και μου τα πήρε σωστά.
με το  Ν+n+(n*m)/w  δεν έχει νόημα να το συγκρίνουμε γιατί πάντα θα ισχύει  Ν+n+(n*m)/w <  Ν+(n*m)/w

!!!!!!Εγω στην πρωτη εκανα 3Ν<(n*m) και μου την πηρε σωστη!!Οταν εκανα  3Ν<Ν+(n*m) μου το παιρνε λαθος!Ελεος!!

Οσον αφορα τα δενδρα,αν δεν εφαρμοσεις την τεχνικη να τα πηγαινεις δεξιοτερα τα ισοβαθμα τοτε θα σου βγει 6 οπως πολυ σωστα παρεθεσες.Εμεις προτιμουμε να τα πηγαινουμε δεξιοτερα διοτι ετσι προκυπτουν λιγοτερα μπιτ,αρα το συμφερει περισσοτερο αυτη η υλοποιηση!

 >:(
χωρίς λόγια

κγω σαν κ σενα Τονια τα βγαλα

ps: τους αραιους εννοω

τα δενδρα η τους αραιους πινακες?

Κ εδω ειχαμε ενα θεμα με τους αραιους πινακες κ σχετικα με ποια ανισοτητα χρησιμοποιουμε!

http://www.thmmy.gr/smf/index.php?topic=17562.msg422503#msg422503

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

Προσωπικά μετά απο αρκετές ώρες ενασχόλησης θεωρητικά αλλά και με applets (και σωρία λαθών στις απαντήσεις που έδωσα που πολλές φορές δεν είναι...) κατέληξα στο εξής:
   Η αυτοαξιολόγηση στις Δομές Δεδομένων είναι πράγματι αυτοαξιολόγηση!Αν ξέρεις το σωστό το γνωρίζεις από μόνος σου  αλλιώς μην περιμένεις να στο πει η βάση δεδομένων του ethmmy!...Cheers!

περα απο την αξιολογηση στις σημειωσεις κεφαλαιο ταξινομησης στην διαφανεια που μιλαει για τν ταξινομηση επιλογης γιατι στην δευτερη στηλη εχει αλλαξει το 23 με το 57????

επιμέμω ¨)
παιδια στο ερωτιμα με το δεντρο αναζητησης οπου διαγραφουμε τιμες 50,35,20.........(http://img104.imageshack.us/img104/3225/200409a1ayl5.gif) (http://imageshack.us)

λεει ποιος αριθμος θα ειναι στον κομβο με το *........
απ οτι ειδα.....στο τεστ δεχεται σωστο το 40....αν το κανεισ ομως στο http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm
δοκιμη βγαινει το 25.....................
ποιο ειναι σωστο τελικα...???????
ΒΟΗΘΕΙΑ ΠΛΗΖΖΖΖΖΖΖΖ

Τώρα το ξανακοίταξα και νομίζω ότι τελικά πρέπει πάντα το άθροισμα να μπαίνει δεξιά από τις ισόβαθμες συχνότητες. Έτσι σου βγαίνει το σωστό δέντρο που είναι το 2ο. Sorry για το προηγούμενο λάθος.

Εγώ σήμερα έβαλα στην αυτοαξοιλόγηση το 25 και μου το πήρε σωστό!!!

Συμφωνώ απόλυτα.Ειδικά στις ταξινομησεις και εγώ δεν βγάζω άκρη.Τουλάχιστον με την αυτοαξιλόγηση φαίνονται ποια είναι τα SOS για το μάθημα. Τα λάθη όμως είναι πολλά και καταντάνε σε κάποια φάση εκνευριστικά.

παιδιά μετά από κάμποσα μαιλ και συζήτηση η τελική απάντηση όσον αφορά στον παγετό είναι η εξής:

"Έχεις δίκιο για τον "παγετό", προφανώς στο site δεν είχε ληφθεί υπόψη
 ο δεύτερος τρόπος. Είναι και τα δύο σωστά.

 Βίβια"



χαχαχα.. διαβάζω τα προηγούμενα ποστ και γελάω.. χαμός γίνεται.. η αυτοαξιολόγηση μάλλον μας έχει μπερδέψει περισσότερο και μας τρώει και ώρα από το διάβασμα. τέσπα..

geo_iv   στα applets και μένα αυτό μου βγάζει αλλά λογικά καλύτερα είναι το 40 (τελικά δε μπόρεσα να βρω γιατί είναι καλύτερο το 40, μάλλον ισοδύναμα είναι και τα δύο. τι θα ανέβει όταν διαγραφεί το 35).
ίσως και τα δύο να είναι σωστά.

Το οποίο είναι πιθανόν να συμβαίνει και σε διάφορες άλλες ερωτήσεις ειδικά στο 2 τμήμα της αυτοαξιολόγησης.

Ερώτηση: Δίνεται ένας αραιός πίνακας ακεραίων διάστασης 16 x 4. Αν Ν είναι ο αριθμός των μη μηδενικών στοιχείων του πίνακα, ποια είναι η τιμή του Ν, ώστε ο να μην έχει σημασία άν ο τρόπος αποθήκευσης του πίνακα θα είναι ως τριάδες αριθμών, όπου κάθε τριάδα αντιστοιχεί σε ένα μη μηδενικό στοιχείο (γραμμή, στήλη, τιμή), ή ως ένας 16 x 4 πίνακας με τα μηδενικά στοιχεία και τα μη μηδενικά σαν μονάδες και έναν 1 x Ν με τις μη μηδενικές τιμές; Θεωρείστε ότι για την αποθήκευση ενός ακεραίου χρησιμοποιούνται 4 bits.

Λοιπον λέω 3x4xN = 16x4x4 +Nx4 άρα αποτέλεσμα Ν=32 Γιατί αυτό είναι λάθος???

στο 16χ4 δεν χρειαζεται το δευτερο 4.

εγώ θα έλεγα 3*Ν = Ν + (16*4)/4
άρα, Ν=8

όπως το είπε ο CyberCaesar. ούτε στο πρώτο μέλος. 3*Ν δηλώνει αριθμό λέξεων

ακριβώς αυτό θα έλεγα και εγώ

Θέμα 10 
Βαθμολογία: 0.0 από 1.0

Ερώτηση: Ποιος είναι ο ελάχιστος αριθμός κόμβων που μπορεί να έχει ένα πλήρες τετραδικό δέντρο ύψους 6. Θεωρούμε πως η ρίζα είναι το επίπεδο 0.

Α/Α    Απάντηση φοιτητή
1.    1366

δε δίνετε κι εδώ τα φώτα σας?

αφου ειναι πληρες ο ελαχιστος αριθμος θα ειναι ισος με τον μεγιστο αρα απο τον τυπο διαφανεια 11 κεφ 4α θα ειναι 4^(6+1)-1/(4-1)=5461. δεν ξερω αν ειναι σωστο βεβαια... :P

Κ εγω νομιζα οτι ειναι σωστο αυτο που εγραψε η Τονια το 1366!

Αλλα η αυτοαξιολογηση δεχεται ως σωστο αυτο που εγραψε ο Cyber..

αλήθεια? το δέχεται ως σωστό?

επίσης, πλήρες δε σημαίνει πάντα ότι έχει όοολους τουσ κόμβους που πρέπει.
πλήρες ονομάζεται όταν στο τελευταίο επίπεδο οι κόμβοι που υφίστανται (και δεν έχουν τιμή ΝΙL) είναι όσο το δυνατόν αριστερότερα ενώ τα προηγούμενα επίπεδα είναι γεμάτα.
αυτόν τον ορισμό δίνει  στη σελίδα 5-1 για το σωρό και από άλλη ερώτηση αξιολόγησης έβγαλα το συμπέρασμα ότι ισχύει γενικώς και το διασταύρωσα και με σημειώσεις άλλων (εκτός του Μήτκα)

Και εγώ αυτό νομίζω ότι είναι σωστό. Η διαίρεση γίνεται με (4-1)=3 γίνεται. Απλά πρέπει να προσέξετε ότι στις σημειώσεις δίνει το τύπο n=(d^h)-1/(d-1) θεωρώντας τη ρίζα στο επίπεδο 1. Εμείς που τη θεωρούμε στο 0 πρέπει να πάρουμε τον τύπο n=d^(h+1)-1/(d-1) , οπότε βγαίνει 5461.

μιλάς για τον τύπο για το μέγιστο ή το ελάχιστο? ο τύπος στη σελίδα 4a-5 είναι για επίπεδο ρίζας=0 (n=d^(h+1)-1/(d-1)).

άρα, αυτό που έβγαλες είναι ο μέγιστος αριθμός κόμβων.

γιατι ομως να δεχεται το40 ως σωστο... :( ?????
καλσσικο BUG μαλλον

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

και εδω...που υπαρχει λάθος???????????
θα τρελαθω!!!!!!!!!!!!!1  :D :D :D :D  >:( >:( >:( >:(
(http://img210.imageshack.us/img210/9817/newwnv8.jpg) (http://imageshack.us)

Επειδή όμως ζητάει πλήρες δένδρο παίρνουμε το μέγιστο...Σε ένα πλήρες μέγιστο=ελάχιστο.

διάβασε λίγο πιο πάνω τι έγραψα για τα πλήρη δέντρα..
δεν είναι σίγουρο, απλά λάβετε το υπόψη σας

Που είναι ο αλγόριθμος ευθείας επιλογής;

Συμφωνώ με αυτό που έγραψες, αλλά στις σημειώσεις στη σελίδα 4a-5 λέει ότι πλήρες δέντρο είναι αυτό με το μέγιστο αριθμό κόμβων.Άρα πρέπει να πάρεις τον τύπο που αναφέρθηκε και δίνει το μέγιστο αριθμό κόμβων.

ειναι ενας αλγοριθμος ταξιμοησης....οπου εξεταζεις πρωτα το πρωτο στοιχειο και το αντικαθιστας με το ΜΙΝ του πινακα ...μετα το δευτερο στοιχειο με το ΜΙΝ του υπολοιπου πινακα........αλλα κατι δεν παει καλα στην αυτοαξιολογηση...:(

ΤΕΛΙΚΑ ΠΩ΅ΒΡΙΣΚΟΥΜΕ ΤΟ ΜΙΝ ΡΕ ΠΑΙΔΙΑ ΓΙΑ ΤΟΝ ΑΡΙΘΜΟ ΚΟΜΒΩΝ????ΤΟ ΒΙΒΛΙΟ ΛΕΕΙ ΗΙΑ ΤΟ ΜΑΧ ΚΑΙ ΟΧΙ ΤΟ ΜΙΝ>>>ΚΑΙ ΑΝ ΤΟ ΔΔΕΝΤΡΟ ΔΕΝ ΕΙΝΑΙ ΠΛΗΡΕΣ???????

Βασικα με βαση αυτα που γραφει ο Μητκας στους Σωρους,μπορει να υπαρξει πληρες δενδρο χωρις να εχει το μεγιστο αριθμο κομβων,αρκει να εχει τα φυλλα το δυνατο αριστεροτερα!
Στις σημειωσεις του μιλαει για ελαχιστο αριθμο κομβων και μεγιστο αριθμο σε πληρες δενδρο,διαφοροποωντας τις 2 περιπτωσεις.Επισης λυνει κ παραδειγμα ετσι!
οποτε κανοντας την αναλυση για την συγκεκριμενη ασκηση,κ επειδη μας ζητα ελαχιστο αριθμο κομβων πληρες δενδρου,αρα 1 φυλλο στο τελευταιο επιπεδο θα ειχαμε καπως ετσι

ύψος 0(ρίζα): 1κόμβος
ύψος 1: 4 κόμβοι
ύψος 2: 4^2 κόμβοι
ύψος 3: 4^3 κόμβοι                          (+)
ύψος 4: 4^4 κόμβοι
ύψος 5: 4^5 κόμβοι
ύψος 6: 1 κόμβος

Σύνολο: 1366 κόμβοι

Κ εγω αυτο θεωρω σωστο αλλα αυτο που δεχεται ως την σωστη απαντηση  4^7-1/4-1

Στη θεωρία λέει οτι ένα δέντρο λέγεται πλήρες όταν έχει τον μέγιστο αριθμό κόμβων, οπότε δεν καταλαβαίνω ποιο είναι το πρόβλημα...

Ταξινόμηση ακόμη δεν είδα... Πιο μετά μπορεί να βοηθήσω

Αυτό που λες είναι σωστό ,με βάση αυτά που λέει στους σωρούς σωστό είναι το 1366. Εγώ απλά βρίσκω κάτι περίεργο στις σημειώσεις.Ενώ στη σελίδα 4a-5 δίνει τον αριθμό των κόμβων του πλήρους δυαδικού δένδρου 2^(h+1)-1 χωρίς διευκρίνιση , στο κεφάλαιο των σωρών αναφέρει ότι ένα πλήρες δένδρο έχει 2^(h-1)-1 μέγιστο αριθμό κόμβων και 2^(h-1) ελάχιστο. Τι ισχύει τελικά::: ΘΑ ΤΡΕΛΑΘΟΥΜΕ ΕΝΤΕΛΩΣ ΜΟΥ ΦΑΙΝΕΤΑΙ!!!!!!!!!

Αυτοι γινεται γιατι αλλου θεωρει ριζα στο 0,αλλου ριζα στο 1και γινεται μπερδεμα!!


Αν εχουμε ριζα στο 0

1)μεγιστος αριθμος κομβων πληρους==d^(h+1)-1/d-1

2)ελαχιστος αριθμος κομβων πληρους==[d^(h)-1/d-1]+1

Riza sto 1

1)μεγιστος αριθμος κομβων πληρους==d^(h)-1/d-1


2)ελαχιστος αριθμος κομβων πληρους==[d^(h-1)-1/d-1]+1



οπου d=βαθμος


Προφανως slash στους σωρους θεωρει ριζα το 1και εχει λαθος που λεει 2^(h-1)-1  το σωστο ειναι 2^(h)-1!

Types of binary trees

    * A rooted binary tree is a rooted tree in which every node has at most two children.
    * A full binary tree, or proper binary tree, is a tree in which every node has zero or two children.
    * A perfect binary tree (sometimes complete binary tree) is a full binary tree in which all leaves are at the same depth.
    * A complete binary tree is a tree with n levels, where for each level d <= n - 1, the number of existing nodes at level d is equal to 2d. This means all possible nodes exist at these levels. An additional requirement for a complete binary tree is that for the nth level, while every node does not have to exist, the nodes that do exist must fill from left to right. (This is ambiguous with perfect binary tree.)

Από τη Wikipedia για τα δυαδικά δέντρα μερικοί ορισμοί που ισχύουν με την ανάλογη επέκταση και για όλα τα δέντρα.

4ΜΟD9 ΠΟΣΟ ΚΑΝΕΙ??

Τελικά το post του BoardRider ισχύει??? δε σταματάω την αξιολόγηση μέχρι να καταλάβω που κάνω λάθος!!!!!! ΝΟΝSTOP!!!

4 νομιζω

Γενικά  kmodx  σημαίνει το ακέραιο υπόλοιπο της διαίρεσης k/x .Για το 4mod9 έχεις k=4, x=9 => 4/9 δίνει υπόλοιπο 4.

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

Είχα βάλει 3 αλλά μάλλον θα είναι 4

γιατί να μην είναι 5?? αφού το άλμα είναι ίσο με 2

Ωχ αντέγραψα λάθος άσκηση. :???: Με δυαδική αναζήτηση έπρεπε να γράψω και όχι άλματος

με δυαδική τελικά όταν χωρίζεις στη μέση και κάνεις διερεύνηση (δεξιά/αριστερά) το μετράει για 2 συγκρίσεις αυτό??? αν ναι τότε είναι υποκειμενικό το 3 ή το 4 νομίζω.. εκτός κι αν ψάχνει πρώτα απ τα μικρότερα.. κάποιος να διαφωτίσει το λαό..

πρωτη συγκριση θεωρειται με το μεσαιο στοιχειο.

4 ειναι. με το 19,27,74 και 99

Τελικά δεν ξέρω αν έχει διαπιστωθεί πιο πριν στην ερώτηση με τους αραιούς πίνακες π.χ  Δίνεται ένας αραιός πίνακας ακεραίων διάστασης 6 x 6. Αν Ν είναι ο αριθμός των μη μηδενικών στοιχείων του πίνακα, ποια είναι η μέγιστη τιμή του Ν, ώστε ο βέλτιστος τρόπος αποθήκευσης του πίνακα να είναι ως τριάδες αριθμών, όπου κάθε τριάδα αντιστοιχεί σε ένα μη μηδενικό στοιχείο (γραμμή, στήλη, τιμή); Θεωρείστε ότι για την αποθήκευση ενός ακεραίου χρησιμοποιούνται 4 bits

Παίρνει σαν σωστή απάντηση το 4 που προκύπτει από το 3Ν<Ν + 36/4 ΚΑΙ ΔΕΝ ΙΣΧΎΕΙ η σχέση 3*Ν*4< 6*6*4 που δίνει αποτέλεσμα 11.

σωστός Καίσαρα.. νομίζω κατάλαβα :)

+ αυτό thanks to Stephanos!
για όποιον ρωτούσε!

οποτε λες οτι το σωστο ειναι το 19?γιατι εμενα με 20 το πηρε σωστο κ με 19 λαθος. οπου σαν το 1 επιπλεον υπεθεσα οτι παιρνει εκει στο 6 με 7 οπου μετραει κ το πρωτο χ.

Α κ για να μν ξεχνιομαστε στο παιχνιδι της εθνικης τα γκολ τα βαλαν κατσουρανης κ χαριστεας   ;D ;D ;D

βασικα υπαρχουν 2 τετοια

αυτο που εχει το χαχοχα σωστο εχει το 19!

και το αλλο με το χοχαχο σωστο το 20!

Δωσε συνθεσεις!!! λολ

μπα μπορεί κάτι για το Ζαχόπουλο να ρωτήσει ... :P :P

σε μας τι μπορεί να είναι μια απειλή μας ρώτησε....

και οι απαντήσεις ήταν:

τριγωνική ασύμμετρη  συμμετρική  :P :P

εμενα με το χαχοχα πηρε σωστο το 20. κ επισης κ στα 2 το ιδιο πραγμα βρηκα.

;D ;D ;D λετε να πεσει καμια του στυλ ποιοι υποστηριζουν τν ανθιμο?δεν τα διαβασα αυτα....

Μα στις σημειώσεις δεν είναι

Τ Ζ Ι Τ Ζ Η Ρ Α Σ
1 2 3 4 5 6
Τ Ζ Ι Τ  Ζ Ι
              7
        Τ Ζ Ι

δηλαδή δεν τα μετράει τα κοινά!!

συμφωνω αλλα κ παλι το 20 πηρε σωστο κ μονο ετσι μπορεσα να το δικαιολογησω. ισως να ειναι λαθος της αξιολογησης.

Ρε παιδιά τι παίζει με την αυτοαξιολόγηση?Έκανα διάφορα πειράματα στο 1ο τεστ και πια δε μ'αφήνει να επανεξεταστώ. Έχω κάνει 30 προσπάθειες επανεξέτασης για να λύνω κάθε φορά τις απορίες μου σε διαφορετικές απαντήσεις και τώρα μου λέει ότι δεν επιττρέπεται η πρόσβαση. Οπότε δεν μπορώ να κάνω και το 2ο τεστ. Τα νεύρα μου. Τι τον πειράζει τον Ψωμόπουλο πόσες φορές θα μπω εγώ να την ψάξω με τις απαντήσεις? Και τώρα τι κάνουμε? Πάει????


ΑΑΑΑΑ, αν κάποιος μπορεί να μου στείλει κάποιες από τις ερωτήσεις (με τις λύσεις τους) του 2ου τεστ με ένα copy-paste θα ήμουν ευγνώμων....

Ευχαριστώ..

Πόσο ήρθε τελικά το ματς?Μπορεί να ρωτήσει κάτι σχετικό με την ομάδα του Ηρακλή.....
Ποιοί παίκτες έφυγαν, ποιοί ήρθαν το Γενάρη............Ποιός ο προπονητής του Ηρακλή.....λολ

Η μια μεθοδος θα εχει Ν+(4*10)/8  και η αλλη 3Ν δηλαδη |{N+5}-{3N}| αρα 2Ν+5 λεξεις.
Δεν εγγυομαι για την ορθοτητα της λυσης ,ετσι τουλαχιστον το καταλαβαινω εγω... :-\

Κάποιος?Κάτι?please......

για να σου επιτραπει ξανα η προσβαση αλλα με αλλα θεματα πρεπει να στειλεις mail στον ψωμοπουλο.

μου είπε μία κοπέλα ότι έβαλε κάτι τέτοιο, (να έχει το Ν μέσα) και της κόλλησε το σύστημα εντελώς. έστειλε μαιλ στον ψωμόπουλο και της είπε ότι αυτό έγινε επειδή έβαλε γράμμα ενώ θέλει αριθμό. Άρα...?

παιδια για να μην μπερδευεστε, καντε το με τον μπακαλικο τροπο.
Ν      1    2   3   4   5  (...)
3Ν    3    6   9   12 15 (...)
Ν+5  6    7   8   9   10 (...)

και βρισκεις καθε φορα οτι θες...

άρα λογικά εμπλέκεται το Ν στη λύση, αφού δεν είναι σταθερός ο αριθμός!! τι λάθος λέει!! ( |2Ν-5| είναι!)

noonno...
πχ πες οτι θες να βρεις πιος ειναι ο βελτιστος Ν για αποθηκευση σε τριαδες,κανεις :
Ν      1    2   3   4   5  6(...)
3Ν    3    6   9   12 15 18 (...)  [σε τριαδες]
Ν+5  6    7   8   9   10  11(...)   [σε δυαδικο πινακα]

και βρισκεις την τελευταια τιμη του Ν κατα την οποια, το 3Ν που αναφερεται στις τριαδες ειναι μικροτερο απο το Ν+5, αρα:

Ν      1    2   3   4   5  6(...)
3Ν    3    6   9   12 15 18 (...)  [σε τριαδες]
Ν+5  6    7    8   9   10  11(...)   [σε δυαδικο πινακα]

αρα το Ν=2.

Ή απλά πάρε την ανίσωση 3N<N+5 και διάλεξε το ακέραιο κομμάτι της λύσης.Βγαίνει 2Ν<5<=>Ν<2.5 =>Ν=2 αφού Ν ακέραιος.

Nαι ρε συ αλλά ρωτάει άλλο! Πόση θα είναι η διαφορά σε λέξεις της καλύτερης με τη χειρότερη μέθοδο αποθήκευσης. Η μία μέθοδος έχει 3Ν λέξεις και η άλλη Ν + (axb)/w άρα αφαιρείς αυτά τα 2! Μήπως παίζει κάτι με το 4x10?? κάτι με το 40 κ το 8 δηλαδή.. για να βρούμε κ το Ν??

παιρνεις την απολυτη τιμη που βρηκες, δειχνει την μεγιστη αποκλιση μεταξυ δυο μεθοδων αποθηκευσης.βαζεις το μεγιστο Ν, πχ το 4ή το 10(δεν ξερω αν ειναι 4χ10 ή 10χ4) και ετσι εχεις την διαφορα σε λεξεις.
 νομιζω...

Ναι κάτι τέτοιο νομίζω κι εγώ :) για να δούμε..

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

η χειρότερη μέθοδος είναι να αποθηκευτεί σε n*m λέξεις.
και δε σου δίνει το Ν, αλλα σου ζητάει αριθμητικό αποτέλεσμα!

τον ηρακλη?και ποιος θα ξερει να απαντησει?
χαχοχαχχοχχαχαχοοχχαχοοχαχαχαχαχοχα! :D

στην ερωτηση με το avl δεντρο που εισαγεις το 56 και σου λεει τι ειδους περιστροφη πρεπει να γινει, τι βαλατε?
καταρχας το δεντρο θελει εξισορροπηση απο την αρχη γιατι ειναι δεξιοβαρο, ετσι δεν ειναι?

Αν η καλύτερη μέθοδος είναι αυτή με τις 3N λέξεις τότε το Ν=2.Για Ν=2 η διαφορά μεταξύ των 2 μεθόδων είναι μία λέξη.Κάντε με πινακάκι όπως ο edenaxas ή με ανίσωση οπως είπα πιο πάνω σε συνδυασμό με αυτό το ποστ.

Μπορεί κάποιος να εξηγήσεις πώς γίνεται αυτό; Αν κάνουμε λάθος και στην ταξινόμηση φυσαλίδας έλεος.

Βάζω: 34 24 58 71 60 5 10 135 και δεν το παίρνει σωστό;
Πώς μετράμε τις συγκρίσεις στην ταξινόμηση φυσαλίδας;

Δίνεται ο πίνακας ακεραίων αριθμών: 34, 135, 58, 24, 71, 60, 5, 10 Χρησιμοποιώντας τον αλγόριθμο ταξινόμησης φυσσαλίδας, να δώσετε τη μορφή του πίνακα μετά από 10 συγκρίσεις.

Και επίσης:

Δίνεται ο παρακάτω πίνακας ακεραίων. Χρησιμοποιώντας τον αλγόριθμο ταξινόμησης ευθείας επιλογής, να δώσετε τη μορφή του πίνακα μετά από 10 συγκρίσεις. Προσοχή! Συγκρίσεις μεταξύ δύο στοιχείων και όχι πλήρεις σαρώσεις του πίνακα. Σημειώστε πως τα αριθμητικά ψηφία έχουν μικρότερη τιμή από τα αλφαβητικά. ΑΡΧΙΚΟΣ ΠΙΝΑΚΑΣ Α Θ Η Ν Α 2 0 0 4

Έβαλα:  0 Θ Η Ν Α 2 Α Ο 4

Γιατί είναι λάθος; Κάτι παρόμοιο μου συμβαίνει και με το ΖΑΓΟΡΑΚΗ.

re ayto epeidi me exei spasei ta nevra Ερώτηση:  Δίνεται ταξινομημένος πίνακας με τα εξής στοιχεία: 6, 10, 13, 20, 22, 27, 55, 58, 87, 99, 121 Να βρείτε το συνολικό αριθμό των συγκρίσεων που απαιτούνται για την εύρεση του 99 με αναζήτηση άλματος με άλμα ίσο με 3
πρωτα στο  13 δεν θα παει? και οταν φτασει στο 87 μετα ξεπερναει τον πινακα .πειραζει αυτο η γινεται τιποτα αλλο?????

συνάδελφοι μπορείται να μπείτε στην αυτοαξιολογηση;

αυτοαξιολόγηση είναι υποχρεωτική;



αυτή τη στιγμή όχι, μάλλον έχει μπούκωσε ο αλεξαντερ.

όπως το βλέπω εγώ όχι,  ξεκινάει από το 6 , μετά 20 , μετά 55 , μετά 99

Εγώ πάντως που το έκανα έτσι και βρήκα ν=4 μου το βγάζει λάθος..
μια σύγκριση με το 6
μια με το 20
μια με το 55
μια με το 99
οπότε μετά από 4 συγκρίσεις το βρίσκει έτσι?

ΑΘΗΝΑ2004 να κανετε αλγοριθμο φυσαλιδας για 5 συγκρισεις.Τα αλφαβητικα ειναι μεγαλυτερα απο τους αριθμους.προσοχη 5 συγκρισεις οχι επαναληψεις

Βρίσκω ΑΗΘΑ2Ν004 και μου το δίνει λάθος...
Ξέρει κανείς την σωστή απάντηση?

re ti einai auto/?// einai sosto???   gmt paideuomai olh mera

an 3erei kapoios thn apantisi please... as apantisei

sas euxaristw polu gia thn amesh antapokrisi paidia...

brika ena polu wraio java aplet me epidi3h tou KMP algori8mou

http://www.enseignement.polytechnique.fr/profs/informatique/Jean-Jacques.Levy/00/pc4/strmatch/e.html

boh8aei polu

Νομίζω πως το σωστό είναι 17.

Τελικά 19 είναι...

Η δεν την παλεύει η αυτοξιολόγηση ή εγώ κάνω βλακείες

Ερώτηση: Δίνεται ο πίνακας ακεραίων αριθμών: 88, 127, 38, 19, 71, 63, 5, 1 Χρησιμοποιώντας τον αλγόριθμο ταξινόμησης φυσαλίδας, να δώσετε τη μορφή του πίνακα μετά από 5 συγκρίσεις. Η ταξινόμηση γίνεται κατά αύξουσα σειρά.

Βαζω αυτό σαν απάντηση και το παίρνει λάθος
88,38,19,71,63,127,5,1

τι γίνεται??

Είναι σωστό έτσι όπως το έχεις! Έχουμε προσέξει πως σε κάποιες ερωτήσεις της αυτοαξιολόγησης δεν είναι σωστές οι απαντήσεις που λαμβάνονται ως σωστές!

void showStars(int n) {
    if (n >= 3) {
        showStars(n-3);
        System.out.print("*");
        showStars(n-1);
        System.out.print("**");
        showStars(n-2);
    }
}

Για n=5 τι θα εκτυπωθει?? και γιατι?   :???:

αν θυμάμαι καλά εβγαιναν 12 αστέρια..
τώρα  το γιατί είναι μεγάλη ιστορία :P
γίνονται συνέχεια αναδρομές

Γιατι γινονται συνεχεια αναδρομες? Για n=5 η πρωτη εντολη που εκτελειται ειναι η showstars(2) δεν προχωρισει στην εκτελεση των αλλων εντολων, σωστα? Αν ναι γιατι ρε παιδια? Επισης μετα θα βγει εξω θα ελεξει αν 2>=3 που δεν ισχυει και θα σταματησει ε? Μαλλον κανω λαθος βεβαια...   :-\

σκέψου ότι όταν θα κληθεί μία αναδρομή, τότε θα τυπωθούν φυσικά τα αστεράκια που είναι σκορπισμένα στις εντολές και θα κληθούν εκ νέου μερικές... οπότε θα ξανατυπώσουν μερικά.... αν το δεις βημα-βημα θα το πιάσεις... απλά έχει αρκετές αναδρομές!

ακυρο!! :D :D
ειχα λυσει παρομοιο και εβγαινε τοσο... sorry...

Σορρυ ρε guys αλλα δεν το πιανω... Η System.out.print("*"); ας πουμε ποτε θα εκτελεστει πρωτη φορα? Δωστε ας πουμε λιγο στην αρχη πως παει..

Ξεκινάμε με n=5. Το 5>=3 αρα τυπώνουμε  σίγουρα 1+3=4 αστεράκια (από τα 2 System.out.print())

Τώρα εξετάζουμε τις κλήσεις (n=n-1, n=n-2 και n=n-3):

1)Για n=4
   4>=3 και τυπώνουμε άλλα 4 αστεράκια.
   Επίσης γίνονται οι εξείς κλήσεις:
   1i) για n=3
            Τυπώνει άλλα 4 αστεράκια γιατί 3>=3
             Καλέι ξανά τη συναρτηση για n=2, n=1 και n=0. Αυτές οι κλήσεις δεν θα τυπώσουν γιατί n<3.
             Άρα απλά επιστρέφουν.
   1ii) για n=2   Ομοίως δεν τυπώνει.
   1iii) για n=1   Ούτε αυτή τυπώνει.
2)Για n=3
    Είναι ίδια περίπτωση με την 1i) . Θα τυπώσει άλλα 4 και τέλος.
3)Για n=2
    Είπαμε ότι για n<3 δεν τυπώνει, μόνο επιστρέφει πίσω στη συνάρτηση που τη κάλεσε.

Τέλος. 16 αστεράκια σύνολο... :)

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

Ευχαριστω πολυ φιλε..  :)

mitso μήπως έκανες κάπου λάθος γιατί στο συγκεκριμένο βγαινουν 12 αστεράκια . Τρέξε τον κώδικα να δεις

edit:
Κάθε φορά τυπώνονται 3 όχι 4 αστεράκια  :P

Το σίγουρο είναι ότι θα τυπώσει 4 φορές από όσα αστεράκια έχουν τα 2 print μαζί.
Άρα 12 σε αυτή τη περίπτωση.

Όταν έκανα την αξιολόγηση έβαλα 16 και το πήρε σωστό. Και είναι σίγουρος ότι τα αστεράκια μου ήταν 1 και 3. Μάλλον έχει μικρές αλλαγές στις ερωτήσεις.

Ξέρει κανένας τι παίζει εδώ;;;
Μάλλον αυνανία της αυτοαξιολόγησης...

Έτσι όπως το καταλαβαίνω εγώ στο συγκεκριμένο παράδειγμα το σωστό είναι 10 αριθμοί.Πρέπει γενικά να υπάρχουν λαθάκια στην αυτοαξιολόγηση...

έλα ρε Δία!!

σοβαρα?? :D.....
γιατι η γενικη ασαφεια που επικρατει στις σημειωσεις τι σε λεει?

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

Λοιπον κοίταξα απο το βιλίο.. Αμα θέλουμε να διαγράψουμε το 50 το ανταλασσουμε με το δεξί παιδί του αριστερού του παιδιού.ΑΝ δεν υπάρχει το ανταλάσσουμεμε το αριστερό παιδί του δεξιού του παιδιού. Οπότε έχουμε τώρα το 35 στην θέση του 50 και το 50 στην θέση του 35.
Απο εκεί και πέρα πρεπει να κατεβάσουμε το 35 , σωστα?
Με ποιο απο τα 25 και 40 το ανταλασσουμε? Δηλαδή ακολουθούμε το αριστερό ή το δεξί παιδί??

Έκανα print screen σαν παράδειγμα τις ερωτήσεις που εμφανίστηκαν σε μένα για την αυτοαξιολόγηση 1, ανεβάζω τις φωτο από τις σωστές μόνο: http://rapidshare.com/files/445636754/domes-aftoaksiologisi1.rar (http://rapidshare.com/files/445636754/domes-aftoaksiologisi1.rar)

Αν έχει κάποιος account στο rapid ας τις ξανακάνει ένα γρήγορο upload μόλις τις κατεβάσει, γιατί νομίζω αν δεν είσαι registered ούτε καν free δεν μένει το link για πολλές φορές.

edit: To katevasate idi 10 fores k svistike. to ksananevasa edw: http://rapidshare.com/files/445661341/domes-aftoaksiologisi1.rar (http://rapidshare.com/files/445661341/domes-aftoaksiologisi1.rar)

Με το τετραδικό δέντρο τον αριθμό των κόμβων πώς τον υπολόγισες;

Στο επιπεδο 0 εχεις τη ριζα, 1 κομβος
Στο επιπεδο 1 εχεις 4 παιδια αλλοι 4 κομβοι
Στο επιπεδο 2 εχεις 4 παιδια απο καθε κομβο δηλ 4*4=4^2

ομοιως στο επιπεδο 5 εχεις 4^5

Η ελαχιστη τιμη των φυλλων (στο επιπεδο 6) ειναι 1 για να ειναι πληρες

οποτε εχεις 1+4+4^2+4^3+4^4+4^5+1  (1 και οχι 4^6 ::) )

Mπραβο που τα ανεβασες Selportion!

Ερώτηση: Δίνεται ο παρακάτω πίνακας ακεραίων. Χρησιμοποιώντας τον αλγόριθμο ταξινόμησης φυσαλίδας, να δώσετε τη μορφή του πίνακα μετά από 5 συγκρίσεις. Προσοχή! Συγκρίσεις μεταξύ δύο στοιχείων και όχι πλήρεις σαρώσεις του πίνακα. Σημειώστε πως τα αριθμητικά ψηφία έχουν μικρότερη τιμή από τα αλφαβητικά. ΑΡΧΙΚΟΣ ΠΙΝΑΚΑΣ Z A Γ Ο Ρ Α Κ Η Σ


Εμένα μου έβγαλε αυτό και μπερδεύτηκα κάπως. Η ταξινόμηση ξέρω πως δουλεύει, το θέμα είναι τι τιμές θα θεωρήσω για κάθε γράμμα;

Επειδη δεν το εχω δει ακομα, δοκιμασε σαν το ASCII ενα πραμα

δηλ Α<Β<...<Ω

κανενας αλλος που το εκανε?

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

Και εμένα μου το έκανε αυτό με τη στοίβα, το κορυφαίο όμως είναι πως σε μία ερώτηση έδωσα την ίδια απάντηση δυο φορές την μία την έβγαλε σωστή και τη δεύτερη φορά λάθος... :???:

εμένα στο τέλος (ειχαν μεινει 2 ερωτησεις) μου έβγαλε ένα    ???el_GR.null???  και δνε μπορω να απαντησω η εστω να καταθεσω οσα εκανα μεχρι τωρα. ξερει κανεις τι ειναι;

Eστειλα ε-μαιλ για να δω τι παίζει και μου πανε απο αύριο ξανά αξιολόγηση

  ???el.null???  ....

wtf

Παιδιά παλιότερα έπεσε το εξής θέμα. Να ταξινομηθεί με quicksort η λέξη ΔΟΜΗΜΕΝΟ..
Μπορει να καταλάβει κανείς πώς γίνεται..
Αρχισα έβαλα Δ  = 4 κλπ.. Αλλά παίζει πρόβλημα.
ΚΑΙ ΠΡΟΦΑΝΩΣ τα παραδείγματα στο βιβλίο  και στις αξιολογήσεις είναι εύκολα και στις εξετάσεις πέφτει το παλούκι. Αν μπορεί κανείς να το λύσει και να δημοσιεύσει την λύση θα βοηθούσε πολύ...

Εγώ φαντάζομαι οτι απλά αντικαθιστάς τα γράμματα με αριθμους, δλδ α=1, β=2 ...

δλδ το κάνεις 4 15 12 7 12 5 13 15
κ μετά κάνεις κανονικά quicksort

Οπως έγραψα το έκανα αυτό... Το θέμα είναι μετά απο αυτό..... Αν προλαβαίνεις λύσ' την.. Γιατί απο εκεί και πέρα αρχίζουν τα περίεργα,,

Περιεργα λεγοντας? Δεν βρισκω κανενα προβλημα :S

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

Οποιος το έχει καταλάβει ας το πει.. Θα βοηθούσε πολύ

Oταν διαγραφουμε κομβο σε δυαδικο δεντρο αναζητησης, στη θεση αυτουνου που σουταρουμε :P βαζουμε τον κομβο που βρισκουμε ως εξης: απο τη θεση διαγραφης κατεβαινουμε στο δεξι παιδι και αν δεν εχει αριστερο παιδι βαζουμε αυτο. Αν εχει, παμε στο αριστερο του αριστερου κλπ μεχρι να φτασουμε σε φυλλο (δεν ξερω αμα καταλαβαινεις τι λεω)
Με αυτη τη διαδικασια εχουμε διαλεξει την μικροτερη τιμη του δεξιου υποδεντρου του κομβου που διαγραφεται

Στο παραδειγμα: διαγραφουμε το 50, παμε στο δεξι παιδι κ μετα στο αριστερο του δλδ 76 κ μετα 65 κ το ανεβαζουμε στη θεση του 50 (ειναι η αμεσως μεγαλυτερη τιμη)
Μετα, διαγραφουμε το 35 παμε δεξι παιδι το 40, δεν εχει αριστερο παιδι, το ανεβαζουμε, τελος.
Και οταν διαγραφουμε το 20 παμε δεξια (τωρα ειναι το 40) κ νομιζω αριστερα (25) κ ξανα αριστερα 21

Θα το ξαναδω παντως...

Kαι εγω εκει που το ετρεξα παντως το 40 δειχνει...

αλλα αυτο που λεω το διαβασα lafore σελ 394... wtf?

KHMMY To λάθος το κάνεις στο τελευταίο βήμα. Το 20 στο τελικό βήμα πριν το διαγράψεις έχει 1 παιδί. Δεν ψάχνεις για διάδοχο στη προκειμένη περίπτωση... Το διαγράφεις κατευθείαν

Aαα λες? Να 'σαι καλα!

άρα το 40 είναι η απάντηση, σωστά?

Εγώ από ότι κατάλαβα από τις σημειώσεις κάθε κόμβο που διαγράφουμε αντικαθίσταται με το μεγαλύτερο σε τιμή κόμβο του αριστερού υποδέντρου.. Αν δεν υπάρχει αριστερό υποδέντρο απλά σηκώνουμε το δεξί υποδέντρο 1 θέση πάνω. Αν δεν έχει ούτε δεξί απλά βρισκόμαστε σε φύλλο. Σύμφωνα με αυτήν την λογική το 25 όντως είναι η σωστή απάντηση. Ας πει και άλλος την γνώμη του για να καταλήξουμε κάπου :???:

Βασικά τώρα που το ξαναείδα μπορείς να επιλέξεις και το μικρότερο του δεξιού υποδέντρου... Αν το πας έτσι βγαίνει το 40 (ή το 21??). Στις σημειώσεις κάπου έχει έναν ψευδοκώδικα και λέει "επιλέγεις ή το μεγαλύτερο του αριστερού ή το μικρότερο του δεξιού"

Με μπέρδεψες.. Τελικά ποιό είναι σωστό? Του ΚΗΜΜΥ το κατάλαβα..

o My name is Legion for We Are Many έχει δίκιο. Σελ. 391 στον Lafore. Όταν ο κομβος που διαγράφεται έχει ένα παιδί, απλά βάζεις στην θέση του αυτό το μοναδικό του παιδί. Άρα εδω το 40 !

Άρα το 2ο post μου είναι το σωστό, τώρα που είδα και του lafore με σωστή απάντηση το 40... Το 21 το πρότεινα γιατί δεν ήμουν σίγουρος ότι στην περίπτωση που ο διαγραμμένος κόμβος έχει μόνο ένα παιδί απλά σηκώνουμε το παιδί

Ερώτηση: Αν f(n) η πολυπλοκότητα ενός αλγορίθμου και O(g(n)) η τάξη του, ποια από τις παρακάτω προτάσεις είναι αληθής;

1.    Αν f(n) = 2n+1, τότε είναι O(g(n)) = n²    
2.    Αν f(n) = 2n²+n+1, τότε είναι O(g(n)) = n²    
3.    Αν f(n) = n³+2n²+n+1, τότε είναι O(g(n)) = n²    
4.    Η 1 και η 2    
5.    Η 2 και η 3    

πώς λύνεται αυτό;

Για να βρείς την πολυπλοκότητα παίρνεις μόνο τον όρο που αυξάνεται πιο γρήγορα..
δλδ αν έχεις 2n²+n+1, η πολυπλοκότητα είναι n² δηλαδή τετραγωνική..
σωστό είναι το δύο

thanks!!

επίσης...

Ερώτηση: Δίνεται ένας αραιός πίνακας ακεραίων διάστασης 16 x 4. Αν Ν είναι ο αριθμός των μη μηδενικών στοιχείων του πίνακα, ποια είναι η τιμή του Ν, ώστε ο να μην έχει σημασία άν ο τρόπος αποθήκευσης του πίνακα θα είναι ως τριάδες αριθμών, όπου κάθε τριάδα αντιστοιχεί σε ένα μη μηδενικό στοιχείο (γραμμή, στήλη, τιμή), ή ως ένας 16 x 4 πίνακας με τα μηδενικά στοιχεία και τα μη μηδενικά σαν μονάδες και έναν 1 x Ν με τις μη μηδενικές τιμές; Θεωρείστε ότι για την αποθήκευση ενός ακεραίου χρησιμοποιούνται 4 bits.

η σωστή απάντηση είναι 8;;

νομιζω ναι.

Εχεις Ν 3-αδες αριθμων για τον πρωτο τρόπο, άρα 3*4*Ν bits.

για τον 2ο τροπο εχεις εναν πινακα 16*4 με ασσους και μιδενικα άρα 16*4 bits (οι ασσοι και τα μηδενικα αποθηκευονται σε 1 bit. Απλα γι'αυτο δεν ειμαι και τοσο σιγουργος!) και εναν πινακα με Ν στοιχεια των 4 bits. οποτε συνολικα 16*4+4*Ν bits.

Τωρα για να μην εχει σημασια ποιον τροπο θα επιλεξεις θα πρεπει 3*4*Ν = 16*4+4*Ν (δηλαδη να καταλαμβανουν τον ιδιο χωρο στην μνημη!). Αρα Ν = 8

στις διαφάνειες δίνει λίγο διαφορετικούς τύπους..
για την πρώτη περίπτωση 3N και για τη δεύτερη N +(m*n)/w...
 εγώ αυτό πήρα...

Βασικα ιδιος ειναι, αν πολ/σεις με το w :P

οκ!!ευχαριστώ!!

έχουμε σωρό.. ζητάει μετά απο δύο διαγραφές να βρείς την μορφή του

σύμφωνα με lafore sel 584 όταν κατεβάζω κόμβο απο πάνω προς τα κάτω αντικαθιστώ με το μεγαλύτερο παιδί του

Οπότε το αριστερό υποδέντρο πρέπει να μείνει απείραχτο εδώ, σωστά?

στη θέση 2 πάω να βάλω το 12 κ δεν υπάρχει καν στη λίστα

ποστάρω το προβλημα και τα αποτελεσματα μου

Μα οταν κανεις την πρωτη διαγραφη, το 70 θα παει πανω, επειδη το 12 ειναι το μικροτερο απ'τα 70,12,21 βαζεις το 12 πανω. Μετα απο τα 70,22,31 παει πανω το 22 κ.ο.κ.

Οποτε στην δευτερη διαγραφη θα φυγει το 12 και θα παει πανω το 61. Απο τα 61,22,21 θα παει το 21 πανω και το 61 στην θεση του 21 κ.ο.κ.

Βασικα τωρα που το ειδα και στον lafore εχει σωρο μεγιστων. Εδω εμεις εχουμε σωρο ελαχιστων οποτε ισχυουν ακριβως τα αντιθετα απ'αυτα που λεει στον lafore. Οπως το ειπα πανω δηλαδη!

λολ μόλις είδα οτι lafore μιλάει για σωρό με τις μέγιστες τιμές πάνω.. τρελή ταγκαλιά εκ μέρους μου

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


στην ερώτηση με τον κατακερματισμό σας παίρνει σωστό το αποτέλεσμα?

Δεν είμαι απόλυτα σίγουρος αλλά κάπου π τ δοκίμασα έπιασε
Λοιπόν στην αυτοαξιολόγηση με ένα Ctrl+U sto firefox (View ->Page Source) έχει και τις απαντήσεις πχ:

"Δίνεται ένας αραιός πίνακας ακεραίων διάστασης 5 x 5. Αν Ν είναι ο αριθμός των μη μηδενικών στοιχείων του πίνακα, ποια είναι η μέγιστη τιμή του Ν, ώστε ο βέλτιστος τρόπος αποθήκευσης του πίνακα να είναι ως τριάδες αριθμών, όπου κάθε τριάδα αντιστοιχεί σε ένα μη μηδενικό στοιχείο (γραμμή, στήλη, τιμή); Θεωρείστε ότι για την αποθήκευση ενός ακεραίου χρησιμοποιούνται 4 bits.">

Οι απαντήσεις είναι της μορφής:

      <input type="hidden" name="qstAnswer1" value="8">       8))       
      <input type="hidden" name="qstIndex1" value="0">
      <input type="hidden" name="qstInfo1" value="">
      <input type="hidden" name="qstPerc1" value="">
   
      <input type="hidden" name="qstAnswer2" value="">
      <input type="hidden" name="qstIndex2" value="0">
      <input type="hidden" name="qstInfo2" value="">
      <input type="hidden" name="qstPerc2" value="">
   
      <input type="hidden" name="qstAnswer3" value="">
      <input type="hidden" name="qstIndex3" value="0">

      <input type="hidden" name="qstInfo3" value="">
      <input type="hidden" name="qstPerc3" value="">
   
      <input type="hidden" name="qstAnswer4" value="">
      <input type="hidden" name="qstIndex4" value="0">
      <input type="hidden" name="qstInfo4" value="">
      <input type="hidden" name="qstPerc4" value="">
   
      <input type="hidden" name="qstAnswer5" value="">
      <input type="hidden" name="qstIndex5" value="0">
      <input type="hidden" name="qstInfo5" value="">

      <input type="hidden" name="qstPerc5" value="">

Όταν έχει αριθμητικό αποτέλεσμα τότε η απάντηση είναι σωστή
Όταν έχει αντιστοίχιση ή ταξινόμηση η σωστή είναι το δεύτερο πεδίο <input type="hidden" name="qstIndex1" value="0"> όπου το index είναι ο αριθμός του στοιχείου στη λίστα επιλογών. Δλδ το πρώτο απ τη λίστα ή το τρίτο κτλ. Υπάρχει παρακάτω από εκείνο το σημείο η αντιστοιχία index - τιμής.
Πολλαπλής δεν έχω βρει ακόμα κάτι.

Κάτι τελευταίο βοηθητικό: Ctrl-f (αναζήτηση) και δώστε qstAnswer

Δινεται αραιος πινακας ακεραιων 4χ10. Αν 5 ειναι ο αριθμος των μη μηδενικων στοιχειων του πινακα, ποση θα ειναι η διαφορα σε λεξεις της καλυτερης με τη χειροτερη μεθοδο αποθηκευσης του πινακα? Θεωρειστε οτι για την αποθηκευση ενος ακεραιου χρησιμοποιουνται 8 bits.

Iδεες?

Και δευτερο, Δινεται ενας αραιος πινακας ακεραιων 5χ5. Αν Ν ο αριθμος των μη μηδενικων στοιχειων, ποια ειναι η μεγιστη τιμη του Ν, ωστε ο βελτιστος τροπος αποθηκευσης του πινακα να ειναι ως τριαδες αριθμων, οπου καθε τριαδα αντιστοιχει σε ενα μη μηδενικο στοιχιεο (γραμμη, στηλη, τιμη). 4 bits για αποθηκευση ακεραιου

+1  !!!!  Εγώ βγάζω 3.125 με τους τύπους... Και έβαλα 3 αλλά μου το βγάζει λάθος.

 Και μένα!!!!

Ποιους τυπους??

3 methodoi, h kanoniki opou thelei 4*10=40 lekseis, h 5+(40)/8 = 10 lekseis, kai h 3N=15 lekseis.., h diafora ths xeiroteris me tin kalyteri einai40-10 = 30 lekseis

edw nomizw sugkrineis tin kanoniki apothikeusi me tin 3N methodo.. stin kanoniki thes 5*5 = 25 Lekseis, stin 3N thes 3N lekseis
3N<25, N<9, dld N=8

an thelei na to sugkrineis me itn allh methodo, tote stin mia periptwsi theleis 3N, stin alli N+25/4 = N+6.25,
ara 3N<N+6.25 , 2N<6.25, N < 3.125,  ara N =3


an thumamai kala h autoaksiologisi thewrei oti kaneis tin prwti sugkrisi k thewrei swsti tin apantisi 8

Ερώτηση: Με βάση την συνάρτηση H(k) = k mod 9 , να αποθηκεύσετε σε πίνακα κατακερματισμού 11 θέσεων τα παρακάτω κλειδιά με τη σειρά που δίνονται: 12, 71, 52, 10, 19, 4, 56 Το πρώτο στοιχείο του πίνακα θεωρείται ότι έχει δείκτη 0. Η επίλυση των συγκρούσεων να γίνει με τη μέθοδο της τετραγωνικής εξέτασης με c = 1.


μου έδωσε 0.73 από 1..έβαλα:
 _ 10 56 12  4 _ 19 52 71  _  _(οι παύλες είναι τα κενά..)


ξέρετε ποιο είναι το λάθος;
για τη σύγκρουση του 19 δεν παίρνουμε add0=1
και add1=add0+c*i^2(όπου c=1)=2 και τα λοιπά...;;;

Αυτο που λες ειναι η τετραγωνικη εξεταση

Στην γραμμικη πηγαινεις στην επομενη θεση μεχρι να βρεις μια αδεια.


edit: den vlepw tin tufla mou, ontws tetragwniki zitaei eleos

ΤΙ παει να πει Β-δεντρο βαθμου 1? Πως θα ειναι δλδ με ενα παιδι?

Βαθμός στο β δέντρο είναι άλλο πράγμα, διαβασε β δεντρα απο διαφάνειες, οταν λέμε βαθμού d  εννοούμε πως κάθε κόμβος έχει το πολύ 2d τιμές μέσα του.. τα παιδια του κόμβου νομίζω δίνονται απο τον αριθμό των κλειδιών που περιέχει +1

Σε ευχαριστω κ για τα προηγουμενα... μπορεις να πεις λιγο για την 3Ν αποθηκευση που την λεει?

edit: μαλλον ειναι χαζη ερωτηση και αναφερεσαι στις τριαδες

Στις διαφάνειες, στους πίνακες στις πρώτες σελίδες λέει για τους αραιούς πίνακες.

loipon exoyme
 12 mod 9 = 3 , to bazeis sto 3
71 mod 9 = 8 to bazeis sto 8
52 mod 9 =  7 to bazeis sto 7
10 mod 9 = 1 to bazeis sto 1
19 mod 9 = 1, exeis sigkrousi to bazeis sti thesi x + c^2, opou edw einai 1 + 1 = 2, to bazeis sto 2
4 mod 9 = 4 to bazeis sto 4
56 mod 9 = 2, sigkrousi to bazeis sto 2 + 1 = 3, sigkrousi to bazeis sto 2 + 4 = 6, to bazeis sto 6

bebaia k auta no baleis tha sto parei lathos.. alla mi masas :D, an exw lathos as me diorthwsei kapoios

ναι στις 3αδες αναφερομαι ολα αυτα τα λεει στις παρουσιασεις του Μητκα, στα arrays

στις διαφάνειες δίνει και έναν άλλο τρόπο τρόπο αποθήκευσης..εκείνον δεν το λαμβάνουμε υπ'όψιν επειδή προφανώς βγαίνει χειρότερος από το Ν+(n*m)/w...;;;

δηλαδή,όταν έχουμε σύγκρουση [πρώτα βρίσκουμε τη θέση του στοιχείου αυτού με τη δεύτερη συνάρτηση κατακερματισμού και μετά συνεχίζουμε με τα υπόλοιπα;;;νομίζω πως στο μάθημα πρώτα έβαζε όλα τα στοιχεία στον πίνακα(σύμφωνα με την h(x)) και μετά έπαιρνε τη δεύτερη συνάρτηση για όσα συγκρούονταν... :???:

Πρόσεξε δεν έχεις διπλό κατακερματισμό για να χρησιμοποιήσεις 2 συναρτήσεις. Τετραγωνική εξέταση κάνεις.Το βήμα αλλάζει.

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

ναι, με την τετραγωνική εξέταση πχ αν δοκιμάσεις τη θέση 5 κ δεν το βρέις, μετα δοκιμάζεισ μια θέση μετα δλδ την 6, μετα 4 θέσεις μετα δλδ την 9, μετα 9 θεσεις μετα δλδ την 14..

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

O, όχι η sunshine!!    lol

χαχα!!συγγνώμη βρε,αλλά πραγματικά δεν το πρόσεξα... :-[
και ευχαριστώ!!με σώζετε!!!!

Ερώτηση: Δίνεται ο παρακάτω πίνακας ακεραίων. Χρησιμοποιώντας τον αλγόριθμο ταξινόμησης ευθείας εισαγωγής, να δώσετε τη μορφή του πίνακα μετά από 5 συγκρίσεις. Προσοχή! Συγκρίσεις μεταξύ δύο στοιχείων και όχι πλήρεις σαρώσεις του πίνακα. Σημειώστε πως τα αριθμητικά ψηφία έχουν μικρότερη τιμή από τα αλφαβητικά. ΑΡΧΙΚΟΣ ΠΙΝΑΚΑΣ Z A Γ Ο Ρ Α Κ Η Σ


Ερώτηση της αυτοαξιολόγησης.. Εγώ σύμφωνα με τον αλγόριθμο έβγαλα την λέξη  ΑΓΖΟΡΑΚΗΣ
Του βγει κανενός/καμιάς  έτσι? Δεν το πιάνει όλο σωστό... Δεν μπορώ να καταλάβω...

Tο μονο που μπορω να σκεφτω ειναι οτι πρεπει πχ να το ταξινομισεις με φθινουσα σειρα και να παει το Α προς το τελος. Αλλα δεν το διευκρινίζει :S

Kαι σε μενα τα βγαζει λαθος (μαλλον ειναι σωστα)

Ελα αυτοαξιολογηση πες την αληθεια, δεν περνας αυριο :P

Ερώτηση: Δίνεται ταξινομημένος πίνακας με τα εξής στοιχεία: 6, 10, 13, 20, 22, 27, 55, 58, 87, 99, 121 Να βρείτε το συνολικό αριθμό των συγκρίσεων που απαιτούνται για την εύρεση του 99 με αναζήτηση άλματος με άλμα ίσο με 3.


Παμε ως εξης: 6,20,55,99 και λεμε 4 συγκρισεις?

4 συγκρίσεις .. και γω έτσι το βαλα και μας το βγαλε σωστό..

ΑΓΖΟΡΑΚΗΣ βρίσκεις και εσύ? Ακολούθησες τον αλγόριθμο ή το παράδειγμα του βιβλίου??

Παιδιά πριν τρελαθώ :

Ερώτηση: Δίνεται ο πίνακας ακεραίων αριθμών: 34, 135, 58, 24, 71, 60, 5, 10 Χρησιμοποιώντας τον αλγόριθμο ταξινόμησης φυσσαλίδας, να δώσετε τη μορφή του πίνακα μετά από 10 συγκρίσεις.

Μου βγάζει οτι παίρνω 0.25 στα 1

Δε μπορώ να καταλάβω τι κάνω λάθος.

παιδια επειδή been there done that για να μην τρελαθείτε η αυτοαξιολόγηση στις ερωτησεις ταξινόμησεις βγάζει οτι να ναι, σωστό βάζετε κ τα βγάζει λαθος

Δικιο εχει ο sunshine

Παρακάτω δίνεται ένας πίνακας χαρακτήρων μαζί με τη συχνότητα εμφάνισής τους. Αν δημιουργήσουμε τον βέλτιστο κώδικα Huffman για τους παραπάνω χαρακτήρες, τότε ποιο θα είναι το μήκος (σε bits) της αναπαράστασης του χαρακτήρα “Α” στον κώδικα Huffman;

Χαρακτήρας: syxnotita

V 1
Α 1
L  2
Ε 3
Ν 3
Τ  5
Ι  8

Πιθανες απαντησεις: 3,4,5,6,7
7 δεν ειναι το σωστο? Τι 3 γραφει η μαλακια?

ο ταξινομημενος ποιος ειναι ποσταρετε καποιος....

6 34 24 58 71 60  5 10 135?

PerMit is trolling us.......

βγαζει οτι ναναι βαθμους!Μας τρολλαρει αγρια!!!!!!!! :P

nai autos xwris to 6 sthn arxh, mallon katala8os to pathses, opws roufages th soupa sou! :D

Εγώ πάλι σε αυτό βρήκα ΖΑΓΟΡΑΚΗΣ ακολουθώντας τον αλγόριθμο των παρουσιάσεων. Βασικά δεν είμαι και τέρμα σίγουρος γιατί για την ταξινόμηση εισαγωγής λέει στα slides ότι ξεκινάμε από το δεύτερο στοιχείο (το 1ο θεωρούμε ότι είναι ταξινομημένο)...

Ίδιο αποτέλεσμα κι εγώ, σκορ = 0.25 ..... έλεος.


Επίσης σε αυτό

Θέμα 4.1   

Βαθμολογία: 0.0 από 1.0

Ερώτηση: Δίνεται ο πίνακας ακεραίων αριθμών: 88, 127, 38, 19, 71, 63, 5, 1 Χρησιμοποιώντας τον αλγόριθμο ταξινόμησης φυσαλίδας, να δώσετε τη μορφή του πίνακα μετά από 10 συγκρίσεις. Η ταξινόμηση γίνεται κατά αύξουσα σειρά.

Έχω 38 19 71 88 63 5 1 127 και σκορ 0... Τι κάνω λάθος ρε παλικάρια;;

Ξερει μεχρι και ΠΟΥ, ΤΙ , και ΤΙ ΩΡΑ τρωω!!!


SCARY

4 είναι το σωστό όπως το έκανα εγώ
εμένα μου βγήκε

V 1000
Α 1001
L  101
Ε 000
Ν 001
Τ  11
Ι  01

Ρε παιδιά αυτές τις ερωτήσεις πού τις βρήκατε;;;; Είναι στην αυτοαξιολόγηση;;;;

Nαι!

Μαλακια, εγω εβαζα ενα bit παραπανω για οταν μειωνεται η συχνοτητα ^mountza^

Τι στην ευχή συμβαίνει και εμένα δεν μου εμφανίζονται αυτά τα θέματα;;;; Επίσης, δεν μπορώ να κάνω επανεξέταση.... Οι υπόλοιποι μπορείτε;;

Μια παραλλαγη της quicksort ειναι αντι για το κλασσικο pivot σε καθε διαμεριση, να επιλεγεται ενα
τυχαιο στοιχειο της συγκεκριμενης διαμερισης και να γινεται swap με το στοιχειο στη θεση low, ωστε
καθε φορα στη θεση low να βρισκεται τυχαιο pivot.Γραψτε τους τρεις αξονες(pivot) για τους τρεις
πρωτους διαμερισμους, καθως και την τελικη μορφη του πινακα που δινεται 19 6 33 19 3 75 30 60 43 1.

Αυτό πώς γίνεται; (από τα θέματα του 2008)

Oταν διαγραφουμε σε σωρο και ανεβαζουμε το τελευταιο φυλλο
πηγαινουμε στο μικροτερο παιδι αν ειναι ελαχιστων κ στο μεγαλυτερο αν ειναι μεγιστων ή κατι άλλο?

αυτό και εγώ δεν το καταλβαίνω.. τι εννοεί? πως να βρούμε τους άξονες pivot αφού επιλέγονται τυχαία :S

αν είναι τα ελάχιστα πάνω πηγαίνουμε στο μικρότερο απο τα δυο παιδιά, αλλιως αν ειναι τα μέγιστα πάνω πηγαίνουμε στο μεγαλύτερο απο τα δυο παιδιά..

αυτο με την quickosrt μήπως το κτλβαίνεις?


edit :
το ξαναδιάβασα, μήπως εννοεί διαλέξτε τυχαίο pivot, φέρτε το στη πρώτη θέση, καντε διαμερισμό, σπαστε τον πινάκα σε δύο μικρότερους, διαλέξτε τυχαίο pivot στο καθένα, καντε διαμερισμό, συγχωνεύστε τα όλα?

ναι αλλά και πάλι είναι τυχαίο! η σωστή απάντηση ποια θα είναι; Βασικά δίνει αυτό: (Απ: 30 1 43) αλλά δε μπορώ να καταλάβω πώς βγαίνει!

ε ισως να μην υπραχει standard απαντηση.. αναλογα τι θα παρεις, ε αυτος αυτα πηρε αυτα βρηκε :P
εγω τουλαχιστον ετσι το αντιλαμβανομαι

Μπορεί κάποιος να μου εξηγήσει ψιλοαναλυτικά πώς προκύπτει η απάντηση γιατί χάθηκα λίγο!

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

To πρωτο φορ γινεται 10 φορες
το δευτερο απο ν μεχρι 0 δηλ ν
το τριτο απο 0 μεχρι ν δηλ ν

συνολο 10*ν*ν που ειναι ταξης ν^2

Ευχαριστώ πολύ! Και μια βοήθεια εδώ αν γίνεται:

Ερώτηση: Έστω ότι θέλουμε να αναζητήσουμε το πρότυπο P = χοχαχο στη συμβολοσειρά S =
χοχαχχοχααχοχαχοχιχι Χρησιμοποιώντας τον αλγόριθμο KMP (Knuth-Morris-Pratt). Ποιος είναι ο
συνολικός αριθμός των συγκρίσεων που θα χρειαστεί να εκτελεστούν; Θεωρείστε ότι ο αλγόριθμος
σταματάει την πρώτη φορά που ανακαλύπτει το πρότυπο P.

Με μπερδεύει αρκετά ο συγκεκριμένος αλγόριθμος...

Tωρα δεν προλαβαινω και βαριεμαι να το δω, αλλα αν βαλει κατι τετοιο τι να πω

με αυτό ασχολούμαι και εγώ τώρα, θα το προσπαθήσω και θα ποστάρω, στο μεταξύ πάρε κατι να σε βοηθήσει να καταλάβεις(και αν καταλάβεις πες κ σε μας :P)
http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/strMatching/KMPMatching/kmp.html

λοιπόν εγώ βρήκα
6+2+5+1+6 = 20

πολύ μπακάλικα νομίζω οτι πηγαίνεις καθε φορά στον τελευταίο 1 που βρήκες απο τον πίνακα.. αν δεν βρεις κανενα 1 πας απλα στην επομενη θεση

δεν ειμαι καθόλου σίγουρος για την λογική οπότε κάθε ενσταση δεκτή.. και δεν σας λέω ότι αυτό είναι το σωστό, μην σας πάρω στο λαιμό μου

εδω συμφωνω με το 4 αλλα δεν ειναι για το Α 0001?

αφου το βαζω διαρκως αριστερα?

εδιτ βασικα πιο σωστα να ρωτησω

πρωτα παιρνω 1-1 μετα το 2 που βγαινει με το 2 που εχω
με τα τα 3-3 μετα το 4 των 2-2 με το 5 το αρχικο και μετα το 6 απο τα 3-3 με το 8 και τελος με το 9? συνολο επανω στη ριζα 23?

ξανα εδιτ νομιζω το καταλαβα οκ!

Ερώτηση: Δίνεται ο πίνακας ακεραίων αριθμών: 34, 135, 58, 24, 71, 60, 5, 10 Χρησιμοποιώντας τον αλγόριθμο ταξινόμησης ευθείας
επιλογής να δώσετε τη μορφή του πίνακα μετά από 5 συγκρίσεις.

Μετά από 5 συγκρίσεις ο πίνακας δεν παραμένει ίδιος; Έτσι όπως το σκέφτομαι δεν έχει προλάβει ακόμη να γίνει ανταλλαγή!
1η: 34 με 135
2η: 34 με 58
3η: 34 με 24 -> βαζω στο min το 24
4η: 24 με 71
5η: 24 με 60

Από τη στιγμή που δεν έχει τελειώσει ο πίνακας δεν έχει γίνει και καμία ανταλλαγή, έτσι δεν είναι;

Φανταζομαι ναι

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

Πολυπλοκότητα;

nlogn

γιατι?

Πώς προκύπτει αυτό;

arashi γιατί το A δεν είναι 0001;;; :o

με βαση το lafore σελ 419 που το κανω

βγαζω τον ιδιο αριθμο bit αλλα 0011. (?)

βασικα εμενα η απορια μου ειναι αφου ξεκιναω με το 1+1 και το βαζω εν πασει περιπτωσει πριν η μετα το 2

γιατι η sunshine βγαζει το v kai to a na ξεκιναμε απο 1001 και οχι 0001πχ?

ενταξει το εξωτερικο ειναι ν,
το εσωτερικο που παει 1,2,4,8,...,ν ειναι logn?? η κι αυτο n?

για εξω Ν=100 μεσα παω σε 7 βηματα (1 2 4 8 16 32 64 και το 128 τρωει ακυρο)

log 100 κανει 2.... οχι 7

οποτε 8ελω να πιασω το 700 εντολες με βαση το Ν=100.....

αρα Ν σημαινει ταξη 100αδων, nlogn  ταξη 200αδων και ντετραγωνο ταξη δεκαδων χιλιαδων?
καπως ετσι βγαινει?

Ε βασικα δεν ειναι ακριβως logn. Ειναι log₂n Μαλλον δεν το εγραψε γιατι το θεωρησε αυτονοητο :P

εξηγειστε το καποιος γενικα δλδ

ποτε ειναι Ν ποτε ειναι Νλογ(2)ν, ποτε ειναι λογ ν^2 ....(?) :???:

η δωστε ενα λινκ τεσπα

ε sunshine?? :) ίδια απορία έχω και γω...

γιατι έχει να κάνει με το απο ποια πλευρά του δέντρου βάζεις τι.. το οποίο δεν παιζει ρόλο.. σημασία έχει ο αριθμός των bits για το κάθε γράμμα

και είναι o sunshine!

log(2)n εχουμε οταν κανουμε δυαδικη αναζητηση

αλλα νομιζω οτι στο πρδ δεν εχουμε...εσεις τι λετε?

Μαθηματικα δεν μπορω να στο εξηγησω (λολ). Απλα επειδη εχει το j*2 προκυπτει αυτο

πιθανόν ναι είσαι σωστός, αλλά όπως το καταλαβαίνω αφού το Α είναι δεδομένο ότι θα βρίσκεται πιό αριστερά απο όλα (μαζί με το V) τα πρώτα 3 στοιχεία θάναι ίδια αν κρατάς τον ίδιο τρόπο ονομασίας των κλαδιών,τώρα αν εσύ αλλάζεις δεν ξέρω..τεσπα τουλαχιστον γιαυτην την ερώτηση έχουμε μια ιδέα

αυτό είναι και το δέντρο μου, αν πάω το 9 απο αριστερά και το 14 δεξιά θα γίνει οπως λέτε εσεις, αλλα δεν θα αλλάξει τιποτα στην ουσία.. στοχος είναι η καλύτερη συμπίεση μονο

P.S δεν θέλω σχόλια για το δέντρο.. ξέρω οτι ειναι πολύ πρόχειρα φτιαγμένο

Καλα μη βαρας, σορρυ  ;D ;D ;D

εχεις δικιο οτι μας νοιαζει το 4.

αλλα αν ζητησει να το ζωγραφισουμε ολο  (καυλες ειναι αυτες αλλωστε) πρεπει τα μικρα να πανε στη θεση τους

κατα τα αλλα


COOL   8))

κοίταξα τις σημειώσεις τώρα και είδα οτι τα δεντρα που φτιάχνει ειναι της μορφήες το αριστερό παιδι μικρότερο απο το δεξί.. οπότε για να είμαστε σίγουροι ασ το κανουμε οπως τα λεει εκει.. κ οχι οπως το εκανα εγω, που εβαλα το 14 αριστερα και το 9 δεξια.. δεν νομιζω οτι παιζει ρολο βεβαια, αλλα you never know

Why Size Matters

Here is a table of typical cases, showing how many "operations" would be performed for various values of N. Logarithms to base 2 (as used here) are proportional to logarithms in other base, so this doesn't affect the big-oh formula.
    constant   logarithmic   linear       quadratic   cubic
n   O(1)    O(log N)    O(N)    O(N log N)    O(N2)    O(N3)
1   1   1   1   1   1   1
2   1   1   2   2   4   8
4   1   2   4   8   16   64
8   1   3   8   24   64   512
16   1   4   16   64   256   4,096
1,024   1   10   1,024   10,240   1,048,576   1,073,741,824
1,048,576   1   20   1,048,576   20,971,520   1012   1016

basika skata fainetai alla tespa/......


Βλεπουμε λοιπον πως για 1Μega εντολες το logn einai 20 enw to n logn einai 20*1mega....

swsto to nlogn loipon

ναι προφανώς είναι log₂n
αλλά και αυτό νομίζω ανήκει στην τάξη αύξησης logn

για n=4 έχουμε σύνολο 4*3=12 εκτελέσεις ενώ από τον πίνακα το nlogn κάνει 8... Κάτι δεν καταλαβαίνω;

nai

κοιταμε ασυμπτωτικα στο απειρο, οπως γραφω παραπανω στα νουμερα

exeis j=1 j<=n j=j*2

thes na deis poses fores tha ektelestei auto.. to poses fores eksartatai apo to n
an ektelestei x fores, o typos pou dinei to x einai 2^x = n,  x= log2(n)


ara perneis diplo athroisma, to prwto einai Σ apo 1 ws n k to deutero mesa sto prwto einai Σ apo 1 ws log2(n)
kai bgainei n *log2(n)

Ερώτηση: Υποθέστε ότι θέλουμε να ταξινομήσουμε τον παρακάτω πίνακα: 24, 71, 34, 65, 43, 56, 75, 7, 12, 29 με τη μέθοδο ταξινόμησης με σωρό (heapsort). Δείξτε την τελική μορφή του σωρού, όταν από τα στοιχεία του πίνακα δημιουργήσουμε έναν σωρό και στη συνέχεια αναδιατάξουμε τα κλειδιά του σωρού, έτσι ώστε αυτός να είναι ένας σωρός μεγίστων.

Μια βοήθεια σε αυτό... Το έκανα πολύ μπακαλίστικα και πήρα  ^mountza^

Το 2^χ που κολλάει? Απο πού τον συμπέρανεσ αυτό τον τύπο?

2^j εννοει... 1, 2^1=2, 2^2=4, ... , 2^j=n

Δηλαδή ψάχνουμε κάθε φορά σε κάθε επανάληψη την i,j κλπ συναρτήσει της n και μετά λύνοντας ως προς n τα πολλαπλασιάζουμε??

oxi den einai geniko auta.. auth th fora to phga etsi gt den mou bgaine alliws


apla ekana kapoies dokimes, dld eipa gia
n = 1 tha treksei 1 fores
n = 2 tha treksei 2 fores
n = 4 tha treksei 3 fores
n = 8 tha treksei 4 fores
...
o typos pou sindeei auta ta megethi einai   2^x = n (opou x o arithmos twn forwn pou tha ektelestei)
to 2 einai epeidi einai 2*j

paw gia ypno paidia.. kalh mas epituxia aurio :)

zitw suggnwmi gia ta greeklish, den tha epanalifthei

75
71 56
65 43 29 12
7 24 34

[ η μαλακια το διορθωνει λαθος προφανως :P :P ]

Καληνύχτα αλλά έτσι όπως το λες, θα έχω πχ για n=4     2^3 =8 ...Αρα δεν είναι ίσα.. Εχω μπερδευτεί άσχημα..

δίκιο έχεις.. μλκιες λέω.. ίσως αν το κάνουμε 2^(χ-1) = n ?? τέσπα nlogn είναι παντως :P

+1   ^curses^ ^crap^

όποιος έχει χρόνο απάντα. στην άσκηση με τον σωρό όταν κάνω ελαχίστων βγαίνει αυτό:

7
12 34
24 29 56 75
71 43 65

μετά όταν κάνω μεγίστων δεν μου βγαίνει το δικό σου.βλέπεις κάποιο λάθος;

Στα θεματα του 2008 στα downloads, πως βγαινει η απαντηση στο 8?

Εγω απο οτι καταλαβαίνω παίρνει πρώτα τυχαία το 30.. Στην συνέχεια κάνει τον διαμερισμό, και ο πίνακας θα πάρει μια μορφή. Μετα κανει τον διαμερισμό.. Μετά πάλι βεβαια επιλέγεις τυχαία pivot αν θες νομίζω.. Αλλά δεν παίρνει τα αριστερά pivot αλλα τυχαία νούμερα τα οποία κάθε φορά δεν είναι το αριστερότερο στοιχείο ... Δεν ξέρω αν κατάλαβες.. Δεν ξέρω αν κατάλαβα  :P...

Στην προηγούμενη ερώτηση (7) λέει πόσους κόμβους πρέπει να διασχίσεις.. Αν πχ κάνεις το δυαδικό δέντρο και βγαίνει πχ με 4 επίπεδα . Για να φτάσεις στον κάτω κάτω κόμβο πρέπει να διασχίσεις πρώτα τον πατερα- μετα το παιδί-μετα το άλλο παιδί και τέλος τον κόμβο που θες??
Δηλαδη σύνολο 4? Η μήπως δεν χρειάζεται να διασχίσεις πχ τον κομβο που ψάχνεις ώστε να κάνεις 3 διασχίσεις?

Υπάρχει και η άποψη ότι διασχίζεις τόσες φορές όσες είναι οι ακμές..