[Ανάλυση Αλγορίθμων] Απορίες στις ασκησεις 2016

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

[12:00-13:30]

Η γραμματεία είναι ανοιχτή καθημερινά 12:00-13:30

[Vlassis]

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

[Vlassis]

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

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

[Ancient]

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

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

Έλενξα αν ισχύει (ταβάνι) και βγήκε ότι ισχύει μόνο για την πρώτη (η δεύτερη και η τρίτη βγάζουν λάθος για κάποια μικρά n)

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

[Aristos]

ισχύει μόνο για την πρώτη (η δεύτερη και η τρίτη βγάζουν λάθος για κάποια μικρά n)

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

[Ancient]

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

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

[Vlassis]

Για να προσδιοριστει το k πρέπει να σου δώσει ένα διάστημα τιμών για το n όμως...

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

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

Το θέμα συνέχιζε  ...αν τρέξουμε τον αλγόριθμο από 1 ως 10.

αρα το δινει κ αυτο 

[Ancient]

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

[Μπιγκόνια]

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

[sabpap]

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

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

[isitsou]

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


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

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

[κύριος Φασόλης]

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

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

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

[κύριος Φασόλης]

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

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

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

[sabpap]

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

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

[isitsou]

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

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

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

[isitsou]

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

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