Teoria de la computació: diferència entre les revisions

 

=== Teoria d'autòmats ===

Aquesta teoria proveeix models matemàtics que formalitzen el concepte d'ordinador o algorisme de manera prou simplificada i general perquè es puguin analitzar les seves capacitats i limitacions.<ref>{{ref-web |url=https://cs.stanford.edu/people/eroberts/courses/soco/projects/2004-05/automata-theory/basics.html |consulta=15 octubre 2021 |títol=Basics of Automata Theory |editor=Stanford Computer Science |llengua=anglès}}</ref> Alguns d'aquests models tenen un paper central en diverses aplicacions de les ciències de la computació, incloent processament de text, [[compilador]] és, disseny de maquinari i [[intel·ligència artificial]].

 

 

=== Teoria de la computabilitat ===

Aquesta teoria explora els límits de la possibilitat de solucionar problemes mitjançant algorismes. Gran part de les ciències computacionals estan dedicades a resoldre problemes de forma algorítmica, de manera que el descobriment de problemes impossibles és una gran sorpresa. La teoria de la computabilitat és útil per no tractar de resoldre algorítmicament aquests problemes, estalviant així temps i esforç.

 

 

=== Teoria de la complexitat computacional ===

Tot i que un problema sigui computable, potser no sigui possible resoldre en la pràctica si es requereix molta memòria o [[temps d'execució]]. La teoria de la complexitat computacional estudia les necessitats de memòria, temps i altres recursos computacionals per resoldre problemes, d'aquesta manera és possible explicar perquè uns problemes són més difícils de resoldre que altres. Un dels majors èxits d'aquesta branca és un la classificació de problemes, anàleg a la taula periòdica, d'acord amb la seva dificultat, en aquesta classificació els problemes se separen per [[Tipus de complexitat|classes de complexitat]].