• Downloads
  • ! Read Me !
  • Μαθήματα
  • Φοιτητικά
  • Τεχνικά Θέματα
  • Συζητήσεις
  • Happy Hour!
  • About THMMY.gr
 V  < 
Search:  
Welcome, Guest. Please login or register.
March 26, 2023, 21:15:56 pm

Login with username, password and session length
Links
  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Θέματα Διπλωματικών Εργασιών ΤΗΜΜΥ
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  
Πίνακας Ελέγχου
Welcome, Guest. Please login or register.
March 26, 2023, 21:15:56 pm

Login with username, password and session length

Αναζήτηση

Google

THMMY.gr Web
Πρόσφατα
Αλλαγές public name.
by Don
[Today at 20:15:00]

Τα παράπονα μου για την α...
by Caterpillar
[Today at 19:48:51]

Logo Guesser
by Nikos_313
[Today at 19:11:34]

ΑΛΛΑΞ' Ο ΚΟΛΙΕΣ - CINE GA...
by Nikos_313
[Today at 19:00:16]

[Ηλ. Μηχανές Ι]Γενικές απ...
by Nikos_313
[Today at 17:37:19]

Πότε θα βγει το μάθημα; -...
by Caterpillar
[Today at 16:38:32]

SpaceDot is recruiting | ...
by SpaceDot
[Today at 16:14:49]

[Προσομοίωση & Μοντελοποί...
by Sintrimi_Sanidi
[Today at 14:50:15]

Των συνειρμών το παίγνιο....
by Caterpillar
[Today at 14:37:10]

Ποιο τραγούδι ακούσατε 5+...
by Katarameno
[March 25, 2023, 22:07:51 pm]

[Τηλεπ. Συστήματα II] Ερε...
by Nikos_313
[March 25, 2023, 21:53:47 pm]

[ΣΗΕ ΙΙ] Γενικές απορίες ...
by Nikos_313
[March 25, 2023, 20:30:36 pm]

[ΣΑΕ ΙΙ] Εργαστήριο 2023
by Caterpillar
[March 25, 2023, 14:09:02 pm]

[Τηλεπ. Συστήματα II] Γεν...
by Caterpillar
[March 25, 2023, 13:35:41 pm]

[Δ.Υ.Σ.]Γενικές απορίες κ...
by DJ Stefzia
[March 25, 2023, 13:35:00 pm]

Η εφαρμογή Water Footprin...
by Rouszia
[March 25, 2023, 11:57:44 am]

Drum & Bass (& Breakbeat,...
by Katarameno
[March 25, 2023, 03:40:57 am]

Πενθούν οι νεοφιλελευθερο...
by Katarameno
[March 24, 2023, 23:29:29 pm]

Νέα Δημοκρατία (and Co. I...
by Katarameno
[March 24, 2023, 23:26:02 pm]

Εκπαιδευτική επίσκεψη στο...
by Caterpillar
[March 24, 2023, 21:27:00 pm]
Στατιστικά
Members
Total Members: 9188
Latest: polyzosi
Stats
Total Posts: 1399592
Total Topics: 30662
Online Today: 192
Online Ever: 901
(October 13, 2020, 16:39:09 pm)
Users Online
Users: 30
Guests: 120
Total: 150
Geoth
filkilkis
vagelisnn
Sintrimi_Sanidi
Caterpillar
cpt38
george14
bubu
Manifold
Nino
Katarameno
alexter
john8
Stelios Leivas
softa
manek
neoklitos
tryfkalt
VengeX
geraltofrivia
tasos gourd
geo66
anest02
Nikos_313
msarafis
stefpapa21
Εμφάνιση

Νέα για πρωτοετείς
Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.
Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.
Νέα!
Ωρολόγιο Πρόγραμμα Εαρινού Εξαμήνου Έτους 2022-2023
THMMY.gr > Forum > Μαθήματα Βασικού Κύκλου > 6o Εξάμηνο >  Μαθήματα Επιλογής > Ανάλυση και Σχεδιασμός Αλγορίθμων (Moderators: hjalmar, Mr Watson, Nikos_313) > [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019
0 Members and 1 Guest are viewing this topic.
Pages: 1 [2] 3 4 5 Go Down Print
Author Topic: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019  (Read 5981 times)
vtsimpouris
Νεούλης/Νεούλα
*
Posts: 32


View Profile
Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019
« Reply #15 on: April 15, 2019, 16:56:16 pm »

Ευχαριστώ. Υπάρχουν κάπου αλγόριθμοι που πρέπει να ξέρουμε? Η γενικά να ξέρουμε να κάνουμε μια υλοποίηση divide and conquer?
sent from mTHMMY 
Logged
panos98
Μόνιμος κάτοικος ΤΗΜΜΥ.gr
******
Posts: 1191



View Profile
Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019
« Reply #16 on: April 15, 2019, 17:12:16 pm »

Αυτες τις μεθοδους που μας εμαθε να ξες
Logged
Patatompataria
Εθισμένος στο ΤΗΜΜΥ.gr
*****
Posts: 671



View Profile
Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019
« Reply #17 on: April 15, 2019, 20:40:56 pm »

+ ίσως κάποια πράγματα για bucketing όπως είχε στη δοκιμαστική πρόοδο
Logged
Prison Mike
Veteran
Μόνιμος κάτοικος ΤΗΜΜΥ.gr
******
Posts: 2162


Nevah got caught, neither


View Profile
Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019
« Reply #18 on: May 27, 2019, 14:18:48 pm »

Έχει κανένας καμιά ιδέα για αυτό το πρόβλημα γιατί δεν μπορώ να το λύσω με τίποτα (Θέμα 1 προοδος β 2016) ;
Logged
Patatompataria
Εθισμένος στο ΤΗΜΜΥ.gr
*****
Posts: 671



View Profile
Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019
« Reply #19 on: May 28, 2019, 13:21:37 pm »

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

Ελπίζω να βοήθησα Smiley
Logged
Prison Mike
Veteran
Μόνιμος κάτοικος ΤΗΜΜΥ.gr
******
Posts: 2162


Nevah got caught, neither


View Profile
Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019
« Reply #20 on: May 28, 2019, 15:27:03 pm »

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


View Profile
Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019
« Reply #21 on: May 29, 2019, 23:46:05 pm »

Κάποιος την 4 από την δοκιμαστική
Logged
The Senate
Καταξιωμένος/Καταξιωμένη
***
Gender: Male
Posts: 102


Meesa be the Senate


View Profile
Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019
« Reply #22 on: May 29, 2019, 23:59:11 pm »

Quote from: Katsan on May 29, 2019, 23:46:05 pm
Κάποιος την 4 από την δοκιμαστική

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

The Dark Side of the Force is a pathway to many abilities some consider to be unnatural.
panos98
Μόνιμος κάτοικος ΤΗΜΜΥ.gr
******
Posts: 1191



View Profile
Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019
« Reply #23 on: June 20, 2019, 21:57:25 pm »

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



View Profile
Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019
« Reply #24 on: June 20, 2019, 22:15:39 pm »

Μπορείς να βρεις την εντροπία και να πολλαπλασιάσεις με 1000 νομίιζω.
« Last Edit: June 26, 2019, 22:01:14 pm by Argirios » Logged

popman
Νεούλης/Νεούλα
*
Posts: 49


View Profile
Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019
« Reply #25 on: June 20, 2019, 22:18:23 pm »

Quote from: panos98 on June 20, 2019, 21:57:25 pm
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)
Logged
panos98
Μόνιμος κάτοικος ΤΗΜΜΥ.gr
******
Posts: 1191



View Profile
Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019
« Reply #26 on: June 20, 2019, 22:23:12 pm »

και γιατι οχι 1 bit για Α  , 2 για το επομενο, 2 ξανα για το επομενο , 3 για το επομενο και ξανα 3 για το επομενο;
Logged
Argirios
Veteran
Επιβεβαρυμένος
******
Gender: Male
Posts: 11213



View Profile
Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019
« Reply #27 on: June 20, 2019, 22:29:17 pm »

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

popman
Νεούλης/Νεούλα
*
Posts: 49


View Profile
Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019
« Reply #28 on: June 20, 2019, 22:31:56 pm »

Quote from: panos98 on June 20, 2019, 22:23:12 pm
και γιατι οχι 1 bit για Α  , 2 για το επομενο, 2 ξανα για το επομενο , 3 για το επομενο και ξανα 3 για το επομενο;
Αν βαλεις πχ στο 1 bit το (1) και βαλεις πχ στα δυο επομενα το (00) και (01) δεν θα μπορεις να συνεχίσεις.. Γιστι το αλλο δεν θα μπορει να εχει ουτε (000) ουτε (001) ουτε (010) ουτε (011).
Γενικα θα πρεπει να φαινεται ποτε τελειωνει ενας χαρακτηρας.
Αν έχεις πχ ακολουθία 001 δεν θα ξερεις αν ειναι ba η αν είναι ενας χαρακτηρας πχ ο (001)
Δεν γινεται για 2 χαρακτητες a, b ο κωδικας του b να έχει ιδια ακολουθία του a στο συνολικό κωδικα του
Logged
ροζ θορυβος
Μόνιμος κάτοικος ΤΗΜΜΥ.gr
******
Gender: Female
Posts: 1852



View Profile
Re: [Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 2019
« Reply #29 on: June 20, 2019, 22:33:24 pm »

Quote from: panos98 on June 20, 2019, 22:23:12 pm
και γιατι οχι 1 bit για Α  , 2 για το επομενο, 2 ξανα για το επομενο , 3 για το επομενο και ξανα 3 για το επομενο;
Εφαρμόζεις Huffman όπως στο παράδειγμα στις διαφανείες  και κανεις το δένδρο.Επειτα πληθος_bits*Σσυχνοτητα_κλειδιου*βαθος_κλειδιου_στο_δενδρο
Logged

Why be a wallflower when you can be a Venus fly trap?
Pages: 1 [2] 3 4 5 Go Up Print
Jump to:  

Powered by SMF | SMF © 2006-2009, Simple Machines LLC
Scribbles2 | TinyPortal © Bloc | XHTML | CSS
Loading...