Ειδικά Θέματα Αλγορίθμων

Συζητήσεις σχετικά με τα μαθήματα Κύκλων και Κατευθύνσεων του τρέχοντος ακαδημαϊκού έτους. Για συζητήσεις παλαιοτέρων ετών κοιτάξτε στην κατηγορία "Παλιές Συζητήσεις "
Post Reply
User avatar
parasleivadaros
Moderator
Posts: 70
Joined: Wed Oct 21, 2015 3:10 pm
Academic status: N>4
Gender:
Location: Athens, Greece
Contact:

Ειδικά Θέματα Αλγορίθμων

Post by parasleivadaros » Thu Oct 31, 2019 7:35 pm

Το παρόν thread προορίζεται για το μάθημα "Ειδικά Θέματα Αλγορίθμων". Εδώ μπορείτε να συζητάτε για ό,τι σχετίζεται με το συγκεκριμένο μάθημα. Υπενθυμίζουμε ότι με βάση τους κανονισμούς λειτουργίας του forum απαγορεύονται τα greeklish, double posts και τα κεφαλαία.
:smt024
teotsi21
bit level
bit level
Posts: 14
Joined: Mon Dec 05, 2016 2:07 am
Academic status: 2nd year
Gender:
Contact:

Re: Ειδικά Θέματα Αλγορίθμων

Post by teotsi21 » Fri Feb 07, 2020 8:01 pm

Θέματα Φλεβαρη 2020:
1ο) Α. Αποδειξτε πως με τον αλγοριθμο EUCLID(a,b) μπορουμε να υπολογισουμε το ΕΚΠ των a,b, αν a,b θετικοι ακεραιοι.(12)
Β. RSA, υποκλεπτουμε το μηνυμα C=10, με public key n=91 και e=11(νομιζω). Να δειξουμε αναλυτικα πως βρισκουμε το plaintext.(15)

2o) Λυστε το Knapsack με δυναμικο προγραμματισμο. Η πολυπλοκοτητα του Αλγο πρεπει να ειναι Ο(n^2 * vmax). Vmax ηταν η μεγιστη αξια μεταξυ των αντικειμενων.(10)

3ο) Α.Αν υπαρχει πολυωνυμικος αλγοριθμος που απανταει στο αν υπαρχει ή οχι Hamilton Path σε ενα G, δειξτε οτι υπαρχει επισης πολυωνυμικος αλγοριθμος που μας επιστρεφει ποιο ειναι το εν λογω path.(10-15)
Β. Εχουμε n εργατες και m εργαλεια. Καθε εργατης χρειαζεται ενα συνολο εργαλειων. Για να δουλεψει ενας εργατης χρειαζεται ολα τα εργαλεια. Ενα εργαλειο μπορει να χρησιμοποιηθει απο μονο εναν εργατη. Δινεται τωρα k<n. Γινεται να εργαστουν k εργατες ταυτοχρονα? (12-15)
Ηθελε να πουμε αν ειναι NP-Complete το προβλημα (αναγωγη σε Independent Set αν δεν κανω λαθος), και να βρουμε την πολυπλοκοτητα για k=2, k=3.

4ο) Α. Θελουμε να λυσουμε το προβλημα Maximum Cut. Ο αλγοριθμος που χρησιμοποιουμε διαλεγει ανεξαρτητα καθε φορα εναν κομβο με p=1/2. Να αποδειξουμε οτι η αναμενομενη προσεγγιση του αλγοριθμου ειναι 1/2.
Β. Παρομοιο με το 2ο θεμα του 2014, πιθανοκρατικοι. Αν θυμαμαι καλα τα clauses ειχαν ολα τουλαχιστον 2 αρνητικά literals, αλλα ισως κανω λαθος.
5ο) Α. Να διατυπωσουμε το Bin Packing με ILP.(7-10)
Β. 1. Να διατυπωσουμε το Vertex Cover με ILP, και μετα ειχε δυο υποερωτηματα με LP-Rounding πανω στο προηγουμενο.(3, 5, 7 μοναδες αντιστοιχα)

Συμπλήρωσα όπου θυμόμουν τις μονάδες κάθε θεματος, γενικα το γραπτό εφτανε μέχρι τις 125 ή καπου εκει, έλυνες όσες ήθελες, μεγιστη βαθμολογια που θα επαιρνες ηταν το 100.
Dreams are made winding through my head.
Post Reply

Return to “Μαθήματα Κύκλων και Κατευθύνσεων”