|
Κωδικός Πόρου |
000434101 |
Τίτλος |
Πιθανοθεωρητικές μέθοδοι στην ανάλυση λογικών κυκλωμάτων |
Άλλος τίτλος |
Probabilistic methods in circuit complexity analysis |
Συγγραφέας
|
Καλοψικάκης, Δημήτρης
|
Σύμβουλος διατριβής
|
Κολουντζάκης, Μιχάλης
|
Μέλος κριτικής επιτροπής
|
τζανάκη, Ελένη
Φραντζικινάκης, Νίκος
|
Περίληψη |
Το κείμενο που ακολουθεί αποτελεί διπλωματική εργασία που εκπονήθηκε στο πλαίσιο του μεταπτυχιακού προγράμματος «Μαθηματικά και Εφαρμογές τους» του Τμήματος Μαθηματικών και Εφαρμοσμένων Μαθηματικών του Πανεπιστημίου Κρήτης. Με άξονα ένα βασικό πρόβλημα όπως περιγράφεται στο βιβλίο «Gems of Theoretical Computer Science»[1] του Uwe Schoning, αναδεικνύεται ο ρόλος της Πιθανοθεωρητικής Μεθόδου στην Ανάλυση Λογικών Κυκλωμάτων.
Αρκετά από τα μαθηματικά προβλήματα που τίθενται, ενέχουν σημαντική εγγενή δυσκολία και συχνά μοναδική διέξοδος μοιάζει η επιστράτευση της Θεωρίας Πιθανοτήτων. Το πρόβλημα που εξετάζεται στην εργασία αυτή είναι το κατά πόσο λογικά κυκλώματα μικρής πολυπλοκότητας -συγκεκριμένα της κλάσης AC0- μπορούν να εκφράσουν λογικές συναρτήσεις ισοτιμίας. Αποδεικνύεται ότι κάτι τέτοιο είναι αδύνατο.
Αναλύονται δύο αποδείξεις με διαφορετικές οπτικές, με καίρια εμπλοκή της Πιθανοθεωρητικής Μεθόδου και στις δύο. Στην πρώτη απόδειξη η προσέγγιση είναι αναλυτική και σημείο κλειδί της επιχειρηματολογίας είναι η τεχνική του τυχαίου περιορισμού. Η δεύτερη απόδειξη έχει αλγεβρική λογική και αποτελείται από δύο βήματα: στο πρώτο, με πιθανοθεωρητική τεχνική, γίνεται μια στενή συσχέτιση των κυκλωμάτων με τον χώρο πολυωνύμων μικρής πολυπλοκότητας· στο δεύτερο βήμα προκύπτει το συμπέρασμα με σύγκριση των διαστάσεων των γραμμικών χώρων που αναδεικνύονται στο πρώτο.
Από την πρώτη απόδειξη, προκύπτει ότι λογικά κυκλώματα πολυωνυμικού μεγέθους πρέπει να έχουν βάθος τουλάχιστον λογαριθμικό για να μπορούν να υπολογίσουν συναρτήσεις ισοτιμίας, ενώ από τη δεύτερη απόδειξη το φράγμα αυτό βελτιώνεται σε Ω=(logn/loglogn)
|
Φυσική περιγραφή |
47 σ. ; : ; 30 εκ. |
Γλώσσα |
Ελληνικά, Αγγλικά |
Θέμα |
Boolean functions |
|
Polynomial method |
|
Random restrictions |
|
Λογικές συναρτήσεις |
|
Μέθοδος πολυωνύμου |
|
Πιθανοθεωρητική μέθοδο |
|
Υπολογιστική πολυπλοκότητα |
Ημερομηνία έκδοσης |
2020-11-20 |
Συλλογή
|
Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Μαθηματικών και Εφαρμοσμένων Μαθηματικών--Μεταπτυχιακές εργασίες ειδίκευσης
|
|
Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
|
Εμφανίσεις |
438 |