• Downloads
  • ! Read Me !
  • Μαθήματα
  • Φοιτητικά
  • Τεχνικά Θέματα
  • Συζητήσεις
  • Happy Hour!
  • About THMMY.gr
 V  < 
Search:  
Welcome, Guest. Please login or register.
June 01, 2023, 11:09:22 am

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.
June 01, 2023, 11:09:22 am

Login with username, password and session length

Αναζήτηση

Google

THMMY.gr Web
Πρόσφατα
[Διανεμημένη Παραγωγή] Γε...
by Διάλεξις
[Today at 10:51:01]

Πρακτική Άσκηση ΤΗΜΜΥ 201...
by Διάλεξις
[Today at 10:30:35]

Τι ακούτε αυτήν τη στιγμή...
by Just Me
[Today at 01:30:19]

Πλωτός Σταθμός LNG στον Θ...
by Katarameno
[Today at 01:08:18]

Ποιο τραγούδι ακούσατε 5+...
by Katarameno
[May 31, 2023, 22:44:37 pm]

[Αρχές Οικονομίας] Γενικέ...
by Chr1sgr
[May 31, 2023, 22:32:19 pm]

[Κυκλώματα I] Παλιά θέματ...
by tzortzis
[May 31, 2023, 22:12:17 pm]

Πότε θα βγει το μάθημα; -...
by Black Velvet
[May 31, 2023, 20:18:27 pm]

Σχετικά με την απαράδεκτη...
by Caterpillar
[May 31, 2023, 19:53:26 pm]

[Αρχές Οικονομίας] ΠΑΡΟΡΑ...
by MrEagle
[May 31, 2023, 19:19:45 pm]

Μέλος του Μήνα - Μάιος 20...
by nectar
[May 31, 2023, 19:16:17 pm]

[Η/Μ Πεδίο ΙΙ] Ανάλυση πα...
by vterz
[May 31, 2023, 18:59:35 pm]

Των συνειρμών το παίγνιο....
by Katarameno
[May 31, 2023, 18:37:57 pm]

ΟΡΚΩΜΟΣΙΑ 12 ΙΟΥΛΙΟΥ 2023...
by Μπιγκόνια
[May 31, 2023, 18:36:26 pm]

Καφενείο και διάβασμα στο...
by tigriss
[May 31, 2023, 17:17:30 pm]

[ΑΡΑΓΕ ΕΑΑΚ] 123 μέρες απ...
by Caterpillar
[May 31, 2023, 16:17:09 pm]

Αρχείο Ανακοινώσεων [Arch...
by Caterpillar
[May 31, 2023, 14:44:26 pm]

Watch Tarkovsky's Best Fi...
by Katarameno
[May 31, 2023, 12:58:34 pm]

Εκλογές Μαΐος 2023
by Caterpillar
[May 31, 2023, 11:29:11 am]

[Τηλεπ. Συστήματα II] Απο...
by Caterpillar
[May 30, 2023, 19:23:58 pm]
Στατιστικά
Members
Total Members: 9202
Latest: Giorgossou
Stats
Total Posts: 1404061
Total Topics: 30762
Online Today: 172
Online Ever: 901
(October 13, 2020, 16:39:09 pm)
Users Online
Users: 48
Guests: 66
Total: 114
noreason
vasiliki_m
gsid
balligeorgia
tzortzis
25thOfMarch
geraltofrivia
xhesikameni
ppss
amprozos
Nikos_313
Caterpillar
Τζιτζίς
Sgt Pepper
Cersei Tsoulannister
goustafson
aioann
kanou_tom
cealexop
sgiannoul
dionisia
Κaraflodaimonas
mariaxalk
Nmparkas
Condoriano
Katsavidi
spoun
elena_k
Θιασώτης
athanous
agkentzi
Leou
Kv
alexter
Chr1sgr
aimiliosd99
ekoemtzo
verve217
JoHn!
ioannisv
Διάλεξις
Elliot Alderson
Εμφάνιση

Νέα για πρωτοετείς
Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.
Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.
Ανεβάζετε τα θέματα των εξετάσεων (και όχι μόνο) στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!
Νέα!
Η γραμματεία είναι ανοιχτή καθημερινά 12:00-13:30 Tongue
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 6123 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...