Hispanopedia WikiEsta es una lista de temas de computabilidad y complejidad , por página de Wikipedia.
La teoría de la computabilidad es la parte de la teoría de la computación que estudia qué se puede calcular, en principio. La teoría de la complejidad computacional estudia la dificultad de los cálculos, en términos cuantitativos, tanto en términos de límites superiores ( algoritmos cuya complejidad, en el peor de los casos, como el uso de recursos computacionales, se puede estimar) como de límites inferiores (pruebas de que ningún procedimiento para llevar a cabo una tarea puede ser muy rápido).
Para obtener más información sobre cuestiones fundamentales y abstractas, consulte la lista de temas de lógica matemática . Consulte también la lista de algoritmos y la lista de temas generales sobre algoritmos .
- Tabla de consulta
- Historia de las computadoras
- Algoritmo de multiplicación
- División por dos
- Exponenciando por cuadrado
- Cadena de adición
- Aritmética de Presburger
Teoría de la computabilidad: modelos de computación
- Circuitos aritméticos
- Algoritmo
- Autómata de estados finitos
- Maquina harinosa
- Máquina registradora Minsky
- Máquina de Moore
- Diagrama de estados
- Sistema de transición de estados
- Autómata finito determinista
- Autómata finito no determinista
- Autómata finito no determinista generalizado
- Lenguaje regular
- Expresión regular
- Gramática regular
- Gramática de prefijos
- Autómata de árbol
- Autómata de empuje hacia abajo
- Autómata Büchi
- Jerarquía de Chomsky
- Registrar máquina
- Máquina apiladora
- Red de Petri
- Máquina de correos
- Reescritura
- Altura de la estrella
- Autómata celular
- Máquina de Turing
- Cálculo lambda
- Lógica combinatoria
- Computación paralela
- Taxonomía de Flynn
- Computadora cuántica
- Tesis de Church-Turing
- Problema de resolución de problemas
- Problema de parada
- Problema de correspondencia postal
- Lenguaje decidible
- Problema de palabras para grupos
- Azulejo Wang
- Mosaico de Penrose
Preguntas de definibilidad
- Número computable
- Número definible
- Probabilidad de detención
- Teoría de la información algorítmica
- Probabilidad algorítmica
- Compresión de datos
- Asesoramiento (complejidad)
- Análisis amortizado
- Protocolo Arthur-Merlin
- Los mejores y peores casos
- Castor ocupado
- Complejidad del circuito
- Función construible
- Teorema de Cook-Levin
- Tiempo exponencial
- Problema de función
- Tiempo lineal
- Teorema de aceleración lineal
- Prueba natural
- Tiempo polinomial
- Reducción de muchos a uno en tiempo polinomial
- Reducción de Turing en tiempo polinomial
- Teorema de Savitch
- Teorema de jerarquía espacial
- Velocidad previa
- Teorema de aceleración
- Tiempo subcuadrático
- Teorema de la jerarquía temporal
Clases de complejidad
Ver la lista de clases de complejidad
Problemas con nombre
- Problema de camarilla
- Problema del ciclo hamiltoniano
- Problema de la trayectoria hamiltoniana
- Factorización de números enteros
- Problema de la mochila
- Problema de satisfacibilidad
- Problema de suma de subconjuntos
- 3SUMA
- Problema del viajante de comercio
- Problema de cobertura de vértices
- Función unidireccional
- Problema con la cubierta del conjunto
- Problema de conjuntos independientes
Extensiones
- Algoritmo probabilístico , algoritmo aleatorio
- Algoritmo de Las Vegas
- No determinismo
- Máquina de Turing no determinista
- Computación interactiva
- Sistema de prueba interactivo
- Máquina de Turing probabilística
- Algoritmo de aproximación
- Recocido simulado
- Algoritmos de optimización de colonias de hormigas
- Semántica del juego
- Juego generalizado
- Sistema de múltiples agentes
- Complejidad parametrizada
- Cálculos de proceso
- Hipercomputación
- Computación real
- Análisis computable