THMMY.gr

Topic που αφορά τις ασκήσεις του μαθήματος. Stay on topic!

καμια ιδεα για το θεμα Γ, απο την 1η προοδο του 15?

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

Έλενξα αν ισχύει (ταβάνι) (https://latex.codecogs.com/gif.latex?n/2%5Cgeq%20sqrt%28x%29) και βγήκε ότι ισχύει μόνο για την πρώτη (η δεύτερη και η τρίτη βγάζουν λάθος για κάποια μικρά n)

Και για τον αναμενόμενο χρόνο εκτέλεσης είναι sqrt(x) αν έχει ρίζα και n/2 αν δεν έχει ρίζα, οπότε T(n)=k*sqrt(x)+(1-k)*n/2  , όπου k η πιθανότητα να έχει ρίζα και 1-k η πιθανότητα να μην έχει ρίζα. Για να προσδιοριστει το k πρέπει να σου δώσει ένα διάστημα τιμών για το n όμως...

είσαι σίγουρος για αυτό; Η δευτερη νομίζω επιστρέφει σωστή τιμή για χ = 1, 4, 9 και σίγουρα για οποιοδήποτε χ > 9

ναι σωστα και η δευτερη ειναι ορθη

ευχαριστω πολυ!  :D

για αυτο που λες,βρηκα στο περσινο τοπικ το εξης:
αρα το δινει κ αυτο  ;)

Βέβαια και αυτή η λύση δεν βγάζει πολυ νόημα αλλά οκ  :D

Νομίζω πως πρέπει να πάριες ως δεδομένο ότι ο αριθμός που σου δίνει είναι τετράγωνο ακέραιου αριθμού

Για θέματα όπως το 1ο Ιουνίου 2015 ποια μεθοδολογία χρησιμοποιούμε για να αποδείξουμε ότι είναι σωστό ή λάθος?
Φαίνεται απλό αλλά δεν μπορώ να βρω τι είδους απόδειξη ΣΩΣΤΟΥ/ΛΑΘΟΥΣ τον καλύπτει.

Επίσης, , μήπως υπάρχουν άλλα παλιά θέματα, πέρα από του Ιουνίου 2015 ?

Στο πρώτο ερώτημα  στο θέμα πρώτο στην Α_πρόοδο 2015 πως βρίσκουμε ότι είναι λάθος ή σωστό? Δεν μπορώ να αποδείξω ούτε ότι είναι λάθος(με αντιπαράδειγμα) ούτε ότι είναι σωστό....  Είδα σε κάποια παλαιότερα ποστ που τα παιδιά λένε ότι είναι σωστό αλλά δεν λένε πως καταλήγουν σε αυτό το συμπέρασμα.  :(   :(   :(


Για το πρώτο θέμα του ιουνίου του 2015 και γενικότερα τέτοιου στυλ, αν έχω καταλάβει σωστά "πηγαίνεις" με επαγωγές απο την αρχική ανίσωση στην ζητούμενη(αν είναι σωστό). Βέβαια δεν έχω θριαμβεύσει στο συγκεκριμένο μάθημα οπότε μπορεί να λέω και μπούρδες....   :D

edit: νομίζω πως για να λύσεις το α απο το πρώτο θέμα του ιουνίου 2015 κάνεις το εξής: lim((n+1)^n)/(n^(n+1))=...=lim(1+(1/n))^n)/n ->de l' hospital-> και το αποτέλεσμα βγαίνει άπειρο. Άρα το πρώτο είναι λάθος.

πρωτον διαφωνω με το οριο εγω το βγαζω 0 αλλα μπορει να το εκανα βιαστικα οποτε σορρυ  :P

δευτερον για το 3ο θεμα του Ιουνιου του 15 τι βρηκατε? εγω θα ελεγα οχι γιατι το προβλημα δε μου φαινεται οτι εγγειται στον τροπο με τον οποιο εισαγονται τα δεδομενα, κατι το οποιο νομιζω οτι επηρεαζει ενας τυχαιοκρατικος αλγοριθμος. Αλλα και παλι μπορει να λεω βλακειες οποτε αν κανεις ειναι σιγουρος ας πει :)

επισης για το 2ο νομιζω ειναι λαθος..εγω εκανα αυτο πειτε καμια γνωμη

Το έψαξα αρκετά και όντως το όριο είναι ο καλύτερος τρόπος για να αποδείξεις τέτοιου είδους σχέσεις.Στην περίπτωση του (β) ερωτήματος υπολόγισα το lim n-.>oo f(n)/g(n) όπου g(n)=nlogn (αφού log(n!)=Θ(nlogn)).
Το βγάζω κι εγώ λάθος.

Έχεις απόλυτο δίκιο όντως το όριο βγαίνει μηδέν. Σορριιιιιιιιιι.......

Στην πρώτη πρόοδο του 2014, στο δεύτερο θέμα, το Α δεν έχει καλύτερο χρόνο εκτέλεσης?

edit:Βασικά έχω την αίσθηση ότι είναι το πρώτο αλλά δεν ξέρω πως να το δείξω.... :P

σαν σκεψη συμφωνω, αλλα το c1 γιατι εφυγε;  :???:

νομιζω οτι συμφωνω αφου και να αλλαξουμε τον τροπο που εισαγονται τα δεδομενα στον αλγοριθμο δεν θα επηρεαστει το αποτελεσμα!  ;)

για το 1ο ναι παραλειψη πρεπει να το εχω το c1 η λογικη ομως δεν αλλαζει γιατι παλι ουσιαστικα καταληγεις στο οτι lgn = Θ(sqrt(n)) Ο(sqrt(n)) που ειναι λαθος οσο μεγαλο c1 και να παρεις παντα θα υπαρχει μια τιμη για n>4 που το lgn θα ειναι μεγαλυτερο...

για το 2ο μου ειπε ενας συναδελφος τη λυση του και συμφωνω...λοιπον σκεψου οτι ο αλγοριθμος που δινει η εκφωνηση στη μονη περιπτωση που σου δινει λαθος αποτελεσμα ειναι αν η απαντηση ειναι OXI και επιστρεψει ΝΑΙ. Οποτε μπορεις να πεις οτι αν το input που δεχεται ο αλγοριθμος το περασεις διαδοχικα απο τον ιδιο αλγοριθμο (αναδρομικα) τοτε η πιθανοτητα να σου επιστρεψει λαθος output μειωνεται...αρα το περναμε τοσες φορες ωστε η πιθανοτητα λαθους να πεσει στο 1%

εγω βρηκα το 2ο οτι ειναι καλυτερο με κεντρικο θεωρημα.

Το lgn είναι ασυμπτωτικά ταχύτερο από το sqrt(n) οπότε ισχύει ότι lgn=O(sqrt(n)). Αυτό που δεν ισχύει είναι ότι lgn=Ω(sqrt(n)) οπότε δεν ισχύει και το Θ.

ναι ναι σωστος

Σ'ευχαριστώ πολύ για τη βοήθεια!!!

Στην 2η πρόοδο του 2015 στο θέμα 1 ποια ήταν η αναδρομική σχέση που βγάλατε?

Έχει υπολογίσει κάποιος στα θέματα Ιουνίου του 2016, θέμα δεύτερο το μέσο κέρδος Ε[Χ^2] ;

+1