Venus AUEB Forum

Το παρόν thread προορίζεται για το μάθημα "Ειδικά Θέματα Αλγορίθμων". Εδώ μπορείτε να συζητάτε για ό,τι σχετίζεται με το συγκεκριμένο μάθημα. Υπενθυμίζουμε ότι με βάση τους κανονισμούς λειτουργίας του forum απαγορεύονται τα greeklish, double posts και τα κεφαλαία.

Θέματα Φλεβαρη 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.