THMMY.gr

Μαθήματα Βασικού Κύκλου => Ανάλυση και Σχεδιασμός Αλγορίθμων => Topic started by: Αλέκος από Κω on September 03, 2019, 09:24:20 am



Title: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Αλέκος από Κω on September 03, 2019, 09:24:20 am
Εδώ μπορείτε να σχολιάζετε τα θέματα και να συζητάτε τις όποιες απορίες σας πάνω σε παλιά θέματα.

edit by leukos: format.


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: twil on September 25, 2019, 19:40:32 pm
Μπορεί κάποιος να πει μια λύση για το 1ο θεμα του Ιουνίου; :???: :???:


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Σοκοφρέτας on September 26, 2019, 15:30:11 pm
Ίσως κάποιος κάποια ιδέα για το θέμα 4 - Ιούνιος 2019 ?
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy)  


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Σοκοφρέτας on September 26, 2019, 15:36:21 pm
Μπορεί κάποιος να πει μια λύση για το 1ο θεμα του Ιουνίου; :???: :???:

Νομίζω θα σε βοηθήσει αρκετά αυτό:

https://www.youtube.com/watch?v=JRFU5ZmL_A0&list=PLLMmbOLFy25HT75HvBGDzqu9KIhRazwoH&index=1


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: 00128419 on September 26, 2019, 15:51:31 pm
Θεμα 2ο 2019 συμφωνειτε οτι T(n)= 2T(n/4)+ Θ(sqrt(n))?

Επισης για το Θεμα 3ο με το Huffman, μου φαινεται σωστος ο ισχυρισμος αλλα δεν ειμαι σιγουρος πως να τον αποδειξω μαθηματικα (ισως με επαγωγη η απαγωγη σε ατοπο)


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: panos98 on September 26, 2019, 15:55:26 pm
Παιζει να ειναι σωστο ναι


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Φασολάκια με Πρόβειο on September 26, 2019, 16:00:31 pm
Θεμα 2ο 2019 συμφωνειτε οτι T(n)= 2T(n/4)+ Θ(sqrt(n))?

Επισης για το Θεμα 3ο με το Huffman, μου φαινεται σωστος ο ισχυρισμος αλλα δεν ειμαι σιγουρος πως να τον αποδειξω μαθηματικα (ισως με επαγωγη η απαγωγη σε ατοπο)
Μπορεις να αποδειξεις οτι ειναι λαθος με ενα αντιπαραδειγμα.


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Αλέκος από Κω on September 26, 2019, 16:07:58 pm
Ίσως κάποιος κάποια ιδέα για το θέμα 4 - Ιούνιος 2019 ?
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy)  
+++


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: sterpapi on September 26, 2019, 19:54:28 pm
Όποιος έχει κάποια λύση από τα θέματα του Ιουνίου ας ανεβάσει


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Deadhead on September 27, 2019, 16:31:02 pm
Όποιος έχει κάποια λύση από τα θέματα του Ιουνίου ας ανεβάσει
+1

Στην άσκηση 1.1 και 1.4 αυτό το i τι είναι; Επίσης λύνεται με όριο ή τον ορισμό του Ο(g(n));


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: RioCompiler on September 27, 2019, 16:33:04 pm
Ln(n) ειναι
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy) 


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: DarkTakis on September 27, 2019, 20:29:43 pm
Λύσεις που πιστεύω για θέμα 1 και 3


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: panos98 on September 27, 2019, 21:15:31 pm
Πολυ σωστες


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: sterpapi on September 30, 2019, 00:10:11 am
Έχει κάποιος λύση για το δεύτερο θέμα του Ιουνίου;


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: xaotikos on September 30, 2019, 10:37:24 am
Ίσως κάποιος κάποια ιδέα για το θέμα 4 - Ιούνιος 2019 ?
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy) 

Με κάθε επιφύλαξη

Όπως το είδα νομίζω ότι φτιάχνουμε έναν n*n πίνακα που θα κρατάμε μεγέθη max data και έναν n*n που κρατάμε τα reboots.

Οι γραμμές των πινάκων αντιστοιχούν στην Xi μέρα και οι στήλες στα Sj.

 Δεδομένου ότι την n μέρα δν γίνεται reboot γεμίζουμε την n γραμμή  ως εξής Data[n,1...n] = min(Xn,Si) (αρχική συνθήκη)

Κάθε στοιχείο επόμενης προς τα πάνω γραμμής γεμίζει ως εξής

Data[i, j] = max[(Data[i+1,j+1]+min(Xi,Sj)), (0+Data[i+1,1])]  (αναδρομική σχέση) 

Δηλαδή κάθε στοιχείο του πίνακα αντιστοιχεί σε μια μέρα i δεδομένου ότι έγινε reboot πριν από j μέρες και η βέλτιστη υποδομή λειτουργεί από εκείνη τη στιγμή και έπειτα, αντιστοιχωντας στο [i, j] στοιχείο του πίνακα το μέγιστο μέγεθος δεδομένων που μπορεί να επεξεργαστεί το σύστημα από κει και έπειτα.

Προφανώς ανάλογα με το αποτελεσμα της σύγκρισης που κάνουμε για να γεμίσουμε τον πίνακα Data μπορούμε να βάζουμε 0 η 1 στα αντίστοιχα στοιχεία ενός n*n πίνακα Reboot για να ανακατασκευασουμε τη λύση μετά.

Το μέγιστο μέγεθος δεδομένων που μας ζητάει το πρόβλημα αντιστοιχει στο Data[1,1]. Επίσης γεμίζουμε τους πίνακες μόνο μέχρι τα στοιχεία της κυρίας διαγωνίου.

Για να βρούμε τις μέρες που γίνονται reboot ξεκινάμε από το Reboot[1,1] αν δούμε 0 σε κάποιο στοιχείο ελέγχουμε το Reboot[i+1,j+1] αν δούμε 1 εκτυπωνουμε το i (μέρα reboot) και επόμενος έλεγχος στο Reboot[i+1,1]


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Σοκοφρέτας on September 30, 2019, 14:33:40 pm
Έχει κάποιος λύση για το δεύτερο θέμα του Ιουνίου;

αν μπορεί κάποιος να επιβεβαιώσει για την ορθότητα..


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Σοκοφρέτας on September 30, 2019, 23:29:20 pm
Τα ανεβάζω εδώ γιατί δεν είναι καλή ποιότητα!!  :(  :-\


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: elenich on October 01, 2020, 00:18:36 am
Έχει μήπως λύσει κανένας τα θέματα από την Πτυχιακή Φεβρουαρίου 2020;


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Thunderlord on October 01, 2020, 12:31:28 pm
Έχει μήπως λύσει κανένας τα θέματα από την Πτυχιακή Φεβρουαρίου 2020;

Έγω τώρα μπαίνω στο τελευταίο κομμάτι, αν θες να συζητήσουμε τα προηγούμενα ευχαρίστως


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: kanou_tom on October 01, 2020, 13:01:37 pm
Έχει μήπως λύσει κανένας τα θέματα από την Πτυχιακή Φεβρουαρίου 2020;

Που υπάρχουν τα θέματα διαθέσιμα;


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Thunderlord on October 01, 2020, 13:11:46 pm
Που υπάρχουν τα θέματα διαθέσιμα;

https://www.thmmy.gr/smf/index.php?action=tpmod;dl=item5064


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Todo on October 01, 2020, 14:14:13 pm
Έγω τώρα μπαίνω στο τελευταίο κομμάτι, αν θες να συζητήσουμε τα προηγούμενα ευχαρίστως
αν θέλετε ανεβάστε λύσεις να δούμε και εμείς :P


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Thunderlord on October 01, 2020, 14:54:44 pm
Ανεβάζω τις δικές μου αλλά δεν είμαι σίγουρος για κάποια, οπότε πείτε μου γνώμη:

1. b
2. c
3. (4)
4. BD
5. no idea
6. το ίδιο με το 3 ή μου φαίνεται;
7. DE
8. Θ(n)
9. Θ(n^2)
10. b
11. a
12 (4)
13. b
14 (2)
15. b
16. (173.9)
17. βρήκα μόνο την 95 αλλά δεν παίζει να είναι σωστό


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Todo on October 01, 2020, 15:13:30 pm
Ανεβάζω τις δικές μου αλλά δεν είμαι σίγουρος για κάποια, οπότε πείτε μου γνώμη:

1. b
2. c
3. (4)
4. BD
5. no idea
6. το ίδιο με το 3 ή μου φαίνεται;
7. DE
8. Θ(n)
9. Θ(n^2)
10. b
11. a
12 (4)
13. b
14 (2)
15. b
16. (173.9)
17. βρήκα μόνο την 95 αλλά δεν παίζει να είναι σωστό

τέλεια. σε καμιά ώρα ανεβάζω και εγώ


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: GkBlue on October 01, 2020, 16:11:18 pm
Ανεβάζω τις δικές μου αλλά δεν είμαι σίγουρος για κάποια, οπότε πείτε μου γνώμη:

1. b
2. c
3. (4)
4. BD
5. no idea
6. το ίδιο με το 3 ή μου φαίνεται;
7. DE
8. Θ(n)
9. Θ(n^2)
10. b
11. a
12 (4)
13. b
14 (2)
15. b
16. (173.9)
17. βρήκα μόνο την 95 αλλά δεν παίζει να είναι σωστό

Στα περισσότερα συμφωνώ με τα δικά σου.
1. α (το οριο στο wolfram =0 αρα Ο(_))
5. b, c pretty sure (η quicksort εχει O(n^2) στην χειρότερη περίπτωση)
11. d (λιγο random δεν ειμαι καθολου σιγουρος για οτι εχει Ε[])
17. 95, 91, 90


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Todo on October 01, 2020, 16:32:20 pm
1-->a
2-->c
3-->4
4-->BD
5-->c
6-->4
7-->ED
8-->d
9-->d
10-->b
11-->a(δεν ειμαι σίγουρη)
12-->4
13-->b
14-->3
15-->b
16-->114.1
17-->90,91,95


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: GkBlue on October 01, 2020, 16:41:42 pm
14-->3
14 (2)
απ' ότι βλέπω και τα 2 είναι σωστά εξαρτάται αν θα κάνεις 1 μεγάλο ή 2 μικρά στην αρχή αλλά το αποτέλεσμα είναι 4,5 sec και στις 2 περιπτώσεις


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Todo on October 01, 2020, 16:42:57 pm
Στα περισσότερα συμφωνώ με τα δικά σου.
1. α (το οριο στο wolfram =0 αρα Ο(_))
5. b, c pretty sure (η quicksort εχει O(n^2) στην χειρότερη περίπτωση)
11. d (λιγο random δεν ειμαι καθολου σιγουρος για οτι εχει Ε[])
17. 95, 91, 90
στο 14 δεν είναι προϋπόθεση οτι πρέπει να περάσει και απο τους 4 σταθμούς χωρίς να προσπεράσει κάποιον;


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: GkBlue on October 01, 2020, 16:47:22 pm
στο 14 δεν είναι προϋπόθεση οτι πρέπει να περάσει και απο τους 4 σταθμούς χωρίς να προσπεράσει κάποιον;

νομίζω πως όχι, είναι οι διαθέσιμες πλατφόρμες που έχεις για να φτάσεις στην κορυφή. Απλώς σου δίνει έναν μικρότερο πίνακα αντί για τον H για να "δουλέψεις" το πρόβλημα σε μικρότερο scale. Ή τουλάχιστον έτσι το καταλαβαίνω εγώ.


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Todo on October 01, 2020, 16:57:44 pm
νομίζω πως όχι, είναι οι διαθέσιμες πλατφόρμες που έχεις για να φτάσεις στην κορυφή. Απλώς σου δίνει έναν μικρότερο πίνακα αντί για τον H για να "δουλέψεις" το πρόβλημα σε μικρότερο scale. Ή τουλάχιστον έτσι το καταλαβαίνω εγώ.

Πάντως στο αντίστοιχο ερωτημα στο επαναλυπτικο quiz δινει σωστη απάντηση την μέγιστη παρόλο που οι λιγότερες στάσεις μόλις παρατηρησα οτι δείχνουν μικρότερο χρονο


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Thunderlord on October 01, 2020, 16:58:28 pm
Στο 1 κι εγώ ο() βρήκα αλλά έβαλα b  :P

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

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

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


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: GkBlue on October 01, 2020, 17:08:21 pm
Μπορεί μήπως κάποιος να γράψει λίγο πολυπλοκότητες για το 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


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Thunderlord on October 01, 2020, 17:17:23 pm
Τώρα που ξαναβλέπω τα αποτελέσματα του κώδικά μου κι εγώ βρήκα τα 90,91 απλά δεν τα έγραψα, ό,τι να ναι.

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


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Boss Rob on October 01, 2020, 20:42:32 pm
Λοιπόν παιδία συμφωνώ σχεδόν σε όλα για τα θέματα της πτυχιακής και έχω να προσθέσω σε αυτό
Για το 11, εγώ το θεώρησα αυτό το πρόβλημα σαν αυτό που υπάρχει στις διαφάνειες του εργαστηρίου με την πρόσληψη. Εκεί έχουμε στην ουσία έναν πίνακα με την αξιολόγηση των εργαζομένων και διαλέγουμε το μεγαλύτερο. Βρίσκει ότι Ε(x) του πίνακα είναι 1/i και άρα Θ(log)
Είχε αναφερθεί στο εργαστήριο ότι πέφτει πάντα η ερώτηση ποια η πιθανότητα το στοιχείο i σε έναν πίνακα να είναι μεγαλύτερο από τα προηγούμενα και αυτή είναι 1/i+1.Το ερώτημα 10 είναι σχεδόν η ίδια ερώτηση άρα νομίζω έχεις δίκιο και το σωστό στο 10 είναι το b ενώ στο 11 το a.   

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

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




Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Thunderlord on October 01, 2020, 20:54:01 pm
Λοιπόν παιδία συμφωνώ σχεδόν σε όλα για τα θέματα της πτυχιακής και έχω να προσθέσω σε αυτόΕίχε αναφερθεί στο εργαστήριο ότι πέφτει πάντα η ερώτηση ποια η πιθανότητα το στοιχείο i σε έναν πίνακα να είναι μεγαλύτερο από τα προηγούμενα και αυτή είναι 1/i+1.Το ερώτημα 10 είναι σχεδόν η ίδια ερώτηση άρα νομίζω έχεις δίκιο και το σωστό στο 10 είναι το b ενώ στο 11 το a.   

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

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


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

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


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: egw_mhxanologos_h8ela on April 08, 2021, 11:25:03 am
στα θεματα του ιουλιου 2020 η "πιθανή" απάντηση ειναι οτι δεν μπορει να εφαρμοστει το θεωρημα κυριαρχίας.ειναι σωστό αυτο; εχω την εντυπωση οτι εφαρμοζεται η τελευταια περίπτωση του κεντρικου θεωρηματος.


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: vterz on April 08, 2021, 15:52:26 pm
στα θεματα του ιουλιου 2020 η "πιθανή" απάντηση ειναι οτι δεν μπορει να εφαρμοστει το θεωρημα κυριαρχίας.ειναι σωστό αυτο; εχω την εντυπωση οτι εφαρμοζεται η τελευταια περίπτωση του κεντρικου θεωρηματος.

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


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: egw_mhxanologos_h8ela on April 08, 2021, 22:10:55 pm
Για αυτη την ερωτηση λες ετσι?
Ναι για αυτην


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: vterz on April 08, 2021, 22:20:30 pm
Ναι για αυτην

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

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


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Πατερ Ημμυων on April 11, 2021, 14:00:42 pm
Φεβρουάριος 2020 , ερώτηση 13 . Πως σκεφτόμαστε ?


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Caterpillar on April 11, 2021, 14:04:45 pm
Φεβρουάριος 2020 , ερώτηση 13 . Πως σκεφτόμαστε ?
+1
επίσης ίδια χρονιά ερωτ 10 το 1/(j+1) είναι το σωστό?


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: vterz on April 11, 2021, 14:56:08 pm
+1
επίσης ίδια χρονιά ερωτ 10 το 1/(j+1) είναι το σωστό?

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


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Caterpillar on April 11, 2021, 15:05:15 pm
Το 1/(i+1) νομίζω. Είναι η πιθανότητα το i να είναι το max μεταξύ των {0,1,..,i-1,i}
ευχαριστώ, τελικά αυτό είχαν πει και οι περσινοί μια σελίδα πίσω.


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: vterz on April 11, 2021, 15:16:31 pm
Φεβρουάριος 2020 , ερώτηση 13 . Πως σκεφτόμαστε ?

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

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



Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Caterpillar on April 11, 2021, 16:53:32 pm
φεβ 2020 στην 5 ποια είναι σωστά, σίγουρο το c είναι σωστό, υπάρχουν και άλλα που είναι σωστά? και το β και αυτό σωστό μου φαίνειται.
Ιουλ 2020, ερώτηση 11 πως βρίσκουμε το σωστό?


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Caterpillar on April 14, 2021, 17:24:47 pm
φεβ 2020 στην 5 ποια είναι σωστά, σίγουρο το c είναι σωστό, υπάρχουν και άλλα που είναι σωστά? και το β και αυτό σωστό μου φαίνειται.
Ιουλ 2020, ερώτηση 11 πως βρίσκουμε το σωστό?

https://www.thmmy.gr/smf/index.php?action=tpmod;dl=item5291
Ιουλ 2020, ερωτ 11 μήπως τελικά λέιπει κομμάτι του κώδικα? Γιατί σωστή απάντηση με αυτόν τον κώδικα δεν μπορώ να βρω.


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Sloth on April 14, 2021, 17:42:26 pm
https://www.thmmy.gr/smf/index.php?action=tpmod;dl=item5291
Ιουλ 2020, ερωτ 11 μήπως τελικά λέιπει κομμάτι του κώδικα? Γιατί σωστή απάντηση με αυτόν τον κώδικα δεν μπορώ να βρω.
Το πιθανοτερο ειναι να λειπει γιατι δεν εχει λογικη


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Caterpillar on May 19, 2021, 20:12:39 pm
Υπάρχει κάποιος που έχει τον κώδικα  που έγραψε στα θέματα του Ιουνίου πέρσυ?
Ή κάποιος άλλος που το έχει κάνει τώρα ?

Αν ναι ας το φέρει και από εδώ.


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Rick Deckard on May 31, 2021, 20:51:14 pm
Ιούλιος 2020, πως βάζουμε να δούμε πού κόβεται το string? έχω σκάσει όλο το απόγευμα


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Caterpillar on May 31, 2021, 21:02:09 pm
Ιούλιος 2020, πως βάζουμε να δούμε πού κόβεται το string? έχω σκάσει όλο το απόγευμα
και εγώ όλο το πρωί, το έστειλα σε φίλο, δεν έκανε και αυτός τίποτα, μετά το χαιρέτησα, είναι παντελώς κουλό. Εδώ εμείς δεν μπορούμε να το λύσουμε , τώρα , θα μπορούμε να λύσουμε κάτι τέτοιο + αλλες ερωτήσεις μέσα σε μία ώρα?  Καλά θα πάει και αυτό το μάθημα.

 


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Rick Deckard on May 31, 2021, 21:05:48 pm
Πραγματικά, θα δώσω και εξετάσεις για 2η ελπίδα...


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Caterpillar on May 31, 2021, 21:10:20 pm
Πραγματικά, θα δώσω και εξετάσεις για 2η ελπίδα...
εκεί θα χεις μέσα στην 1 ώρα να κάνεις αυτό το κομμάτι του μαθήματος συν πολυπλοκότητες + πιθανότητες. Μπρος γκρεμός και πίσω ρέμα  :D :D


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Rick Deckard on June 03, 2021, 18:11:24 pm
Έχει κανείς θέματα πτυχιακής 2021 Φλεβάρη;


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Caterpillar on June 03, 2021, 18:19:37 pm
Έχει κανείς θέματα πτυχιακής 2021 Φλεβάρη;
Αυτά που αφορούν το 1ο μέρος του μαθήματος τα έχω ανεβάσει. Από το 2ο έναν γράφο μόνο βρήκα το ανέβασα και αυτό.

Του δυναμικού προγραμματισμού αν έχει κάποιος, θα μας βοηθούσε αν το ανέβαζε.


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Rick Deckard on June 03, 2021, 18:36:43 pm
Και γω αυτα θελω να εξασκηθω λιγο αλλα rip  :'(


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Caterpillar on June 03, 2021, 18:38:52 pm
Και γω αυτα θελω να εξασκηθω λιγο αλλα rip  :'(
να δεις που θα βάλλει πάλι αύριο κανένα κουλό θέμα με string, και δεν θα μπορούμε να το λύσουμε, ενώ μπορεί να βάλλει πολύ πιο ωραία θέματα.


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Rick Deckard on June 07, 2021, 10:26:13 am
Όσοι θέλουνε να δοκιμάσουν το θέμα της δεύτερης προόδου, here ya go:

Quote
terrain=[[1.0, 1.0, 1.2, 1.3, 1.4, 1.4, 1.4, 1.3, 1.2, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0],
[1.0, 1.2, 1.4, 1.8, 2.0, 2.2, 2.0, 1.8, 1.4, 1.2, 1.1, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0], [1.2, 1.4,
1.9, 2.6, 3.2, 3.4, 3.2, 2.6, 1.9, 1.4, 1.2, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0], [1.3, 1.8, 2.6, 3.6,
4.6, 5.0, 4.6, 3.6, 2.6, 1.8, 1.3, 1.1, 1.0, 1.0, 1.0, 1.1, 1.0, 1.0, 1.0, 1.0], [1.4, 2.0, 3.2, 4.6, 5.9, 6.4,
5.9, 4.6, 3.2, 2.1, 1.4, 1.1, 1.1, 1.1, 1.2, 1.2, 1.2, 1.1, 1.0, 1.0], [1.4, 2.2, 3.4, 5.0, 6.4, 7.0, 6.4, 5.0,
3.4, 2.2, 1.5, 1.2, 1.2, 1.3, 1.4, 1.5, 1.4, 1.3, 1.2, 1.1], [1.4, 2.0, 3.2, 4.6, 5.9, 6.4, 5.9, 4.6, 3.2, 2.1,
1.5, 1.3, 1.4, 1.6, 1.8, 1.9, 1.8, 1.6, 1.4, 1.2], [1.3, 1.8, 2.6, 3.6, 4.6, 5.0, 4.6, 3.6, 2.6, 1.8, 1.4, 1.4,
1.7, 2.1, 2.5, 2.7, 2.5, 2.1, 1.6, 1.3], [1.2, 1.4, 1.9, 2.6, 3.2, 3.4, 3.2, 2.6, 2.0, 1.5, 1.4, 1.6, 2.1, 2.8,
3.4, 3.6, 3.4, 2.8, 2.0, 1.5], [1.0, 1.2, 1.4, 1.8, 2.1, 2.2, 2.1, 1.8, 1.5, 1.3, 1.4, 1.8, 2.5, 3.5, 4.4, 4.8,
4.4, 3.5, 2.5, 1.7], [1.0, 1.0, 1.2, 1.3, 1.5, 1.7, 2.0, 2.1, 1.8, 1.5, 1.5, 2.0, 3.0, 4.2, 5.4, 5.9, 5.4, 4.2,
2.9, 1.9], [1.0, 1.0, 1.0, 1.1, 1.5, 2.5, 3.9, 4.7, 3.9, 2.5, 1.8, 2.2, 3.3, 4.8, 6.1, 6.7, 6.1, 4.8, 3.3, 2.1],
[1.0, 1.0, 1.0, 1.1, 1.6, 3.2, 5.7, 7.0, 5.7, 3.3, 2.1, 2.3, 3.4, 5.0, 6.4, 7.0, 6.4, 5.0, 3.4, 2.2], [1.0, 1.0,
1.0, 1.0, 1.3, 2.3, 3.8, 4.6, 3.8, 2.4, 1.8, 2.2, 3.3, 4.8, 6.1, 6.7, 6.1, 4.8, 3.3, 2.1], [1.0, 1.0, 1.0, 1.0,
1.0, 1.3, 1.6, 1.8, 1.6, 1.4, 1.4, 2.0, 2.9, 4.2, 5.4, 5.9, 5.4, 4.2, 2.9, 1.9], [1.0, 1.0, 1.0, 1.0, 1.0, 1.0,
1.0, 1.0, 1.0, 1.1, 1.3, 1.7, 2.5, 3.5, 4.4, 4.8, 4.4, 3.5, 2.5, 1.7], [1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,
1.0, 1.0, 1.2, 1.5, 2.0, 2.8, 3.4, 3.6, 3.4, 2.8, 2.0, 1.5], [1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,
1.1, 1.3, 1.6, 2.1, 2.5, 2.7, 2.5, 2.1, 1.6, 1.3], [1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.2,
1.4, 1.6, 1.8, 1.9, 1.8, 1.6, 1.4, 1.2], [1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.1, 1.2, 1.3,
1.4, 1.5, 1.4, 1.3, 1.2, 1.1]]


Code:
def movement(terrain, from_x, from_y, to_x, to_y):
    if to_y <= from_y:
        raise Exception("Can only go forward and not move from y = "+str(from_y) + " to y = " +
str(to_y))
    if abs(to_y-from_y) > 1 or abs(from_x-to_x)>1:
        raise Exception('Cannot move immediately from ('+str(from_x)+','+str(from_y)+') to ('+str(to_x)
+','+str(to_y)+') because teleportation is not possible')
    return ( float(to_x-from_x)**2 + float(to_y-from_y)**2 )**0.5 * (terrain[from_x][from_y] +
terrain[to_x][to_y])/2

Code:
def path(terrain, start_x, end_x):
    size = len(terrain)
    t = [(_ for _ in range(size)] for _ in range(size)]
    # size2size 2D table - DOWT create with other expressions (can cause memory problems)
    for x in range(0, size):
        t[x][0] = # fill in initial conditions
    for y in range(1, size):
        for x in range(0, size):
            t[x][y] = # implement the recursive formula
    return # return the correct quantity


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Nickgian on June 16, 2021, 21:57:16 pm
Quiz 2020 για τα τελυταια ερωτηματα (το εβαλα βοηθητικα για μελλοντικη χρηση)
Code:
def makestops(D):
    t = [0] * len(D)
    best = 0
    for k in range(1, len(D)):
        t[k] = float('inf')
        for i in range(k):
            for R in range(100, 201, 100):
                if D[k] - D[i] <= R:
                    q = t[i] + 2 * R - D[k] + D[i]

                    if q < t[k]:
                        t[k] = q
                        best = k

                    else:
                        t[k] = t[best]
                        if i >85:
                            print(i)

    return t[-1]


D = [0, 110, 260, 310, 400, 470, 530, 600,
700, 800, 930, 1040, 1190, 1270, 1450, 1500,
1650, 1760, 1890, 1960, 2030, 2200, 2390, 2480,
2630, 2810, 2990, 3050, 3100, 3170, 3350, 3410,
3520, 3710, 3830, 3980, 4070, 4220, 4390, 4440,
4600, 4790, 4950, 5040, 5200, 5260, 5370, 5550,
5640, 5730, 5790, 5840, 5990, 6070, 6150, 6270,
6320, 6450, 6520, 6650, 6800, 6860, 6970, 7120,
7230, 7280, 7410, 7550, 7670, 7860, 7990, 8170,
8240, 8310, 8480, 8580, 8650, 8830, 8930, 9090,
9240, 9420, 9560, 9720, 9820, 9910, 10090, 10200,
10390, 10530, 10670, 10730, 10920, 11030, 11160,
11270, 11350, 11530, 11660, 11710, 11850]

print(makestops(D))


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Caterpillar on June 17, 2021, 05:15:50 am
Quiz 2020 για τα τελυταια ερωτηματα (το εβαλα βοηθητικα για μελλοντικη χρηση)

Αυτό όμως θα έπρεπε να εκτυπώνει και το 98 ?


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Nickgian on June 17, 2021, 16:27:31 pm
Για το ερωτημα 4 πως το λυνουμε εχω γραψει αυτο αλλα συνεχιζει να γαμιζει ο πινακας με τιμες 6 εννοω απο καποιο σημειο θα πρεπει να σταμαει καμια βοηθεια
Code:
P = [0, 1, 5, 8, 9, 10, 17, 17, 18, 20, 21, 23, 25, 27, 27,
     27, 29, 30, 32, 34, 35, 37, 38, 38, 38, 40, 41, 42,
     43, 45, 45, 46, 47, 50, 51, 52, 55, 56, 58, 65, 65,
     67]


def cut_cable(P, n):
    c = [0] * (n + 1)
    d = [0] * (n + 1)
    best = 0
    for i in range(0, n + 1):
        for j in range(i):
            q = P[i - j] + c[j]
            if q > c[i]:
                c[i] = q
                best = q
                d[i] = i - j

            else:
                c[i] = best

    return c[n], d



print(cut_cable(P, 41))


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Rick Deckard on June 17, 2021, 16:56:14 pm
(https://scontent.fskg1-1.fna.fbcdn.net/v/t1.15752-9/201410070_157764029716560_8254496308636763412_n.png?_nc_cat=104&ccb=1-3&_nc_sid=ae9488&_nc_ohc=zmpAYyOhduMAX8Q30Hu&_nc_ht=scontent.fskg1-1.fna&oh=81d2b933054d7d168c05b6a11b61eee5&oe=60D10D47)


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Nickgian on June 17, 2021, 19:36:38 pm
σε αυτο εγω βρηκα με το χερι 3.733 παιρνωντας
  • 2 κιλα μανταρινια 2$
  • 1 κιλο κερ. 1.2$
  • και 0.533 κιλα μανταρινια με κοστος 0.8$
εχει γραψει κανεις κωδικα για την επιλυση αυτου του προβληματος


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Caterpillar on June 17, 2021, 19:44:40 pm
σε αυτο εγω βρηκα με το χερι 3.733 παιρνωντας
  • 2 κιλα μανταρινια 2$
  • 1 κιλο κερ. 1.2$
  • και 0.533 κιλα μανταρινια με κοστος 0.8$
εχει γραψει κανεις κωδικα για την επιλυση αυτου του προβληματος

όχι με το χέρι το έλυσα στην πρόοδο, αλλά το έβγαλα αν βλεπω καλά στις μουτζουρες μου  ειναι 3.666  αλλά μπορεί να είναι λάθος μουτζουρα, αλλα το χα λυσει σωστα απο οτι φανηκε.
2 μανταρινιο 1.6666 κερασια
έχεις άπληστο αλγοριθμο οχι δυναμικο.
επιλέγεις απο το φθινοτερο οσο περισσοτερα κιλα μπορεις, ειναι το ιδιο με τον κλεφτη και τα κλοπιμαια που εχει στις διαφανειες.


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: MajorTom on May 05, 2022, 19:29:51 pm
Υπάρχει λυμένο το πρόβλημα με το cloud από τον Ιούλιο του 21;


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Grigohas on May 31, 2022, 17:40:05 pm
υπάρχουν κάπου οι λύσεις για την β πρόοδο του 2021?


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: MajorTom on June 06, 2022, 21:52:07 pm
Στην Α' πρόοδο του '21 στα ερωτήματα με τις πιθανότητες παίρνουμε:

E[T(n)] = E[T(n/2)] + (p)*E[T(n/2)] + (p)*Θ(n) => E[T(n)] = (3/2)*E[T(n/2)] + (1/2)*Θ(n) = (3/2)*E[T(n/2)] + Θ(n);

Και μετά το κεντρικό θεώρημα το χρησιμοποιούμε βάσει αυτού του τύπου;


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Grigohas on June 09, 2022, 12:38:13 pm
εχει κανείς απαντήσεις για την β πρόοδο του 2021?


Title: Re: [Ανάλυση Αλγορίθμων] Παλιά Θέματα & Σχολιασμός
Post by: Μαρτσέλο on July 06, 2022, 17:29:46 pm
μπορει κανεις να λυσει τις ερωτησεις 10, 11, 13 απο τα θεματα ιουνιου21;