Μαθηματικά Πληροφορικής
Χειμερινό εξάμηνο 2011-12
Τμήμα Πληροφορικής και Τηλεπικοινωνιών
Πανεπιστήμιο Αθηνών
Καθηγητής: Ηλίας Κουτσουπιάς
Table of Contents
4o Σύνολο Ασκήσεων
Οι ασκήσεις μπορούν να είναι τυπωμένες ή χειρόγραφες. Ηλεκτρονική παράδοση των ασκήσεων δεν επιτρέπεται σε καμία περίπτωση.
Παρακαλώ θερμά να μην χρησιμοποιείτε πλαστικούς φακέλους παρά μόνο χαρτί.
Ώρα παράδοσης των ασκήσεων: 5:00, Πέμπτη 09/02/2012
Παράδοση στο γραφείο Α1 (1ος όροφος) ή στην τάξη πριν και μετά το μάθημα, (αλλά όχι στη διάρκεια του μαθήματος).
Πρόβλημα 1
Δείξτε όλους τους υπολογισμούς του RSA για p=7, q=11, e=7 για την κωδικοποίηση του μηνύματος T=3.
Πρόβλημα 2
Δείξτε με χρήση του ορισμού του συμβολισμού \(O\) πως αν για δυο συναρτήσεις \(f(n)\) και \(g(n)\) με \(g(n)\geq 2\) ισχύει \(f(n)=Ο(g(n))\), τότε θα ισχύει και \(\log f(n)=Ο(\log g(n))\).
Ο περιορισμός \(g(n)\geq 2\), εγγυάται πως \(\log g(n)\geq 1\). Ισχύει η πρόταση αν αφαιρέσουμε τον περιορισμό \(g(n)\geq 2\)?
Πρόβλημα 3
Θεωρήστε το γράφο \(L_n\) που περιέχει κόμβους \[ V=\{l_1,l_2,\ldots,l_n\}\cup\{r_1,r_2,\ldots,r_n\} \] και ακμές \[ E=\{[l_i,r_j]\,:\, i\geq j\} \] Ποιοι από τους γράφους \(L_1\), \(L_2\), \(\ldots\) είναι επίπεδοι και ποιοι δεν είναι επίπεδοι. Για τους επίπεδους γράφους δώστε μια κατάλληλη αναπαράσταση στο επίπεδο και για τους μη επίπεδους δώστε μια κατάλληλη απόδειξη.
Πρόβλημα 4
Έστω ότι έχουμε ένα πιθανοτικό αλγόριθμο \(A\) για ένα πρόβλημα απόφασης (δηλαδή απαντά ναι ή όχι) που
για κάθε είσοδο δίνει τη σωστή απάντηση με πιθανότητα τουλάχιστον q.
Για να βελτιώσουμε την πιθανότητα \(q\), τρέχουμε τον αλγόριθμο 3 φορές και επιστρέφουμε την απάντηση που πλειοψηφεί.
Ποια η πιθανότητα να είναι σωστή η απάντηση? Είναι πράγματι μεγαλύτερη αυτή η πιθανότητα από το \(q\)?