Θεωρία υπολογισμού: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ interwiki additions |
μΧωρίς σύνοψη επεξεργασίας |
||
Γραμμή 1:
Η '''θεωρία υπολογισμού''' είναι ο κλάδος της [[επιστήμη υπολογιστών|επιστήμης υπολογιστών]] που πραγματεύεται το εάν και το πόσο αποδοτικά μπορεί να λυθεί κάποιο πρόβλημα σε ένα [[υπολογιστικό μοντέλο]], με χρήση ενός [[αλγόριθμος|αλγορίθμου]]. Ο τομέας διαιρείται σε δύο κύριους κλάδους:
Για να πραγματοποιήσουν μια εξονυχιστική μελέτη των υπολογισμών, οι επιστήμονες υπολογιστών αντιμετωπίζουν τον [[υπολογιστής|υπολογιστή]] ως μια αφηρημένη [[μαθηματικά|μαθηματική]] έννοια, το ''μοντέλο υπολογισμού''. Υπάρχουν διάφορες διατυπώσεις που χρησιμοποιούνται, αλλά η πιο συχνή είναι η [[μηχανή Τούρινγκ]]. Μπορεί κανείς να θεωρήσει τη μηχανή Τούρινγκ σαν έναν [[προσωπικός υπολογιστής|προσωπικό υπολογιστή]] με άπειρη [[μνήμη]], αν και η μνήμη αυτή είναι προσβάσιμη μόνο
Η θεωρία υπολογισμού για να φτάσει στα
== Τυπικές γραμματικές ==
{{Κύριο|Τυπική γραμματική}}
Στην [[επιστήμη υπολογιστών]] μια τυπική γραμματική (formal grammar) είναι μια [[αφηρημένη δομή]] που περιγράφει μια [[τυπική γλώσσα]] επακριβώς, δηλαδή είναι ένα σύνολο κανόνων που απεικονίζουν μαθηματικώς το [[σύνολο|σύνολο]], (συνήθως [[σύνολο|απειροσύνολο]]), των πεπερασμένου μήκους [[Στοιχειοσειρά|στοιχειοσειρών]] / συμβολοσειρών που σχηματίζονται με διακριτά στοιχεία / σύμβολα (π.χ. γράμματα), τα οποία ανήκουν σε ένα σύνολο, συνήθως πεπερασμένο, που το λέμε ''αλφάβητο''. Οι τυπικές γραμματικές ονομάστηκαν έτσι κατ’ αναλογία των [[γραμματική|γραμματικών]] των γλωσσών που μιλούν οι άνθρωποι, αλλά τα
Μια [[γενετική γραμματική]], η οποία θα μπορούσε να ονομάζεται ''γεννητική'' ή ''παραγωγική γραμματική'', είναι ένα σύνολο κανόνων με το οποίο όλες οι συμβολοσειρές που μπορούν να υπάρξουν σε μια γλώσσα μπορούν να παραχθούν με διαδοχικά [[Στοιχειοσειρά#Συναλύσωση|επιθέματα]] ξεκινώντας από ένα προκαθορισμένο ''αρχικό σύμβολο δημιουργίας στοιχειοσειράς''. Μια γενετική γραμματική ουσιαστικά είναι η τυπική μορφή του [[αλγόριθμος|αλγορίθμου]] παραγωγής στοιχειοσειρών που ανήκουν
:Συνοπτικά για την γενετική γραμματική :
:* λειτουργεί ως δημιουργός στοιχειοσειρών της γλώσσας, δηλαδή ''γράφει
:* η πορεία είναι από
:* εφαρμόζεται παραγωγική (top-down) προσέγγιση, από το γενικό προς το μερικό.
Μια [[αναλυτική γραμματική]], αντιθέτως, είναι ένα σύνολο κανόνων που υποθέτουν ότι μία αυθαίρετη στοιχειοσειρά δίνεται προς επεξεργασία και με διαδοχικά βήματα ανάλυσης προκύπτει ως αποτέλεσμα η τιμή μιας [[μεταβλητή (υπολογιστές)#Λογικές μεταβλητές|λογικής μεταβλητής]]:
* ΑΛΗΘΗΣ, αν η στοιχειοσειρά ανήκει
* ΨΕΥΔΗΣ, αν η στοιχειοσειρά δεν ανήκει
:Συνοπτικά για την αναλυτική γραμματική :
:* σαρώνει
:* η πορεία είναι από τις λέξεις της γλώσσας προς
:* εφαρμόζεται επαγωγική (bottom-up) προσέγγιση, από το μερικό προς το γενικό.
== Βασικές αρχές ==
''[[Αστέρι Κλέινι]]'' ή ''κλειστότητα Κλέινι'' (Kleene Star) ενός αλφαβήτου Σ ονομάζουμε το σύνολο Σ* όλων των δυνατών [[συμβολοσειρά|συμβολοσειρών]] που προκύπτουν από αυτό το αλφάβητο. Πρόκειται για ένα μετρήσιμο [[σύνολο|απειροσύνολο]] (''Συμπέρασμα 1''). Γλώσσα ονομάζουμε ένα [[υποσύνολο]] του Σ* για δεδομένο αλφάβητο Σ. Το σύνολο όλων των γλωσσών που προκύπτουν από ένα αλφάβητο Σ είναι το [[δυναμοσύνολο]] (το σύνολο όλων των δυνατών υποσυνόλων) του Σ* και είναι μη μετρήσιμο απειροσύνολο (''Συμπέρασμα 2''). Μπορούμε να καταλήξουμε σε διάφορους πεπερασμένους τρόπους αναπαράστασης γλωσσών (ασχέτως του αν οι ίδιες οι γλώσσες είναι πεπερασμένες ή άπειρες), όμως όλοι οδηγούν σε μία συμβολοσειρά ως τρόπο αναπαράστασης μίας γλώσσας. Όμως, δεδομένου ενός αλφαβήτου αναπαράστασης Σ, υπάρχουν μετρήσιμα άπειρες συμβολοσειρές αναπαράστασης (Συμπέρασμα 1) και μη μετρήσιμα άπειρες γλώσσες (Συμπέρασμα 2). Επομένως, αφού υπάρχουν περισσότερες γλώσσες απ' ότι αναπαραστάσεις, αναπόφευκτα θα υπάρχουν πάντα γλώσσες που δεν μπορούμε να αναπαραστήσουμε με πεπερασμένο τρόπο.
Υπάρχουν δύο ισοδύναμοι τρόποι περιγραφής μίας γλώσσας: είτε μέσω ενός παραγωγού γλώσσας, ενός εκφραστικού μηχανισμού που περιγράφει τις έγκυρες συμβολοσειρές της συγκεκριμένης γλώσσας, είτε μέσω ενός αναγνώστη γλώσσας, ενός μαθηματικού μοντέλου-μηχανής που αποδέχεται συμβολοσειρές της συγκεκριμένης γλώσσας (τερματίζοντας θετικά αν η
:{| border="1" cellpadding="3" cellspacing="0"
Γραμμή 38:
|2||Γραμματικές χωρίς συμφραζόμενα || Αυτόματα στοίβας
|-
|3|| Γραμματικές με συμφραζόμενα ||
|-
|4|| Γενικές γραμματικές || Μηχανές Τούρινγκ
Γραμμή 46:
Κάποιες από αυτές τις καταστάσεις είναι τελικές, δηλαδή αν η είσοδος εξαντληθεί όσο το αυτόματο είναι σε κάποια από αυτές η συμβολοσειρά είναι αποδεκτή. Υπάρχει ένας πίνακας μεταβάσεων που καθορίζει το σε ποια κατάσταση θα εισέλθει για κάθε περίπτωση.
Μία γλώσσα η οποία ''γίνεται αποδεκτή'' από κάποια Μηχανή Τούρινγκ, δηλαδή η τελευταία είναι βέβαιο ότι τερματίζει μόνο όταν δέχεται ως είσοδο συμβολοσειρά που ανήκει στη γλώσσα (διαφορετικά μπορεί να μπει σε ατέρμονα βρόχο), ονομάζεται ''MT-αποδεκτή''. Μία γλώσσα η οποία ''αποφασίζεται'' από κάποια Μηχανή Τούρινγκ, δηλαδή η τελευταία τερματίζει για κάθε είσοδο και δίνει θετικό αποτέλεσμα αν η συμβολοσειρά ανήκει στη γλώσσα και αρνητικό αν δεν ανήκει, ονομάζεται ''ΜΤ-αποφασίσιμη''. Επίσης η Μηχανή Τούρινγκ μπορεί να γράφει σύμβολα στην ταινία εισόδου της (σε αντίθεση με τα αυτόματα) οπότε μπορεί να υπολογίζει και [[συνάρτηση|συναρτήσεις]],
Τόσο στα αυτόματα όσο και στις Μηχανές Τούρινγκ υπάρχει μία παραλλαγή τους που διαθέτει ένα πανίσχυρο αλλά αντιρεαλιστικό μαθηματικό χαρακτηριστικό:
== Υπολογισιμότητα και πολυπλοκότητα ==
Παγκόσμια Μηχανή Τούρινγκ ονομάζεται μία Μηχανή Τούρινγκ που δέχεται ως είσοδο κατάλληλα κωδικοποιημένες συμβολοσειρές που συμβολίζουν άλλες Μηχανές Τούρινγκ (Μ) και μία είσοδο γι' αυτές (w) και προσομοιώνει τη λειτουργία της Μ με είσοδο w. Με αυτόν τον τρόπο κωδικοποίησης ένα οποιοδήποτε υπολογιστικό πρόβλημα μπορεί να εκφραστεί ως ένα σύνολο συμβολοσειρών, δηλαδή μία γλώσσα, και να επιλυθεί από μία κατάλληλη Μηχανή Τούρινγκ που αποφασίζει
Παρόλο που κάποια προβλήματα είναι επιλύσιμα, δεν έχει βρεθεί μέχρι στιγμής αλγόριθμος που να τα επιλύει σε λογικά χρονικά όρια·
Τα προβλήματα του NP που
Οι υπολογιστές [[αρχιτεκτονική φον Νόιμαν|φον Νόιμαν]] αλλά και άλλα μοντέλα υπολογισμού (π.χ. ορισμένα [[νευρωνικό δίκτυο|τεχνητά νευρωνικά δίκτυα]]) ισοδυναμούν μαθηματικώς με Παγκόσμιες Μηχανές Τούρινγκ και γι' αυτό μπορεί σε αυτά να εκτελεστεί, με κατάλληλη κωδικοποίηση, οποιοσδήποτε αλγόριθμος.
== Βιβλιογραφία ==
|