[Δομές Δεδομένων] Αυτοαξιολόγηση - απαντήσεις;

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

[height=400]

  Όταν ανεβάζουμε φωτογραφίες στις Ανακοινώσεις και Έκτακτα νέα, βάζουμε τη μεγαλύτερη πλευρά 400 (width=400 ή height=400 ). π.χ. [img height=400 (κλείνει η αγκύλη) 

[drfeelgood]

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

[bjlobby]

Ξέρει κανείς την απαντηση?     ----->
 Ερώτηση: Δίνεται ένας αραιός πίνακας ακεραίων διάστασης 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). Κάνω λάθος????

[Mendoza]

Ερώτηση:

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

[MonteCristo]

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

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

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

[bjlobby]

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

[quote/]Αυτο το δινει σε πολλαπλη επιλογη?
Η χειροτερη μορφη αποθηκευσης λογικα θα ειναι σε εναν κανονικο πινακα με (4*10) λεξεις

Η καλύτερη μορφη νομιζω θα ειναι με εναν πινακα 4*10 με μηδενικα και ασσους(μονο bits) και εναν βοηθητικο πινακα 1*Ν με Ν λεξεις!Αρα γι αυτο χρειαζονται Ν+(4*10)/8 λεξεις..Αρα η διαφορα ειναι 4*10-Ν-(4*10)/8=35-Ν..συφωνει κανεις?

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

[bjlobby]

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

[bjlobby]

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

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

[slash]

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

[Mendoza]

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

Σε σχετικό μέιλ προς κο Ψωμόπουλο, μου απάντησε το εξής:
Από την θεωρία έχουμε ότι για Ν μη μηδενικά στοιχεία χρειαζομαστε   3Ν λέξεις
(σελ.2-5, διαφάνεια 11). Έτσι εάν δεσμεύουμε στην μνήμη   έναν πίνακα 6x6 κάποιου
τύπου μεταβλητής τότε αυτόματα δεσμεύουμε   μνήμη 6x6x(αριθμό των λέξεων που
καταλαμβάνει η μεταβλητή).

Για παράδειγμα εάν η μεταβλητή ακέραιος αντιστοιχεί σε μία λέξη μνήμης τότε ένας
πίνακας ακεραίων 6x6 θα δεσμεύσει 36 λέξεις   μνήμης. Εάν για κάθε μη μηδενικό
στοιχείο χρειάζονται 3 λέξεις   μνήμης τότε  ο μέγιστος αριθμός μη μηδενικών
στοιχείων Ν που   μπορεί να  αποθηκευτεί σε αυτήν την δεσμευμένη μνήμη είναι 11   
(για Ν=12 έχουμε  ακριβώς την ίδια κατανάλωση μνήμης, και άρα δεν  μιλάμε για
βέλτιστη  λύση).

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

[slash]

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

[Mendoza]

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

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

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


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

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

[Mendoza]

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

[slash]

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

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

[Mendoza]

α μάλιστα thanks!

[geo_iv]

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

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