[Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός

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

[Admins]

Για αλλαγή του public name σας, επικοινωνήστε με έναν από τους Admins.

[Thunderlord]

Στο 1 κι εγώ ο() βρήκα αλλά έβαλα b  

Μπορεί μήπως κάποιος να γράψει λίγο πολυπλοκότητες για το 5 γιατί λίγο έχω μπερδευτεί;

Για το 11, εγώ το θεώρησα αυτό το πρόβλημα σαν αυτό που υπάρχει στις διαφάνειες του εργαστηρίου με την πρόσληψη. Εκεί έχουμε στην ουσία έναν πίνακα με την αξιολόγηση των εργαζομένων και διαλέγουμε το μεγαλύτερο. Βρίσκει ότι Ε(x) του πίνακα είναι 1/i και άρα Θ(log)

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

[GkBlue]

Μπορεί μήπως κάποιος να γράψει λίγο πολυπλοκότητες για το 5 γιατί λίγο έχω μπερδευτεί;

mergesort: T(n) =  2T(n/2) + Θ(n) -> Θ(nlogn)
quicksort: Χειρότερη Περίπτωση: T(n) = T(n-1) + Θ(n) -> O(n^2)
               Καλύτερη Περίπτωση:  T(n) =  2T(n/2) + Θ(n) -> Θ(nlogn)

Ο Ψούνης είχε αναφέρει κάπου στα βίντεο του ότι γενικά η πιο γρήγορη και αυτή που χρησιμοποιείται είναι η quicksort

[Thunderlord]

Τώρα που ξαναβλέπω τα αποτελέσματα του κώδικά μου κι εγώ βρήκα τα 90,91 απλά δεν τα έγραψα, ό,τι να ναι.

Θενξ guys,
 άμα διαφωνεί κανείς με αυτό που είπα για τη μέση τιμή πιο πάνω ας μου πει

[Boss Rob]

Λοιπόν παιδία συμφωνώ σχεδόν σε όλα για τα θέματα της πτυχιακής και έχω να προσθέσω σε αυτό

Για το 11, εγώ το θεώρησα αυτό το πρόβλημα σαν αυτό που υπάρχει στις διαφάνειες του εργαστηρίου με την πρόσληψη. Εκεί έχουμε στην ουσία έναν πίνακα με την αξιολόγηση των εργαζομένων και διαλέγουμε το μεγαλύτερο. Βρίσκει ότι Ε(x) του πίνακα είναι 1/i και άρα Θ(log)

Είχε αναφερθεί στο εργαστήριο ότι πέφτει πάντα η ερώτηση ποια η πιθανότητα το στοιχείο i σε έναν πίνακα να είναι μεγαλύτερο από τα προηγούμενα και αυτή είναι 1/i+1.Το ερώτημα 10 είναι σχεδόν η ίδια ερώτηση άρα νομίζω έχεις δίκιο και το σωστό στο 10 είναι το b ενώ στο 11 το a.   

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

Τέλος μήπως έχει κάποιος σωστό κώδικα για το θέμα του φετινού Ιουλίου διότι έχω καεί με αυτο;

[Thunderlord]

Λοιπόν παιδία συμφωνώ σχεδόν σε όλα για τα θέματα της πτυχιακής και έχω να προσθέσω σε αυτόΕίχε αναφερθεί στο εργαστήριο ότι πέφτει πάντα η ερώτηση ποια η πιθανότητα το στοιχείο i σε έναν πίνακα να είναι μεγαλύτερο από τα προηγούμενα και αυτή είναι 1/i+1.Το ερώτημα 10 είναι σχεδόν η ίδια ερώτηση άρα νομίζω έχεις δίκιο και το σωστό στο 10 είναι το b ενώ στο 11 το a.   

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

Τέλος μήπως έχει κάποιος σωστό κώδικα για το θέμα του φετινού Ιουλίου διότι έχω καεί με αυτο;

Για τον αλγόριθμο του Dijkstra δες αυτό το βίντεο, τα εξηγεί υπέροχα
<a href="https://www.youtube.com/watch?v=eVIIkgiSaBc" target="_blank">http://www.youtube.com/watch?v=eVIIkgiSaBc</a>

Για τον κώδικα του Ιούλη κι εγώ το δουλεύω, αν βγάλω άκρη θα σου πω.
Μου φαίνεται πως η λίστα έχει αλλάξει από τότε που βάλανε το θέμα γιατί όλες οι λέξεις έχουν αξία της τάξης 10^5 και δεν ξέρω πως πρέπει να καταλήξω στο -10,6 που βγαίνει 

[egw_mhxanologos_h8ela]

στα θεματα του ιουλιου 2020 η "πιθανή" απάντηση ειναι οτι δεν μπορει να εφαρμοστει το θεωρημα κυριαρχίας.ειναι σωστό αυτο; εχω την εντυπωση οτι εφαρμοζεται η τελευταια περίπτωση του κεντρικου θεωρηματος.

[vterz]

στα θεματα του ιουλιου 2020 η "πιθανή" απάντηση ειναι οτι δεν μπορει να εφαρμοστει το θεωρημα κυριαρχίας.ειναι σωστό αυτο; εχω την εντυπωση οτι εφαρμοζεται η τελευταια περίπτωση του κεντρικου θεωρηματος.

Για αυτη την ερωτηση λες ετσι?

[egw_mhxanologos_h8ela]

Για αυτη την ερωτηση λες ετσι?

Ναι για αυτην

[vterz]

Ναι για αυτην

Ναι νομίζω έχεις δίκιο

Ο αναδρομικός τύπος είναι T(n) = 2^n  + 3T(n/3), η 2^n ειναι Ω( n^(log_3 (3) + ε) ) και η 2^n αυξουσα οποτε βγαινει αυτό που λες, ετσι το βγαζω εγω τουλαχιστον 

[Πατερ Ημμυων]

Φεβρουάριος 2020 , ερώτηση 13 . Πως σκεφτόμαστε ?

[Caterpillar]

Φεβρουάριος 2020 , ερώτηση 13 . Πως σκεφτόμαστε ?

+1
επίσης ίδια χρονιά ερωτ 10 το 1/(j+1) είναι το σωστό?

[vterz]

+1
επίσης ίδια χρονιά ερωτ 10 το 1/(j+1) είναι το σωστό?

Το 1/(i+1) νομίζω. Είναι η πιθανότητα το i να είναι το max μεταξύ των {0,1,..,i-1,i}

[Caterpillar]

Το 1/(i+1) νομίζω. Είναι η πιθανότητα το i να είναι το max μεταξύ των {0,1,..,i-1,i}

ευχαριστώ, τελικά αυτό είχαν πει και οι περσινοί μια σελίδα πίσω.

[vterz]

Φεβρουάριος 2020 , ερώτηση 13 . Πως σκεφτόμαστε ?

Για την diff2 διαισθητικά μου φαίνεται σαν το παράδειγμα με τον μέσο χρόνο εκτέλεσης της bubblesort.
Σε παράδειγμα που έγινε στο μάθημα προέκυψε Θ(n^2 + M*n*ln n). Το n^2 είναι για τους ελέγχους κλπ και το n*ln(n) για τις εκχωρήσεις, εντός της if, που ζητάει εδώ ( υποθέτοντας Μ = Θ(1) )

Οπότε έχεις Τ2 = Θ(n*ln n), έχεις και το Τ1 από προηγούμενο ερώτημα και τα συγκρίνεις

[Caterpillar]

φεβ 2020 στην 5 ποια είναι σωστά, σίγουρο το c είναι σωστό, υπάρχουν και άλλα που είναι σωστά? και το β και αυτό σωστό μου φαίνειται.
Ιουλ 2020, ερώτηση 11 πως βρίσκουμε το σωστό?