Your browser does not support JavaScript!

Αρχική    Πιθανοθεωρητικές μέθοδοι στην ανάλυση λογικών κυκλωμάτων  

Αποτελέσματα - Λεπτομέρειες

Προσθήκη στο καλάθι
[Προσθήκη στο καλάθι]
Κωδικός Πόρου 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
Συλλογή   Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Μαθηματικών και Εφαρμοσμένων Μαθηματικών--Μεταπτυχιακές εργασίες ειδίκευσης
  Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
Εμφανίσεις 109

Ψηφιακά τεκμήρια
No preview available

Κατέβασμα Εγγράφου
Προβολή Εγγράφου
Εμφανίσεις : 14