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

[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.

[vtsimpouris]

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

sent from mTHMMY 

[panos98]

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

[Patatompataria]

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

[Prison Mike]

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

[Patatompataria]

Ονομάζω τον πίνακα με τις ώρες εμφάνισης 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, εννοώ ότι είναι από το Α

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

[Prison Mike]

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

sent from mTHMMY 

[Katsan]

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

[The Senate]

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

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

[panos98]

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

[Argirios]

Μπορείς να βρεις την εντροπία και να πολλαπλασιάσεις με 1000 νομίιζω.

[popman]

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)

[panos98]

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

[Argirios]

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

[popman]

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

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

[ροζ θορυβος]

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

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