Μοντέλο υπολογισμού
From Wikipedia, the free encyclopedia
Στη θεωρία υπολογισιμότητας και στη θεωρία υπολογιστικής πολυπλοκότητας, ένα μοντέλο υπολογισμού είναι ο ορισμός του συνόλου των επιτρεπόμενων λειτουργιών που χρησιμοποιούνται στον υπολογισμό και τις αντίστοιχες δαπάνες. Χρησιμοποιείται για τη μέτρηση της πολυπλοκότητας ενός αλγορίθμου σε χρόνο εκτέλεσης ή χώρο μνήμης: αναλαμβάνοντας ένα συγκεκριμένο υπολογιστικό μοντέλο, είναι δυνατόν να αναλυθούν οι υπολογιστικοί πόροι που απαιτούνται ή για να συζητηθούν οι περιορισμοί των αλγορίθμων ή υπολογιστές.
Μερικά παραδείγματα από τα μοντέλα περιλαμβάνουν:
- Μηχανές Turing
- Μηχανές πεπερασμένων καταστάσεων
- Αναδρομικές συναρτήσεις
- Λογισμός Λάμδα
- Συνδιαστική λογική
- Κυψελοειδές αυτόματο
- Αφηρημένα συστήματα
Στο πεδίο του χρόνου εκτέλεσης της ανάλυσης των αλγορίθμων, είναι κοινό να καθορίζεται ένα υπολογιστικό μοντέλο όσον αφορά τις πρωτόγονες πράξεις που επιτρέπονται οι οποίες έχουν το κόστος ανά μονάδα, ή απλά μονάδα κόστους εργασιών. Ένα συνήθως χρησιμοποιημένο παράδειγμα είναι το τυχαίο μηχάνημα πρόσβασης, το οποίο έχει κόστος μονάδας για πρόσβαση ανάγνωσης και εγγραφής σε όλα τα κύτταρα μνήμης. Σε αυτό το πλαίσιο, διαφέρει από την παραπάνω μοντελοποιημένη μηχανή Turing.
Στο μοντέλο με γνώμονα μηχανικής, το υπολογιστικό μοντέλο εξηγεί το πώς η συμπεριφορά του συστήματος είναι το αποτέλεσμα της συμπεριφοράς του καθενός από τα συστατικά του.
Ένα βασικό σημείο που συχνά παραβλέπεται είναι ότι δίνονται συχνά δημοσιευμένα κατώτερα όρια για τα προβλήματα για ένα υπολογιστικό μοντέλο το οποίο είναι πιο περιορισμένο από το σύνολο των λειτουργιών που θα μπορούσε κανείς να χρησιμοποιήσει στην πράξη και ως εκ τούτου μπορεί να υπάρχουν αλγόριθμοι που είναι πιο γρήγοροι από ό,τι κανείς θα νόμιζε ότι είναι δυνατόν.[1]
Υπάρχουν πολλά μοντέλα υπολογισμού, που διαφέρουν ως προς το σύνολο των παραδεκτών επιχειρήσεων και τους υπολογισμούς κόστους. Εμπίπτουν στις ακόλουθες γενικές κατηγορίες: αφηρημένη μηχανή και μοντέλα ισοδύναμα με αυτό (π.χ. ο λογισμός Λάμδα είναι ισοδύναμη με τη μηχανή Turing), που χρησιμοποιείται στις αποδείξεις υπολογισιμότητας και άνω φράγματα στην υπολογιστική πολυπλοκότητα των αλγορίθμων, και μοντέλα δέντρων απόφασης, που χρησιμοποιούνται στις αποδείξεις των κάτω ορίων στην υπολογιστική πολυπλοκότητα των αλγοριθμικών προβλημάτων.
- Στοίβα μηχανής (0-τελεστή μηχανή)
- Συσσωρευτής μηχανής (1-τελεστή μηχανή)
- Μηχανές εγγραφών (2,3,... τελεστή μηχανή)
- Τυχαίο μηχάνημα πρόσβασης
- Κύτταρα για τον έλεγχο του μοντέλου
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
