Θεωρία υπολογισμού: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μΧωρίς σύνοψη επεξεργασίας |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 3:
Για να πραγματοποιήσουν μια εξονυχιστική μελέτη των υπολογισμών, οι επιστήμονες υπολογιστών αντιμετωπίζουν τον υπολογιστή ως μια αφηρημένη μαθηματική έννοια, που λέγεται μοντέλο υπολογισμού. Υπάρχουν διάφορες διατυπώσεις που χρησιμοποιούνται, αλλά η πιο συχνή είναι η [[μηχανή Τούρινγκ]]. Μπορεί κανείς να θεωρήσει τη μηχανή Τούρινγκ σαν ένα [[προσωπικός υπολογιστής|προσωπικό υπολογιστή]] με άπειρη μνήμη, αν και μπορεί να την προσπελάσει μόνο σε μικρά διακριτά κομμάτια. Οι επιστήμονες υπολογιστών μελετούν τη μηχανή Τούρινγκ γιατί έχει απλή διατύπωση και μπορούν να την αναλύσουν, να την χρησιμοποιήσουν σε αποδείξεις, και λόγω του ότι κατά πολλούς αντιπροσωπεύει το πιο ισχυρό εφικτό μοντέλο υπολογισμού. Αν και η άπειρη μνήμη μπορεί να θεωρηθεί ανέφικτη, στην πραγματικότητα κάθε πρόβλημα που λύνει η μηχανή Τούρινγκ χρειάζεται πάντα πεπερασμένη μνήμη, άρα κάθε πρόβλημα που μπορεί να λυθεί από μια μηχανή Τούρινγκ, θα μπορούσε να λυθεί από έναν προσωπικό υπολογιστή που έχει αρκετή μνήμη.
== Βασικές Αρχές ==
Kleen Star Κλειστότητα ενός αλφαβήτου Σ ονομάζουμε το σύνολο Σ* όλων των δυνατών συμβολοσειρών που προκύπτουν από αυτό το αλφάβητο. Πρόκειται για ένα [[μετρήσιμο απειροσύνολο]] (''Συμπέρασμα 1''). Γλώσσα ονομάζουμε ένα υποσύνολο του Σ* για δεδομένο αλφάβητο Σ. Το [[σύνολο]] όλων των γλωσσών που προκύπτουν από ένα αλφάβητο Σ είναι το δυναμοσύνολο (το σύνολο όλων των δυνατών υποσυνόλων) του Σ* και είναι μη μετρήσιμο απειροσύνολο (''Συμπέρασμα 2''). Μπορούμε να καταλήξουμε σε διάφορους πεπερασμένους τρόπους αναπαράστασης γλωσσών (ασχέτως του αν οι ίδιες οι γλώσσες είναι πεπερασμένες ή άπειρες), όμως όλοι οδηγούν σε μία συμβολοσειρά ως τρόπο αναπαράστασης μίας γλώσσας. Όμως, δεδομένου ενός αλφαβήτου αναπαράστασης Σ, υπάρχουν μετρήσιμα άπειρες συμβολοσειρές αναπαράστασης (Συμπέρασμα 1) και μη μετρήσιμα άπειρες γλώσσες (Συμπέρασμα 2). Επομένως, αφού υπάρχουν περισσότερες γλώσσες απ' ότι αναπαραστάσεις, αναπόφευκτα θα υπάρχουν πάντα γλώσσες που δεν μπορούμε να αναπαραστήσουμε με πεπερασμένο τρόπο.
Υπάρχουν δύο ισοδύναμοι τρόποι περιγραφής μίας γλώσσας: είτε μέσω ενός παραγωγού γλώσσας, ενός εκφραστικού μηχανισμού που περιγράφει τις έγκυρες συμβολοσειρές της συγκεκριμένης γλώσσας, είτε μέσω ενός αναγνώστη γλώσσας, ενός μαθηματικού μοντέλου-μηχανής που αποδέχεται συμβολοσειρές της συγκεκριμένης γλώσσας (τερματίζοντας θετικά αν η είσοδος του είναι συμβολοσειρά που ανήκει στη γλώσσα). Υπάρχουν διάφορες κλάσεις παραγωγών και των αντίστοιχων αναγνωστών, με την κάθε κλάση να καλύπτει ένα υπερσύνολο των γλωσσών που καλύπτει η προηγούμενη. Κατηγοριοποιούνται με την ιεραρχία [[Νόαμ Τσόμσκι|Τσόμσκι]], από τις πιο περιορισμένες ως τις πιο ευρείες:
[[Κατηγορία:Θεωρία υπολογισμού]]▼
Παραγωγοί | Αναγνώστες
------------------------------------------------------------------
1) Κανονικές Εκφράσεις | Πεπερασμένα Αυτόματα
2)Γραμματικές Χωρίς Συμφραζόμενα| Αυτόματα Στοίβας
3) Γραμματικές Με Συμφραζόμενα |Γραμμικά Περιορισμένες Μηχανές Turing
4)Γραμματικές Χωρίς Περιορισμούς| Μηχανές Turing
Ένα αυτόματο αποτελείται από ένα σύνολο καταστάσεων στις οποίες εισέρχεται ανάλογα με το σε ποια κατάσταση βρίσκεται ήδη και ποιο σύμβολο διάβασε τελευταία από τη συμβολοσειρά εισόδου.
Κάποιες από αυτές τις καταστάσεις είναι τελικές, δηλαδή αν η είσοδος εξαντληθεί όσο το αυτόματο είναι σε κάποια από αυτές η συμβολοσειρά είναι αποδεκτή. Υπάρχει ένας πίνακας μεταβάσεων που καθορίζει το σε ποια κατάσταση θα εισέλθει για κάθε περίπτωση.
Μία γλώσσα η οποία γίνεται αποδεκτή από κάποια Μηχανή Turing, δηλαδή η τελευταία είναι βέβαιο ότι τερματίζει μόνο όταν δέχεται ως είσοδο συμβολοσειρά που ανήκει στη γλώσσα (διαφορετικά μπορεί να μπει σε ατέρμονα βρόχο), ονομάζεται MT-αποδεκτή. Μία γλώσσα η οποία αποφασίζεται από κάποια Μηχανή Turing, δηλαδή η τελευταία τερματίζει για κάθε είσοδο και δίνει θετικό αποτέλεσμα αν η συμβολοσειρά ανήκει στη γλώσσα και αρνητικό αν δεν ανήκει, ονομάζεται ΜΤ-αποφασίσιμη. Επίσης η Μηχανή Turing μπορεί να γράφει σύμβολα στην ταινία εισόδου της (σε αντίθεση με τα αυτόματα) οπότε μπορεί να υπολογίζει και συναρτήσεις -δεχόμενη μία συμβολοσειρά εισόδου και παράγοντας την αντίστοιχη συμβολοσειρά εξόδου.
Τόσο στα αυτόματα όσο και στις Μηχανές Turing υπάρχει μία παραλλαγή τους που διαθέτει ένα πανίσχυρο αλλά αντιρεαλιστικό μαθηματικό χαρακτηριστικό: το μη ντετερμινισμό, τη δυνατότητα δηλαδή σε κάθε βήμα της λειτουργίας τους να μαντεύουν το σωστή διαδρομή που πρέπει να ακολουθήσουν στη συνέχεια από ένα πλήθος δυνατών διαδρομών. Τα μη ντετερμινιστικά αυτόματα συνήθως έχουν εκθετικά λιγότερες καταστάσεις από τα ρεαλιστικά αντίστοιχα ντετερμινιστικά, ενώ οι μη ντετερμινιστικές Μηχανές Turing ολοκληρώνουν τη λειτουργία τους σε εκθετικά λιγότερο χρόνο από τις αντίστοιχες ρεαλιστικές ντετερμινιστικές. Ώστόσο κάθε μη ντετερμινστικό πεπερασμένο αυτόματο μπορεί να μετασχηματιστεί σε ένα ισοδύναμο ντετερμινιστικό που αναγνωρίζει την ίδια γλώσσα (έστω και με πολύ περισσότερες καταστάσεις), καθώς και κάθε μη ντετερμινιστική Μηχανή Turing μπορεί να μετασχηματιστεί σε μία ισοδύναμη ντετερμινιστική (έστω και με πολύ μεγαλύτερη χρονική πολυπλοκότητα). Αυτή η ισοδυναμία δεν ισχύει στα αυτόματα στοίβας, αφού υπάρχουν γλώσσες χωρίς συμφραζόμενα που γίνονται αποδεκτές μόνο από μη ντετερμινιστικά αυτόματα στοίβας για τα οποία δεν υπάρχουν αντίστοιχα ντετερμινιστικά. Ειδικά για τις Μηχανές Turing έχουν προταθεί και διάφορες άλλες παραλλαγές (πιο ρεαλιστικές, όπως π.χ. με ταινία διπλής κατεύθυνσης ή πολλαπλές κεφαλές ανάγνωσης συμβόλων) οι οποίες όμως έχει αποδειχθεί ότι επίσης είναι ισοδύναμες με την πρότυπη ντετερμινιστική Μηχανή Turing και μάλιστα με την ίδια χρονική πολυπλοκότητα.
== Υπολογισιμότητα και πολυπλοκότητα ==
Παγκόσμια Μηχανή Turing ονομάζεται μία Μηχανή Turing που δέχεται ως είσοδο κατάλληλα κωδικοποιημένες συμβολοσειρές που συμβολίζουν άλλες Μηχανές Turing (Μ) και μία είσοδο γι' αυτές (w) και προσομοιώνει τη λειτουργία της Μ με είσοδο w. Με αυτόν τον τρόπο κωδικοποίησης ένα οποιοδήποτε υπολογιστικό πρόβλημα μπορεί να εκφραστεί ως ένα σύνολο συμβολοσειρών, δηλαδή μία γλώσσα, και να επιλυθεί από μία κατάλληλη Μηχανή Turing που αποφασίζει αυτήν τη γλώσσα -δηλαδή τερματίζει με βεβαιότητα για όλες τις εισόδους της. Σύμφωνα λοιπόν με τη Θέση Church-Turing η ντετερμινιστική Μηχανή Turing που αποφασίζει μία γλώσσα είναι το έσχατο και πιο ευρύ υπολογιστικό μοντέλο -μία αυστηρή μαθηματική περιγραφή της άτυπης έννοιας του αλγορίθμου! Αν για ένα υπολογιστικό πρόβλημα δεν μπορεί να βρεθεί μία Μηχανή Turing που να αποφασίζει την αντίστοιχη γλώσσα, τότε το πρόβλημα αυτό είναι μη επιλύσιμο -δεν μπορεί δηλαδή να υπάρξει αλγόριθμος που το επιλύει. Ένα διάσημο μη επιλύσιμο πρόβλημα είναι το πρόβλημα του τερματισμού (η εύρεση μίας Μηχανής Turing που αποφασίζει αν μία άλλη Μηχανή Turing θα τερματίσει με συγκεκριμένη είσοδο ή θα πέσει σε ατέρμονα βρόχο), το οποίο χρησιμεύει ώστε να ανάγονται άλλα προβλήματα σε αυτό και να αποδεικνύεται έτσι ότι είναι μη επιλύσιμα. Η Μηχανή Turing είναι το πιο ισχυρό μοντέλου υπολογισμού γιατί διαθέτει άπειρη μνήμη (την ταινία εισόδου / εξόδου), ενώ τα πεπερασμένα αυτόματα και τα αυτόματα στοίβας έχουν σοβαρούς περιορισμούς μνήμης (στα πρώτα η μνήμη τους είναι κωδικοποιημένη στις καταστάσεις τους ενώ τα δεύτερα έχουν επιπλέον και μια στοίβα).
Παρόλο που κάποια προβλήματα είναι επιλύσιμα, δεν έχει βρεθεί μέχρι στιγμής αλγόριθμος που να τα επιλύει σε λογικά χρονικά όρια -δηλαδή με πολυωνυμική και όχι εκθετική χρονική πολυπλοκότητα. Σε αυτό το σημείο συνεισφέρει η Θεωρία Πολυπλοκότητας από τη Σχεδίαση και Ανάλυση Αλγορίθμων:
P ονομάζεται το σύνολο των γλωσσών που αναπαριστούν υπολογιστικά προβλήματα για τα οποία είναι γνωστή ντετερμινιστική Μηχανή Turing που τα επιλύει σε πολυωνυμικό χρόνο. NP ονομάζεται το σύνολο των γλωσσών που αναπαριστούν υπολογιστικά προβλήματα για τα οποία είναι γνωστή μη ντετερμινιστική Μηχανή Turing που τα επιλύει σε πολυωνυμικό χρόνο αλλά όχι ντετερμινιστική (οι ισοδύναμες ντετερμινιστικές Μηχανές Turing έχουν αυξημένη εκθετική πολυπλοκότητα). E ονομάζεται το σύνολο των γλωσσών που αναπαριστούν υπολογιστικά προβλήματα για τα οποία είναι γνωστή μη/ντετερμινιστική Μηχανή Turing που τα επιλύει σε εκθετικό χρόνο. Αυτή τη στιγμή γνωρίζουμε ότι το P είναι υποσύνολο του NP και ότι το NP είναι υποσύνολο του Ε. Ωστόσο δε γνωρίζουμε κατά πόσο αυτές οι σχέσεις είναι γνήσιου υποσυνόλου, αν και υποψιαζόμαστε ότι αυτό ισχύει. Αν αποδειχτεί ότι το P δεν είναι γνήσιο υποσύνολο του NP τότε σημαίνει ότι υπάρχουν ντετερμινιστικές Μηχανές Turing που επιλύουν όλα τα προβλήματα του NP σε πολυωνυμικό χρόνο και απλά δεν έχουν επινοηθεί μέχρι στιγμής -όμως κανείς αυτό δεν το θεωρεί πιθανό και κατά πάσα πιθανότητα η εκθετική πολυπλοκότητα είναι εγγενής σε αυτά τα προβλήματα.
Τα προβλήματα του NP που δε φαίνεται να ανήκουν στο P έχουν την ιδιότητα να ανάγονται όλα σε ένα μικρό σύνολο βασικών και καλά μελετημένων προβλημάτων. Αυτή η ιδιότητα ονομάζεται πληρότητα και αυτά τα προβλήματα ονομάζονται NP-πλήρη.Έχει αποδειχθεί ότι αν ανακαλυφθεί κάποτε Μηχανή Turing που να επιλύει κάποιο από αυτά ντετερμινιστικά σε πολυωνυμικό χρόνο (οπότε αυτό θα ανήκει στο P), τότε όλα τα NP-πλήρη προβλήματα θα ανήκουν στο P. Όπως ειπώθηκε πριν κανείς δεν το θεωρεί αυτό πιθανό.
== Βιβλιογραφία ==
''Στοιχεία Θεωρία Υπολογισμού'', Harry Lewis και Χρήστος Παπαδημητρίου, Εκδόσεις Κριτική
▲[[Κατηγορία:Επιστήμη υπολογιστών|Θεωρία υπολογισμού]]
[[ar:نظرية التحسيب]]
| |||