Αλγόριθμοι: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 36:
<tr><td><pre><nowiki>
Υπάρχουν όμως πολλά προβλήματα με πρακτική εφαρμογή που μπορούν να λυθούν - δηλαδή
να γραφούν τα αντίστοιχα προγράμματα - για τα οποία όμως οι απαιτήσεις σε χρόνο και
μνήμη είναι πρακτικά απαγορευτικές. Τελικά η μνήμη και ο χρόνος που απαιτούνται είναι
αυτά που έχουν πρακτική αξία. Έχουν γίνει, λοιπόν, το αντικείμενο θεωρητικής μελέτης
στο πεδίο της επιστήμης των υπολογιστών που ονομάζεται "υπολογιστική πολυπλοκότητα".
Ένας κλάδος αυτής της μελέτης είναι η διατύπωση μιας αυστηρής και αφηρημένης θεωρίας
της πολυπλοκότητας των υπολογιστέων συναρτήσεων. (Γιατί η επίλυση ενός προβλήματος
ισοδυναμεί με τον υπολογισμό μιας συνάρτησης που παράγει συγκεκριμένες εξόδους για συγκεκριμένες εισόδους). Διατυπώθηκαν έτσι αυστηρά και γενικά αξιώματα για τη μέτρηση
της πολυπλοκότητας, προσμετρώντας τη μνήμη (σε bits) και τον αριθμό των εντολών που
πρέπει να εκτελεστούν από ένα πρόγραμμα. Χρησιμοποιώντας αυτά τα αξιώματα, μπορεί κανείς
να αναδείξει την ύπαρξη τυχαίων πολύπλοκων προβλημάτων καθώς και προβλημάτων για τα
οποία δεν μπορεί να γραφτεί "καλό" πρόγραμμα.
| |||