Μοντέλο υπολογισμού
Στη θεωρία υπολογισιμότητας και στη θεωρία υπολογιστικής πολυπλοκότητας, ένα μοντέλο υπολογισμού είναι ο ορισμός του συνόλου των επιτρεπόμενων λειτουργιών που χρησιμοποιούνται στον υπολογισμό και τις αντίστοιχες δαπάνες. Χρησιμοποιείται για τη μέτρηση της πολυπλοκότητας ενός αλγορίθμου σε χρόνο εκτέλεσης ή χώρο μνήμης: αναλαμβάνοντας ένα συγκεκριμένο υπολογιστικό μοντέλο, είναι δυνατόν να αναλυθούν οι υπολογιστικοί πόροι που απαιτούνται ή για να συζητηθούν οι περιορισμοί των αλγορίθμων ή υπολογιστές.
Μοντέλα[Επεξεργασία | επεξεργασία κώδικα]
Μερικά παραδείγματα από τα μοντέλα περιλαμβάνουν:
- Μηχανές Turing
- Μηχανές πεπερασμένων καταστάσεων
- Αναδρομικές[1] συναρτήσεις
- Λογισμός Λάμδα
- Συνδιαστική λογική
- Κυψελοειδές αυτόματο
- Αφηρημένα συστήματα
Χρήσεις[Επεξεργασία | επεξεργασία κώδικα]
Στο πεδίο του χρόνου εκτέλεσης της ανάλυσης των αλγορίθμων, είναι κοινό να καθορίζεται ένα υπολογιστικό μοντέλο όσον αφορά τις πρωτόγονες πράξεις που επιτρέπονται οι οποίες έχουν το κόστος ανά μονάδα, ή απλά μονάδα κόστους εργασιών. Ένα συνήθως χρησιμοποιημένο παράδειγμα είναι το τυχαίο μηχάνημα πρόσβασης, το οποίο έχει κόστος μονάδας για πρόσβαση ανάγνωσης και εγγραφής σε όλα τα κύτταρα μνήμης. Σε αυτό το πλαίσιο, διαφέρει από την παραπάνω μοντελοποιημένη μηχανή Turing.
Στο μοντέλο με γνώμονα μηχανικής, το υπολογιστικό μοντέλο εξηγεί το πώς η συμπεριφορά του συστήματος είναι το αποτέλεσμα της συμπεριφοράς του καθενός από τα συστατικά του.
Ένα βασικό σημείο που συχνά παραβλέπεται είναι ότι δίνονται συχνά δημοσιευμένα κατώτερα όρια για τα προβλήματα για ένα υπολογιστικό μοντέλο το οποίο είναι πιο περιορισμένο από το σύνολο των λειτουργιών που θα μπορούσε κανείς να χρησιμοποιήσει στην πράξη και ως εκ τούτου μπορεί να υπάρχουν αλγόριθμοι που είναι πιο γρήγοροι από ό,τι κανείς θα νόμιζε ότι είναι δυνατόν.[1]
Κατηγορίες[Επεξεργασία | επεξεργασία κώδικα]
Υπάρχουν πολλά μοντέλα υπολογισμού, που διαφέρουν ως προς το σύνολο των παραδεκτών επιχειρήσεων και τους υπολογισμούς κόστους. Εμπίπτουν στις ακόλουθες γενικές κατηγορίες: αφηρημένη μηχανή και μοντέλα ισοδύναμα με αυτό (π.χ. ο λογισμός Λάμδα είναι ισοδύναμη με τη μηχανή Turing), που χρησιμοποιείται στις αποδείξεις υπολογισιμότητας και άνω φράγματα στην υπολογιστική πολυπλοκότητα των αλγορίθμων, και μοντέλα δέντρων απόφασης, που χρησιμοποιούνται στις αποδείξεις των κάτω ορίων στην υπολογιστική πολυπλοκότητα των αλγοριθμικών προβλημάτων.
Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]
- Στοίβα μηχανής (0-τελεστή μηχανή)
- Συσσωρευτής μηχανής (1-τελεστή μηχανή)
- Μηχανές εγγραφών (2,3,... τελεστή μηχανή)
- Τυχαίο μηχάνημα πρόσβασης
- Κύτταρα για τον έλεγχο του μοντέλου
Αναφορές[Επεξεργασία | επεξεργασία κώδικα]
- ↑ Παραδείγματα η τιμή της αφαίρεσης?, cstheory.stackexchange.com
Περαιτέρω ανάγνωση[Επεξεργασία | επεξεργασία κώδικα]
- Fernández, Maribel (2009). Models of Computation: An Introduction to Computability Theory. Undergraduate Topics in Computer Science. Springer. ISBN 978-1-84882-433-1.
- Savage, John E. (1998). Models Of Computation: Exploring the Power of Computing. Αρχειοθετήθηκε από το πρωτότυπο στις 12 Οκτωβρίου 2016. Ανακτήθηκε στις 25 Μαΐου 2016.
|
Αυτό το άρθρο "επιστήμη των υπολογιστών" είναι ένα στέλεχος. Μπορείτε να βοηθήσετε την Βικιπαίδεια από την επέκταση. |