miniatura|Un autòmat finit del camp de la teoria d'autòmats, una branca la informàtica teòrica La Informàtica teòrica és una divisió o subconjunt de la Informàtica i les Matemàtiques que se centra en els aspectes més abstractes o formals de la informàtica.
Aquesta divisió inclou l'Anàlisi d'algorismes i la Semàntica Formal dels llenguatges de programació. Hi ha més conjunts d'estudi a part d'aquests dos, els quals tenen diferents grups professionals i associacions d'estudi i revistes i congressos diferents.
Abast No és senzill circumscriure amb precisió les àrees d'aquesta teoria i el grup de treball Special Interest Group on Algorithms and Computation Theory (SIGACT) de l'ACM descriu la seva missió com la de promoure la informàtica teorica i notes.
El camp de la informàtica teòrica s'interpreta àmpliament de manera que inclou algoritme, estructures de dades, Complexitat computacional, computació distribuïda, computació paral·lela, circuit integrat a molt gran escala, aprenentatge automàtic, Biologia computacional, Geometria computacional, Teoria de la informació, Criptografia, Computació quàntica, Teoria de nombres, Àlgebra computacional, Semàntica formal, Mètodes Formals, Teoria de la computabilitat i l'estudi de l'Atzar. Aquestes tasques es distingeixen pel seu èmfasi en tècniques matemàtiques i el rigor matemàtic.
A aquesta llista, la revista “Transactions on Computation Theory” de l'ACM hi afegeix la Teoria de codis, Aprenentatge de computadors i aspectes teòrics de parts de la informàtica tals com bases de dades, Recuperació d'Informació, models econòmics i de xarxes. Tot i l'ampli ventall que abasta aquesta disciplina, els especialistes en aquest camp es diferencien ells mateixos dels especialistes més aplicats. Ells mateixos sovint es defineixen com que fan la ciència més fonamental que hi ha sota la Informàtica.
96px|Teoria d'autòmats 96px|Teoria de nombres 96px|Teoria de grafs Lògica Matemàtica Teoria d'Autòmats Teoria de Nombres Teoria de Grafs 96px|Teoria de Categories 96px|Geometria Computacional 96px|Computació Quàntica Teoria de Tipus Teoria de Categories Geometria Computacional Computació Quàntica
Història Tot i que algorismes han existit des de fa segles (l'Algorisme d'Euclides per determinar el Màxim comú divisor de dos nombres encara s'usa en informàtica), no va ser fins al 1936 que Alan Turing, Alonzo Church i Stephen Kleene van formalitzar la definició d'algorisme en termes de computabilitat. Mentre que el sistema binari de numeració i els Sistemes Formals han existit abans de 1703, és llavors quan Gottfried Leibniz va formalitzar la lògica amb valors binaris de “cert” o “fals”. Tot i que la inferència lògica i les demostracions matemàtiques han existit des de temps antics, fins al 1931 Kurt Gödel no va provar amb el seu Teorema d'incompletesa de Gödel que hi havia limitacions fonamentals en afirmacions que, inclús sent veritat, poden o no ser provades.
Aquests esdeveniments han portat a l'estudi modern de la lògica i la computabilitat, i de fet el camp de les ciències de la computació teòrica en conjunt. La Teoria de la informació va ser introduït en el camp el 1948 amb una teoria matemàtica de la computació feta per Claude Shannon. A la mateixa dècada, Donald Hebb va introduir el concepte matemàtic d'aprenentatge del cervell. Amb les dades biològiques que sustenten aquesta hipòtesi i algunes modificacions es van establir els camps de la xarxa neuronal i processament paral·lel distribuït.
Amb el desenvolupament de la Mecànica quàntica a inicis del va introduir el concepte que múltiples operacions matemàtiques es poden fer en una funció d'ona d'una partícula. En altres paraules, es poden calcular funcions en diferents estats simultàniament. Això porta cap al concepte d'Ordinador quàntic a les darreries del , quan Peter Shor a la dècada del 1990 va demostrar que aquests mètodes es podrien usar per a la factorització de grans nombres en temps polinòmic, la qual cosa, si s'implementés, ocasionara que la majoria de la criptografia de clau pública fos insegura.
Temes Algorismes
Un algorisme és un procediment pas a pas per realitzar càlculs. Els algorismes s'utilitzen en el càlcul, en el processament de dades i en el raonament automatitzat.
Un algorisme és un mètode eficaç expressat com una llista finita"Cualquier algoritmo matemático clásico, por ejemplo, puede describirse en un número finito de palabras en inglés". Pàgina 2. d'instruccions ben definidesBien definidas con respecto al agente que ejecuta el algoritmo: "Hay un agente informático, normalmente humano, que puede reaccionar a las instrucciones y llevar a cabo los cálculos" . per calcular una funció."un algoritmo es un procedimiento para calcular una función (con respecto a alguna notación elegida para números enteros) . .. esta limitación (a funciones numéricas) resulta en ninguna pérdida de generalidad",. Partint d'un estat inicial i una entrada inicial (potser buida),"Un algoritmo tiene cero o más entradas, es decir, cantidades que se le dan inicialmente antes de que comience el algoritmo" (Knuth 1973:5). les instruccions descriuen un càlcul que, quan s'executa, procedeix a través d'un nombre finit"Un procedimiento que tiene todas las características de un algoritmo excepto que posiblemente carece de finitud puede llamarse un 'método computacional'" (Knuth 1973:5). d'estats successius ben definits, produint eventualment una "sortida", o resultat"Un algoritmo tiene una o más salidas, es decir, cantidades que tienen una relación especificada con las entradas" (Knuth 1973:5). i acabant en un estat final. La transició d'un estat al següent no és necessàriament determinista; alguns algorismes, coneguts com algorismes aleatoris, incorporen entrades aleatòries.Si un procés amb processos interiors aleatoris (sense incloure l'entrada) és o no un algorisme és discutible. Rogers opina que "un còmput es du a terme d'una manera discreta pas a pas, sense l'ús de mètodes continus o dispositius analògics... es du a terme de manera determinista, sense recórrer a mètodes o dispositius aleatoris, per exemple, daus" .
Teoria d'autòmats
La teoria d'autòmats és l'estudi de les màquines abstractes i dels autòmats, així com dels problemes computacionals que poden resoldre's utilitzant-los. És una teoria de la informàtica teòrica, dins de la matemàtica discreta (una secció de les matemàtiques i també de la informàtica). La paraula autòmat prové de la paraula grega αὐτόματα que significa "que actua per si mateix".
La teoria d'autòmats és l'estudi de màquines virtuals autooperatives per a ajudar en la comprensió lògica del procés d'entrada i sortida, sense o amb etapes intemèdies de computació (o qualsevol funció o procés).
Teoria de la codificació
La teoria de la codificació és l'estudi de les propietats dels codis i la seva adequació a un aplicació específica. Els codis s'utilitzen en la compressió de dades, en la criptografia, en la correcció d'errors i, més recentment, també en la cofificació de xarxes. Els codis s'estudien en divereses disciplines científiques, com la teoria de la informació, l'enginyeria elèctrica, les matemàtiques i la informàtica, amb l'objectiu de dissenyar mètodes de transmissió de dades eficients i fiables. Això sol simplificar l'eliminació de redundàncies i la correcció (o detecció) d'errors en les dades transmeses.
Biologia computacional
La biologia computacional implica el desenvolupament i l'aplicació de mètodes teòrics i d'anàlisi de dades, modelatge matemàtic i tècniques de simulació computacional en l'estudi de sistemes biològics, conductuals i socials. El camp està àmpliament definit i inclou fonament de la informàtica, de les matemàtiques aplicades, de l'animació, de l'estadística, de la bioquímica i de la química, de la biofísica, de la biologia molecular, de la genètica i de la genòmica, de l'ecologia, de l'evolució, de l'anatomia, de la neurociència i de la visualització científica.
La biologia computacional és diferent de la computació biològica, que és un subcamp de la informàtica i de l'enginyeria informàtica que utilitza la bioenginyeria i la biologia per construir ordinadors, però és similar a la bioinformàtica, que és una ciència interdisciplinar que utilitza ordinadors per emmagatzemar i processar dades biològiques.
Teoria de la complexitat computacional
La teoria de la complexitat computacional és una branca de la teoria de la computació centrada en classificar els problemes computacionals segons la seva dificulatat inherent, i en relacionar aquestes classes entre sí. S'entén per problema computacional una tasca que en principi és susceptible a ser resolta per un ordinador, la qual cosa equival a afirmar que el problema pot resoldre's mitjançant l'aplicació mecànica de passos matemàtics, com un algorisme.
Es considera que un problema és intrínsecament difícil si la seva solució requereix recursos significatius, sigui quin sigui l'algorisme emprat. La teoria formalitza aquesta intuïció, introduint models matemàtics de computació per tal d'estudiar aquests problemes i quantificant la quantitat de recursos necessaris per resoldre'ls, com el temps i l'emmegatzematge requerits. També s'utilitzen altres mètriques de complexitat, com la quantitat de comunicació (utilitzada en complexitat dels circuits) i el nombre de processadors (utilitzats en computació paral·lela). Una de les funcions de la teoria de la complexitat computacional és determinar els límits pràctics d'allò que els ordinadors poden i no poden fer.
Geometria computacional
La geometria computacional és una branca de la informàtica dedicada a l'estudi dels algorismes que poden enunciar-se en termes de geometria. Alguns problemes purament geomètrics sorgeixen de l'estudi d'algorismes geomètrics computacionals, i també es consideren tals problemes part de la geometria computacional.
El principal impuls en el desenvolupament de la geometria computacional com a disciplina va ser el progrés en els gràfics per ordinador i el disseny i la fabricació assistits per ordinador (DAO i FAO), però motls problemes de geometria computacional són de naturalesa clàssica, i poden provenir de la visualització matemàtica.
Altres aplicacions importants de la geometria computacional són la robòtica (planificació del moviment i problemes de visibilitat), els sistema d'informació geogràfica o SIG (localització i recerca geomètrica, planificació de rutes), el disseny de circuits integrats (disseny i verificació de la geometria d'un CI), l'enginyeria assistida per ordinador o CAE, per les seves sigles en anglès (generació de malles) i la visió per ordinador (reconstrucció 3D).
Teoria de l'aprenentatge computacional Els resultats teòrics en l'aprenentatge automàtic fan referència principalment a un tipus d'aprenentatge inductiu anomenat aprenentatge supervisat. En l'aprenentatge supervisat, un algorisme rep mostres etiquetades d'alguna manera útil. Per exemple, les mostres poden ser descripcions de boles i les etiquetes poden ser si els bolets són comestibles o no. L'algorisme pren aquestes mostres prèviament etiquetades i les utilitza per induir un classificador. Aquest classificador és una funció que assigna etiquetes a les mostres, incloses les mostres que l'algorisme no ha vist prèviament. L'objectiu de l'algorisme d'aprenentatge supervisat és optimitza alguna mètrica de rendiment, com minimitzar el nombre d'errors comesos en mostres noves.
Teoria computacional de nombres La teoria de nombres computacional, també coneguda com a teoria algorísmica de nombres, és l'estudid d'algorismes per realitza teoria de nombres i càlcul. El problema més conegut d'aquest camp és la factorització dels enters.
Criptografia