| rdfs:comment
| - La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée …) requis par un algorithme pour résoudre un problème algorithmique. Il s'agit donc d'étudier la difficulté intrinsèque des problèmes, de les organiser par classes de complexité et d'étudier les relations entre les classes de complexité. (fr)
- 계산 복잡도 이론(計算 複雜度 理論, 영어: Computational complexity theory)은 컴퓨터 과학에서 계산 이론의 분야로, 를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연구한다. 이 때 알고리즘의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용한다. 복잡도의 기준은 알고리즘이 소모하는 소요 시간과 메모리 사용량 등의 자원이다. 전자를 시간 복잡도, 후자를 라 한다. 일반적으로 이와 같은 시공간 등의 자원은 입력의 크기에 의존하는 것으로 취급한다. (ko)
- 計算複雑性理論（けいさんふくざつせいりろん、英: computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。 「計算量」と「計算複雑性」はともに computational complexity に対応する語であるが、個々のアルゴリズムの効率に着目する文脈では「計算量」が広く用いられるのに対し、問題に内在する本質的困難さを表す意識からは「複雑性」「複雑さ」が好まれる傾向がある。 (ja)
- Computationele complexiteitstheorie is een tak van theoretische informatica en wiskunde die als doel heeft computationele problemen te classificeren in een aantal categorieën die de inherente moeilijkheidsgraad van deze problemen aangeven. Een computationeel probleem is een probleem dat door een computer kan worden opgelost. Een voorbeeld van een probleem dat computationeel is, is de vraag of een getal wel of niet priem is. Dit kan worden bepaald door middel van een priemgetaltest. Een probleem wordt gezien als inherent moeilijk, als het voor alle denkbare algoritmes veel tijd of geheugen in beslag neemt. Computationele complexiteitstheorie beschrijft dus de praktische limieten van computers. (nl)
- 计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。 如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。 (zh)
- نظرية التعقيد هي فرع من فروع نظرية الحوسبة والرياضيات، وهذه النظرية تتركز في تصنيف المسائل الحاسوبية حسب صعوبتها وربط أقسام التعقيد (complexity classes) ببعضها، والمسألة الحاسوبية هي المسألة التي يستطيع الحاسوب بحلها. وأحد أهم أساسيات نظرية التعقيد الحسابي هي إظهار الحدود العملية لما يستطيع الحاسوب القيام به وما لا يستطيع القيام به. (ar)
- La teoria de la complexitat computacional se centra a classificar problemes computacionals segons el seu ús de recursos i relacionar aquestes classes entre si. Un problema computacional és una tasca resolta per un ordinador. Un problema de càlcul es pot resoldre mitjançant l'aplicació mecànica de passos matemàtics, com ara un algorisme. (ca)
- Teorie složitosti je odvětvím v informatice a matematice, které se zaměřuje na klasifikaci dle jejich vlastní složitosti a určení vztahů mezi nimi. Ke studiu a určení složitosti těchto problémů definuje výpočetní modely, jako je Turingův stroj nebo RAM, na kterých je simuluje a určuje složitost (typicky časovou a paměťovou). Používají se i další míry složitosti, jako množství komunikace (v ), počet hradel obvodu (ve ), počet přístupů do keše (v analýze kešování) a počet procesorů (v paralelním programování). Jeden z cílů teorie složitosti je určit praktické limity toho, co počítače dokážou spočítat a co ne. (cs)
- Η θεωρία πολυπλοκότητας είναι το μέρος εκείνο της θεωρίας υπολογισμού, το οποίο ασχολείται με την κοστολόγηση των πόρων που απαιτούνται για την αλγοριθμική επίλυση ενός προβλήματος. Επομένως η θεωρία πολυπλοκότητας αποτελεί βασικό δομικό λίθο της και κεντρικό γνωστικό πεδίο της επιστήμης υπολογιστών. (el)
- Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Komplexität algorithmisch behandelbarer Probleme auf verschiedenen formalen Rechnermodellen. Die Komplexität von Algorithmen wird in deren Ressourcenverbrauch gemessen, meist Rechenzeit oder Speicherplatzbedarf, manchmal auch speziellere Maße wie die Größe eines Schaltkreises oder die Anzahl benötigter Prozessoren bei parallelen Algorithmen. Die Komplexität eines Problems ist wiederum die Komplexität desjenigen Algorithmus, der das Problem mit dem geringstmöglichen Ressourcenverbrauch löst. (de)
- In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. (en)
- La teoría de la complejidad computacional o teoría de la complejidad informática es una rama de la teoría de la computación que se centra en la clasificación de los problemas computacionales de acuerdo con su dificultad inherente, y en la relación entre dichas clases de complejidad. (es)
- Konplexutasun konputazionalaren teoria edo konplexutasun informatikoaren teoria teoria konputazionalaren adar bat da, arazo konputazionalak berezko zailtasunaren arabera sailkatzean eta konplexutasun klase horien arteko erlazioan oinarritzen dena. Konplexutasun konputazionalaren teoria baliabide kopuru jakin batekin ebatzi daitezkeen edo ezin diren arazoak sailkatzen saiatzen da. Era berean, baliabide horiei, murrizketak ezartzea da konputagarritasunaren teoriatik bereizten duena, hau da, zer-nolako arazok ebatzi daitezkeen algoritmikoki. (eu)
- La teoria della complessità computazionale è una branca della teoria della computabilità che studia le risorse minime necessarie (principalmente tempo di calcolo e memoria) per la risoluzione di un problema. Con complessità di un algoritmo o efficienza di un algoritmo ci si riferisce dunque alle risorse di calcolo richieste. I problemi sono classificati in differenti classi di complessità, in base all'efficienza del migliore algoritmo noto in grado di risolvere quello specifico problema. (it)
- Теорія складності обчислень — підрозділ теоретичної інформатики, що займається дослідженням складності алгоритмів для розв'язання задач на основі формально визначених моделей обчислювальних пристроїв. Складність алгоритмів вимірюється за необхідними ресурсами, в основному це тривалість обчислень або необхідний обсяг пам'яті. В окремих випадках досліджуються інші міри складності, такі як розмір мікросхем, або кількість процесорів, необхідна для роботи паралельних алгоритмів. (uk)
- Теория сложности вычислений — подраздел теоретической информатики, занимающейся исследованием сложности алгоритмов для решения задач на основе формально определённых моделей вычислительных устройств. Сложность алгоритмов измеряется необходимыми ресурсами, в основном это продолжительность вычислений или необходимый объём памяти. В отдельных случаях исследуются другие степени сложности, такие как размер микросхем, или количество процессоров, необходимая для работы параллельных алгоритмов. (ru)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)