ΠΕ19-ΠΕ20 - ασεπ 2009-γνωστικο

[petrosp_13]

Η παράσταση που μας δόθηκε στον διαγωνισμό ήθελε να υπολογίσουμε το άθροισμα 1+2+3+...+ν για το οποίο αρκούν ν ΕΠΑΝΑΛΗΨΕΙΣ, ν ΕΝΤΟΛΕΣ και όχι ν*(ν+1)/2.
Άρα, θεωρώ ότι η ερώτηση είναι ή κακοδιατυπωμένη, ή η μόνη σωστή απάντηση είναι η Ο(ν)
Ας βγάλουν τις όποιες απαντήσεις τους να ξέρουμε τουλάχιστον τι θεωρούν αυτοί σωστό

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

Μα και το παράδειγμα που αναφέρεις μιλάει πιο πάνω για αριθμό εντολών ή επαναλήψεων. Ο τύπος που μου δείχνεις αναφέρεται σε άθροισμα εντολών ή επαναλήψεων, όχι το άθροισμα 1+2+3+...ν
Πες μου που έλεγε στην εκφώνηση της ερώτησης ότι το κ και το ν είναι αριθμός επαναλήψεων ή εντολών ή συγκρίσεων ή ή ή;
Μας έδινε μια συνάρτηση και ζητούσε την πολυπλοκότητα της
Ε κι εγώ θεώρησα ότι η συνάρτηση είναι το άθροισμα αριθμητικής προόδου αριθμών και όχι αριθμού εντολών

[PDE ads]

[thymiaras]

Ένα μπράβο στον thymiaras που παραδέχτηκε το λάθος του. Δείχνει το (υψηλό) επίπεδό του.

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

[banned]

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

Βασικό: Μην προσπαθείτε να "υπολογίσετε" καμιά συνάρτηση. Δεν ζητάει αυτό. Αυτό που ζητάει είναι με ποια ταχύτητα αυξάνεται μία συγκεκριμένη συνάρτηση. Δεν υπάρχει πουθενά κανένας αλγόριθμος. Απλώς, αυτά τα μαθηματικά ΤΥΧΑΙΝΕΙ να χρησιμοποιούνται στην ανάλυση της πολυπλοκότητας των αλγορίθμων.
 
Το πρόβλημα από εκεί και πέρα είναι πιστεύω στην ερμηνεία των συμβόλων '=', 'Σκ' και 'Ο'. Γι' αυτό υπάρχουν οι ορισμοί. Δεν είναι θέμα γνώμης. Είναι θέμα ορισμού. Τέλος.

• Το Ο(n^2) συμβολίζει το σύνολο των συναρτήσεων που από μια τιμή και μετά αυξάνονται με ρυθμό ίδιο ή μικρότερο από την g(n)=n^2
• To '=' μπαίνει καταχρηστικά αντί του '\in' (ανήκει), (είναι ο συνήθης συμβολισμός)
• Το Σ_{1}^{n} k  είναι ΣΥΝΑΡΤΗΣΗ του n. Αυτό σημαίνει ότι αν πχ το ονομάσουμε f(n), τότε έχουμε: f(1)=1, f(2)=1+2=3, f(3)=1+2+3=6, f(4)=1+2+3+4=10 ... κλπ
  
• To ΑΣΕΠ ρωτάει: "Ποια συνάρτηση αυξάνετε τουλάχιστον με τον ίδιο ρυθμό με (ή μεγαλύτερο από) την f(n), όταν αυξάνεται το n?"
• H g(n)=1 δεν είναι γιατί δεν αυξάνεται καθόλου με το n. Άρα όχι Ο(1).
• Η g(n)=n αυξάνεται ως εξής: g(1)=1, g(2)=2, g(3)=3, g(4)=4 κλπ. Δηλαδή πιο αργά από την f, άρα έξω και το Ο(n)
• Η g(n)=n^2 αυξάνεται ως εξής: g(1)=1, g(2)=4, g(3)=9, g(4)=16... κλπ. Άρα για οποιoδήποτε n>1 έχουμε f(n)=<g(n). Δηλαδή εξ'ορισμού, f(n)=Ο(n^2). qed
• Το πιο tight που είπε και κάποιος προηγουμένως είναι f(n)=Θ(n^2) αντί για Ο, που σημαίνει ακριβώς με τον ίδιο ρυθμό με την g(n)=n^2

Πείτε μου ρε παιδιά ότι το καταλάβατε να ηρεμήσω

[giak]

Και μιά αιτιολόγηση για την 19 συμπληρώνοντας την θαυμάσια δουλειά του aroniotis.
Με πρώτη ματιά δεν υπάρχει overflow. Αν εκτελεσθεί η πρόσθεση βγαίνει 9 bit με το MSB 1. Αρα πρέπει να είναι έξυπνος ο αθροιστής και να απορρίψει το MSB. Αρα το δ.

Μα αν είδες την δικαιολογηση μου, υπερχείληση μπορεί να έχεις ΜΟΝΟ όταν δύο ομόσημοι αριθμοί δίνουν ετερόσημο... Δες εδώ http://www.google.gr/url?sa=t&source=web&ct=res&cd=2&url=http%3A%2F%2Fwww.csd.uoc.gr%2F~hy120%2F01f%2Flessons%2FHY120Lesson2.ppt&ei=Z9mKScDOD4b00AXd1NmXBw&usg=AFQjCNFEecTBsssFURx1rhuHMCvBiTQpmw&sig2=dNSi4ggPxxK-H0CGI9wsgA   στην 23η διαφάνεια...

Τελικά δεν κατάλαβα το γ ή το δ? Δεν ξέρω από αθροιστές (βαριέμαι να τους διαβαάσω) αλλά για το συγγεκριμένο παράδειγμα που έδωσε ο ΑΣΕΠ, υπάρχει αθροιστής που δημιουργείται overflow παρόλο που δεν έχουμε ομοόσημους αριθμούς?

[PDE ads]

[batman]

Άντε επιτέλους, απλά ενημέρωσε και τους καθηγητές στο ΑΤΕΙ που είχαν την ίδια άποψη να ξέρουν την απάντηση, μην λένε λάθος πράγματα στους φοιτητές τους, γιατί που ξέρεις μπορεί αργότερα οι φοιτητές αυτοί να δώσουν ΑΣΕΠ και να πέσουν μπροστά σε κανένα τέτοιο ερώτημα και άντε μετά να τους πείσεις ότι έχουν κάνει λάθος

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

[batman]

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

Πείτε μου ρε παιδιά ότι το καταλάβατε να ηρεμήσω

[GOODmorning]

Eπομένως για να τα συνοψίσουμε λίγο, τουλάχιστον να μάθουμε κάτι από το θέμα 17 μιας και σύμφωνα με τα παιδαγωγικά οι εξετάσεις πρέπει να έχουν και
επιμορφωτικό χαρακτήρα,υποθέτω. Σχετικά με την πολυπλοκότητα και μιας και δεν βρίσκομαι σε επαφή με κανένα ανώτατο εκπαιδευτικό ίδρυμα, όχι ότι όταν ήμουνα το είχα ξεκαθαρίσει το θέμα' Παραθέτω μία σύνοψη των 2 απόψεων γ, δ όχι ως πρός το ποιά είναι ορθή με βάση τους ορισμούς(πιστεύω αυτό εξυπακούεται και μόνο αν τις αθροίσουμε) αλλά με βάση τον τεκμηριωμένο τρόπο σκέψης των συναδέλφων.
Άρα άποψη ( Γ ) :  Θεωρείται ορθή γιατί
i) Έχουμε ένα απλό άθροισμα αριθμών. Δεν μας ενδιαφέρει τί αντιπροσωπεύει ο κάθε ένας αριθμός εντολές, πατάτες, μήλα ή πορτοκάλια απλά κοιτάμε ότι έχου- με κάθε φορά να προσθέσουμε ΕΝΑΝ ακόμα αριθμό(λόγω Σειράς-Αθροίσματος)! Άρα εξετάζουμε ουσιαστικά πόσες φορές θα γίνει ο ΤΕΛΕΣΤΗΣ-εντολή της πρόσθεσης. Άρα όσοι απαντήσαμε το γ ότι είναι Ο(n) ουσιαστικά θα απαντούσαμε το ίδιο αν η ερώτηση έλεγε ότι έχουμε αλγόριθμο που διαβάζει n στο πλήθος αριθμούς και τους προσθέτει(  f(n)  ).
ii) Σε αυτό θέλω την βοήθειά σας, γιατί μπορεί να είναι λάθος;;(ρωτάω έτσι;) : Πάντα συνεχίζοντας τη λογική του (i), και γνωρίζοντας σε γενικές γραμμές πώς το στυλό κλείνει προς το γ :-) , σκεπτόμενος ότι έχουμε να κάνουμε με πληροφορική=>προγραμματισμό άρα με τη λογική ότι φτιάχνω ένα πρόγραμμα και συγκρίνω την πολυπλοκότητά του (ταχύτητα=>πλήθος ενολών=>πλήθος δεδομένων) τόσο με άλλα προγράμματα που λύνουν το ίδιο πρόβλημα για τα ίδια δεδομένα n, όσο και με το ίδιο για διαφορετικά κάθε φορά δεδομένα(n+100,n+1,n-50....,2,1) οδηγούμαι στο εξής: Έστω ότι τρέχω τον όποιο αλγόριθμο-συνάρτηση για πχ n=3. To αποτέλεσμα f(3)=6. Στη συγκεκριμένη περίπτωση δεν κοιτάω όπως στο i, τον αριθμό των προσθέσεων που έγιναν, αλλά απλά το αποτέλεσμα της f. Οκ συνεχίζω και τρέχω τον νέο αλγόριθμο-συνάρτηση για n=4, τότε f(4)=10. Για να μη πολυλογώ δείχνω το πινακάκι για μερικά n από 1 μέχρι 5:
n=1     f(1)=1
n=2     f(2)=3
n=3     f(3)=6
n=4     f(4)=10
n=5     f(5)=15      Το ερώτημα είναι το εξής και πραγματικά περιμένω κάποια απάντηση αν δεν βαρεθήκατε να τα διαβάσετε ώστε να λυθεί και το θέμα,από μεριάς μου τουλάχιστον:-)  Όταν κάποιος φτιάξει τον αλγόριθμο της f(10000) και ΜΟΝΟ αυτόν, δηλαδή φτιάξει έναν αλγόριθμο που θα κάνει 10000 "πράγματα", δεν είναι σε θέση να καθίσει να υπολογίσει πόσο θα του πάρει σε χρόνο να εκτελεστεί ο αλγόριθμός του;σίγουρα ΝΑΙ. Ωραία, με βάση αυτό ότι για συγκεκριμένο n δεν υπάρχει λόγος ακόμα να μιλάμε για θεωρητικά εργαλεία περί πολυπλοκότητας σκεφτόμαστε το εξής: Πώς μπορεί να ξέρει με βάση το πινακάκι, και χωρίς να καθήσει να υπολογίσει για τα 1000000 "πράγματα", πώς θα συμπεριφερθεί ο αλγόριθμός του ( f(x) );;;;Ουσιαστικά θέλει μία προσέγγιση όχι ακριβώς του χρόνου για οποιοδήποτε n, αλλά πώς θα συμπεριφερθεί ο αλγόριθμός του(χειρότερη περίπτωση) ΣΕ ΣΧΕΣΗ με τα ήδη γνωστά και μικρά n=1, n=2, n=3, n=4, ...ΒΕΒΑΙΑ δεν μιλάμε για αλγορίθμους αλλά αν βάλουμε και τους αλγορίθμους στη λογική μας (που το έχουμε ήδη κάνει) τότε πρέπει να συμφωνίσουμε ότι "κβάντο χρόνου ή κβάντο εντολών" του αλγορίθμου μας θα πρέπει να θεωρήσουμε το αποτέλεσμα της f(1)=1!!!(βέλτιστη περίπτωση). Άρα οποιοδήποτε   f(n) το υπολογίζουμε σε ΣΧΕΣΗ με το f(n-1),f(n-2),...f(2) και εν τέλει το F(1).
Ωραία ΚΛΕΙΝΩ ρωτώντας το εξής: Αντιστρέφω το ερώτημα και κάνω την εξής σκέψη(από το τέλος f(n), στην αρχή f(1) ):
πχ f(5)=f(4)+5    f(n)=f(n-1)+n           
f(4)=f(3)+4         f(n-1)=f(n-2)+n-1
f(3)=f(2)+3         f(n-2)=f(n-3)+n-2
f(2)=f(1)+2         f(n-3)=f(n-4)+n-3
f(1)=1                f(n-4)=1=γν.

f(n)=f(n-4)+n-3+n-2+n-1+n => f(n)=4n-1-2-3+f(n-4)=>f(n)=(n-1)+(n-2)+(n-3)+( n+f(n) )=>f(n)=O(n)+O(n)+O(n)+O(n)=>                      f(n)=Ο(n)!!!!           ΛΟΓΩ ότι  f(n-4)=f(1)=ΣΤΑΘΕΡΟ_ΒΕΛΤΙΣΤΟ=ΚΒΑΝΤΟ υπολογισμών. Στο τέλος θα μου πείτε έχω δίκαιο μόνο και μόνο για να μην τα διαβάσετε.Καληνύχτα!

[aroniotis]

....Στο τέλος θα μου πείτε έχω δίκαιο μόνο και μόνο για να μην τα διαβάσετε.Καληνύχτα!

δικιο εχεις!!! 

[batman]

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

Στο τέλος θα μου πείτε έχω δίκαιο μόνο και μόνο για να μην τα διαβάσετε.Καληνύχτα!

[GOODmorning]

Δεν έχω πρόβλημα απορία έχω:-)Το θέμα είναι αν υπάρχει κάποιο λάθος....Ξέρεις δεν μπόρεσα να διαβάσω για ασεπ και αν διάβαζα το μόνο που είχα στο πρόγραμμα ήταν πολυπλοκότητες γιαυτό τόση..απορία.Βάλανε και πολλές ερωτήσεις.

[nobody]

πχ f(5)=f(4)+5    f(n)=f(n-1)+n           
f(4)=f(3)+4         f(n-1)=f(n-2)+n-1
f(3)=f(2)+3         f(n-2)=f(n-3)+n-2
f(2)=f(1)+2         f(n-3)=f(n-4)+n-3
f(1)=1                f(n-4)=1=γν.

f(n)=f(n-4)+n-3+n-2+n-1+n => f(n)=4n-1-2-3+f(n-4)=>f(n)=(n-1)+(n-2)+(n-3)+( n+f(n) )=>f(n)=O(n)+O(n)+O(n)+O(n)=>                      f(n)=Ο(n)!!!!           ΛΟΓΩ ότι  f(n-4)=f(1)=ΣΤΑΘΕΡΟ_ΒΕΛΤΙΣΤΟ=ΚΒΑΝΤΟ υπολογισμών. Στο τέλος θα μου πείτε έχω δίκαιο μόνο και μόνο για να μην τα διαβάσετε.Καληνύχτα!

Σε ποιο σημείο απέδειξες ότι  για κάθε n, το f(n-4)=1 και η πολυπλοκότητά του είναι Ο(n);

[GOODmorning]

το f(n-4) αντικαθιστά το f(1) που είναι δίπλα, θεωρώντας για n=5. H ίδια λογική θα ισχύει και για n=100 οπότε f(n-99)=f(1)="κβάντο_βάση γεωμετρικής προόδου"

[GOODmorning]

Λάθος έτσι:Γεωμετρικής προόδου δεν ισχύει!

[GOODmorning]

Καλημέρα! Τελικά για να μην το κουράζουμε-ω τώρα που το ξανασκέφτομαι πιστεύω ότι όσον αφορά το n θα έπρεπε να έλεγε ότι τείνει στο άπειρο ή τουλάχιστον ότι έχουμε τη συνάρτηση f(n) για ΟΠΟΙΟΔΗΠΟΤΕ-ΚΑΘΕ n. Διαφορετικά αν θέσουμε ένα όριο στο n πχ 100.000.000 γιατί πιστεύουμε ότι ο αλγόριθμός μας δεν πρόκειται να είναι πιο πολύπλοκος από αυτό το n όταν θα τον τρέχουμε τότε η συνάρτηση-άθροισμα n*(n-1)/2 μπορεί να προσεγγιστεί στην πολυπλοκότητα με βάση την ευθεία:
50.000.000*n=O(n). Αν έχω λάθος κάπου ελπίζω να διορθωθώ!