Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και Υπολογισμού
Βιβλιοθήκη Σχολής Θετικών Επιστημών

2014-09-25

2009

Τέντες Αριστείδης

Ευστάθιος Ζάχος Καθηγητής (Επιβλέπων), Α. Παγουρτζής Αναπλ. Καθηγητής , Δ. Φωτάκης Λέκτορας

Expander graphs, randomness extractors and error correcting codes

Αγγλικά

Expander Γράφοι, Εξαγωγή Τυχαιότητας και Κώδικες Διόρθωσεις Λαθών με Λίστα

Ο σκοπός της εργασίας είναι να κάνει μια εισαγωγή από τρεις έννοιες που είναι
σημαντικές στη Θεωρία Πολυπλοκότητας, στην Κρυπτογραφία αλλά και στη Θεωρία
Ψευδοτυχαιότητας γενικότερα. Οι έννοιες αυτές είναι οι Expander Γράφοι, Εξαγωγή
Τυχαιότητας και Κώδικες Διόρθωσης Λαθών με Λίστα. Οι expander γράφοι έχουν την
ιδιότητα ότι αποτελούνται απο λίγες ακμές όμως οι κορυφές τους είναι πολύ καλά
συνδεδεμένοι. Ένας αλγόριθμος εξάγει τυχαιότητα όταν παίρνει σαν είσοδο μία
ακολοθία που δεν έχει τέλεια τυχαιότητα και επιστρέφει μία άλλη ακολουθία που
είναι σχεδόν τυχαία. Οι Κώδικες Διόρθωσης Λαθών με Λίστα ίσως να φαίνεται ότι
δεν έχουν άμεση σχέση με τη θεωρία Ψευδοτυχαιότητας. Χρησιμοποιούνται για να
λύσουν το πρόβλημα επικοινωνίας σε ένα δίκτυο το οποίο μπορεί να εισάγει θόρυβο
μεγαλύτερο από αυτόν που μπορούν να αφαιρέσουν οι απλοί Κώδικες Διόρθωσης
Λαθών. Η αποκωδικοποίηση σε αυτήν την περίπτωση δε γίνεται με την επιστροφη
μίας μοναδικής λέξης, αλλά με την επιστροφή μίας λίστας λέξεων η οποία σίγουρα
θα περιέχει την αρχική λέξη. Η καθεμία από αυτές τις τρεις έννοιες έχει
μελετηθεί ξεχωριστά, χρησιμοποιώντας αρκετά διαφορετικές τεχνικές. Ωστόσο,
υπάρχει τρόπος να εκφραστεί η καθεμία ως περίπτωση της άλλης. Πιο συγκεκριμένα
οι expander γράφοι και αλγόριθμοι εξαγωγής τυχαιότητας μπορούν να εκφραστούν
σαν Κώδικες Διόρθωσης Λαθών με Λίστα και το αντίστροφο.

Ψευδοτυχαιότητα, Θεωρία Πολυπλοκότητας, Expander Γράφοι, Εξαγωγή Τυχαιότητας, Κώδικες Διόρθωσης Λαθών με Λίστα

Όχι

0

Όχι

34

56

https://pergamos.lib.uoa.gr/uoa/dl/object/1321056/file.pdf

https://pergamos.lib.uoa.gr/uoa/dl/object/1321056