[Ανάλυση Αλγορίθμων]Απορίες στις ασκήσεις 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.

[babyshark]

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

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

[panos98]

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

[Σοκοφρέτας]

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

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

sent from mTHMMY 

[sterpapi]

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

[Argirios]

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

[Αλέκος από Κω]

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

οχι

[Αλέκος από Κω]

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

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

[panos98]

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

[Αλέκος από Κω]

Πως γραψαμε?

[Argirios]

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

[Αλέκος από Κω]

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

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

[Argirios]

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

[Αλέκος από Κω]

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

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

[Αλέκος από Κω]

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

[Patatompataria]

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

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

Αρχικά κάνουμε τον δισδιάστατο πίνακα 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 ή όχι, για να βρούμε μετά ποιες μέρες κάναμε.

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