Δομές Δεδομένων - αναλυση θεματων

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

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

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

[nfelekid]

παιδια μια βοηθεια Please οποιος ξερει για τα θέματα που κυκλοφορουν:
έχει
for i=1 to n
for j=1 to i
for k=1 to j*j
S=S+1;
και ζητάει πολυπλοκότητα.
αρχικά ο ι=1 μπανει στο 2ο for το j ειναι 1 (δλδ από 1 σε ένα)και μέσα το k απο 1 σε ενα^2 πάλι δλδ από σε ενα.η εντολή ειναι μία και σπάω στο 1ο for.εκει το ι είναι 2,μπαίνει το j που ήταν 2 και γίνεται 1 πάλι απο την αρχικοποίηση αρα από 1 σε 2 και το κ από 1 που γίνεται πάλι μέχρι 1^2 και όταν τελειώσει το j γίνεται 2 και το κ πάλι 1 αλλά τωρα απο 1 μέχρι 4...τι γίνεται παραγοντικά μου μυρίζουν για επαναλήψεις..στο j n!  και στο κ n!n!...κάπου έχω λάθος..ξερει κανεις;

[Panzapart]

Φίλε και συνεργάτη Νίκο, έλα να το πιάσουμε μαζί. "Ένα στοιχημα με απόδοση 1.5 ότι θα το βρούμε".
Λοιπόν,  for i=1 to n, σίγουρα θα εκτελεστεί n φορές. Τα υπόλοιπα θα εκτελεστούν n φορές το for j=1 to i λόγω του i + μερικές ακόμα(που δεν ξέρω πόσες), και το for k=1 to j*j θα εκτελεστεί n*n φορές + μερικές επίσης. Άρα σαν πολυπλοκότητα έχουμε σίγουρα το (n^4 * κάτι τώρα ποιος λογάριθμος είναι δεν μπόρεσα να το δω) εκτελώντας το όμως για n=12 έκανε 27884 περίπου πράξεις. το 12^4 είναι 20736. Κάτι θα λέει αυτό.

[nfelekid]

για σου πανο με τις λυσεις σου..το πιασαμε δλδ το στοιχημα;σε πρωτη φαση έτσι φαίνεται..κλασσικό.αν το δεις όμως βήμα βήμα μπορεί να χαθείς γιατι κάθε φορά το j πηγαίνει απο 1   σε ι.ετσι,φαίνεται να ξαναρχίζει για πιο μεγάλο ι.καθε φορα το ι θα μακραίνει και το j θα αρχιζει από 1.και αντίστοιχα το κ.αφού όμως οι απαντήσεις δεν  δίνουν τέτοια κα το τρεξες παω πασο.καπου εχω λάθος (στανταρ).για n=12 το log2(12)=3.5 αρα το πετάει στα 60.000 και οπότε μάλλον το ν^4 εύκολα..
off topic,bettopic:έχω καλή φωνή για ατρομητο-λεβαδιεακό άσσο,και τα ίδια αστέρας τριπολης-λαρισα.μην πουλήσεις και κάνα οικόπεδο...αλλά έχε τα στο νου.

[Panzapart]

Thanks για το bet. Χθες που εκανα την αξιολόγηση ειχε και άλλη μια απάντηση με λογάριθμο. Δνε τη θυμάμαι και αν βγαίνει αυτη... Κάνε κι εσύ στο ethmmy την αυτοαξιολόγηση και δες το... ν^4 σκέτο δε νομίζω να είναι. Αν κάποιος ξέρει θα μας πει ελπίζω...

[liago13]

Το ν^4 σκετο δεν ειναι,το εβαλα εγω και το εβγαλε λαθος!

[Spacetraveler]

Παιδιά  βάζω το loop στη Mathematica

S = 0
Do[Do[Do[S = S + 1, {k, 1, j^2}], {j, 1, i}], {i, 1, 10}]
S

όπου έθεσα n=10

και το αποτέλεσμα βγαίνει  1210  που είναι 10*10*10 και κάτι ψιλά που είναι
δηλαδή πολυπλοκότητας N^3. 

Επίσης,  με μικρή ανάλυση του loop έχω να πω τα εξής:
Αν παραλήψουμε το loop for k=1 to j*j .   Τότε βλέπουμε ότι έχουμε την αριθμητική πρόοδο 1+2+3+...+Ν= Ν(Ν+1)/2
που είναι πολυπλοκότητας Ν^2
Τώρα, αν βάλουμε και το τελευταίο loop θα έχουμε τη σειρά  1+4+9+...+Ν^2= Ν(1+Ν)(1+2Ν)/6 που είναι πολυπλοκότητας Ν^3.

Υπήρχε η επιλογή N^3 ?? Δεν θυμάμαι. Τότε απάντησα  Ν^4 που είναι τελικά λάθος.

[liago13]

Δεν ειχε ν^3!!!

[Spacetraveler]

Υπολογίζοντας όλες τις περιπτώσεις δεν βλέπω να είναι κάποια ορθή 

S=0;
n=10;
Do[Do[Do[S=S+1,{k,1,j^2}],{j,1,i}],{i,1,n}]
S

n^4
Log[2,n]//N
n^6
n
n^4 Log[2,n]//N


και τα αποτελέσματα:
S=  1210
n^4 =10000
Log[2,n] =3.32193
n^6   = 1000000
n   =10
n^4 Log[2,n] = 33219.3

[Krono]

      Σταματήστε να μετράτε τις πράξεις που κάνει. Η πολυπλοκότητα έτσι κι αλλιώς ορίζεται ασυμπτωτικά δηλαδή για n->oo. Το πιθανότερο είναι να μην ισχύει καθόλου για μικρά n.

[Spacetraveler]

      Σταματήστε να μετράτε τις πράξεις που κάνει. Η πολυπλοκότητα έτσι κι αλλιώς ορίζεται ασυμπτωτικά δηλαδή για n->oo. Το πιθανότερο είναι να μην ισχύει καθόλου για μικρά n.

Θεωρείς ότι το 1000000 είναι μικρό n ??
Το έβαλα μόλις και τα αποτελέσματα δεν δέιχνουν κάτι διαφορετικό από αυτά που έλεγα παραπάνω...
Ποια απάντηση έδωσες εσύ στην άσκηση αυτή??

[liago13]

Βασικα παιζει να μην ειναι και κανενα σωστο,δεν ξερω γιατι,αλλα θελουν να μας τρελανουν!!!!

[cyb3rb0ss]

εμένα πάντως μου πήρε δυο φορές σωστό το Ν^4

[PerMit]

...

και τα αποτελέσματα:
S=  1210
n^4 =10000
Log[2,n] =3.32193
n^6   = 1000000
n   =10
n^4 Log[2,n] = 33219.3

      Σταματήστε να μετράτε τις πράξεις που κάνει. Η πολυπλοκότητα έτσι κι αλλιώς ορίζεται ασυμπτωτικά δηλαδή για n->oo. Το πιθανότερο είναι να μην ισχύει καθόλου για μικρά n.

Θεωρείς ότι το 1000000 είναι μικρό n ??
Το έβαλα μόλις και τα αποτελέσματα δεν δέιχνουν κάτι διαφορετικό από αυτά που έλεγα παραπάνω...
Ποια απάντηση έδωσες εσύ στην άσκηση αυτή??

Spacetraveler, δεν περνάς από το γραφείο να το συζητήσουμε;
Να σε γνωρίσω κιόλας πριν βγάλω τους βαθμούς στις Δομές?

Το n=10 ειναι μικρό. Το n^6 είναι μεγάλο.
Και μεγαλώνει ακόμη περισσότερο αν το n=100 

ΠΑΜ

[cyb3rb0ss]

...

και τα αποτελέσματα:
S=  1210
n^4 =10000
Log[2,n] =3.32193
n^6   = 1000000
n   =10
n^4 Log[2,n] = 33219.3

      Σταματήστε να μετράτε τις πράξεις που κάνει. Η πολυπλοκότητα έτσι κι αλλιώς ορίζεται ασυμπτωτικά δηλαδή για n->oo. Το πιθανότερο είναι να μην ισχύει καθόλου για μικρά n.

Θεωρείς ότι το 1000000 είναι μικρό n ??
Το έβαλα μόλις και τα αποτελέσματα δεν δέιχνουν κάτι διαφορετικό από αυτά που έλεγα παραπάνω...
Ποια απάντηση έδωσες εσύ στην άσκηση αυτή??

Spacetraveler, δεν περνάς από το γραφείο να το συζητήσουμε;
Να σε γνωρίσω κιόλας πριν βγάλω τους βαθμούς στις Δομές?

Το n=10 ειναι μικρό. Το n^6 είναι μεγάλο.
Και μεγαλώνει ακόμη περισσότερο αν το n=100 

ΠΑΜ

Μιας και σας πετύχαμε στο φόρουμ... Πότε θα βγουν οι βαθμοί κ. Μήτκα?

[fpsom]

Μόλις ανέβηκαν στο eTHMMY στα αντίστοιχα εξάμηνα...

Φώτης