| dbpprop:abstract
|
- The theory of computation is the branch of computer science and mathematics that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm. The field is divided into two major branches: computability theory and complexity theory, but both branches deal with formal models of computation. In order to perform a rigorous study of computation, computer scientists work with a mathematical abstraction of computers called a model of computation. There are several models in use, but the most commonly examined is the Turing machine. A Turing machine can be thought of as a desktop PC with a potentially infinite memory capacity, though it can only access this memory in small discrete chunks. Computer scientists study the Turing machine because it is simple to formulate, can be analyzed and used to prove results, and because it represents what many consider the most powerful possible "reasonable" model of computation. It might seem that the potentially infinite memory capacity is an unrealizable attribute, but any decidable problem solved by a Turing machine will always require only a finite amount of memory. So in principle, any problem that can be solved (decided) by a Turing machine can be solved by a computer that has a bounded amount of memory.
- Die Theoretische Informatik beschäftigt sich mit der Abstraktion, Modellbildung und grundlegenden Fragestellungen, die mit der Struktur, Verarbeitung, Übertragung und Wiedergabe von Informationen in Zusammenhang stehen. Forschungsgebiete sind die Automatentheorie und die Theorie der formalen Sprachen sowie die Berechenbarkeits- und Komplexitätstheorie aber auch Bereiche der Kryptologie, Logik und formaler Semantik sowie die Informations-, Algorithmen-, Datenbank- und Spieltheorie, um nur einige zu nennen. Die Theoretische Informatik wurde – von den Befürwortern dieser Wissenschaftskategorie – in die Strukturwissenschaften eingeordnet und bietet Grundlagen für die Definition, Prüfung und Ausführung der Programme von Programmiersprachen, den Bau der Compiler von Programmiersprachen – dem Compilerbau – und die mathematische Formalisierung und Untersuchung von meist diskreten Problemstellungen und deren Modellen. Mit Hilfe mathematischer Abstraktion der Eigenschaften von gewonnenen Modellen ergaben sich nützliche Definitionen, Sätze, Beweise, Algorithmen, Anwendungen und Lösungen von bzw. zu Problemen. Die Theoretische Informatik bildet mit ihren zeitlosen, mathematischen Wahrheiten und Methoden ein formales Skelett, das die Informatik in der Praxis mit konkreten Implementierungen durchdringt. Die Theoretische Informatik identifizierte viele unlösbare Problemstellungen mittels der Berechenbarkeitstheorie und erlaubt, häufig mit konstruktiver Beweisführung der Komplexitätstheorie, die Abgrenzung der praktisch effizient lösbaren Probleme von denen, für die das Gegenteil gilt. Zu den konstruktiven Methoden der Theoretischen Informatik zählt auch das Entwerfen von formalen Systemen, Automaten, Graphen und Syntaxdiagrammen sowie das Festlegen von Grammatiken und Semantiken, um eine Problemstellung mit mathematischen Ausdrücken formal zu fassen und von der informellen Ebene abzuheben. Die Konstrukte beschreiben so die innere Logik eines Problems mit mathematisch-logischen Aussagen, was im Weiteren eine formale Untersuchung erlaubt und potenziell neue – durch Beweise gestützte – Aussagen und Algorithmen der formalen Modelle als Resultate erschließbar macht. Neben dem mathematischen Erkenntnisgewinn lassen sich manche gefundenen Lösungen praktisch implementieren, um Menschen durch Maschinensemantik automatisierte Vorteile der Mathematik- und Computer-Nutzung zu verschaffen. Mit den vielfältig kombinierfähigen Umsetzungen der mathematischen Erkenntnisse in die Praxis gehen mancherorts auch Nachteile einher, die mit den verwendeten Daten zu tun haben können.
- La teoría de la computación es una ciencia, en particular una rama de la matemática y de la computación que centra su interés en el estudio y definición formal de los cómputos. Se le llama cómputo a la obtención de una solución o resultado (generalmente en el sentido matemático/aritmético del término), a partir de ciertos datos o entradas utilizando para ello un proceso o algoritmo.
- Laskettavuus tai laskettavuusteoria on teoreettisen tietojenkäsittelytieteen haara, joka tutkii ongelmien ratkeavuutta ja ratkaisemisen tehokkuutta algoritmisesti. Käytännössä laskettavuusteoriassa pyritään selvittämään, voidaanko jokin ongelma ratkaista tietokoneiden avulla vai ei, ja jos voidaan, kuinka tehokkaasti. Tehokkuus voi tarkoittaa joko laskennan vaatimaa aikaa tai muistikapasiteettia. Ongelmanasettelu on ensin muotoiltava täsmällisesti erilaisten laskennan mallien avulla, joiden voidaan ajatella olevan tietokoneiden matemaattisia malleja. Esimerkki tällaisesta mallista on Turingin kone. Vasta tämän jälkeen voidaan analysoida, kuinka paljon laskentaresursseja tehtävä vaatii tai onko se ylipäänsä ratkaistavissa.
- L'informatique théorique est l'étude des fondements logiques et mathématiques de l'informatique. Plus généralement, le terme est utilisé pour désigner des domaines ou sous-domaines de recherche centrés sur des vérités universelles en rapport avec l'informatique. L'informatique théorique se caractérise par une approche par nature plus mathématique et moins empirique de l'informatique et ses objectifs ne sont pas toujours directement reliés à des enjeux technologiques. De nombreuses disciplines peuvent être regroupées sous cette dénomination diffuse dont la théorie de la calculabilité, l'algorithmique et la théorie de la complexité, la théorie de l'information, l'étude de la sémantique des langages de programmation et la théorie des automates et des langages formels.
- L' Informatica teorica è un insieme di argomenti dell'informatica che si concentrano sugli aspetti più astratti e matematici della computazione, come la teoria della computazione. l'analisi degli algoritmi e la semantica della programmazione. Nonostante non abbia come oggetto un singolo argomento, i suoi ricercatori formano un gruppo distinto tra i ricercatori informatici.
- 計算理論（けいさんりろん、theory of computation）は、計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。 計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは最も強力な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、チューリングマシンで具体的な問題を解く際に使われるメモリ量は常に有限であり、チューリングマシンで解くことが出来る問題は普通の（メモリをそれなりに搭載した）コンピュータでも解くことが出来る。
- De theoretische informatica is een vorm van informatica die zich bezighoudt met formele talen (dwz. automaten-, berekenbaarheids- en complexiteitstheorie), logica en formele semantiek en biedt hiermee een theoretische fundering voor het maken van compilers van programmeertalen en de wiskundige formalisering van probleemstellingen. Ze is daarmee het formele fundament onder de informatica.
- Teoria obliczeń to dział informatyki teoretycznej. Dzieli się on na dwie główne części: teorię obliczalności oraz złożoność obliczeniową. Pierwszy z nich zajmuje się odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a drugi tym jak szybko da się to zrobić. Rozważania tego typu nie są możliwe bez formalnego, matematycznego modelu komputera. Najczęściej używanym modelem jest maszyna Turinga. Taką maszynę można w uproszczeniu rozumieć jako komputer o nieograniczonych zasobach pamięci. Inne używane modele, takie jak: rachunek lambda, rachunek kombinatorów, algorytmy Markowa, funkcje rekurencyjne są sobie równoważne w tym sensie, że wszystko co jest obliczalne na jednym z nich da się też obliczyć na maszynie Turinga. Rozważa się również węższe modele (tzn. takie, które nie pozwalają na wyrażenie dowolnej funkcji obliczalnej). funkcje pierwotnie rekurencyjne O niektórych problemach związanych z modelami obliczeń wiadomo, że są nierozstrzygalne. Na przykład nie istnieje algorytm, który rozstrzyga, czy dwa λ-wyrażenia są równoważne lub czy maszyna Turinga dla danego wejścia się zatrzyma.
- Computação pode ser definida como a solução de um problema ou, formalmente, o cálculo de uma função, através de um algoritmo. A teoria da computação, um subcampo da ciência da computação e matemática, busca determinar quais problemas podem ser computados em um dado modelo de computação. Por milhares de anos, a computação foi feita com lápis e papel, ou giz e quadro, ou mentalmente, às vezes com a ajuda de tabelas. A teoria da computação teve início nos primeiros anos do século XX, antes da invenção dos modernos computadores eletrônicos. Naquela época, os matemáticos estavam tentando descobrir quais problemas matemáticos poderiam ser resolvidos por um método simples, e quais não poderiam. O primeiro passo estava em definir o significado de um "método simples" para resolver o problema. Em outras palavras, eles precisavam de um modelo formal da computação. Diversos modelos diferentes da computação foram propostos pelos primeiros pesquisadores. Um modelo, conhecido como Máquina de Turing, propunha a construção de uma máquina universal, capaz de operar com uma sequência de instruções e dados entremeados em uma fita de comprimento infinito; a máquina poderia operar em um ponto da fita de cada vez utilizando um cabeçote de leitura e escrita, executando assim a programação que lhe for passada. Outro modelo, se baseia em recursividadefunções recursivas compostas para operar diretamente sobre os números. Uma abordagem similar é o Cálculo Lambdacálculo lambda. Outra classe de abordagens trabalha com regras gramaticais operando sobre cadeias de caracteres, como é o caso dos cadeias de Markov e dos sistemas de Post. Todos os formalismos propostos acima são equivalentes em termos de poder computacional—ou seja, qualquer computação que possa ser realizada com um modelo pode ser realizada com qualquer um dos outros modelos. Ainda em termos teóricos, os modelos propostos são equivalentes aos computadores eletrônicos, desde que não hajam restrições de memória envolvidas. Na verdade, acredita-se que todas as formalizações teoricamente possíveis para o conceito de algoritmo são equivalentes em poder a uma máquina de Turing; esta é a tese de Church-Turing. As questões relativas à possibilidade de realizar certos tipos de computação em determinados tipos de máquina (ou formalismo teórico) são investigadas pela teoria da computabilidade. A teoria da computação estuda os modelos de computação genéricos, assim como os limites da computação: Quais problemas jamais poderão ser resolvidos por um computador, independente da sua velocidade ou memória? Quais problemas podem ser resolvidos por um computador, mas requerem um período tão extenso de tempo para completar a ponto de tornar a solucão impraticável? Em que situações pode ser mais difícil resolver um problema do que verificar cada uma das soluções manualmente?. Em geral, as questões relativas aos requerimentos de tempo ou espaço (memória, em particular) de problemas específicos são investigadas pela Complexidade computacionalteoria da complexidade computacional. Além dos modelos genéricos de computação, alguns modelos computacionais mais simples são úteis para aplicações mais restritas. Expressão RegularExpressões regulares, são por exemplo utilizadas para especificar padrões de cadeias de caracteres, sendo populares em aplicações UNIX e em algumas linguages de programação, como Perl e Python. Outro formalismo matematicamente equivalente às expressões regulares são os Máquina de estado finitoautômatos finitos, que são utilizados em desenho de circuitos e em alguns sistemas de resolução de problemas. As Gramática livre de contextogramáticas livres de contexto são utilizadas para especificar a sintaxe das linguagens de programação; um formalismo equivalente, são os Autômato#Autômatos à pilha (ou pushdown)autômatos com pilha, ou pushdown automata. As funções recursivas primitivas formam uma subclasse das funções recursivas. Modelos de computação diferentes podem realizar tarefas distintas. Uma forma de estudar o poder de um modelo computacional é estudar a classe das Linguagem formallinguagens formais que o modelo pode gerar; o resultado é a hierarquia de Chomsky das linguagens. As tabelas abaixo mostram algumas das classes de problemas (ou linguagens, ou gramáticas) que são consideradas em teoria da computabilidade (azul) e em teoria da complexidade (vermelho). Se a classe X é um subconjunto propriamente contido em Y, então X é mostrado abaixo de Y, conectados por um linha escura. Se X é um subconjunto, mas não é sabido se os conjuntos são iguais ou não, então a linha que os conecta será mais clara e pontilhada.
- Hesap kuramı, problemlerin verilen bir hesap modeli üzerinde bir algoritma işletilerek çözülüp çözülemeyeceğini ve çözülebiliyorsa ne kadar verimle çözülebileceğini araştıran bilgisayar bilimi dalıdır. İki alt dala ayrılır: Hesaplanabilirlik kuramı ve hesap karmaşıklığı kuramı. Hesap sorununu eksiksiz bir şekilde inceleyebilmek için, bilgisayar bilimciler bilgisayarların hesap modeli denilen matematiksel soyutlamaları ile çalışırlar. Araştırmalarda pek çok model kullanılmakla birlikte, en çok ele alınan model Turing makinesidir. Bir Turing makinesi, sonsuz bellek kapasitesine sahip fakat belleğe ancak sonlu ayrık parçaları üzerinden erişebilen bir tür masaüstü bilgisayar olarak düşünülebilir. Bilgisayar bilimcilerin Turing makinesi üzerinde çalışmasının sebepleri, formülasyonunun ve analizinin kolaylığında ve muhtemel "makul" hesap modellerinin en güçlüsü olduğu inancında yatar. Bu durumda sonsuz bellek kapasitesi gerçekleştirilmesi imkansız bir özellik olarak görülebilir; fakat Turing makinesince karar verilebilir her problem, çözümü sırasında sonlu miktarda belleğe gereksinim duyar. Dolayısıyla prensipte, Turing makinesinin çözebileceği (karar verebileceği) her problemin gerektirdiği bellek miktarı üstten sınırlıdır.
- Теорія алгоритмів (англ. Theory of computation) як окремий розділ математики, що вивчає загальні властивості алгоритмів, виникла в 30-х роках 20 століття. Алгоритми, проте, простежуються в математиці протягом всього часу її існування. Необхідність точного математичного уточнення інтуїтивного поняття алгоритму стала неминучою після усвідомлення неможливості існування алгоритмів розв’язку багатьох масових проблем, в першу чергу пов'язаних з арифметикою та математичною логікою (проблеми істинності арифметичних формул та формул першопорядкового числення предикатів, 10-та проблема Гільберта про розв'язність діофантових рівнянь та ін.). Для доведення неіснування алгоритму треба мати його точне математичне визначення, тому після сформування поняття алгоритму як нової та окремої сутності першочерговою стала проблема знаходження адекватних формальних моделей алгоритму та дослідження їх властивостей. При цьому формальні моделі були запропоновані як для первісного поняття алгоритму, так і для похідного поняття алгоритмічно обчислюваної функції. Вперше поняття алгоритму з’явилося в працях Е. Бореля (1912) та Г. Вейля (1921). Першими формальними моделями алгоритмічно обчислюваних функцій були λ-означувані функції та загальнорекурсивні функції. Вказані класи визначались як функції, графіки яких породжуються відповідно численням λ-конверсій та численням Ербрана-Геделя. В 1936 році Стівен Коул Кліні поширив поняття загальнорекурсивної функції на випадок часткових функцій, ввівши поняття частково рекурсивної функції, та описав клас таких функцій в чисто функціональних термінах. В 1943 році Еміль Пост запропонував модель обчислюваних функцій на основі введеного ним числення спеціального вигляду (канонічних систем). Для формалізації самого поняття алгоритму були запропоновані точні математичні описи алгоритмічної машини та обчислюваності на ній. Першою формальною моделлю алгоритмічної машини була машина Тюрінга (Алан Тюрінг, Еміль Пост, 1936). Із пізніших моделей відзначимо нормальні алгоритми та регістрові машини . В 1936 р. А. Черч та С. Кліні довели співпадіння класів загально-рекурсивних та λ-означуваних функцій. На основі цього факту та аналізу ідей, які привели до вказаних понять, А. Черч висунув тезу про співпадіння класу АОФ з класом загальнорекурсивних функцій. С. Кліні узагальнив цю тезу для випадку часткових функцій. Доведене А. Тьюрінгом в 1937 р. співпадіння класів частково рекурсивних функцій та функцій, обчислюваних на машинах Тюрінга, стало ще одним підтвердженням тези Черча. Пізніше такі співпадіння були встановлені для всіх відомих формальних моделей АОФ. Тому є всі підстави вважати, що кожна із названих вище формальних моделей адекватно уточнює інтуїтивне поняття АОФ. Теорія алгоритмів виникла як розділ математичної логіки, поняття алгоритму тісно пов'язане з поняттям числення. Перші та найчисельніші застосування теорія алгоритмів має саме в математичній логіці. Теорія алгоритмів є теоретичним фундаментом програмування, вона має застосування всюди, де зустрічаються алгоритмічні проблеми.
- 计算理论和计算机有密切关系，解决哪些是能计算的、哪些是不能计算的（即可计算性理论）、有多快、要用多少存储 （即計算複雜性理論），以及采用什么计算模型的理论。其中的理论是现代密码协议、计算机设计和许多应用领域的基础。 計算理論的「計算」並非指純粹的算術運算（Calculation），而是指從已知的輸入透過算法來取得一個問題的答案（Computation），因此，計算理論屬於計算機科學和數學。 計算理論早於現代計算機發明前的20世紀便開始了。
|
| rdfs:comment
|
- The theory of computation is the branch of computer science and mathematics that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm. The field is divided into two major branches: computability theory and complexity theory, but both branches deal with formal models of computation. In order to perform a rigorous study of computation, computer scientists work with a mathematical abstraction of computers called a model of computation.
- Die Theoretische Informatik beschäftigt sich mit der Abstraktion, Modellbildung und grundlegenden Fragestellungen, die mit der Struktur, Verarbeitung, Übertragung und Wiedergabe von Informationen in Zusammenhang stehen.
- La teoría de la computación es una ciencia, en particular una rama de la matemática y de la computación que centra su interés en el estudio y definición formal de los cómputos. Se le llama cómputo a la obtención de una solución o resultado (generalmente en el sentido matemático/aritmético del término), a partir de ciertos datos o entradas utilizando para ello un proceso o algoritmo.
- Laskettavuus tai laskettavuusteoria on teoreettisen tietojenkäsittelytieteen haara, joka tutkii ongelmien ratkeavuutta ja ratkaisemisen tehokkuutta algoritmisesti. Käytännössä laskettavuusteoriassa pyritään selvittämään, voidaanko jokin ongelma ratkaista tietokoneiden avulla vai ei, ja jos voidaan, kuinka tehokkaasti. Tehokkuus voi tarkoittaa joko laskennan vaatimaa aikaa tai muistikapasiteettia.
- L'informatique théorique est l'étude des fondements logiques et mathématiques de l'informatique. Plus généralement, le terme est utilisé pour désigner des domaines ou sous-domaines de recherche centrés sur des vérités universelles en rapport avec l'informatique. L'informatique théorique se caractérise par une approche par nature plus mathématique et moins empirique de l'informatique et ses objectifs ne sont pas toujours directement reliés à des enjeux technologiques.
- L' Informatica teorica è un insieme di argomenti dell'informatica che si concentrano sugli aspetti più astratti e matematici della computazione, come la teoria della computazione. l'analisi degli algoritmi e la semantica della programmazione. Nonostante non abbia come oggetto un singolo argomento, i suoi ricercatori formano un gruppo distinto tra i ricercatori informatici.
- De theoretische informatica is een vorm van informatica die zich bezighoudt met formele talen (dwz. automaten-, berekenbaarheids- en complexiteitstheorie), logica en formele semantiek en biedt hiermee een theoretische fundering voor het maken van compilers van programmeertalen en de wiskundige formalisering van probleemstellingen. Ze is daarmee het formele fundament onder de informatica.
- Teoria obliczeń to dział informatyki teoretycznej. Dzieli się on na dwie główne części: teorię obliczalności oraz złożoność obliczeniową. Pierwszy z nich zajmuje się odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a drugi tym jak szybko da się to zrobić. Rozważania tego typu nie są możliwe bez formalnego, matematycznego modelu komputera. Najczęściej używanym modelem jest maszyna Turinga.
- Computação pode ser definida como a solução de um problema ou, formalmente, o cálculo de uma função, através de um algoritmo. A teoria da computação, um subcampo da ciência da computação e matemática, busca determinar quais problemas podem ser computados em um dado modelo de computação. Por milhares de anos, a computação foi feita com lápis e papel, ou giz e quadro, ou mentalmente, às vezes com a ajuda de tabelas.
- Hesap kuramı, problemlerin verilen bir hesap modeli üzerinde bir algoritma işletilerek çözülüp çözülemeyeceğini ve çözülebiliyorsa ne kadar verimle çözülebileceğini araştıran bilgisayar bilimi dalıdır. İki alt dala ayrılır: Hesaplanabilirlik kuramı ve hesap karmaşıklığı kuramı. Hesap sorununu eksiksiz bir şekilde inceleyebilmek için, bilgisayar bilimciler bilgisayarların hesap modeli denilen matematiksel soyutlamaları ile çalışırlar.
- Теорія алгоритмів (англ. Theory of computation) як окремий розділ математики, що вивчає загальні властивості алгоритмів, виникла в 30-х роках 20 століття. Алгоритми, проте, простежуються в математиці протягом всього часу її існування.
|
![[RDF Data]](/statics/sw-cube.png)
