2.1.1 Η έννοια Πρόβλημα

Με τον όρο Πρόβλημα προσδιορίζεται μια κατάσταση η οποία χρειάζεται να αντιμετωπιστεί και απαιτεί ΑνοικτάΕπιλύσιμαΜη επιλύσιμαάθροισμααναλυτικήςδιατυπωθείείσοδοενοποίησηςεπίλυσηλύσημη υπολογιστικάπροφανήςσυντομότερης διαδρομήςταξινόμησηυπολογιστήφυσικής γλώσσας η οποία δεν είναι γνωστή, ούτε ΑνοικτάΕπιλύσιμαΜη επιλύσιμαάθροισμααναλυτικήςδιατυπωθείείσοδοενοποίησηςεπίλυσηλύσημη υπολογιστικάπροφανήςσυντομότερης διαδρομήςταξινόμησηυπολογιστήφυσικής γλώσσας.

Η διατύπωση ενός προβλήματος και η αντιμετώπισή του, αποτελούν ζητήματα που απαιτούν ικανότητες ορθολογικής, ΑνοικτάΕπιλύσιμαΜη επιλύσιμαάθροισμααναλυτικήςδιατυπωθείείσοδοενοποίησηςεπίλυσηλύσημη υπολογιστικάπροφανήςσυντομότερης διαδρομήςταξινόμησηυπολογιστήφυσικής γλώσσας και συνθετικής σκέψης, αλλά και ορθό χειρισμό της ΑνοικτάΕπιλύσιμαΜη επιλύσιμαάθροισμααναλυτικήςδιατυπωθείείσοδοενοποίησηςεπίλυσηλύσημη υπολογιστικάπροφανήςσυντομότερης διαδρομήςταξινόμησηυπολογιστήφυσικής γλώσσας.

2.1.2 Κατηγορίες Προβλημάτων

Τα προβλήματα ανάλογα με τη δυνατότητα επίλυσης διακρίνονται σε τρεις κατηγορίες:

α) ΑνοικτάΕπιλύσιμαΜη επιλύσιμαάθροισμααναλυτικήςδιατυπωθείείσοδοενοποίησηςεπίλυσηλύσημη υπολογιστικάπροφανήςσυντομότερης διαδρομήςταξινόμησηυπολογιστήφυσικής γλώσσας είναι εκείνα τα προβλήματα για τα οποία η λύση έχει βρεθεί και έχει διατυπωθεί.
Π.χ. η αποψίλωση μιας έκτασης γης (ο καθαρισμός δηλαδή ενός χωραφιού από κάθε είδους βλάστηση), η επίλυση της δευτεροβάθμιας εξίσωσης κ.ά.

β) ΑνοικτάΕπιλύσιμαΜη επιλύσιμαάθροισμααναλυτικήςδιατυπωθείείσοδοενοποίησηςεπίλυσηλύσημη υπολογιστικάπροφανήςσυντομότερης διαδρομήςταξινόμησηυπολογιστήφυσικής γλώσσας χαρακτηρίζονται εκείνα τα προβλήματα για τα οποία έχει αποδειχτεί, ότι δεν επιδέχονται λύση.
Π.χ. το πρόβλημα του τετραγωνισμού του κύκλου με κανόνα και διαβήτη.

γ) ΑνοικτάΕπιλύσιμαΜη επιλύσιμαάθροισμααναλυτικήςδιατυπωθείείσοδοενοποίησηςεπίλυσηλύσημη υπολογιστικάπροφανήςσυντομότερης διαδρομήςταξινόμησηυπολογιστήφυσικής γλώσσας ονομάζονται τα προβλήματα για τα οποία η λύση τους δεν έχει ακόμα βρεθεί, ενώ ταυτόχρονα δεν έχει αποδειχτεί, ότι δεν επιδέχονται λύση.
Π.χ. 1: το πρόβλημα της ΑνοικτάΕπιλύσιμαΜη επιλύσιμαάθροισμααναλυτικήςδιατυπωθείείσοδοενοποίησηςεπίλυσηλύσημη υπολογιστικάπροφανήςσυντομότερης διαδρομήςταξινόμησηυπολογιστήφυσικής γλώσσας των τεσσάρων πεδίων δυνάμεων (βαρυτικού, ηλεκτρομαγνητικού, ασθενούς πυρηνικού και ισχυρού πυρηνικού),
Π.χ. 2: η εικασία του Γκόλντμπαχ (Goldbach) ότι κάθε άρτιος μπορεί να γραφτεί ως ΑνοικτάΕπιλύσιμαΜη επιλύσιμαάθροισμααναλυτικήςδιατυπωθείείσοδοενοποίησηςεπίλυσηλύσημη υπολογιστικάπροφανήςσυντομότερης διαδρομήςταξινόμησηυπολογιστήφυσικής γλώσσας δύο πρώτων αριθμών.

2.1.3 Υπολογιστικά Προβλήματα

Οποιοδήποτε πρόβλημα μπορεί να λυθεί και μέσω του υπολογιστή, χαρακτηρίζεται υπολογιστικό πρόβλημα.

Για να λυθεί ένα πρόβλημα με τη βοήθεια του υπολογιστή, χρειάζεται να ΑνοικτάΕπιλύσιμαΜη επιλύσιμαάθροισμααναλυτικήςδιατυπωθείείσοδοενοποίησηςεπίλυσηλύσημη υπολογιστικάπροφανήςσυντομότερης διαδρομήςταξινόμησηυπολογιστήφυσικής γλώσσας το αντίστοιχο υπολογιστικό πρόβλημα και στη συνέχεια να υλοποιηθεί η επίλυσή του μέσω του ΑνοικτάΕπιλύσιμαΜη επιλύσιμαάθροισμααναλυτικήςδιατυπωθείείσοδοενοποίησηςεπίλυσηλύσημη υπολογιστικάπροφανήςσυντομότερης διαδρομήςταξινόμησηυπολογιστήφυσικής γλώσσας.
Παραδείγματα υπολογιστικών προβλημάτων είναι:
α) Η ΑνοικτάΕπιλύσιμαΜη επιλύσιμαάθροισμααναλυτικήςδιατυπωθείείσοδοενοποίησηςεπίλυσηλύσημη υπολογιστικάπροφανήςσυντομότερης διαδρομήςταξινόμησηυπολογιστήφυσικής γλώσσας της δευτεροβάθμιας εξίσωσης.
β) Η ΑνοικτάΕπιλύσιμαΜη επιλύσιμαάθροισμααναλυτικήςδιατυπωθείείσοδοενοποίησηςεπίλυσηλύσημη υπολογιστικάπροφανήςσυντομότερης διαδρομήςταξινόμησηυπολογιστήφυσικής γλώσσας των μαθητών σε αλφαβητική σειρά.
γ) Η αναζήτηση και ο υπολογισμός της χιλιομετρικά ΑνοικτάΕπιλύσιμαΜη επιλύσιμαάθροισμααναλυτικήςδιατυπωθείείσοδοενοποίησηςεπίλυσηλύσημη υπολογιστικάπροφανήςσυντομότερης διαδρομήςταξινόμησηυπολογιστήφυσικής γλώσσας που θα κάνει ένας ταχυδρόμος για να επισκεφθεί δέκα χωριά και να επιστρέψει στο χωριό από όπου ξεκίνησε περνώντας μόνο μία φορά από κάθε χωριό, με βάση έναν δεδομένο χάρτη των χωριών και των δρόμων που συνδέουν τα χωριά.
δ) Η εύρεση λέξης που να ξεκινά από ένα γράμμα και να τελειώνει σε ένα άλλο γράμμα.

Τα ΑνοικτάΕπιλύσιμαΜη επιλύσιμαάθροισμααναλυτικήςδιατυπωθείείσοδοενοποίησηςεπίλυσηλύσημη υπολογιστικάπροφανήςσυντομότερης διαδρομήςταξινόμησηυπολογιστήφυσικής γλώσσας προβλήματα δεν μπορούν να λυθούν από έναν υπολογιστή ή από άλλα μηχανικά μέσα.
Για παράδειγμα, καμία μηχανή δεν μπορεί γενικά να αποφανθεί αν ένα δεδομένο πρόγραμμα θα επιστρέψει απάντηση για μια δεδομένη ΑνοικτάΕπιλύσιμαΜη επιλύσιμαάθροισμααναλυτικήςδιατυπωθείείσοδοενοποίησηςεπίλυσηλύσημη υπολογιστικάπροφανήςσυντομότερης διαδρομήςταξινόμησηυπολογιστήφυσικής γλώσσας, ή αν θα εκτελείται για πάντα.