Teoria de la computació: diferència entre les revisions
Contingut suprimit Contingut afegit
m Enllaços a Google Llibres en català |
m Format |
||
Línia 1:
La '''teoria de la computació''' és una [[ciència]], en particular una branca de la [[matemàtica]] i de la [[Ciències de la computació|computació]] que tracta de quins problemes es poden resoldre en un model de càlcul, mitjançant un algorisme, de quina manera es poden resoldre de manera eficient o en quin grau (per exemple, les solucions aproximades enfront de les precises). El camp es divideix en tres grans branques: teoria dels autòmats i llenguatges formals, teoria de la computabilitat i teoria de la complexitat computacional, que es relacionen amb la pregunta: "Quines són les capacitats i limitacions fonamentals dels ordinadors?".<ref>{{ref-llibre|autor=Michael Sipser |any=2013 |títol=Introduction to the Theory of Computation 3rd |citació=central areas of the theory of computation: automata, computability, and complexity |pàgines=1 |editorial=Cengage Learning |isbn=978-1-133-18779-0|enllaçautor=Michael Sipser |llengua=anglès}}</ref>
Per tal de realitzar un estudi rigorós de la computació, els informàtics treballen amb una abstracció matemàtica dels ordinadors anomenada model de computació. Hi ha diversos models en ús, però el més freqüentment examinat és la [[màquina de Turing]].<ref>{{ref-llibre|nom=Andrew |cognom=Hodges |enllaçautor=Andrew Hodges |any=2012 |títol=Alan Turing: The Enigma |editorial=[[Princeton University Press]] |isbn=978-0-691-15564-7|edició=The Centenary |llengua=anglès}}</ref> perquè és senzilla de formular, es pot analitzar i utilitzar per demostrar resultats i perquè representa el que molts consideren el model de càlcul "raonable" més potent possible.<ref>{{cite video |last=Rabin |first=Michael O. |author-link=Michael O. Rabin |title=Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View |date= juny 2012 |url=http://videolectures.net/turing100_rabin_turing_church_goedel/
== Història ==
| |||