Model of computation (original) (raw)
نموذج الحوسبة في نظرية الحاسوب ونظرية التعقيد الحسابي هو تعريف مجموعة من العمليات المسموح استخدامها في الحوسبة وتكلفة كل منها. وهو يستخدم لقياس مدى تعقيد خوارزمية حسب زمن التنفيذ و/أو : بافتراض نموذج معين من الحوسبة، فمن الممكن تحليل الموارد الحاسوبية المطلوبة أو مناقشة القيود المفروضة على خوارزميات أو أجهزة الكمبيوتر.
| Property | Value |
|---|---|
| dbo:abstract | نموذج الحوسبة في نظرية الحاسوب ونظرية التعقيد الحسابي هو تعريف مجموعة من العمليات المسموح استخدامها في الحوسبة وتكلفة كل منها. وهو يستخدم لقياس مدى تعقيد خوارزمية حسب زمن التنفيذ و/أو : بافتراض نموذج معين من الحوسبة، فمن الممكن تحليل الموارد الحاسوبية المطلوبة أو مناقشة القيود المفروضة على خوارزميات أو أجهزة الكمبيوتر. (ar) Výpočetní model (anglicky model of computation) je abstraktní model v teorii vyčíslitelnosti a teorii složitosti definující množinu povolených operací používaných při výpočtu a jejich cen (nákladů). Používá se pro určení míry složitosti algoritmů vyjádřené nebo : pro konkrétní výpočetní model lze analyzovat, jaké výpočetní prostředky vyžaduje, nebo diskutovat omezení algoritmů nebo počítačů. (cs) Στη θεωρία υπολογισιμότητας και στη θεωρία υπολογιστικής πολυπλοκότητας, ένα μοντέλο υπολογισμού είναι ο ορισμός του συνόλου των επιτρεπόμενων λειτουργιών που χρησιμοποιούνται στον υπολογισμό και τις αντίστοιχες δαπάνες. Χρησιμοποιείται για τη μέτρηση της πολυπλοκότητας ενός αλγορίθμου σε χρόνο εκτέλεσης ή χώρο μνήμης: αναλαμβάνοντας ένα συγκεκριμένο υπολογιστικό μοντέλο, είναι δυνατόν να αναλυθούν οι υπολογιστικοί πόροι που απαιτούνται ή για να συζητηθούν οι περιορισμοί των αλγορίθμων ή υπολογιστές. (el) En la teoría de la computabilidad y en la teoría de la complejidad computacional, un modelo de computación es la definición un conjunto de operaciones permitibles usadas en el cómputo y sus respectivos costos. Solo asumiendo un cierto modelo de computación es posible analizar los recursos de cómputo requeridos, como el tiempo de ejecución o el , o discutir las limitaciones de algoritmos o computadores. Algunos ejemplos de modelos incluyen las máquinas de Turing, las funciones recursivas, cálculo lambda, y . En la ingeniería dirigida por modelos, el modelo de computación explica cómo el comportamiento del sistema entero es el resultado del comportamiento de cada uno de sus componentes. En el campo del tiempo de ejecución del análisis de algoritmos, es común especificar un modelo computacional en términos de operaciones primitivas permitidas que tengan un costo unitario, o simplemente operaciones costo unitario. Un ejemplo comúnmente usado es la , que tiene costo unitario para acceso de lectura y escritura para todas sus celdas de memoria. En este respecto, se diferencia del modelo de máquina de Turing mencionado arriba. Hay muchos modelos de computación, diferenciándose en el conjunto de operaciones admisibles y de su costo computacional. Ellos entran en las amplias categorías siguientes: * La máquina abstracta, usada en pruebas de computabilidad y de los límites superiores en la complejidad computacional de algoritmos, y * El modelo de árbol de decisión, usado en las pruebas de los límites más bajos en la complejidad computacional de problemas algorítmicos. * Datos: Q2651576 * Multimedia: Computational models / Q2651576 (es) In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how units of computations, memories, and communications are organized. The computational complexity of an algorithm can be measured given a model of computation. Using a model allows studying the performance of algorithms independently of the variations that are specific to particular implementations and specific technology. (en) 計算モデル（けいさんモデル、（英: model of computation）は、計算・推論・証明といった行為を理論的・抽象的に考察するための数理モデルである。計算模型ともいう。これに含まれるうちで、チューリングマシンなどのような、現実の機械に似せた架空のものを抽象機械といい、そうでないものとしてはラムダ計算などがある。ラムダ計算は数学の関数式の組み合わせであり、ソースコードのような計算モデルである。 理論計算機科学の多くの分野で、「計算機械」を理論的に、すなわちモデル化して扱うために多大に活用されている。また特に抽象機械は、実際のプロセッサやコンパイラやインタプリタの研究や開発など、理論に限らず実際的な分野でも活用される。計算理論においては、計算可能性や計算複雑性について形式的・定量的に示すためなどに使われており、古典的な成果にチャーチ＝チューリングのテーゼがある。 より現実の計算機に近づけた機械の定義には命令セット、レジスタ、メモリモデルなども含まれる。現在の一般的なコンピュータ（要するにいわゆるノイマン型）を抽象化した計算モデルとしてはRAMモデル（ランダムアクセスマシン）がある。これはメモリに対してインデックス付けによりランダムアクセス可能な計算モデルである（チューリングマシンではテープの1区画ずつの移動しかできない）。キャッシュメモリが一般化し、そのヒット率が性能に与える影響が大きくなるにつれて、メモリの階層を前提とした計算モデルが重要となった。 ハードウェアとして実装されていない（実装する予定のない）プロセッサの設計も一種の抽象機械である。特にインタプリタの形式でソフトウェアとして実装されている抽象機械を仮想機械と呼ぶ。研究目的などで、より抽象的な抽象機械の実装を作って研究などに使うこともある。 抽象機械を使用することで、実際にシステムを組み立てることなく時間、メモリ使用量など特定の操作の実行に要するリソースを計算で求めることが可能である。 (ja) Теория вычислимости и теория сложности вычислений трактует модель вычисления (англ. model of computation) не только как определение множества допустимых операций, использованных для вычисления, но также и относительных издержек их применения. Охарактеризовать необходимые вычислительные ресурсы — время выполнения, объём памяти, а также ограничения алгоритмов или компьютера — можно только в том случае, если выбрана определённая модель вычислений. В модельно-ориентированной инженерии модель вычислений и её выбор дают ответ на вопрос, как ведёт себя система в целом, если известно поведение её отдельных частей. При асимптотической оценке сложности вычислений модель вычислений определяется через допустимые примитивные операции с известной ценой. Известен целый ряд моделей вычислений, зависящих от набора применяемых операций и их вычислительной сложности. Они распадаются на следующие большие категории: абстрактные машины (абстрактные вычислители), используемые для доказательства вычислимости и получения верхней границы вычислительной сложности алгоритма, и модели принятия решений, используемые для получения нижней границы сложности вычислений для алгоритмических задач. (ru) Em teoria da computabilidade, um modelo de computação é a definição de um conjunto de operações que podem ser usadas numa computação e seus respectivos custos. Somente assumindo certo modelo de computação é possível analisar os recursos computacionais requeridos, como tempo de execução e espaço de armazenamento, ou discutir as limitações de algoritmos ou computadores. Na área de análise de algoritmos, é comum especificar um modelo de computação em termos de operações primitivas, cada uma com um custo unitário associado. Alguns exemplos de modelos de computação incluem a máquina de Turing, função recursiva, cálculo lambda e sistema de produção. Há diversos modelos, que diferem entre si no conjunto de operações e custos associados. De forma geral, eles são categorizados em máquinas abstratas, usadas em provas de computabilidade e no cálculo dos limites máximos na complexidade de algoritmos, e modelos de árvore de decisão, usados em provas dos limites mínimos de complexidade em problemas algorítmicos. (pt) 在可计算性理论和計算複雜性理論中，计算模型（model of computation）描述了如何根据一组输入值计算得出输出值，也包含了负责运算、存储和通讯等结构的具体组织方式。它可以用于测量一个算法在时间和/或空间上的复杂度。通过计算模型的抽象化总结，我们可以分析出算法的性能，而避免在具体程序层面，被不同的技术和实现方式造成的性能差异所误导。 (zh) Модель обчислення в інформатиці, а особливо у теорії обчислюваності та теорії складності обчислень — це визначення множин допустимих операцій, що використовуються при обчисленні, та їх відповідні витрати. Вона використовується у обчисленні складності алгоритму або проблеми, для вирішення якої вона була створена. Це допомагає дослідити продуктивність алгоритмів незалежно від варіантів, специфічних для конкретних імплементацій та конкретних технологій. (uk) |
| dbo:wikiPageID | 1773278 (xsd:integer) |
| dbo:wikiPageLength | 3716 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1094361730 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algorithm dbr:Decision_tree_model dbr:Interaction_nets dbr:Robertson–Webb_query_model dbr:Combinatory_logic dbr:Computability_theory_(computer_science) dbr:Analysis_of_algorithms dbr:Function_(mathematics) dbr:General_recursive_function dbr:Stack_machine dbr:Computational_complexity dbr:Computational_complexity_theory dbr:Computer_science dbr:Tag_system dbr:Actor_model dbr:Cell-probe_model dbr:Cellular_automaton dbr:Kahn_process_networks dbr:Logic_gate dbc:Computational_complexity_theory dbr:Abstract_machine dbr:Abstract_rewriting_system dbc:Computability_theory dbc:Models_of_computation dbr:Chomsky_hierarchy dbr:Lambda_calculus dbr:Register_machine dbr:Post–Turing_machine dbr:Circuit_(computer_science) dbr:Pushdown_automata dbr:Random-access_machine dbr:Turing_machine dbr:Synchronous_Data_Flow dbr:Nondeterministic_model_of_computation dbr:Implementation dbr:Turing_completeness dbr:Petri_nets dbr:Finite_state_machine dbr:Accumulator_machine dbr:Deterministic_model |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cn dbt:For dbt:One_source dbt:Reflist dbt:Short_description dbt:Computer_science |
| dct:subject | dbc:Computational_complexity_theory dbc:Computability_theory dbc:Models_of_computation |
| gold:hypernym | dbr:Definition |
| rdf:type | yago:WikicatModelsOfComputation yago:Assistant109815790 yago:CausalAgent100007347 yago:LivingThing100004258 yago:Model110324560 yago:Object100002684 yago:Organism100004475 yago:Person100007846 yago:PhysicalEntity100001930 yago:Worker109632518 yago:YagoLegalActor yago:YagoLegalActorGeo dbo:VideoGame yago:Whole100003553 |
| rdfs:comment | نموذج الحوسبة في نظرية الحاسوب ونظرية التعقيد الحسابي هو تعريف مجموعة من العمليات المسموح استخدامها في الحوسبة وتكلفة كل منها. وهو يستخدم لقياس مدى تعقيد خوارزمية حسب زمن التنفيذ و/أو : بافتراض نموذج معين من الحوسبة، فمن الممكن تحليل الموارد الحاسوبية المطلوبة أو مناقشة القيود المفروضة على خوارزميات أو أجهزة الكمبيوتر. (ar) Výpočetní model (anglicky model of computation) je abstraktní model v teorii vyčíslitelnosti a teorii složitosti definující množinu povolených operací používaných při výpočtu a jejich cen (nákladů). Používá se pro určení míry složitosti algoritmů vyjádřené nebo : pro konkrétní výpočetní model lze analyzovat, jaké výpočetní prostředky vyžaduje, nebo diskutovat omezení algoritmů nebo počítačů. (cs) Στη θεωρία υπολογισιμότητας και στη θεωρία υπολογιστικής πολυπλοκότητας, ένα μοντέλο υπολογισμού είναι ο ορισμός του συνόλου των επιτρεπόμενων λειτουργιών που χρησιμοποιούνται στον υπολογισμό και τις αντίστοιχες δαπάνες. Χρησιμοποιείται για τη μέτρηση της πολυπλοκότητας ενός αλγορίθμου σε χρόνο εκτέλεσης ή χώρο μνήμης: αναλαμβάνοντας ένα συγκεκριμένο υπολογιστικό μοντέλο, είναι δυνατόν να αναλυθούν οι υπολογιστικοί πόροι που απαιτούνται ή για να συζητηθούν οι περιορισμοί των αλγορίθμων ή υπολογιστές. (el) In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how units of computations, memories, and communications are organized. The computational complexity of an algorithm can be measured given a model of computation. Using a model allows studying the performance of algorithms independently of the variations that are specific to particular implementations and specific technology. (en) 在可计算性理论和計算複雜性理論中，计算模型（model of computation）描述了如何根据一组输入值计算得出输出值，也包含了负责运算、存储和通讯等结构的具体组织方式。它可以用于测量一个算法在时间和/或空间上的复杂度。通过计算模型的抽象化总结，我们可以分析出算法的性能，而避免在具体程序层面，被不同的技术和实现方式造成的性能差异所误导。 (zh) Модель обчислення в інформатиці, а особливо у теорії обчислюваності та теорії складності обчислень — це визначення множин допустимих операцій, що використовуються при обчисленні, та їх відповідні витрати. Вона використовується у обчисленні складності алгоритму або проблеми, для вирішення якої вона була створена. Це допомагає дослідити продуктивність алгоритмів незалежно від варіантів, специфічних для конкретних імплементацій та конкретних технологій. (uk) En la teoría de la computabilidad y en la teoría de la complejidad computacional, un modelo de computación es la definición un conjunto de operaciones permitibles usadas en el cómputo y sus respectivos costos. Solo asumiendo un cierto modelo de computación es posible analizar los recursos de cómputo requeridos, como el tiempo de ejecución o el , o discutir las limitaciones de algoritmos o computadores. Algunos ejemplos de modelos incluyen las máquinas de Turing, las funciones recursivas, cálculo lambda, y . (es) 計算モデル（けいさんモデル、（英: model of computation）は、計算・推論・証明といった行為を理論的・抽象的に考察するための数理モデルである。計算模型ともいう。これに含まれるうちで、チューリングマシンなどのような、現実の機械に似せた架空のものを抽象機械といい、そうでないものとしてはラムダ計算などがある。ラムダ計算は数学の関数式の組み合わせであり、ソースコードのような計算モデルである。 理論計算機科学の多くの分野で、「計算機械」を理論的に、すなわちモデル化して扱うために多大に活用されている。また特に抽象機械は、実際のプロセッサやコンパイラやインタプリタの研究や開発など、理論に限らず実際的な分野でも活用される。計算理論においては、計算可能性や計算複雑性について形式的・定量的に示すためなどに使われており、古典的な成果にチャーチ＝チューリングのテーゼがある。 ハードウェアとして実装されていない（実装する予定のない）プロセッサの設計も一種の抽象機械である。特にインタプリタの形式でソフトウェアとして実装されている抽象機械を仮想機械と呼ぶ。研究目的などで、より抽象的な抽象機械の実装を作って研究などに使うこともある。 抽象機械を使用することで、実際にシステムを組み立てることなく時間、メモリ使用量など特定の操作の実行に要するリソースを計算で求めることが可能である。 (ja) Em teoria da computabilidade, um modelo de computação é a definição de um conjunto de operações que podem ser usadas numa computação e seus respectivos custos. Somente assumindo certo modelo de computação é possível analisar os recursos computacionais requeridos, como tempo de execução e espaço de armazenamento, ou discutir as limitações de algoritmos ou computadores. Na área de análise de algoritmos, é comum especificar um modelo de computação em termos de operações primitivas, cada uma com um custo unitário associado. (pt) Теория вычислимости и теория сложности вычислений трактует модель вычисления (англ. model of computation) не только как определение множества допустимых операций, использованных для вычисления, но также и относительных издержек их применения. Охарактеризовать необходимые вычислительные ресурсы — время выполнения, объём памяти, а также ограничения алгоритмов или компьютера — можно только в том случае, если выбрана определённая модель вычислений. При асимптотической оценке сложности вычислений модель вычислений определяется через допустимые примитивные операции с известной ценой. (ru) |
| rdfs:label | نموذج حوسبة (ar) Výpočetní model (teorie algoritmů) (cs) Μοντέλο υπολογισμού (el) Modelo de computación (es) 計算モデル (ja) Model of computation (en) Modelo de computação (pt) Модель вычислений (ru) Модель обчислення (uk) 计算模型 (数学) (zh) |
| owl:sameAs | freebase:Model of computation yago-res:Model of computation wikidata:Model of computation dbpedia-ar:Model of computation dbpedia-bg:Model of computation dbpedia-cs:Model of computation dbpedia-el:Model of computation dbpedia-es:Model of computation dbpedia-fa:Model of computation dbpedia-fi:Model of computation dbpedia-he:Model of computation dbpedia-hr:Model of computation dbpedia-ja:Model of computation dbpedia-pt:Model of computation dbpedia-ru:Model of computation dbpedia-uk:Model of computation dbpedia-vi:Model of computation dbpedia-zh:Model of computation https://global.dbpedia.org/id/2V5LV |
| prov:wasDerivedFrom | wikipedia-en:Model_of_computation?oldid=1094361730&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Model_of_computation |
| is dbo:academicDiscipline of | dbr:Carl_Hewitt |
| is dbo:wikiPageDisambiguates of | dbr:MOC |
| is dbo:wikiPageRedirects of | dbr:Theoretical_model_of_computation dbr:Theoretical_models_of_computation dbr:Models_of_computation dbr:Machine_model dbr:Mathematical_model_of_computation dbr:Computation_model dbr:Computational_formalism dbr:Computational_mechanism |
| is dbo:wikiPageWikiLink of | dbr:Ambric dbr:Quantum_logic_gate dbr:Entscheidungsproblem dbr:One_Clean_Qubit dbr:Jose_Meseguer dbr:Per_Martin-Löf dbr:Decision_tree_model dbr:Decomposition_(computer_science) dbr:Deterministic_system dbr:Integer_circuit dbr:Interaction_nets dbr:Quantum_computing dbr:List_of_quantum_processors dbr:Worst-case_complexity dbr:Pseudorandom_generator dbr:Ptolemy_Project dbr:Robertson–Webb_query_model dbr:Combinatory_logic dbr:Computability dbr:Computability_theory dbr:Computable_function dbr:Computational_complexity_of_matrix_multiplication dbr:Analysis_of_algorithms dbr:Ancilla_bit dbr:Matrix_multiplication dbr:Church–Turing_thesis dbr:Geometric_median dbr:Glossary_of_artificial_intelligence dbr:Glossary_of_computer_science dbr:Theoretical_model_of_computation dbr:Theoretical_models_of_computation dbr:Arnold_L._Rosenberg dbr:Blum–Shub–Smale_machine dbr:Cache-oblivious_algorithm dbr:Closest_pair_of_points_problem dbr:Comparison_of_application_virtualization_software dbr:Complexity_and_Real_Computation dbr:Complexity_class dbr:Computation dbr:Computational_complexity dbr:Computational_problem dbr:Programming_language_theory dbr:State_(computer_science) dbr:Theoretical_computer_science dbr:Theory_of_computation dbr:To_Mock_a_Mockingbird dbr:Busy_beaver dbr:Toby_Ord dbr:UP_Diliman_Department_of_Computer_Science dbr:TFNP dbr:Curry–Howard_correspondence dbr:Carl_Hewitt dbr:Cellular_automaton dbr:Fair_cake-cutting dbr:Globally_asynchronous_locally_synchronous dbr:Kahn_process_networks dbr:Predecessor_problem dbr:Halting_problem dbr:Asymptotically_optimal_algorithm dbr:Counter_machine dbr:Hypercomputation dbr:Range_searching dbr:AI-complete dbr:AI_effect dbr:Abstract_machine dbr:Abstraction_(computer_science) dbr:Lambda_calculus dbr:BlooP_and_FlooP dbr:Echopraxia dbr:Boolean_algebra dbr:Boolean_circuit dbr:Circuit_(computer_science) dbr:Integer_sorting dbr:Categorical_abstract_machine dbr:MOC dbr:Massively_parallel_processor_array dbr:SIGNAL_(programming_language) dbr:SKI_combinator_calculus dbr:Semantics_(computer_science) dbr:Quantum_circuit dbr:External_memory_algorithm dbr:External_sorting dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Finite-state_machine dbr:Quantized_state_systems_method dbr:Population_protocol dbr:Reversible_computing dbr:Word_RAM dbr:Parallel_programming_model dbr:Turing_completeness dbr:Models_of_computation dbr:Machine_model dbr:Mathematical_model_of_computation dbr:Computation_model dbr:Computational_formalism dbr:Computational_mechanism |
| is dbp:fields of | dbr:Carl_Hewitt |
| is foaf:primaryTopic of | wikipedia-en:Model_of_computation |