Ciència computacional teòrica

Ciència computacional teòrica

Les ciències de la computació teòrica o informàtica teòrica (en anglés, theoretical computer science, abreviat TCS) constituïxen una branca de les ciències de la computació i les matemàtiques que se centra en els fonaments formals de la computació, incloent models abstractes, algoritmes i estructures matemàtiques subjacents als sistemes computacionals.

Entre les seues àrees principals es troben l'anàlisis d'algoritmes, la teoria d'autómates, la teoria de la computació, la semàntica formal de llenguages de programació, la teoria de la complexitat computacional i la llògica matemàtica aplicada a l'informàtica. Estes disciplines exploren qüestions com l'eficiència dels algoritmes, els llímits de lo computable i les propietats formals dels llenguages de programació.

L'informàtica teòrica es caracterisa pel seu enfocament rigorós i abstracte, a sovint amprant ferramentes de la matemàtica discreta, la llògica, la teoria de grafos i la combinatòria. A lo llarc de les décades, ha donat lloc a alvanços significatius en diverses aplicacions, des del disseny de compiladors fins a la criptografia i l'inteligència artificial.

Numeroses associacions científiques i conferències especialisades, com l'ACM Symposium on Theory of Computing (STOC) i l'IEEE Symposium on Foundations of Computer Science (FOCS), reunixen a investigadors de l'àrea per a la difusió de resultats i el debat acadèmic.

Àmbit

No és fàcil circumscriure les àrees de teoria precisament. El Special Interest Group on Algorithms and Computation Theory (SIGACT) de l'ACM descriu a la seua missió com la promoció de les ciències de la computació teòrica i nota:

El camp de les ciències de la computació teòrica és interpretat àmpliament per a incloure algoritmes, estructures de senyes, teoria de la complexitat computacional, computació distribuïda, computació paralela, VLSI, aprenentage de màquina, biologia computacional, geometria computacional, teoria de l'informació, criptografia, computació quàntica, teoria computacional de números i àlgebra, semàntica de programa i verificació, teoria d'autómates i l'estudi de l'aleatorietat. A sovint el treball en este camp és distinguit pel seu émfasis en la tècnica i rigor matemàtics.

A esta llista, revista Transactions on Computation Theory de la ACM agrega teoria de la codificació, teoria de l'aprenentage computacional i aspectes de ciències de la computació teòrica d'àrees tals com bases de senyes, recuperació d'informació, models econòmics i rets. A pesar d'esta amplitut, la "gent de teoria" en ciències de la computació s'identifica a sí mateixa com a diferent de la "gent d'aplicacions". Alguns es caracterisen com fent la "(més fonamental) 'ciència' subjacent en el camp de la computació". Una atra "gent de teoria aplicada" sugerix que és impossible separar teoria i aplicació. Açò significa, que la cridada "gent de teoria" usa regularment science experimental feta en àrees menys teòriques com a investigació de sistema de software. Açò també significa, que existix una cooperació més que una competència mútuament excloent entre la teoria i aplicació.

$P\to Q$	Archiu:Caps block 10 Aexample.svg	Archiu:Elliptic curve simple.png	Archiu:6n-graf.svg
Llògica matemàtica	Teoria d'autómates	Teoria de números	Teoria de grafos
$\Gamma ⊢x:Int$	Archiu:Commutative diagram for morphism.svg	Archiu:SimplexRangeSearching.png	Archiu:Blochsphere.svg
Teoria de tipos	Teoria de categories	Geometria computacional	Teoria de computació quàntica

Història

Artícul principal → Història de les ciències de la computació.

Mentres que els algoritmes formals han existit durant milenis (en computació encara s'usa l'algoritme de Euclides per a determinar el màxim comú divisor de dos números), no va ser sino fins a 1936 que Alan Turing, Alonzo Church i Stephen Kleene varen formalisar la definició d'un algoritme en térmens de computació. Mentres que els sistemes binario i llògic de les matemàtiques havien existit abans de 1703, quan Gottfried Leibniz va formalisar la llògica en els valors binarios per a verdader i fals. Mentres que l'inferència llògica i prova matemàtica havien existit en l'antiguetat, en 1931 Kurt Gödel va demostrar en la seua teorema de incompletitud que va haver llimitacions fonamentals sobre quines sentències, inclús si verdaderes, podrien provar-se.

Estos desenrolls han dut als estudis moderns de la llògica i computabilidad, i de fet al camp de les ciències de la computació teòrica com un tot. La teoria de l'informació va ser agregada al camp en una teoria matemàtica de 1948 sobre la comunicació per Claude Shannon. En la mateixa década, Donald Hebb va introduir un model matemàtic d'aprenentage en el cervell. En montage de senyes biològiques soportant esta hipòtesis en algunes modificacions, varen ser establits els camps de rets neuronals i processament distribuït paralel.

En el desenroll de la mecànica quàntica al principi de el XX va aplegar el concepte que operacions matemàtiques pogueren ser realisades en una funció d'ona d'una partícula. En atres paraules, es podrien calcular funcions en varis Estats simultàneament. Açò va dur al concepte d'un ordenador quàntic en la segona mitat de el XX que va desapegar en la década de 1990 quan Peter Shor va demostrar que tals métodos podrien utilisar-se per a factorizar números grans en temps polinòmic, lo que, si s'apliquen, faria més moderns sistemes de criptografia de clau pública inútilment insegura.

Investigació de ciències de la computació teòrica moderna es basa en estos desenrolls bàsics, pero inclou molts atres problemes matemàtics i interdisciplinaris que han segut plantejats.

Temes

Algoritmes

Artícul principal → Algoritme.

Un algoritme és un procediment passe a pas per a realisar càlculs. Els algoritmes s'utilisen para càlcul, processament de senyes i raonament automatizado.

Un algoritme és un método eficaç expressat com una llista finita d'instruccions ben definides per a calcular una funció. Partint d'un estat inicial i una entrada inicial (potser buida), les instruccions descriuen un càlcul que, quan s'eixecuta, procedix a través d'un finito número d'estats successius ben definits, produint finalment una "eixida" i terminant en un estat final. La transició d'un estat al següent no és necessàriament determinista; alguns algoritmes, coneguts com algoritmes aleatoris, incorporen entrades aleatòries.

Teoria autómata

Artícul principal → Teoria d'autómates.

Teoria d'autómates és l'estudi de màquina abstracta i autómata, aixina com dels problemes computacionals que poden resoldre's usant-los. És una teoria de l'informàtica teòrica, dins de la matemàtica discreta (una secció de les matemàtiques i també de l'informàtica). Autómata ve de la paraula grega αὐτόματα que significa "que actua per sí mateixa".

La Teoria d'Autómates és l'estudi de màquines virtuals autooperativas per a ajudar en la comprensió llògica del procés d'entrada i eixida, sense o en etapa(s) intermija(s) de computació (o qualsevol funció/procés).

Teoria de la codificació

Artícul principal → Teoria de la codificació.

Teoria de la codificació és l'estudi de les propietats dels còdics i la seua adequació a una aplicació específica. Els còdics s'utilisen para compressió de senyes, criptografia, correcció d'errors i, més recentment, també para codificació de rets. Els còdics s'estudien en diverses disciplines científiques, com la teoria de l'informació, l'ingenieria elèctrica, les matemàtiques i l'informàtica, en la finalitat de dissenyar métodos de transmissió de senyes eficients i fiables. Açò sol implicar l'eliminació de redundància i la correcció (o detecció) d'errors en les senyes transmeses.

Biologia computacional

Artícul principal → Biologia computacional.

Biologia computacional implica el desenroll i l'aplicació de métodos teòrics i d'anàlisis de senyes, modelació matemàtica i tècniques de simulació computacional a l'estudi de sistemes biològics, conductuales i socials. El camp està àmpliament definit i inclou fonaments d'informàtica, matemàtiques aplicades, animació, estadística, bioquímica, química, biofísica, biologia molecular, genètica, genómica, ecologia, evolució, anatomia, neurociencia i visualisació.

La biologia computacional és diferent de la computació biològica, que és un subcampo de l'informàtica i l'ingenieria informàtica que utilisa la bioingeniería i la biologia per a construir ordenadors, pero és similar a la bioinformática, que és una ciència interdisciplinar que utilisa ordenadors per a almagasenar i processar senyes biològiques.

Teoria de la complexitat computacional

Artícul principal → Teoria de la complexitat computacional.

La Teoria de la complexitat computacional és una branca de la Teoria de la computació que se centra en classificar els problemes computacionals segons la seua dificultat inherent, i en relacionar eixes classes entre sí. S'entén per problema computacional una tasca que en principi és susceptible de ser resolta per un ordenador, lo que equival a afirmar que el problema pot resoldre's per mig de l'aplicació mecànica de passos matemàtics, com un algoritme.

Es considera que un problema és intrínsecament difícil si la seua solució requerix recursos significatius, siga com siga l'algoritme utilisat. La teoria formalisa esta intuïció, introduint models matemàtics de computació per a estudiar estos problemes i quantificant la cantitat de recursos necessaris per a resoldre'ls, com el temps i l'almagasenament. També s'utilisen atres mides de complexitat, com la cantitat de comunicació (utilisada en complexitat de la comunicació), el número de comportes en un circuit (utilisat en complexitat dels circuits) i el número de processadors (utilisat en computació paralela). Una de les funcions de la teoria de la complexitat computacional és determinar els llímits pràctics de lo que els ordenadors poden i no poden fer.

Geometria computacional

Artícul principal → Geometria computacional.

Geometria computacional és una branca de l'informàtica dedicada a l'estudi d'algoritmes que poden enunciar-se en térmens de geometria. Alguns problemes purament geomètrics sorgixen de l'estudi d'algoritmes geomètrics computacionals, i dits problemes també es consideren part de la geometria computacional.

El principal impuls per al desenroll de la geometria computacional com a disciplina va ser el progrés en gràfics per ordenador i disseny i fabricació assistits per ordenador (CAD/CAM), pero molts problemes de geometria computacional són de naturalea clàssica, i poden provindre de la visualisació matemàtica.

Atres aplicacions importants de la geometria computacional són la robòtica (planificació del moviment i problemes de visibilitat), els sistemes d'informació geogràfica (SIG) (localisació i busca geomètrica, planificació de rutes), el disseny de circuits integrats (disseny i verificació de la geometria de CI), l' ingenieria assistida per ordenador (CAE) (generació de malles), la visió per ordenador (reconstrucció 3D).

Teoria de l'aprenentage computacional

Els resultats teòrics en l'aprenentage automàtic es referixen principalment a un tipo d'aprenentage inductivo cridat aprenentage supervisat. En l'aprenentage supervisat, un algoritme rep mostres etiquetades d'alguna manera útil. manera útil. Per eixemple, les mostres poden ser descripcions de bolets, i les etiquetes poden ser si els bolets són comestibles o no. L'algoritme pren estes mostres prèviament etiquetades i les utilisa per a induir un classificador. les utilisa per a induir un classificador. Este classificador és una funció que assigna etiquetes a les mostres, incloses les mostres que l'algoritme mai ha vist prèviament. L'objectiu de l'algoritme d'aprenentage supervisat és optimisar alguna mida de rendiment, com minimisar el número d'errors comesos en mostres noves.

Teoria computacional de números

Artícul principal → Teoria de números computacional.

Teoria de números computacional, també coneguda com a teoria algorítmica de números, és l'estudi d'algoritmes per a realisar teoria de números càlcul. El problema més conegut en este camp és la factorización de sancers.

Criptografia

Artícul principal → Criptografia.

Criptografia és la pràctica i l'estudi de tècniques para comunicació segura en presència de tercers (cridats adversaris). En térmens més generals, es tracta de construir i analisar protocols que superen l'influència dels adversaris i que estan relacionats en diversos aspectes en seguritat de l'informació com la confidencialitat de les senyes integritat de senyes, autenticació i no repudie. La criptografia moderna comprén les disciplines de matemàtiques, informàtica i ingenieria elèctrica. Les aplicacions de la criptografia inclouen targetes ATM, contrasenyes informàtiques i comerç electrònic.

La criptografia moderna es basa en gran mida en la teoria matemàtica i la pràctica de l'informàtica; els algoritmes criptográficos es dissenyen entorn a suposts de durea computacional, lo que fa que dits algoritmes siguen difícils de trencar en la pràctica per qualsevol adversari. En teoria, és possible trencar un sistema d'este tipo, pero és inviable fer-ho per qualsevol mig pràctic conegut. Els alvanços teòrics, com les millores en els algoritmes de factorización de sancers, i l'acceleració de la tecnologia informàtica obliguen a adaptar contínuament estes solucions. Existixen esquemes d'informació teòricament segura que no poden trencar-se inclús en una potència de càlcul illimitada -un eixemple és la llibreta d'un sol us- pero estos esquemes són més difícils d'implementar que els millors mecanismes teòricament rompibles pero computacionalment segurs.

Organisacions

• European Association for Theoretical Computer Science
• SIGACT

Revistes i bolletins

• Information and Computation
• Theory of Computing (Revista open access)
• Formal Aspects of Computing
• Journal of the ACM
• SIAM Journal on Computing (SICOMP)
• SIGACT News
• Theoretical Computer Science
• Theory of Computings Systems
• International Journal of Foundations of Computer Science
• Chicago Journal of Theoretical Computer Science (Revista open access)
• Foundations and Trends in Theoretical Computer Science
• Journal of Automata, Languages and Combinatorics
• Acta Informatica
• Fonamenta Informaticae
• ACM Transactions on Computation Theory
• ACM Transactions on

Algorithms * Information Processing Letters

Conferències

• Annual ACM Symposium on Theory of Computing (STOC)
• Annual IEEE Symposium on Foundations of Computer Science (FOCS)
• ACM–SIAM Symposium on Discrete Algorithms (SODA)

• Annual ACM Symposium on Computational Geometry (SoCG)
• International Colloquium on Automata, Languages and Programming (ICALP)
• Symposium on Theoretical Aspects of Computer Science (STACS)
• European Symposium on Algorithms (ESA)
• IEEE Symposium on Logic in Computer Science (LICS)
• International Symposium on Algorithms and Computation (ISAAC)
• Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)
• Workshop on Randomization and Computation (RANDOM)
• Computational Complexity Conference (CCC)
• ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
• ACM Symposium on Principles of Distributed Computing (PODC)

Llectura adicional

• Martin Davis, Ron Sigal, Elaine J. Weyuker, Computability, complexity, and languages: fundamentals of theoretical computer science, 2nd ed., Academic Press, 1994, ISBN 0-12-206382-1. Covers theory of computation, but also program semantics and quantification theory. Aimed at graduate students.

Vore també

• Ciència formal
• Problemes no resolts en ciències de la computació

Enllaços externs

• SIGACT directory of additional theory links
• Theory Matters Wiki Theoretical Computer Science (TCS) Advocacy Wiki
• ^{[enllaç trencat]}
• List of academic conferences in the area of theoretical computer science at confsearch
• Theoretical Computer Science - StackExchange, a Question and Answer site for researchers in theoretical computer science
• Computer Science Animated
• http://theory.csail.mit.edu/ Massachusetts Institute of Technology