THMMY.gr

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

Από 4η διάλεξη ποιες ασκήσεις έκανε?

Έχει βρει κανείς λύση στην άσκηση της δοκιμαστικής προόδου;

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

Εμένα δεν μου έβγαλε τίποτα

ξερει κανεις πως γινεται?

1Τ(n/2) γιατί η συνάρτηση καλεί αναδρομικά τον εαυτό της μία φορά, με όρισμα n/2 (και ίδιο α, μάλλον ξέχασε να το γράψει)

+Θ(1) γιατί εκτός από την αναδρομική κλήση, η πολυπλοκότητα του υπολοίπου είναι "σταθερή" με την έννοια ότι δεν έχει κάποιο loop που να εξαρτάται από το n

Ευχαριστω!! :) :) :) :)

και μετα που ζηταει την πολυπλοκοτητα, εφαρμοζω την κεντρικη μεθοδο θεωρώντας f(n)= Θ(1) ?

πλεον βγαζει βαθμολογια και τις σωστες απαντησεις στο τελος :)

ναι   :)

Εάν έχω διπλό άθροισμα ( ΣΣ(1) ) αλλά τα όρια είναι διαφορετικά (πχ 1->n και 1->m) (για παράδειγμα 2 for() με διαφορετικό πλήθος στοιχείων) στο τέλος προκύπτει T(n)=n*m σωστά?
Και αν είναι έτσι τότε η πολυπλοκότητα είναι Θ(n) ?

Θ(n*m)

Ευχαριστώω

Μπορεί να μας πει κάποιος που έδωσε πρόοδο τι περίπου ήταν η άσκηση στο τέλος? Μοιάζει με αυτή που έχει στη δοκιμαστική πρόοδο?

Σε εμας ηταν πλ πιο ευκολη ουσιαστικα επρεπε να γραψεις τον αλγοριθμο της δυαδοκης αναζητησης να βαλεις 2 for λιγα λογια και εισαι κομπλε

Ευχαριστώ. Υπάρχουν κάπου αλγόριθμοι που πρέπει να ξέρουμε? Η γενικά να ξέρουμε να κάνουμε μια υλοποίηση divide and conquer?

Αυτες τις μεθοδους που μας εμαθε να ξες

+ ίσως κάποια πράγματα για bucketing όπως είχε στη δοκιμαστική πρόοδο

Έχει κανένας καμιά ιδέα για αυτό το πρόβλημα γιατί δεν μπορώ να το λύσω με τίποτα (Θέμα 1 προοδος β 2016) ;

Ονομάζω τον πίνακα με τις ώρες εμφάνισης coord[t], δηλαδή τη στιγμή t, ποια συντεταγμένη έχει αντικείμενο.

Ο πίνακας A[t, x] είναι 1 όπου x=coord(t), και 0 αλλού.
Ο πίνακας B[t, x] έχει τη σημασία "ποιος είναι ο μέγιστος αριθμός αντικειμένων που γίνεται να πάρω από τη στιγμή t μέχρι το τέλος, αν βρίσκομαι στη θέση χ".

Το πιο "απλό" κομμάτι του Β είναι για t=T_end, όπου ο Β ταυτίζεται με τον Α, δηλαδή είναι 1 μόνο στο x=coord(T_end).
Στον υπόλοιπο Β ισχύει η αναδρομική σχέση:
B[t, x] = A[t, x] + max(για k από x-1 ως x+1) του B[t+1, k]
(προσέχοντας τα όρια του κ όταν το χ βρίσκεται στην άκρη)
Αυτό έχει το νόημα, αν υπάρχει αντικείμενο εδώ που είμαστε αυτή τη στιγμή, το παίρνουμε, και μετά προσθέτουμε το βέλτιστο δυνατό πλήθος για το επόμενο t, αν πάμε αριστερά, δεξιά, ή μείνουμε στην ίδια θέση.
Συμπληρώνουμε τον πίνακα Β από κάτω προς τα πάνω (από t=T_end μέχρι 0)
Για να ανακατασκευάσουμε τη λύση, κρατάμε σε έναν άλλο πίνακα (πχ K) ποιο είναι το κ που επιλέγουμε κάθε φορά.

Τελικά, το B[t=0, x=0] δείχνει πόσα αντικείμενα μπορούμε το πολύ να πάρουμε συνολικά (ξεκινώντας απ'το 0).
Για να κατασκευάσουμε τη λύση, πάμε μετά στο x=K[t=0, x=0], μετά στο x=K[t=1, x] (x ότι βγήκε πριν) κλπ.

Στην φωτογραφία όπου έχει κόκκινο 1, εννοώ ότι είναι από το Α

Ελπίζω να βοήθησα :)

Ευχαριστώ πάρα πολύ πατατομπαταρια ησουν απίστευτα βοηθητικός. Αν το κατάλαβα σωστά, μπορείς να φτιάξεις τον πίνακα Α και μετα να εφαρμόσεις αλγόριθμο τύπου Goldmine (link για reference: https://www.geeksforgeeks.org/gold-mine-problem/)

Κάποιος την 4 από την δοκιμαστική

Διάβασε καλά τις 12 πρώτες διαφάνειες από το 2ο pdf με τους άπληστους αλγόριθμους (διαλέξεις 18-19). Σου λέει ουσιασικά πως να φτιάξεις έναν κώδικα για τα σύμβολα που έχεις χτίζοντας ένα δυαδικό δένδρο. Αφού έχεις τον κώδικα κάνεις αντίστοιχες πράξεις με αυτές που κάνει στην 4η διαφάνεια.

Q1.  Δίνονται  τα  σύμβολα a,b,c,d,e  με  πιθανότητες  εμφάνισης (1/2, 1/4, 1/8, 1/16, 1/16),  αντίστοιχα.
Ποιος είναι ο μέσος αριθμός bits που απαιτούνται για την κωδικοποίηση κατά Huffman μιας ακολουθίας
από 1000 σύμβολα?
Απάντηση: 1875 bits
Mπορει καποιος να εξηγησει με ποιον  τροπο βγαινει;

1 Bit για α,2 για b ,3 για c,4 για d,4 για e
Αρα:
1000*(0.5*1 +0.25*2 + 0.125*3 + 0.0625*4 + 0.0625*4)

και γιατι οχι 1 bit για Α  , 2 για το επομενο, 2 ξανα για το επομενο , 3 για το επομενο και ξανα 3 για το επομενο;

Έτσι βγαίνει αμα κάνεις Huffman.

Αν βαλεις πχ στο 1 bit το (1) και βαλεις πχ στα δυο επομενα το (00) και (01) δεν θα μπορεις να συνεχίσεις.. Γιστι το αλλο δεν θα μπορει να εχει ουτε (000) ουτε (001) ουτε (010) ουτε (011).
Γενικα θα πρεπει να φαινεται ποτε τελειωνει ενας χαρακτηρας.
Αν έχεις πχ ακολουθία 001 δεν θα ξερεις αν ειναι ba η αν είναι ενας χαρακτηρας πχ ο (001)
Δεν γινεται για 2 χαρακτητες a, b ο κωδικας του b να έχει ιδια ακολουθία του a στο συνολικό κωδικα του

Εφαρμόζεις Huffman όπως στο παράδειγμα στις διαφανείες  και κανεις το δένδρο.Επειτα πληθος_bits*Σσυχνοτητα_κλειδιου*βαθος_κλειδιου_στο_δενδρο

ωραια ευχαριστω...σε ποια διαφανεια εχει παραδειγμα κ ποια σελιδα;

Διαφανεια 18 στην αρχη.

Στην άσκηση με τα κυρίαρχα σημεία γτ θεωρούμε ότι για n=2 κυρίαρχο είναι αυτό με το μεγαλύτερο Χ? αν έχει μικρότερο Υ είναι και τα 2 κυρίαρχα 

μπορει καποιος να εξηγησει ποια ειναι η διαφορα μεταξυ min(κατι) ,maxmin(κατι) minmin(κατι)? ωστε να ξερουμε ποτε χρησιμοποιειται το καθετι

Πού το είδες? Μήπως είναι μία min μέσα σε άλλη?

2η προοδος πολλαπλης επιλογης με τα αμαξια,ξενοδοχεια,Κατασκευη αλγοριθμου δπ παραγραφος με λεξεις,   . Δοκιμαστικη προοδος 2 πολλαπληςασκηση με  παιχνιδι τηλεμεταφορας και ασκηση με υπολοιπο σε δυναμεις του 2 κ τ 3

Εγώ αυτό που καταλαβαίνω είναι ότι έχεις δύο μεταβλητές απλά, πχ σε αυτό με τα αυτοκίνητα την R και την i και πρέπει να ελαχιστοποιήσεις ως προς και τις δυο. Βρίσκεις το min ως προς i μία φορά για R=100 και μία για R=200 και μετά το ελάχιστο αυτών των δύο. Αλλά μπορεί να κάνω και λάθος, αμα έχει κάποιος καμιά άλλη ιδέα ας πει.

ενας λογος σιγουρα ειναι οταν εχω 2 ανεξαρτητες μεταβλητες (θυμιζει λιγο σαν διπλο ολοκληρωμα η λογικη) απλα σε αυτο με τις λεξεις δε βρισκω το λογο να παρει το για το  ελαχιστο κοστος πρωτα το max κοστος  απο (     Τ[j-1],  lc[i,j]) και στη συνεχεια να το ελαχιστοποιησει με  min ()

Όπως τα λέει ο Argirios είναι για το min min.

Για το min max, πχ στην 2η δοκιμαστική πρόοδο Q7,  μια επιλογή είναι
min_b( max_i bⁱ )

Αυτό το διαβάζουμε από "μέσα προς τα έξω", δηλαδή: επιλέγουμε το i που μεγιστοποιεί το bⁱ (χωρίς να ξεπερνά τον περιορισμό), και μετά επιλέγω το b που ελαχιστοποιεί αυτό που μένει μέσα.

Στα προβλήματα ΔΠ που κάνουμε νομίζω θα είναι ή min min ή max max, δε σκέφτομαι κάποιο λόγο να θέλουμε να ελαχιστοποιήσουμε κάτι και να το μεγιστοποιήσουμε μαζί.

ωραια ευχαριστω , αυτα εχουν μια λογικη, απλα στο  maxmin στο δπ με τις λεξεις εξακολουθω να μην μπορω να δωσω εξηγηση

Λοιπον παιζει να καταλαβα τη λογικη του minmax .Αρχικα αυτος δηλωνει στην εκφωνηση με bold κιολας οτι ''το κοστος παραγραφου ειναι το ΜΕΓΙΣΤΟ απο  τα επιμερους κοστη των γραμμων'' ,επομενως εξορισμου βγαινει το max{kati} και ακολουθω με τη λογικη π σκεφτηκαμε ολοι περνει το minmax{kati}

Ε ναι άρα για minmax λες όχι για maxmin, νομίζω είναι αυτό που είπε ο Patatompataria για όλες τις περιπτώσεις ούτως ή άλλως, σκεφτόμαστε από μεσα προς τα έξω. Έτσι κιαλλιώς δε νομίζω να μας βάλει να υπολογίσουμε το min ή κάτι τέτοιο, ξεφεύγει από το μάθημα, απλά να γράψουμε τον αναδρομικό τύπο θέλει απ'ότι είδα στις ασκήσεις, και να αποδείξουμε ότι είναι σωστός.

Μόνο σε εμένα οι τελευταίες ασκήσεις των προόδων φαίνονται πολύ δύσκολες ή δεν τις έχω κατανοήσει καλά?  :???: :???: :???: :???:

Ρωτα

Γενικά μιλώντας, εντάξει αμα δω τη λύση θα την ψιλοκαταλάβω χοντρικά αλλά μου φαίνεται δύσκολο να κάνω τους συλλογισμούς που κάνει αυτός, ειδικά αν βάλει κάτι που δεν μοιάζει με τα παραδείγματα δε παίζει.

εγω δεν νομιζω οτι μπορω να γραψω κατι απο μονη μου σε καινουριο προβλημα  :D :D
ας βαλει πολυ παρομοια με των προοδων  :D

Ενταξει οταν βλεπουμε ετοιμη λυση λεμε ευκολη μετα απο 10 προσπαθειες κατανοησης,προφανως και το μαθημα γινεται πολυ ευκολα παλουκι , το ξερει και ο καθηγητης αλλα απο την αλλη πρεπει να κρατησει ενα επιπεδο και να ξεχωρισουν ολοι αναλογα με τις γνωσεις π πηραν...καπου στη μεση βρισκεται η απαντηση για αυριπ

Όλοι οι υπόλοιποι που δεν απαντάμε στις ερωτήσεις που γίνονται εδώ, σε ποια κατηγορία λες να βρισκόμαστε; Λες να μην απαντάμε σκόπιμα για να μη βοηθήσουμε;;  ;D :D

πέρα από το υλικό στο elearning έχει κάνει άλλες ασκήσεις;

Α εντάξει λέω κεγώ, ανακουφίστηκα  :P

οχι

αν δεν πεσει κατι που εχει την ιδια λογικη ζητω που καηκαμε

Αυτο που κλαιγομαστε ολοι πριν δωσουμε το μαθημα πρεπει να συμβαινει πρωτη φορα ;D ;D ας ελπισοουμε να το λαβει υποψιν του αυριο ο καθηγητης καλη επιτυχια σε ολους

Πως γραψαμε?

Εγώ πιστεύω ένα 6-7 το έγραψα, εκτός αν τα έχω κάνει όλα λάθος  :P, το τελευταίο με δυσκόλεψε λίγο μάλλον δε το έχω και πολύ σωστό.

εγω λυνοντας το 4.3 βελτιωσα περισσοτερο τον αλγοριθμο μου .Εχω σιγουρα λαθος στο αντιπαραδειγμα(γιατι ειμαι μαλακας) και καπου πρεπει να εχω ενα λαθακι ακομη...Βαθμο δε μαντευω γιατι παντα πεφτω εξω

Εγώ το 4.3 το έλυσα με το μάτι οπότε παίζει να μου κόψει κάτι. Γενικά δε ξέρω για εσένα, αλλά ο χρόνος μου ήταν ίσα ίσα, αν είχα και λίγο παραπάνω θα το βελτίωνα και εγώ πιστεύω το 4.1 γιατί το έκανα σε μισή ώρα περίπου.

σιγουρα θα βοηθουσαι λιγος χρονος ακομη

Μπορεί καποθις να ανεβάσει μια προτεινόμενη λύση για τον αλγόριθμο στα θέματα του Ιουνίου?

σκέφτηκα αυτό:

Αρχικά κάνουμε τον δισδιάστατο πίνακα A[i, r] που δείχνει πόσα δεδομένα θα επεξεργαστούν τη μέρα i, που έχουν περάσει r μέρες από το τελευταίο reboot.
A[i, r] = min{x[ i], s[r]}
όπως γράφει και στην εκφώνηση. Αυτόν τον πίνακα μπορούμε να τον συμπληρώσουμε κατευθείαν και χωρίς συγκεκριμένη σειρά.

Τώρα κάνουμε τον πίνακα maxDataFrom[i, r] που δείχνει τον μέγιστο όγκο δεδομένων που μπορούν να επεξεργαστούν από τη μέρα i μέχρι το τέλος (ενώ έχουν περάσει r μέρες από το τελευταίο reboot).
Για την τελευταία μέρα, i=n ισχύει maxDataFrom[n, r] = A[n, r]
Γενικά, την μέρα i, είτε θα κάνουμε reboot είτε όχι.
Άρα η αναδρομική σχέση θα είναι:
maxDataFrom[i, r] = max{ A[n, r] + maxDataFrom[i+1, r+1] , maxDataFrom[i+1, 1] }
(το πρώτο μισό είναι αν δεν κάνουμε reboot, προσθέτουμε τα δεδομένα της σημερινής μέρας και το βέλτιστο από τις επόμενες. Στο δεύτερο μισό δεν μπαίνει τίποτα από σήμερα, αλλά από την επόμενη μέρα το r γίνεται 1)

Τον πίνακα τον συμπληρώνουμε από την τελευταία μέρα προς την πρώτη, και ο μέγιστος όγκος δεδομένων είναι το maxDataFrom[1, 1].
(σημείωση, πάνω από τη διαγώνιο δεν έχει νόημα να συμπληρώσουμε τον πίνακα (για r>i) επειδή δε γίνεται να έχουν περάσει περισσότερες μέρες από το reboot από τον αριθμό της μέρας)

Όσο συμπληρώνουμε τον maxDataFrom μπορούμε να κρατάμε το αν επιλέξαμε να κάνουμε reboot ή όχι, για να βρούμε μετά ποιες μέρες κάναμε.

Στο συνημμένο είναι οι πίνακες για το παράδειγμα που δίνεται

Σωστο  ειναι?

Ωραίος θα το κοιτάξω αναλυτικά πιο μετά, σε ευχαριστώ πολύ!