Teorie složitosti je odvětvím teorie počítání v informatice a matematice, které se zaměřuje na klasifikaci výpočetních problémů dle jejich vlastní složitosti a určení vztahů mezi třídami. V tomto kontextu je problém chápán jako úkol, který lze vyřešit na počítači, čímž se myslí mechanickou aplikací postupných kroků pomocí algoritmu. Konkrétní zadání problému je tzv. instance a algoritmus vrátí řešení instance.

PropertyValue
prop-cs:wikiPageUsesTemplate
dbpedia-owl:abstract
  • Teorie složitosti je odvětvím teorie počítání v informatice a matematice, které se zaměřuje na klasifikaci výpočetních problémů dle jejich vlastní složitosti a určení vztahů mezi třídami. V tomto kontextu je problém chápán jako úkol, který lze vyřešit na počítači, čímž se myslí mechanickou aplikací postupných kroků pomocí algoritmu. Konkrétní zadání problému je tzv. instance a algoritmus vrátí řešení instance. Základním příkladem je situace, kdy chceme zjistit, zdali je nějaké přirozené číslo n prvočíslem nebo ne. Zadáním tohoto jsou tedy přirozená čísla a výsledkem je odpověď ANO/NE případně 0 nebo 1.Problém, například výše zmíněné testování prvočíselnosti, se považuje za těžký, pokud jeho řešení potřebuje značné zdroje bez ohledu na to, jaký algoritmus je použit. Teorie složitosti formalizuje tento intuitivní přístup a zavádí výpočetní modely. Na nich se studuje a kvantifikuje množství potřebných zdrojů pro řešení problémů, např. čas a paměť.Používají se i další míry složitosti, jako množství komunikace (v komunikační složitosti), počet hradel obvodu (ve složitosti obvodů), 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.Příbuzné oblasti informatiky jsou analýza algoritmů a teorie vyčíslitelnosti. Hlavním rozdílem mezi analýzou algoritmů a teorií složitosti je, že analýza algoritmů se zabývá množstvím potřebných zdrojů, které potřebuje konkrétní algoritmus, zatímco teorie složitosti zjišťuje obecnější otázky týkající se všech algoritmů, které se dají použít pro řešení určitého problému. Snaží se tedy klasifikovat problémy podle daných omezení na dostupné zdroje. Tedy zavedení omezení na dostupné zdroje odlišuje teorii složitosti od teorie vyčíslitelnosti, které se ptá, jaké problémy lze, v principu, vyřešit algoritmicky.
dbpedia-owl:thumbnail
dbpedia-owl:wikiPageExternalLink
dbpedia-owl:wikiPageID
  • 22876 (xsd:integer)
dbpedia-owl:wikiPageLength
  • 9266 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 52 (xsd:integer)
dbpedia-owl:wikiPageRevisionID
  • 16143874 (xsd:integer)
dbpedia-owl:wikiPageWikiLink
dbpedia-owl:wikiPageWikiLinkText
  • teorie složitosti
  • Teorie složitosti
  • výpočetní složitost
  • složitosti
  • teorii složitosti
  • teorií složitosti
  • Teorie výpočetní složitosti
dcterms:subject
rdfs:comment
  • Teorie složitosti je odvětvím teorie počítání v informatice a matematice, které se zaměřuje na klasifikaci výpočetních problémů dle jejich vlastní složitosti a určení vztahů mezi třídami. V tomto kontextu je problém chápán jako úkol, který lze vyřešit na počítači, čímž se myslí mechanickou aplikací postupných kroků pomocí algoritmu. Konkrétní zadání problému je tzv. instance a algoritmus vrátí řešení instance.
rdfs:label
  • Teorie složitosti
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbpedia-owl:wikiPageWikiLink of
is foaf:primaryTopic of