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

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Αντιστοίχηση Μαθημάτων ΝΠΣ με ΠΠΣ
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ.

Για ανανέωση (ή προσθήκη νέου) avatar, πρέπει η μεγαλύτερη διάσταση της εικόνας να είναι 110 pixels.

[Vlassis]

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

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

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

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

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

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

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

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

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

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

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

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

[Ancient]

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

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

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

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

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

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

[isitsou]

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

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

[Eilex]

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

[TheoProt]

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

[Παναγιώτης]

Έχει υπολογίσει κάποιος στα θέματα Ιουνίου του 2016, θέμα δεύτερο το μέσο κέρδος

+1