Informàtica teòrica
divisió o subconjunt de les ciències de computació i matemàtiques From Wikipedia, the free encyclopedia
Remove ads
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.
Remove ads
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.[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]
|
 |
 | |
| Lògica Matemàtica | Teoria d'Autòmats | Teoria de Nombres | Teoria de Grafs |
 |
 |
 | |
| Teoria de Tipus | Teoria de Categories | Geometria Computacional | Computació Quàntica |
Remove ads
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 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.
Remove ads
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[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
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.[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
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
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.
Remove ads
Organitzacions
- European Association for Theoretical Computer Science
- SIGACT
Revistes
Plantilla:Unreferenced section
- Information and Computation
- Theory of Computing (open access journal)
- 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 (open access journal)
- Foundations and Trends in Theoretical Computer Science
- Journal of Automata, Languages and Combinatorics
- Acta Informatica
- Fundamenta Informaticae
- ACM Transactions on Computation Theory
- ACM Transactions on Algorithms
- Information Processing Letters
Remove ads
Conferències
- Annual ACM Symposium on Theory of Computing (STOC)[16]
- Annual IEEE Symposium on Foundations of Computer Science (FOCS)[16]
- ACM–SIAM Symposium on Discrete Algorithms (SODA)[16]
- Annual ACM Symposium on Computational Geometry (SoCG)[17]
- International Colloquium on Automata, Languages and Programming (ICALP)[17]
- Symposium on Theoretical Aspects of Computer Science (STACS)[17]
- European Symposium on Algorithms (ESA)[17]
- IEEE Symposium on Logic in Computer Science (LICS)[16]
- International Symposium on Algorithms and Computation (ISAAC)[17]
- Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)[17]
- Workshop on Randomization and Computation (RANDOM)[17]
- Computational Complexity Conference (CCC)[17]
- ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)[17]
- ACM Symposium on Principles of Distributed Computing (PODC)[16]
Remove ads
Vegeu també
Notes
Bibliografia
Enllaços externs
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads