Your browser does not support JavaScript!

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

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

Προσθήκη στο καλάθι
[Προσθήκη στο καλάθι]
Κωδικός Πόρου 000368496
Τίτλος Πιθανοθεωρητικές μέθοδοι και εφαρμογές σε κάτω φράγματα πολυπλοκότητας
Άλλος τίτλος Probabilistic Methods and Applications in Lower Complexity Bounds
Συγγραφέας Χόνδρος, Αναστάσιος Θεόδωρος
Σύμβουλος διατριβής Κολουντζάκης, Μιχάλης
Περίληψη Σκοπός της εργασίας που ακολουθεί είναι να δείξει την «δύναμη» των πιθανοθεωρητικών μεθόδων, χάρη στις οποίες τελικά μπορούμε να αποφανθούμε εάν τελικά κάτι «υπάρχει» χωρίς αναγκαστικά να το κατασκευάσουμε. Έτσι, στα κεφάλαια 1 και 2, δείχνουμε την ύπαρξη υποσυνόλων του Ν τα οποία έχουν κάποιες συγκεκριμένες ιδιότητες. Συγκεκριμένα, στο κεφάλαιο 1, δείχνουμε την ύπαρξη ασυμπτωτικής προσθετικής βάσης με συνάρτηση αναπαράστασης μεγέθους O(log(x)), ενώ στο κεφάλαιο 2, την ύπαρξη και κατασκευή σε πολυωνυμικό χρόνο ενός sum-free συνόλου, από ένα δεδομένο υποσύνολο του Ν Στα κεφάλαια 3 και 4, ασχολούμαστε με την συνάρτηση parity και χρησιμοποιώντας πιθανοθεωρητικά επιχειρήματα πάλι, δείχνουμε ότι δεν μπορεί να υπολογιστεί από λογικά κυκλώματα σταθερού βάθους και πολυωνυμικού μεγέθους καθώς και κάποια άλλα φράγματα.
Φυσική περιγραφή 50 σ. : εικ. ; 28 εκ.
Γλώσσα Αγγλικά
Θέμα Probabilistic
Random Restrictions
Πιθανοθεωρητικός
Τυχαίος περιορισμός
Ημερομηνία έκδοσης 2011-07-15
Συλλογή   Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Μαθηματικών--Μεταπτυχιακές εργασίες ειδίκευσης
  Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
Εμφανίσεις 36

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

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