Computational problem (original) (raw)
Στη θεωρητική πληροφορική, ένα υπολογιστικό πρόβλημα είναι ένα που αντιπροσωπεύει ένα σύνολο ερωτημάτων τα οποία ένας υπολογιστής είναι ικανός να λύσει. Για παράδειγμα, το πρόβλημα της παραγοντοποίησης: «Δοθέντος ενός θετικού ακεραίου n, να βρεθεί ένας μη τετριμμένος πρώτος παράγοντας του n.» Κατά σύμβαση αναπαριστούμε τόσο τα στιγμιότυπα όσο και τις λύσεις με δυαδικές συμβολοσειρές (binary strings), δηλαδή συμβολοσειρές με στοιχεία {0, 1}*. Για παράδειγμα, οι αριθμοί μπορούν να παρασταθούν με δυαδικές συμβολοσειρές χρησιμοποιώντας τη δυαδική κωδικοποίηση.
| Property | Value |
|---|---|
| dbo:abstract | Στη θεωρητική πληροφορική, ένα υπολογιστικό πρόβλημα είναι ένα που αντιπροσωπεύει ένα σύνολο ερωτημάτων τα οποία ένας υπολογιστής είναι ικανός να λύσει. Για παράδειγμα, το πρόβλημα της παραγοντοποίησης: «Δοθέντος ενός θετικού ακεραίου n, να βρεθεί ένας μη τετριμμένος πρώτος παράγοντας του n.» είναι ένα υπολογιστικό πρόβλημα. Τα υπολογιστικά προβλήματα αποτελούν ένα από τα βασικά αντικείμενα μελέτης στη θεωρητική πληροφορική. Ο τομέας των αλγορίθμων ερευνά μεθόδους αποδοτικής επίλυσης υπολογιστικών προβλημάτων. Ο συμπληρωματικός κλάδος της υπολογιστικής πολυπλοκότητας επιχειρεί να εξηγήσει το λόγο που κάποια υπολογιστικά προβλήματα είναι δυσεπίλυτα για τους υπολογιστές. Ένα υπολογιστικό πρόβλημα μπορεί να θεωρηθεί ως ένα άπειρο σύνολο στιγμιοτύπων, μαζί με μία λύση για κάθε στιγμιότυπο. Για παράδειγμα, στο πρόβλημα της παραγοντοποίησης που αναφέρθηκε παραπάνω, τα στιγμιότυπα είναι οι ακέραιοι n και οι λύσεις είναι οι πρώτοι αριθμοί p που περιγράφουν μη τετριμμένους πρώτους παράγοντες του κάθε n. Κατά σύμβαση αναπαριστούμε τόσο τα στιγμιότυπα όσο και τις λύσεις με δυαδικές συμβολοσειρές (binary strings), δηλαδή συμβολοσειρές με στοιχεία {0, 1}*. Για παράδειγμα, οι αριθμοί μπορούν να παρασταθούν με δυαδικές συμβολοσειρές χρησιμοποιώντας τη δυαδική κωδικοποίηση. (el) In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring "Given a positive integer n, find a nontrivial prime factor of n." is a computational problem. A computational problem can be viewed as a set of instances or cases together with a, possibly empty, set of solutions for every instance/case. For example, in the factoring problem, the instances are the integers n, and solutions are prime numbers p that are the nontrivial prime factors of n. Computational problems are one of the main objects of study in theoretical computer science. The field of computational complexity theory attempts to determine the amount of resources (computational complexity) solving a given problem will require and explain why some problems are intractable or undecidable. Computational problems belong to complexity classes that define broadly the resources (e.g. time, space/memory, energy, circuit depth) it takes to compute (solve) them with various abstract machines. For example, the complexity class P for classical machines, and BQP for quantum machines. It is typical of many problems to represent both instances and solutions by binary strings, namely elements of {0, 1}*. For example, numbers can be represented as binary strings using binary encoding. (en) En ciencia computacional teórica, un problema raro o problema subliminal es una relación entre un conjunto de puntos y comas y un conjunto de soluciones. Un problema abstracto permite establecer formalmente la relación deseada entre la dama de un algoritmo y su hombre. Una solución algorítmica a un problema abstracto consiste de un algoritmo que por cada instancia del problema calcula al menos una solución correspondiente –en caso de haberla– o expide un certificado de que no existe solución alguna. Un problema abstracto se convierte en un problema concreto cuando las instancias y soluciones están codificadas en forma de lenguajes formales. Los problemas abstractos suelen definirse en dos partes: en la primera se describe al conjunto de instancias y en la segunda se describe la solución esperada para cada instancia. Por ejemplo, el problema de ordenación de números enteros se suele definir como sigue: Instancia: Una sucesión finita de números enteros Solución: Una permutación de la sucesión de entrada tal que Aquí tanto el conjunto de instancias y el de soluciones es el mismo, pues se trata del conjunto de todas las sucesiones finitas de números enteros. La relación que hay entre ellos asigna a cada sucesión la única permutación tal que . Por ejemplo, tiene como solución a . Una solución algorítmica al problema de ordenamiento es el ordenamiento de burbuja porque este algoritmo produce una solución como salida cada vez que se le suministra una instancia como entrada. (es) Un problème algorithmique est, en informatique théorique, un objet mathématique qui représente une question ou un ensemble de questions auxquelles un ordinateur devrait être en mesure de répondre. Le plus souvent, ces problèmes sont de la forme : étant donné un objet (l'instance), effectuer une certaine action ou répondre à telle question. Par exemple, le problème de la factorisation est le problème suivant : étant donné un nombre entier, trouver un facteur premier de cet entier. On distingue en particulier deux types de problèmes : * les problèmes de décision, qui consistent à répondre oui ou non à une question (par exemple, cet entier est-il premier ?) ; * les problèmes d'évaluation ou de construction, qui consistent à produire un objet spécifié par l'énoncé du problème. Les problèmes algorithmiques jouent un rôle central en informatique théorique et forment un domaine à part entière, à côté de celui des algorithmes qui étudient les méthodes efficaces de résolution de problèmes décidables et de celui de l'analyse de la complexité des algorithmes qui cherche à comprendre les performances de ces algorithmes. (fr) Nell'informatica teorica, un problema computazionale o problema astratto è una relazione tra un insieme di istanze e un insieme di soluzioni. Un problema computazionale permette di stabilire formalmente la relazione desiderata tra l'entrata o input di un algoritmo e la sua uscita o output. Una soluzione algoritmica a un problema computazionale consiste in un algoritmo che per ogni istanza del problema calcola almeno una soluzione corrispondente – nel caso esista – o certifica che non esiste alcuna soluzione. Un problema astratto diventa un problema concreto quando le istanze e le soluzioni sono codificate in forma di linguaggi formali. I problemi computazionali sono soliti essere definiti in due parti: nella prima si descrive l'insieme di istanze e nella seconda si descrive la soluzione attesa per ogni istanza. Per esempio, il problema dell'ordinamento di numeri interi si definisce di solito come segue: Istanza: Una successione finita di numeri interi Soluzione: Una permutazione della successione in entrata tale che Qui tanto l'insieme delle istanze quanto quello delle soluzioni è lo stesso, poiché si tratta dell'insieme di tutte le successioni finite di numeri interi. La relazione che vi è tra di essi assegna a ogni successione l'unica permutazione tale che . Ad esempio, ha come soluzione . Una soluzione algoritmica al problema dell'ordinamento è quella dell'ordinamento a bolle, perché questo algoritmo produce una soluzione come uscita ogni volta che gli si somministra una istanza come entrata. (it) Na , um problema computacional é um objeto matemático que representa um coleção de questões que computadores talvez queiram resolver. Por exemplo, o problema da fatoração "Dado um inteiro positivo n, encontre um fator primo não-trivial de n." é um problema computacional. Problemas computacionais são um dos principais objetos de estudo na ciência da teoria da computação. O campo de algoritmos estuda métodos de solução eficiente de problemas computacionais. O campo complementar de complexidade computacional tenta explicar porquê certos problemas computacionais são intratáveis por computadores. Um problema computacional pode ser visto como uma coleção infinita de instâncias junto com uma solução para cada instância. Por exemplo, no problema da fatoração, as instâncias são os inteiros n, e as soluções são números primos p que descrevem fatores primos não-triviais de n. É convencional representar ambas instâncias e soluções por strings binárias, a saber elementos de {0, 1}*. Por exemplo, números podem ser representados como strings binárias usando-se codificação binária. (Para melhor leitura, identificamos números com suas codificações binárias nos exemplos abaixo.) (pt) Problem obliczeniowy, zadanie obliczeniowe – zadanie, które może być rozwiązane za pomocą komputera lub innej maszyny liczącej. Na opis problemu obliczeniowego składają się: zbiór danych wejściowych (ang. input) oraz warunki jakie ma spełniać wynik, czyli dane wyjściowe (ang. output). Bardziej formalnie, przez problem obliczeniowy możemy rozumieć funkcję, która przekształca zbiór danych wejściowych na zbiór danych wyjściowych. Pojęcie problemu obliczeniowego leży u podstaw informatyki rozumianej jako nauki zajmującej się przetwarzaniem informacji, gdyż praktycznie każde zadanie informatyczne można rozważać jako problem obliczeniowy. Metody rozwiązywania problemów obliczeniowych nazywamy algorytmami, a dziedzina nauki, która zajmuje się ich konstrukcją i badaniem, to teoria algorytmów. (pl) |
| dbo:wikiPageID | 4594672 (xsd:integer) |
| dbo:wikiPageLength | 7201 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1099779198 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cambridge_University_Press dbr:Algorithm dbr:Regular_expression dbr:Relation_(mathematics) dbr:Decision_problem dbr:Independent_set_(graph_theory) dbr:Interactive_proof_system dbr:Analysis_of_algorithms dbr:NP-hard dbr:The_Princeton_Companion_to_Mathematics dbr:Combinatorial_optimization dbr:Complexity_class dbr:Computational_complexity dbr:Computational_complexity_theory dbr:Function_problem dbr:Hardness_of_approximation dbr:P_(complexity) dbr:String_(computer_science) dbr:Theoretical_computer_science dbr:BQP dbr:Total_function dbr:Travelling_salesman_problem dbr:Lateral_computing dbr:Promise_problem dbr:Counting_problem_(complexity) dbc:Computational_problems dbc:Theoretical_computer_science dbr:Abstract_machine dbr:Factoring_problem dbr:Operations_research dbr:Optimization_problem dbr:Search_problem dbr:Set_(mathematics) dbr:Model_of_computation dbr:Undecidable_problem dbr:Transcomputational_problem dbr:Property_testing dbr:Maximum_independent_set_problem dbr:Primality_testing |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Efn dbt:Main dbt:No_footnotes dbt:Notelist dbt:Short_description |
| dct:subject | dbc:Computational_problems dbc:Theoretical_computer_science |
| gold:hypernym | dbr:Object |
| rdf:type | yago:WikicatComputationalProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 dbo:Planet yago:State100024720 |
| rdfs:comment | Στη θεωρητική πληροφορική, ένα υπολογιστικό πρόβλημα είναι ένα που αντιπροσωπεύει ένα σύνολο ερωτημάτων τα οποία ένας υπολογιστής είναι ικανός να λύσει. Για παράδειγμα, το πρόβλημα της παραγοντοποίησης: «Δοθέντος ενός θετικού ακεραίου n, να βρεθεί ένας μη τετριμμένος πρώτος παράγοντας του n.» Κατά σύμβαση αναπαριστούμε τόσο τα στιγμιότυπα όσο και τις λύσεις με δυαδικές συμβολοσειρές (binary strings), δηλαδή συμβολοσειρές με στοιχεία {0, 1}*. Για παράδειγμα, οι αριθμοί μπορούν να παρασταθούν με δυαδικές συμβολοσειρές χρησιμοποιώντας τη δυαδική κωδικοποίηση. (el) In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring "Given a positive integer n, find a nontrivial prime factor of n." is a computational problem. A computational problem can be viewed as a set of instances or cases together with a, possibly empty, set of solutions for every instance/case. For example, in the factoring problem, the instances are the integers n, and solutions are prime numbers p that are the nontrivial prime factors of n. (en) En ciencia computacional teórica, un problema raro o problema subliminal es una relación entre un conjunto de puntos y comas y un conjunto de soluciones. Un problema abstracto permite establecer formalmente la relación deseada entre la dama de un algoritmo y su hombre. Una solución algorítmica a un problema abstracto consiste de un algoritmo que por cada instancia del problema calcula al menos una solución correspondiente –en caso de haberla– o expide un certificado de que no existe solución alguna. Un problema abstracto se convierte en un problema concreto cuando las instancias y soluciones están codificadas en forma de lenguajes formales. (es) Un problème algorithmique est, en informatique théorique, un objet mathématique qui représente une question ou un ensemble de questions auxquelles un ordinateur devrait être en mesure de répondre. Le plus souvent, ces problèmes sont de la forme : étant donné un objet (l'instance), effectuer une certaine action ou répondre à telle question. Par exemple, le problème de la factorisation est le problème suivant : étant donné un nombre entier, trouver un facteur premier de cet entier. On distingue en particulier deux types de problèmes : (fr) Nell'informatica teorica, un problema computazionale o problema astratto è una relazione tra un insieme di istanze e un insieme di soluzioni. Un problema computazionale permette di stabilire formalmente la relazione desiderata tra l'entrata o input di un algoritmo e la sua uscita o output. Una soluzione algoritmica a un problema computazionale consiste in un algoritmo che per ogni istanza del problema calcola almeno una soluzione corrispondente – nel caso esista – o certifica che non esiste alcuna soluzione. Un problema astratto diventa un problema concreto quando le istanze e le soluzioni sono codificate in forma di linguaggi formali. (it) Problem obliczeniowy, zadanie obliczeniowe – zadanie, które może być rozwiązane za pomocą komputera lub innej maszyny liczącej. Na opis problemu obliczeniowego składają się: zbiór danych wejściowych (ang. input) oraz warunki jakie ma spełniać wynik, czyli dane wyjściowe (ang. output). Bardziej formalnie, przez problem obliczeniowy możemy rozumieć funkcję, która przekształca zbiór danych wejściowych na zbiór danych wyjściowych. Pojęcie problemu obliczeniowego leży u podstaw informatyki rozumianej jako nauki zajmującej się przetwarzaniem informacji, gdyż praktycznie każde zadanie informatyczne można rozważać jako problem obliczeniowy. (pl) Na , um problema computacional é um objeto matemático que representa um coleção de questões que computadores talvez queiram resolver. Por exemplo, o problema da fatoração "Dado um inteiro positivo n, encontre um fator primo não-trivial de n." é um problema computacional. Problemas computacionais são um dos principais objetos de estudo na ciência da teoria da computação. O campo de algoritmos estuda métodos de solução eficiente de problemas computacionais. O campo complementar de complexidade computacional tenta explicar porquê certos problemas computacionais são intratáveis por computadores. (pt) |
| rdfs:label | Υπολογιστικό πρόβλημα (el) Computational problem (en) Problema computacional (es) Problème algorithmique (fr) Problema computazionale (it) Problem obliczeniowy (pl) Problema computacional (pt) |
| owl:sameAs | freebase:Computational problem yago-res:Computational problem wikidata:Computational problem dbpedia-el:Computational problem dbpedia-es:Computational problem dbpedia-fa:Computational problem dbpedia-fr:Computational problem http://hi.dbpedia.org/resource/प्रॉब्लम_(कंप्यूटर_विज्ञान) dbpedia-hr:Computational problem dbpedia-hu:Computational problem dbpedia-it:Computational problem dbpedia-pl:Computational problem dbpedia-pt:Computational problem dbpedia-sr:Computational problem https://global.dbpedia.org/id/3A6Kp |
| prov:wasDerivedFrom | wikipedia-en:Computational_problem?oldid=1099779198&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Computational_problem |
| is dbo:wikiPageDisambiguates of | dbr:Problem_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Computational_problems dbr:Computation_problem |
| is dbo:wikiPageWikiLink of | dbr:Proof_of_secure_erasure dbr:Quantum_complexity_theory dbr:Quantum_logic_gate dbr:Enumeration_algorithm dbr:Memory-bound_function dbr:Metagame_analysis dbr:Algorithm dbr:Anytime_algorithm dbr:Approximation-preserving_reduction dbr:DLOGTIME dbr:DSPACE dbr:DTIME dbr:Decision_problem dbr:Decomposition_(computer_science) dbr:Descriptive_complexity_theory dbr:Dutch_national_flag_problem dbr:Quantum_computing dbr:Numberlink dbr:Post-modern_portfolio_theory dbr:Power_iteration dbr:Pseudorandom_generator dbr:Security_parameter dbr:Simon's_problem dbr:♯P-completeness_of_01-permanent dbr:Computability dbr:Analysis_of_algorithms dbr:Generic-case_complexity dbr:Optimality_Theory dbr:Non-constructive_algorithm_existence_proofs dbr:Glossary_of_areas_of_mathematics dbr:Glossary_of_artificial_intelligence dbr:Glossary_of_computer_science dbr:Glossary_of_quantum_computing dbr:Constraint_programming dbr:Cooperative_coevolution dbr:LH_(complexity) dbr:Collision_detection dbr:Complete_(complexity) dbr:Complexity_class dbr:Computability_logic dbr:Computation dbr:Computational_complexity dbr:Computational_complexity_theory dbr:Computational_resource dbr:Computer_science dbr:Computing dbr:Function_problem dbr:Function_tree dbr:Software_architecture dbr:Probabilistically_checkable_proof dbr:Succinct_game dbr:Market_equilibrium_computation dbr:Distributed_computing dbr:K-line_(artificial_intelligence) dbr:Karp's_21_NP-complete_problems dbr:Lateral_computing dbr:Learning_with_errors dbr:Promise_problem dbr:Resource_bounded_measure dbr:Fallibilism dbr:And–or_tree dbr:Chronology_of_the_universe dbr:Graph_isomorphism_problem dbr:History_of_statistics dbr:Problem_(disambiguation) dbr:Reduction_(complexity) dbr:Ring_learning_with_errors dbr:2-satisfiability dbr:Asymptotic_computational_complexity dbr:Backtracking dbr:Counting_problem_(complexity) dbr:Binary_decision_diagram dbr:Biodiversity_informatics dbr:Automata_theory dbr:PostBQP dbr:Circuit_complexity dbr:Micah_Altman dbr:Optimization_problem dbr:Recursion_(computer_science) dbr:Search_problem dbr:Self-avoiding_walk dbr:Self-driving_car dbr:Tutte_polynomial dbr:Computational_problems dbr:List_of_undecidable_problems dbr:Olfactory_bulb dbr:Finite_model_theory dbr:First-order_reduction dbr:Tree_alignment dbr:NSPACE dbr:Motion_planning dbr:Physical_and_logical_qubits dbr:Simplicial_complex_recognition_problem dbr:Transcomputational_problem dbr:Overlapping_subproblems dbr:Space_complexity dbr:Computation_problem |
| is foaf:primaryTopic of | wikipedia-en:Computational_problem |