Πιθανοθεωρητικοί Αλγόριθμοι (μεταπτυχιακό μάθημα)

Μιχάλης Κολουντζάκης

Τμήμα Μαθηματικών, Πανεπιστήμιο Κρήτης, Λεωφόρος Κνωσού, 714 09 Ηράκλειο, E-mail: kolount@gmail.com

Φθινόπωρο 2007-08

Περιεχόμενα

• 1 Ωράριο
• 2 Περιγραφή του μαθήματος
  • 2.1 Βιβλίο
  
  
• 3 Βαθμολογικό Σύστημα - Εξετάσεις
• 4 Ημερολόγιο Μαθήματος
  • 4.1 Δε, 1/10/07: Εισαγωγικά παραδείγματα
  • 4.2 Τε, 3/10/07: Παραδειγμάτων συνέχεια
  • 4.3 Δε, 8/10/07: Υπολογισμοί μέσων τιμών. Μέση ανάλυση του χρόνου του αλγορίθμου Quicksort
  • 4.4 Τε, 10/10/07: Ανισότητες απόκλισης από τη μέση τιμή. Πιθ. αλγόριθμος για εύρεση median μιας λίστας.
  • 4.5 Δε, 15/10/07: Εκθετικές ανισότητες για μεγάλες αποκλίσεις
  • 4.6 Τε, 17/10/07: Το θεώρημα του Erdös για ασυμπτωτικές προσθετικές βάσεις των φυσικών
    • 4.6.1 Πα, 19/10/07: ΑΝΑΚΟΙΝΩΣΗ: Αναβολή μαθήματος
  • 4.7 Δε, 22/10/07: Η μέθοδος των δεσμευμένων πιθανοτήτων για derandomization
    • 4.7.1 ΑΝΑΚΟΙΝΩΣΗ: Πρώτη συλλογή ασκήσεων
  • 4.8 Δε, 29/10/07: Ανάλυση δρομολόγησης
    • 4.8.1 ΑΝΑΚΟΙΝΩΣΗ: Δε, 29/10/07: Αλλαγή ώρας μαθήματος
    • 4.8.2 ΑΝΑΚΟΙΝΩΣΗ: Τρ, 30/10/07: Ένα ακόμη πρόβλημα
  • 4.9 Τε, 31/10/07: Πρόβλημα με m μπάλες σε n κουτιά
  • 4.10 Δε, 5/11/07: Προσέγγιση Poisson του προβλήματος m μπάλες σε n κουτιά. Hash tables.
  • 4.11 Τε, 7/11/07: Τοπικό λήμμα του Lovasz
  • 4.12 Δε, 12/11/07: Αλυσίδες Markov και εφαρμογές
  • 4.13 Τε, 14/11/07: Αλυσίδες Markov και εφαρμογές, συνέχεια
  • 4.14 Δε, 19/11/07: Λύση ασκήσεων. Διευκρίνιση προβλήματος. Ιδιότητες καταστάσεων μιας αλυσίδας Markov
  • 4.15 Τε, 21/11/07: Τυχαίοι περίπατοι σε γραφήματα. Εντροπία.
    • 4.15.1 ΑΝΑΚΟΙΝΩΣΗ: Δεύτερη συλλογή ασκήσεων
  • 4.16 Δε, 26/11/07: Εντροπία και ιδιότητές της
  • 4.17 Τε, 28/11/07: Εφαρμογές της εντροπίας σε προβλήματα συνδυαστικής. Συμπίεση.
  • 4.18 Δε, 3/12/07: Συμπίεση. Αλγόριθμοι στη θεωρία αριθμών.
  • 4.19 Τε, 5/12/07: Αλγόριθμοι στη θεωρία αριθμών
  • 4.20 Δε, 10/12/07: Αλγόριθμοι στη θεωρία αριθμών
  • 4.21 Τε, 12/12/07: Αλγόριθμοι στη θεωρία αριθμών
    • 4.21.1 Πέ, 13/12/07: ΑΝΑΚΟΙΝΩΣΗ: Σταματάνε τα μαθήματα μέχρι νεωτέρας
    • 4.21.2 Δε, 17/12/07: ΑΝΑΚΟΙΝΩΣΗ: Θέματα για παρουσίαση
    • 4.21.3 Τε, 19/12/07: ΑΝΑΚΟΙΝΩΣΗ: Ξαναρχίζουν τα μαθήματα στο ΠΚ
  • 4.22 Τε, 19/12/07: Ασφάλεια του RSA. Θεώρ. Pratt για αποδεικτικά πρώτων.
  • 4.23 Δε, 7/1/08: Primality testing
  • 4.24 Τε, 8/1/08: Ιδιότητες του συμβόλου Legendre/Jacobi
    • 4.24.1 Τε, 6/2/08: ΑΝΑΚΟΙΝΩΣΗ: Ομιλίες στα πλαίσια του μαθήματος

1 Ωράριο

Δευτέρα 5-7, Τετάρτη 1-3 στην αίθουσα Λ 210. Έναρξη μαθημάτων: 1/10/07.

Ώρες γραφείου: Τρίτη 10-12πμ.

2 Περιγραφή του μαθήματος

Θα περιγράψουμε τρόπους με τους οποίους αλγόριθμοι οι οποίοι έχουν πρόσβαση σε μια πηγή τυχαιότητας μπορούν να πλεονεκτούν των αμιγώς ντετερμινιστικών αλγορίθμων, σε απλότητα ή ταχύτητα. Θα δούμε διάφορα παραδείγματα επιτυχημένων τέτοιων αλγορίθμων και θα τα αναλύσουμε.

2.1 Βιβλίο

Θα χρησιμοποιήσουμε κυρίως το βιβλίο των Mitzenmacher και Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press (2005).

3 Βαθμολογικό Σύστημα - Εξετάσεις

4 Ημερολόγιο Μαθήματος

Η σελίδα αυτή θα ενημερώνεται τουλάχιστον μετά από κάθε μάθημα και σκοπό έχει να μεταδίδει μερικές βασικές χρήσιμες πληροφορίες για το περιεχόμενο του μαθήματος (π.χ. τι να προσέξετε, υποδείξεις για λύσεις των ασκήσεων, κ.ά.) καθώς και για διαδικαστικά θέματα.

Σπανίως θα βγαίνουν ανακοινώσεις που αφορούν το μάθημα σε χαρτί. Παρακαλώ να συμβουλεύεστε αυτή τη σελίδα τουλάχιστον 2-3 φορές την εβδομάδα.

4.1 Δε, 1/10/07: Εισαγωγικά παραδείγματα

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

Συγκεκριμένα είδαμε

1. Ένα πιθανοθεωρητικό αλγόριθμο για να αποφασίζουμε αν δύο πολυώνυμα είναι μεταξύ τους ίσα χρησιμοποιώντας $O(\log d)$ υπολογισμούς των πολυωνύμων αυτών ($d$ είναι ο βαθμός τους).
2. Ένα πιθανοθεωρητικό αλγόριθμο για να αποφασίζουμε αν ισχύει $AB=C$ για δοσμένους $n\times n$ πίνακες $A,B,C$, σε χρόνο $O(n^2)$.
3. Ένα πιθανοθεωρητικό αλγόριθμο για να βρίσκουμε ένα υποσύνολο $B$ δοσμένου συνόλου ακεραίων $A$ που να είναι sum-free ( $\forall x,y,z \in B: x+y \neq z$) και με ${\left\vert{B}\right\vert} \ge {\left\vert{A}\right\vert}/3$ (λεπτομέρειες εδώ).

4.2 Τε, 3/10/07: Παραδειγμάτων συνέχεια

Επειδή είχαμε δύο καινούργια άτομα στο ακροατήριο επαναλάβαμε τα Παραδείγματα 1 και 2 της Δευτέρας. Επίσης παρουσιάσαμε και αναλύσαμε ένα πιθανοθεωρητικό αλγόριθμο για της εύρεση μιας ελάχιστης τομής (min cut) ενός γραφήματος και υπολογίσαμε άνω φράγμα γαι την πιθανότητα να μη βρεθεί η ελάχιστη τομή (ο αλγόριθμος δίνει πάντα κάποια τομή του γραφήματος). Είδαμε πόσες φορές πρέπει να τρέχουμε ανεξάρτητα τον αλγόριθμο για να «ενισχύσουμε» αυτή την πιθανότητα επιτυχίας.

4.3 Δε, 8/10/07: Υπολογισμοί μέσων τιμών. Μέση ανάλυση του χρόνου του αλγορίθμου Quicksort

Δείξαμε διάφορες μεθόδους για τον υπολογισμό μέσων τιμών τυχαίων μεταβλητών (ΤΜ) και ιδιαίτερα το σπάσιμο μιας ΤΜ σε άθροισμα απλών (και συνήθως με τιμές 0 ή 1) ΤΜ.

Είδαμε τι σημαίνει ο συμβολισμός ${{\bf E}\left[{X { \vert }Y}\right]}$ όπως και την ταυτότητα

$${{\bf E}\left[{{{\bf E}\left[{X { \vert }Y}\right]}}\right]} = {{\bf E}\left[{X}\right]},$$

και είδαμε ένα απλό branching process και πώς υπολογίζουμε το μέσο πληθυσμό στο χρόνο $t$.

Τέλος είδαμε πώς δουλεύει ο αλγόριθμος Quicksort για την ταξινόμηση μιας λίστας αριθμών και υπολογίσαμε τη μέση τιμή του χρόνου που χρειάζεται για να ταξινομήσει μια λίστα μήκους $n$ (είδαμε ότι αυτή η μέση τιμή είναι $O(n \log n)$.

4.4 Τε, 10/10/07: Ανισότητες απόκλισης από τη μέση τιμή. Πιθ. αλγόριθμος για εύρεση median μιας λίστας.

Είδαμε μερικές βασικές ανισότητες απόκλισης από τη μέση τιμή. Συγκεκριμένα είδαμε τις ανισότητες Markov και Chebyshev. Είδαμε επίσης πώς εφαρμόζονται αυτές οι δύο στο πρόβλημα με τη συλλογή κουπονιών (coupon collector problem).

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

4.5 Δε, 15/10/07: Εκθετικές ανισότητες για μεγάλες αποκλίσεις

Είδαμε ανισότητες του τύπου ${{\bf {Pr}}\left[{{\left\vert{X-{{\bf E}\left[{X}\right]}}\right\vert} > a}\right]} \le \cdots$ όπου το άνω φράγμα είναι εκθετικά μικρό. Τέτοιου είδους ανισότητες ισχύουν όταν η $X$ έχει κάποια δομή, και συγκεκριμένα προκύπτει ως άθροισμα πολλών ανεξαρτήτων ΤΜ.

4.6 Τε, 17/10/07: Το θεώρημα του Erdös για ασυμπτωτικές προσθετικές βάσεις των φυσικών

Χρησιμοποιώντας την ανισότητα του Chernoff δείξαμε το εξής θεώρημα του Erdös:

υπάρχουν ασυμπτωτικές προσθετικές βάσεις των ακεραίων (σύνολα $A \subseteq {\mathbf N}$ τέτοια ώστε κάθε αρκετά μεγάλος φυρικός αριθμός γράφεται σαν άθροισμα δύο στοιχείων του $A$) τέτοιες ώστε το πλήθος των αναπαραστάσεων του φυσικού αριθμού $x$ φράσσεται άνω και κάτω από ένα σταθερό πολλαπλάσιο του $\log x$.

Λεπτομέρειες εδώ, σελ. 6.

4.6.1 Πα, 19/10/07: ΑΝΑΚΟΙΝΩΣΗ: Αναβολή μαθήματος

Το μάθημα της Τετάρτης 24/10/07 αναβάλλεται λόγω κωλύματός μου με ένα συνέδριο που οργανώνεται εδώ.

4.7 Δε, 22/10/07: Η μέθοδος των δεσμευμένων πιθανοτήτων για derandomization

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

Είδαμε διάφορα παραδείγματα εφαρμογής της μεθόδου. Περισσότερα μπορείτε να διαβάσετε εδώ, σελ. 8.

4.7.1 ΑΝΑΚΟΙΝΩΣΗ: Πρώτη συλλογή ασκήσεων

Παρακαλώ λύστε τις ασκήσεις του βιβλίου σας: 1.6, 1.11, 2.2, 2.4, 2.10, 2.14, 2.18, 2.21, 2.26, 2.28. Πρέπει να παραδώσετε τις λύσεις μέχρι και το μάθημα της 5 Νοεμβρίου 2007.

4.8 Δε, 29/10/07: Ανάλυση δρομολόγησης

Είδαμε ένα πιθανοθεωρητικό αλγόριθμο για δρομολόγηση πακέτων πάνω στον υπερκύβο διάστασης $n$ και αναλύσαμε την απόδοσή του.

4.8.1 ΑΝΑΚΟΙΝΩΣΗ: Δε, 29/10/07: Αλλαγή ώρας μαθήματος

Την προσεχή Τετάρτη, 31/10/07, το μάθημα θα γίνει 5-7μμ στην ίδια αίθουσα.

4.8.2 ΑΝΑΚΟΙΝΩΣΗ: Τρ, 30/10/07: Ένα ακόμη πρόβλημα

Το πρόβλημα 1.5 του βιβλίου σας είναι εξαιρετικά ενδιαφέρον αν και πολύ απλό στη λύση του. Μην παραλείψετε να το κοιτάξετε (το παράδοξο των μη μεταβατικών ζαριών - nontransitive dice paradox).

4.9 Τε, 31/10/07: Πρόβλημα με m μπάλες σε n κουτιά

Είδαμε διάφορα ερωτήματα που προκύπτουν αν ρίξουμε τυχαία m μπάλες σε n διακεκριμένα κουτιά, ένα πρόβλημα που μοντελοποιεί πολλά άλλα. Π.χ. είδαμε τον αλγόριθμο bucket sort, ένα ντετερμινιστικό αλγόριθμο διάταξης $n$ στοιχείων τον οποίο αναλύσαμε για ένα τυχαίο input και είδαμε ότι ο μέσος χρόνος που παίρνει για ένα τυχαίο input είναι $O(n)$.

Δείξαμε επίσης ότι αν ρίξουμε $n$ μπάλες σε $n$ κουτιά τότε σχεδόν σίγουρα (με πιθανότητα που τείνει στο 1) κάθε κουτί έχει το πολύ $3 \log n \bigl/ \log\log n$ μπάλες.

Εισαγάγαμε την κατανομή Poisson($\mu$) και είδαμε διάφορες ιδιότητές της. Είδαμε επίσης ότι όταν $n\to\infty$ και $np \to \mu$ τότε η κατανομή $B(n,p)$ (διωνυμική με παραμέτρους $n, p$) τείνει στην Poisson($\mu$), με την έννοια ότι αν $X_n \sim B(n, p)$ και $Y \sim$ Poisson($\mu$) τότε ${{\bf {Pr}}\left[{X_n = k}\right]} \to {{\bf {Pr}}\left[{Y=k}\right]}$, για κάθε σταθερό $k$.

4.10 Δε, 5/11/07: Προσέγγιση Poisson του προβλήματος m μπάλες σε n κουτιά. Hash tables.

Είδαμε με ποιο τρόπο μπορούμε να λύσουμε διάφορα προβλήματα που αφορούν το πρόβλημα $m$ μπάλες σε $n$ κουτιά, λύνοντας πρώτα το αντίστοιχο πρόβλημα όπου υποθέτουμε ότι το κάθε κουτί έχει ανεξάρτητα περιεχόμενα που ακολουθούν την Poisson($m/n$), και χρησιμοποιώντας κάποια θεωρήματα που φράσσουν πιθανότητες που αφορούν το πραγματικό πρόβλημα με πιθανότητες που αφορούν το προσεγγιστικό πρόβλημα Poisson, το οποίο είναι, συνήθως, πολύ ευκολότερο να αναλυθεί μια και τα περιεχόμενα των κουτιών είναι ανεξάρτητα.

Είδαμε πώς λειτουργεί ένα απλό hash table και κάναμε μια ανάλυση των ιδιοτήτων του. Είδαμε π.χ. ότι σχεδόν σίγουρα ο μέγιστος χρόνος αναζήτησης σε ένα hash table με $n$ bins και $n$ αντικείμενα είναι $O(\log n \bigl/ \log\log n)$ και ο μέσος χρόνος αναζήτησης είναι $O(1)$ (σταθερός).

4.11 Τε, 7/11/07: Τοπικό λήμμα του Lovasz

Είδαμε την απόδειξη του τοπικού λήμματος του Lovasz καθώς και δύο εφαρμογές αυτού (§6.7).

4.12 Δε, 12/11/07: Αλυσίδες Markov και εφαρμογές

Είδαμε μερικές από τις βασικές ιδιότητες των αλυσίδων Markov και ξεκινήσαμε να βλέπουμε ένα αλγόριθμο επίλυσης του προβλήματος 2SAT που συνίσταται στην εκτέλεση ενός τυχαίου περίπατου μέχρι να βρούμε μια ανάθεση τιμών στις μεταβλητές που ικανοποιεί όλα τα clauses.

4.13 Τε, 14/11/07: Αλυσίδες Markov και εφαρμογές, συνέχεια

Τελειώσαμε την ανάλυση του αλγορίθμου για το 2SAT (εκτός από ένα λεπτό σημείο για τη σύγκριση δύο στοχαστικών ανελίξεων το οποίο δεν εξηγείται καλά στο βιβλίο).

Μιλήσαμε για ιδιότητες των καταστάσεων μιας αλυσίδας Markov όσον αφορά την επαναφορά (recurrence) κυρίως.

4.14 Δε, 19/11/07: Λύση ασκήσεων. Διευκρίνιση προβλήματος. Ιδιότητες καταστάσεων μιας αλυσίδας Markov

Λύσαμε μερικές ασκήσεις από το Φυλλάδιο 1 στις οποίες υπήρχε κάποιο πρόβλημα.

Διευκρινήσαμε ένα πρόβλημα σύγκρισης δύο τυχαίων περιπάτων που μας είχε απασχολήσει αρκετά.

Συνεχίσαμε τη συζήτηση για τα είδη των καταστάσεων μιας αλυσίδας Markov όσον αφορά την επαναφορά.

4.15 Τε, 21/11/07: Τυχαίοι περίπατοι σε γραφήματα. Εντροπία.

Τελειώσαμε τη συζήτηση για αλυσίδες Markov αναφέροντας ιδιότητες των τυχαίων περιπάτων σε μη κατευθυνόμενα γραφήματα και ένα αλγόριθμο για $s-t$ συνδετικότητα πάνω σε τέτοια γραφήματα.

Αρχίσαμε να μιλάμε για την έννοια της εντροπίας μιας κατανομής.

4.15.1 ΑΝΑΚΟΙΝΩΣΗ: Δεύτερη συλλογή ασκήσεων

Παρακαλώ λύστε τις ασκήσεις του βιβλίου σας: 3.7, 3.8, 3.13, 3.20, 3.21, 3.25, 4.1, 4.5, 4.8, 4.9, 4.18.

Πρέπει να παραδώσετε τις λύσεις μέχρι και το μάθημα της 12 Δεκεμβρίου 2007.

4.16 Δε, 26/11/07: Εντροπία και ιδιότητές της

Είδαμε την έννοια της εντροπίας μιας κατανομής, εντροπία υπό δέσμευση, κανόνες αλυσίδας για την εντροπία, την έννοια της κοινής πληροφορίας δύο τυχαίων μεταβλητών και της απόστασης Kullbak-Leibler.

4.17 Τε, 28/11/07: Εφαρμογές της εντροπίας σε προβλήματα συνδυαστικής. Συμπίεση.

Την πρώτη ώρα του μαθήματος είδαμε διάφορες εφαρμογές της έννοιας της εντροπίας σε αποδείξεις συνδυαστικών θεωρημάτων χωρίς πιθανοθεωρητικό περιεχόμενο.

Κατά τη δεύτερη ώρα αρχίσαμε να μιλάμε για κώδικοποίηση των τιμών μιας ΤΜ $X$ που παίρνει πεπερασμένες το πλήθος τιμές. Αποδείξαμε την ανισότητα του Kraft. Για το υλικό αυτό θα ακολουθήσουμε κυρίως το βιβλίο Information Theory, Inference, and Learning Algorithms του David J.C. MacKay (Κεφ. 5), το οποίο μπορείτε να βρείτε εδώ σε μορφή PDF (9 Mbytes).

4.18 Δε, 3/12/07: Συμπίεση. Αλγόριθμοι στη θεωρία αριθμών.

Τελειώσαμε το κεφάλαιο περί συμπίεσης πηγής αποδεικνύοντας ότι το αναμενόμενο μήκος κώδικα φράσσεται κάτω από την εντροπία της πηγής $H(X)$ και άνω από $H(X)+1$. Δείξαμε πώς λειτουργεί η κωδικοποίηση Huffman, η οποία είναι βέλτιστη (αυτό δεν το δείξαμε).

Αρχίσαμε να μιλάμε για αλγόριθμους στη θεωρία αριθμών (ακολουθούμε το βιβλίο των Motawni και Raghavan, Randomized Algorithms, Κεφ. 14. Είδαμε το γενικευμένο αλγόριθμο του Ευκλείδη, πώς να υπολογίζουμε τετραγωνικές ρίζες και άλλους αλγόριθμους για απλές αλγεβρικές πράξεις οι οποίοι πρέπει να τρέχουν σε πολυωνυικό χρόνο στο μέγεθος του input.

4.19 Τε, 5/12/07: Αλγόριθμοι στη θεωρία αριθμών

Μιλήσαμε κυρίως για υπολογισμούς σε πεπερασμένες ομάδες ${\mathbf Z}_n$ (προσθετική ομάδα υπολοίπων mod $n$) και ${\mathbf Z}_n^*$ (πολλαπλασιαστική ομάδα των υπολοίπων $x \bmod n$ που είναι πρώτα ως προς το $n$).

4.20 Δε, 10/12/07: Αλγόριθμοι στη θεωρία αριθμών

Δείξαμε ότι η ομάδα ${\mathbf Z}_p^*$ ($p$ περιττός πρώτος) είναι κυκλική και είδαμε ένα πιθανοθεωρητικό αλγόριθμο υπολογισμού μιας τετραγωνικής ρίζας του $x \in {\mathbf Z}_p^*$ για τετραγωνικό υπόλοιπο $x$ (για υπόλοιπο δηλ. που είναι τετράγωνο κάποιου υπολοίπου). Ο αλγόριθμος αυτός γενικεύεται και στην περίπτωση που το modulus είναι $p^k$ ή $2^k$ και, χρησιμοποιώντας το Κινέζικο Θεώρημα υπολοίπων γενικεύεται και σε οποιοδήποτε modulus $n$ του οποίου η ανάλυση σε πρώτους παράγοντες είναι γνωστή (μέρος του input δηλ.).

4.21 Τε, 12/12/07: Αλγόριθμοι στη θεωρία αριθμών

Δείξαμε ότι το πρόβλημα της παραγοντοποίησης ακεραίων ανάγεται πολυωνυμικά (με πιθανοθεωρητικό αλγόριθμο) στο πρόβλημα εύρεσης τετραγωνικών ριζών mod $n$.

Περιγράψαμε τον αλγόριθμο κρυπτογράφησης δημοσίου κλειδιού RSA και δείξαμε ότι αν κανείς μπορέσει να συνάγει το ιδιωτικό κλειδί από το δημόσιο τότε μπορεί και να παραγοντοποιήσει το modulus.

4.21.1 Πέ, 13/12/07: ΑΝΑΚΟΙΝΩΣΗ: Σταματάνε τα μαθήματα μέχρι νεωτέρας

Δείτε εδώ σε μορφή PDF ανακοίνωση της Συγκλήτου του ΠΚ.

4.21.2 Δε, 17/12/07: ΑΝΑΚΟΙΝΩΣΗ: Θέματα για παρουσίαση

Μπορείτε να τα δείτε εδώ σε μορφή PDF με ενσωματωμένα links. (Τελευταία ενημέρωση: Tue Dec 18 09:43:27 EET 2007)

4.21.3 Τε, 19/12/07: ΑΝΑΚΟΙΝΩΣΗ: Ξαναρχίζουν τα μαθήματα στο ΠΚ

4.22 Τε, 19/12/07: Ασφάλεια του RSA. Θεώρ. Pratt για αποδεικτικά πρώτων.

Δείξαμε ακόμη ένα θέωρημα στην κατεύθυνση της ασφάλειας του RSA (ότι αν μπορούμε να αποκρυπτογραφήσουμε ένα κλάσμα των λέξεων τότε μπορούμε να τις αποκρυπτογραφήσουμε όλες).

Επίσης δείξαμε ότι κάθε πρώτος αριθμός επιδέχεται ένα certificate πολυωνυμικού μήκους και χρόνου επαλήθευσης (Θ. Pratt).

Συζητήσαμε λίγο για τα θέματα που προτείνονται για τις ομιλίες μετά τις γιορτές.

4.23 Δε, 7/1/08: Primality testing

Είδαμε τον αλγόριθμο Solovay-Strassen για έλεγχο του αν ένας αριθμός είναι πρώτος ή όχι (αλγόριθμος πιθανοθεωρητικός και πολυωνυμικού χρόνου).

4.24 Τε, 8/1/08: Ιδιότητες του συμβόλου Legendre/Jacobi

Αποδείξαμε λεπτομερώς τις ιδιότητες του συμβόλου Legendre και αυτές του συμβόλου Jacobi που χρησιμοποιήσαμε στην προηγούμενη διάλεξη για τον υπολογισμό του συμβόλου Jacobi, και ιδιαίτερα τον τύπο τετραγωνικής αντιστροφής (quadratic reciprocity).

4.24.1 Τε, 6/2/08: ΑΝΑΚΟΙΝΩΣΗ: Ομιλίες στα πλαίσια του μαθήματος

Στο πλαίσιο του μαθήματος θα γίνουν 45-λεπτες ομιλίες από τους συμμετέχοντες φοιτητές. Οι ομιλίες θα γίνουν το απόγευμα της Δευτέρας 11/2/08 στην αίθουσα Ζ301. Τα θέματα είναι αρκετά διαφορετικά μεταξύ τους και καλύπτουν το φάσμα από την εφαρμογή ως την πράξη.

Οι ομιλίες είναι ανοιχτές στο κοινό.

Μπορείτε να δείτε εδώ σε μορφή PDF το πρόγραμμα και τις περιλήψεις των ομιλιών.