Accés més ràpid que el navegador!
29 les relacions: Algorisme, Algorisme d'ordenació, Andrew Chi-Chih Yao, Classe de complexitat, Edat de l'Univers, EXPTIME, Factorial, Factorització dels enters, Jerarquia aritmètica, Juris Hartmanis, Leslie Valiant, Llenguatge formal, Logaritme, Manuel Blum, Nombre de Shannon, Nombre primer, Notació de Landau, NP (Complexitat), P (complexitat), P versus NP, Problema de decisió, Problema de satisfacibilitat booleana, Recursivitat, Richard Karp, Richard Stearns, Sistema formal, Stephen Cook, Teoria de la computabilitat, Vector (programació).
Algorisme
nombres primers Un algorisme (o, alternativament, algoritme) és un conjunt finit d'instruccions o passos que serveixen per a executar una tasca o resoldre un problema.
Nou!!: Complexitat computacional і Algorisme · Veure més »
Algorisme d'ordenació
En informàtica i matemàtiques un algorisme d'ordenació és un algorisme que posa elements d'una llista seguint l'ordre donat per una relació d'ordre.
Nou!!: Complexitat computacional і Algorisme d'ordenació · Veure més »
Andrew Chi-Chih Yao
Andrew Chi-Chih Yao (Xangai, Xina, 24 de desembre de 1946) és un destacat científic xinès en l'àmbit de la computació.
Nou!!: Complexitat computacional і Andrew Chi-Chih Yao · Veure més »
Classe de complexitat
En teoria de complexitat, una classe de complexitat és un conjunt de problemes de decisió de complexitat relacionada.
Nou!!: Complexitat computacional і Classe de complexitat · Veure més »
Edat de l'Univers
Hubble L'edat de l'univers, d'acord amb la teoria del ''big bang'', és el temps que ha passat entre el big bang i el present.
Nou!!: Complexitat computacional і Edat de l'Univers · Veure més »
EXPTIME
En teoria de la complexitat, la classe de complexitat EXPTIME és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en temps O(2p(n)), on p(n) és una funció polinomial sobre n. En termes de DTIME es té Es coneix que i pel teorema de la jerarquia temporal: de manera que almenys una de les inclusions de la primera línia ha de ser estricta (es creu que totes ho son).
Nou!!: Complexitat computacional і EXPTIME · Veure més »
Factorial
En matemàtiques, el factorial d'un enter no negatiu n, denotat per n! (en alguns llibres antics es pot trobar denotat per \beginn\\ \hline\end), és el producte de tots els nombres enters positius inferiors o iguals a n. Per exemple, El valor de 0! és 1, d'acord amb la convenció d'un producte buit.
Nou!!: Complexitat computacional і Factorial · Veure més »
Factorització dels enters
En teoria de nombres, la factorització dels enters és el procés de trobar quins nombres primers es multipliquen per fer un nombre compost, doncs els divisors no trivials (diferent de l'1 i del mateix nombre).
Nou!!: Complexitat computacional і Factorització dels enters · Veure més »
Jerarquia aritmètica
En lògica matemàtica, la jerarquia aritmètica o jerarquia de Kleene és una classificació de conjunts de nombres naturals (i per extensió de qualsevol tipus d'elements que es codifiquin en nombres naturals) segons la complexitat de les fórmules que els defineixen.
Nou!!: Complexitat computacional і Jerarquia aritmètica · Veure més »
Juris Hartmanis
és un important informàtic i teòric de la computació que, juntament amb Richard E. Stearns, va rebre el premi Turing de l'ACM de 1993 "com a reconeixement pel seu article pioner que va establir els fonaments del camp de la teoria de complexitat computacional".
Nou!!: Complexitat computacional і Juris Hartmanis · Veure més »
Leslie Valiant
Leslie Gabriel Valiant, nascut el 28 de març de 1949, és un informàtic teòric britànic.
Nou!!: Complexitat computacional і Leslie Valiant · Veure més »
Llenguatge formal
teoremes. En alguns sistemes formals, però, el conjunt dels teoremes coincideix amb el de les fórmules ben formades. A matemàtiques, lògica, i ciències de la computació, un llenguatge formal és un llenguatge on els símbols primitius i regles per a unir aquests símbols estan formalment especificats.
Nou!!: Complexitat computacional і Llenguatge formal · Veure més »
Logaritme
mai l'interseca. Gràfiques de les funcions logarítmiques per a diverses bases ''b'': vermell en base ''e'', verd en base 10, i morat en base 1,7. La gràfica talla l'eix de les abscisses a ''x''.
Nou!!: Complexitat computacional і Logaritme · Veure més »
Manuel Blum
Manuel Blum (Caracas, 26 d'abril de 1938) és un informàtic veneçolà que va rebre el Premi Turing de 1995 "en reconeixement de les seves contribucions als fonaments de la teoria de la complexitat computacional i la seva aplicació a la criptografia i a la comprovació de programes".
Nou!!: Complexitat computacional і Manuel Blum · Veure més »
Nombre de Shannon
El nombre de Shannon, 10120, és una estimació de la complexitat de l'arbre de joc dels escacs.
Nou!!: Complexitat computacional і Nombre de Shannon · Veure més »
Nombre primer
Un nombre primer és un nombre enter superior a 1 que admet exactament dos divisors: 1 i ell mateix.
Nou!!: Complexitat computacional і Nombre primer · Veure més »
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.
Nou!!: Complexitat computacional і Notació de Landau · Veure més »
NP (Complexitat)
En complexitat computacional, NP és la classe de complexitat que conté els problemes de decisió que es poden resoldre amb una màquina de Turing no determinista usant una quantitat de temps de computació polinòmic, temps polinòmic.
Nou!!: Complexitat computacional і NP (Complexitat) · Veure més »
P (complexitat)
En Teoria de complexitat computacional, P és la classe de complexitat que conté els problemes de decisió que es poden resoldre amb una màquina de Turing determinista usant una quantitat de temps de computació polinòmic (temps polinòmic).
Nou!!: Complexitat computacional і P (complexitat) · Veure més »
P versus NP
Diagrama de classes de complexitat suposant que '''P''' ≠ '''NP'''. Si '''P'''.
Nou!!: Complexitat computacional і P versus NP · Veure més »
Problema de decisió
En teoria de la computabilitat i en complexitat computacional, un problema de decisió és una qüestió en algun sistema formal amb una resposta sí o no.
Nou!!: Complexitat computacional і Problema de decisió · Veure més »
Problema de satisfacibilitat booleana
En teoria de complexitat computacional, el problema de satisfacibilitat booleana (també conegut per les sigles SAT) és el problema de determinar si existeix una interpretació que satisfà una fórmula booleana donada.
Nou!!: Complexitat computacional і Problema de satisfacibilitat booleana · Veure més »
Recursivitat
Publicitat amb la utilització d'una imatge ''recursiva'' La recursivitat és la forma en la qual s'especifica un procés basat en la seva pròpia definició.
Nou!!: Complexitat computacional і Recursivitat · Veure més »
Richard Karp
Richard Manning Karp (nascut el 3 de gener de 1935) és un informàtic i teòric de la computació estatunidenc que treballa a la Universitat de Califòrnia a Berkeley.
Nou!!: Complexitat computacional і Richard Karp · Veure més »
Richard Stearns
Richard Edwin Stearns (nascut el 5 de juliol de 1936) és un informàtic destacat que, juntament amb Juris Hartmanis, va rebre el premi Turing de l'ACM de 1993 "en reconeixement del seu article pioner que va establir els fonaments del camp de la teoria de la complexitat computacional" (Hartmanis and Stearns, 1965).
Nou!!: Complexitat computacional і Richard Stearns · Veure més »
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.
Nou!!: Complexitat computacional і Sistema formal · Veure més »
Stephen Cook
Stephen Arthur Cook, (nascut el 14 de desembre de 1939) és un prestigiós informàtic i matemàtic que ha fet contribucions importants en els camps de la complexitat computacional i la complexitat de proves.
Nou!!: Complexitat computacional і Stephen Cook · Veure més »
Teoria de la computabilitat
La teoria de la computabilitat és la part de la computació que estudia els problemes de decisió que poden ser resolts amb un algorisme o equivalentment amb una màquina de Turing.
Nou!!: Complexitat computacional і Teoria de la computabilitat · Veure més »
Vector (programació)
Representació d'un vector bidimensional En informàtica un vector és una estructura de dades consistent en un grup d'elements que són accedits per indexació.
Nou!!: Complexitat computacional і Vector (programació) · Veure més »
Redirigeix aquí:
Complexitat, Complexitat algorísmica, Teoria de complexitat, Teoria de la complexitat.
