Viquipèdia

Informàtica teòrica

divisió o subconjunt de les ciències de computació i matemàtiques

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.

Un autòmat finit del camp de la teoria d'autòmats, una branca la informàtica teòrica

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

modifica

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.[1]

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.[2] 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.[3]

Teoria d'autòmats Teoria de nombres Teoria de grafs
Lògica Matemàtica Teoria d'Autòmats Teoria de Nombres Teoria de Grafs
Teoria de Categories Geometria Computacional Computació Quàntica
Teoria de Tipus Teoria de Categories Geometria Computacional Computació Quàntica

Història

modifica

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 segle xx 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 segle xx, 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

modifica

Algorismes

modifica

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[4] d'instruccions ben definides[5] per calcular una funció.[6] Partint d'un estat inicial i una entrada inicial (potser buida),[7] les instruccions descriuen un càlcul que, quan s'executa, procedeix a través d'un nombre finit[8] d'estats successius ben definits, produint eventualment una "sortida", o resultat[9] 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.[10]

Teoria d'autòmats

modifica

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ó

modifica

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

modifica

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.[11] 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.[12]

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

modifica

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

modifica

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

modifica

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

modifica

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

modifica

La criptografia és la pràctica i l'estudi de tècniques per a la comunicació segura en presència de tercers (anomeneats adversaris).[13] En termes més generals, es tracta de construir i analitzar protocols que superin la influència dels adversaris[14] i que estan relacionats amb diversos aspectes en seguretat de la informació com la confidencialitat de les dades, la integritat de dades, l'autenticació i el no repudi.[15] La criptografia moderna avarca les disciplines de les matemàtiques, la informàtica i l'enginyeria elèctrica. Les aplicacions de la criptografia inclouen els caixers automàtics, les contrasenyes i el comerç electrònic.

La criptografia moderna es basa en gran manera en la teoria matemàtica i la pràctica de la informàtica; es dissenyen els algorismes criptogràfics al voltant de supòsits de duresa computacional, la qual cosa fa que tals alforismes siguin difícils de trencar en la pràctica per cap adversari. En teoria, és possible trencar un sistema d'aquest tipus, però és inviable fer-ho per qualsevol mitjà pràctic conegut. Els avençps teòrics, com les millores en els algorismes de factorització dels enters, i l'acceleració de la tecnologia informàtica obliguen a adaptar contínuament aquestes solucions. Existeixen esquemes de d'informació teòricament segura que no poden trencar-se inclús amb una potència de càlcul il·limitada -un exemple és el bloc d'un sol ús- però aquests esquemes són més difícils d'implementar que els millors mecanismes teòricament trencables però computacionalment segurs.

Organitzacions

modifica

Revistes

modifica

Conferències

modifica

Vegeu també

modifica

Notes

modifica
  1. ↑ «SIGACT». [Consulta: 29 març 2009].
  2. ↑ «ToCT». [Consulta: 9 juny 2010].
  3. ↑ «Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing». [Consulta: 29 març 2009].
  4. ↑ "Cualquier algoritmo matemático clásico, por ejemplo, puede describirse en un número finito de palabras en inglés". Rogers, Hartley Jr. Teoría de las funciones recursivas y computabilidad efectiva. McGraw-Hill, 1967. Pàgina 2.
  5. ↑ Bien 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" (Rogers 1967, p. 2).
  6. ↑ "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",(Rogers 1967, p. 1).
  7. ↑ "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).
  8. ↑ "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).
  9. ↑ "Un algoritmo tiene una o más salidas, es decir, cantidades que tienen una relación especificada con las entradas" (Knuth 1973:5).
  10. ↑ 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" (Rogers 1967, p. 2).
  11. ↑ «Definición de trabajo de los NIH sobre bioinformática y biología computacional». Iniciativa de Ciencia y Tecnología de la Información Biomédica, 17-07-2000. Arxivat de l'original el 5 de septiembre de 2012. [Consulta: 18 agost 2012].
  12. ↑ «Acerca del CCMB». Centro de Biología Molecular Computacional.. [Consulta: 18 agost 2012].
  13. ↑ Rivest, Ronald L. «Criptología». A: J. Van Leeuwen. Handbook of Theoretical Computer Science. 1. Elsevier, 1990.
  14. ↑ Bellare, Mihir; Rogaway, Phillip. «Introducción». A: Introducción a la Criptografía Moderna, 21 de septiembre de 2005, p. 10.
  15. ↑ Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A.. Handbook of Applied Cryptography, 1997. ISBN 978-0-8493-8523-0.
  16. 1 2 3 4 5 The 2007 Australian Ranking of ICT Conferences Arxivat 2009-10-02 a Wayback Machine.: tier A+.
  17. 1 2 3 4 5 6 7 8 9 The 2007 Australian Ranking of ICT Conferences Arxivat 2009-10-02 a Wayback Machine.: tier A.

Bibliografia

modifica

Enllaços externs

modifica
A Wikimedia Commons hi ha contingut multimèdia relatiu a: Informàtica teòrica
Obtingut de «https://ca.wikipedia.org/w/index.php?title=Informàtica_teòrica&oldid=37051814»