Taula de continguts
28 les relacions: Andrei Kolmogórov, Bit, Compressió de dades, Constant de Chaitin, Distribució uniforme discreta, Efecte Mateu, Entropia, Entropia de Shannon, Estructura de dades, Funció computable, Gregory Chaitin, Intèrpret (informàtica), Lisp, Màquina universal de Turing, Navalla d'Occam, Nombre de Gödel, Nombre natural, Notació de Landau, Pascal (llenguatge de programació), Principi de les caselles, Probabilitat bayesiana, Problema de la parada, Programa informàtic, Quod erat demonstrandum, Reducció a l'absurd, Sistema formal, Teoria Algorísmica de la Informació, Turing complet.
Andrei Kolmogórov
fou un matemàtic rus, preeminent en el, que va avançar diversos camps científics (entre ells la teoria de probabilitats, la topologia, la lògica intuïcionista, les turbulències, la mecànica clàssica i la complexitat computacional).
Veure Complexitat de Kolmogórov і Andrei Kolmogórov
Bit
Un bit —simbolitzat habitualment com a b, de l'anglès, binary digit, "dígit binari"— és la unitat d'informació mínima utilitzada en Informàtica i en teoria de la informació.
Veure Complexitat de Kolmogórov і Bit
Compressió de dades
La compressió de dades, aplicada al món de la informàtica, consisteix en el procés de codificació de dades utilitzant el mínim nombre possible de bits, o unitats d'informació.
Veure Complexitat de Kolmogórov і Compressió de dades
Constant de Chaitin
En complexitat computacional, la constant de Chaitin o nombre Omega de Chaitin o probabilitat de parada és, de forma informal, la probabilitat de que un programa escrit al atzar aturi correctament una màquina de Turing determinista.
Veure Complexitat de Kolmogórov і Constant de Chaitin
Distribució uniforme discreta
La distribució uniforme discreta és una distribució de probabilitat sobre un conjunt finit de punts als quals els assigna la mateixa probabilitat.
Veure Complexitat de Kolmogórov і Distribució uniforme discreta
Efecte Mateu
El model de disc de Poincaré es diu així malgrat haver estat obra d'Eugenio Beltrami, en un exemple d'efecte Mateu L′efecte Mateu és la denominació sociològica d'un fenomen d'acumulació injusta de bens, riquesa, reconeixement, prestigi o reputació.
Veure Complexitat de Kolmogórov і Efecte Mateu
Entropia
Rudolf Clausius L'entropia és una magnitud termodinàmica definida originàriament com a criteri per a predir l'evolució dels sistemes termodinàmics.
Veure Complexitat de Kolmogórov і Entropia
Entropia de Shannon
Dos bits d'entropia: en el cas de llançar a l'aire dues monedes justes, l'entropia d'informació en bits és el logaritme en base 2 del nombre de possibles resultats; amb dues monedes hi ha quatre possibles resultats, i dos bits d'entropia. En general, l'entropia d'informació és la quantitat mitjana d'informació que es transmet en un esdeveniment, considerant-ne tots els possibles resultats.
Veure Complexitat de Kolmogórov і Entropia de Shannon
Estructura de dades
En programació, una estructura de dades és una forma d'organitzar un conjunt de dades elementals amb l'objectiu de facilitar la seva manipulació.
Veure Complexitat de Kolmogórov і Estructura de dades
Funció computable
Les funcions computables són l'objecte bàsic d'estudi de la teoria de la computabilitat i consisteixen en les funcions que poden ser calculades per una màquina de Turing.
Veure Complexitat de Kolmogórov і Funció computable
Gregory Chaitin
Gregory J. Chaitin (Chicago, 15 de Novembre de 1947) és un matemàtic i científic de la computació argentí-estatunidenc.
Veure Complexitat de Kolmogórov і Gregory Chaitin
Intèrpret (informàtica)
A ciències de la computació, intèrpret o interpretador és un programa informàtic capaç d'analitzar i executar altres programes, escrits en un llenguatge d'alt nivell.
Veure Complexitat de Kolmogórov і Intèrpret (informàtica)
Lisp
Lisp (o LISP) és un dels grans pioners dels llenguatges de programació, creador del paradigma funcional.
Veure Complexitat de Kolmogórov і Lisp
Màquina universal de Turing
Una màquina universal de Turing (o també màquina de Turing universal) és una màquina de Turing que pot simular qualsevol màquina de Turing amb una entrada arbitrària.
Veure Complexitat de Kolmogórov і Màquina universal de Turing
Navalla d'Occam
Guillem d'Occam La navalla d'Occam o navalla d'Ockham és un principi metodològic i filosòfic atribuït al frare franciscà Guillem d'Occam, lògic del, que forma la base del mètode reduccionista segons el qual «en igualtat de condicions, l'explicació més simple sol ser la més probable».
Veure Complexitat de Kolmogórov і Navalla d'Occam
Nombre de Gödel
En teoria dels nombres un nombre de Gödel és una funció que assigna a cada símbol i fórmula d'un llenguatge formal un nombre únic, anomenat Nombre de Gödel (GN).
Veure Complexitat de Kolmogórov і Nombre de Gödel
Nombre natural
Un nombre natural és qualsevol dels nombres 0, 1, 2, 3…, 19, 20, 21..., que es poden utilitzar per a comptar els elements d'un conjunt finit.
Veure Complexitat de Kolmogórov і Nombre natural
Notació de Landau
En matemàtica, la Notació de Landau, també anomenada "o minúscula" i "O majúscula", és una notació per a la comparació asimptòtica de funcions, la qual cosa permet establir la cota inferior asimptòtica, la cota superior asimptòtica i la cota ajustada asimptòtica.
Veure Complexitat de Kolmogórov і Notació de Landau
Pascal (llenguatge de programació)
Pascal és un llenguatge de programació desenvolupat pel professor Niklaus Wirth a finals dels anys 60.
Veure Complexitat de Kolmogórov і Pascal (llenguatge de programació)
Principi de les caselles
''k''.
Veure Complexitat de Kolmogórov і Principi de les caselles
Probabilitat bayesiana
El anomenat Concepte de Probabilitat Bayesià (angl. Bayesianism) del matemàtic anglès Thomas Bayes, interpreta la probabilitat com a grau de convicció personal.
Veure Complexitat de Kolmogórov і Probabilitat bayesiana
Problema de la parada
En teoria de la computabilitat el problema de la parada és un problema de decisió que es pot formular de forma informal: Alan Turing va provar el 1936 que un algorisme general per resoldre el problema de la parada per totes les possibles parelles programa-entrades no pot existir.
Veure Complexitat de Kolmogórov і Problema de la parada
Programa informàtic
Un programa informàtic escrit en un estil orientat a objectes Un programa informàtic o programa d'ordinador és una seqüència d'instruccions, escrites per fer una tasca específica en una computadora.
Veure Complexitat de Kolmogórov і Programa informàtic
Quod erat demonstrandum
Quod erat demonstrandum o la seva abreviació Q.E.D. és una locució llatina que significa: "tal com volíem veure", "tal com es volia demostrar".
Veure Complexitat de Kolmogórov і Quod erat demonstrandum
Reducció a l'absurd
En matemàtica, la demostració per contradicció o per reducció a l'absurd (o en llatí, reductio ad absurdum) és un mètode indirecte.
Veure Complexitat de Kolmogórov і Reducció a l'absurd
Sistema formal
Un sistema formal o axiomàtic és un artifici matemàtic compost de símbols que s'uneixen entre si formant cadenes que, al seu torn, poden ser manipulades segons regles per produir altres cadenes.
Veure Complexitat de Kolmogórov і Sistema formal
Teoria Algorísmica de la Informació
La teoria algorísmica de la informació és una branca de la informàtica teòrica que s'ocupa de la relació entre la computació i la informació d'objectes generats computacionalment (a diferència dels generats estocàsticament), com ara cadenes de caràcters o qualsevol altra estructura de dades.
Veure Complexitat de Kolmogórov і Teoria Algorísmica de la Informació
Turing complet
En la teoria d'ordinadors reals i imaginaris, dels llenguatges de programació i d'altres sistemes lògics, un sistema Turing complet és aquell que té un poder computacional equivalent a la màquina universal de Turing.
Veure Complexitat de Kolmogórov і Turing complet