Μονάδα:
Τομέας Θεωρητικής ΠληροφορικήςΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2015-09-01
Συγγραφέας:
Μαζαράκης Ευγένιος
Στοιχεία επιβλεπόντων καθηγητών:
Σταύρος Κολλιόπουλος
Πρωτότυπος Τίτλος:
Ο μη ντετερμινιστικός χώρος είναι κλειστός ως προς το συμπλήρωμα
Γλώσσες εργασίας:
Ελληνικά
Μεταφρασμένος τίτλος:
nondeterministic space is closed under complementation
Περίληψη:
Στη πτυχιακή αυτή εργασία εξηγείται η μελέτη του Neil Immerman που δημοσιεύτηκε
το 1988 [23]. Για αυτή τη δημοσίευση του απονεμήθηκε το 1995 το βραβείο Godel
διότι απάντησε σε ένα ερώτημα που έμενε πάνω από τρεις δεκαετίες ανοικτό. Κύριος
στόχος της εργασίας αυτής είναι να εξηγήσουμε τι απέδειξε ο Neil Immerman αλλά
και
με ποιο τρόπο τα κατάφερε. Αρχικά αναφέρονται όλοι οι απαραίτητοι ορισμοί γύρω
από τις μηχανές Turing, την πολυπλοκότητα, τις κλάσεις πολυπλοκότητας, τις
διάφορες
σχέσεις που υπάρχουν ανάμεσά τους, τις γραμματικές. Αυτό είναι το απαραίτητο
υπόβαθρο που θα χρειαστούμε για να ακολουθήσουμε το συλλογισμό του Neil Immer-
man. Μετά παρουσιάζονται και εξηγούνται με απλό και κατανοητό τρόπο τα
περιεχόμενα
της δημοσίευσης του. Τέλος ακολουθούν τα συμπεράσματα που προκύπτουν από την
ενασχόλησή μας με τα αποτελέσματα στα οποία οδηγήθηκε ο Immerman.
Λέξεις-κλειδιά:
Πολυπλοκότητα Χώρου, Μηχανή Turing, Μη Ντετερμινισμός, Κλειστότητα ως Προς Συμπλήρωμα, Κλάσεις Πολυπλοκότητας
Αρ. σελίδων ευρετηρίου:
6
Αρ. βιβλιογραφικών αναφορών:
24
