Tabla de contenidos
11 relaciones: Algoritmo DPLL, Algoritmo genético, Backjumping, Clase de complejidad, Forma normal conjuntiva, NP-completo, Richard Karp, Satisfacibilidad, Stephen Cook, Teoría de la complejidad computacional, Teorema de Cook.
- Álgebra de Boole
- Automatización de diseño electrónico
- Métodos formales
Algoritmo DPLL
El algoritmo DPLL/Davis-Putnam-Logemann-Loveland es un algoritmo completo basado en la vuelta atrás que sirve para decidir la satisfactibilidad de las fórmulas de lógica proposicional en una forma normal conjuntiva, es decir, para resolver el problema CNF-SAT.
Ver Problema de satisfacibilidad booleana y Algoritmo DPLL
Algoritmo genético
Un algoritmo es una serie de pasos organizados que describe el proceso que se debe seguir, para dar solución a un problema específico.
Ver Problema de satisfacibilidad booleana y Algoritmo genético
Backjumping
En algoritmos de backtracking, el backjumping es una técnica que reduce espacio de búsqueda, y por tanto, aumenta la eficacia de esta.
Ver Problema de satisfacibilidad booleana y Backjumping
Clase de complejidad
En teoría de la complejidad computacional, una clase de complejidad es un conjunto de problemas de decisión de complejidad relacionada.
Ver Problema de satisfacibilidad booleana y Clase de complejidad
Forma normal conjuntiva
En lógica booleana, una fórmula está en forma normal conjuntiva (FNC) si corresponde a una conjunción de cláusulas, donde una cláusula es una disyunción de literales, donde un literal y su complemento no pueden aparecer en la misma cláusula.
Ver Problema de satisfacibilidad booleana y Forma normal conjuntiva
NP-completo
En teoría de la complejidad computacional, la clase de complejidad NP-completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo. Problema de satisfacibilidad booleana y nP-completo son problemas NP-completos.
Ver Problema de satisfacibilidad booleana y NP-completo
Richard Karp
Richard Manning Karp (Boston, (Estados Unidos), 3 de enero de 1935) es un científico de la computación, conocido por su investigación en teoría de algoritmos, por lo que recibió el Premio Turing en 1985, el premio del Instituto Franklin en 2004 y el Premio Kioto en 2008.
Ver Problema de satisfacibilidad booleana y Richard Karp
Satisfacibilidad
En lógica proposicional, la satisfacibilidad se define como la propiedad de un conjunto de fórmulas de tener un modelo.
Ver Problema de satisfacibilidad booleana y Satisfacibilidad
Stephen Cook
Stephen Arthur Cook (1939, Búfalo (Nueva York)) es un reconocido científico de la computación.
Ver Problema de satisfacibilidad booleana y Stephen Cook
Teoría de la complejidad computacional
La teoría de la complejidad computacional o teoría de la complejidad informática es una rama de la teoría de la computación que se centra en la clasificación de los problemas computacionales de acuerdo con su dificultad inherente, y en la relación entre dichas clases de complejidad.
Ver Problema de satisfacibilidad booleana y Teoría de la complejidad computacional
Teorema de Cook
En teoría de la complejidad computacional, el Teorema de Cook establece lo siguiente: Cook demostró este teorema en su artículo de 1971 "The Complexity of Theorem Proving Procedures".
Ver Problema de satisfacibilidad booleana y Teorema de Cook
Ver también
Álgebra de Boole
- Álgebra de Boole
- Álgebra de Cantor
- Álgebra mediana
- Σ-álgebra
- Alfabeto lógico
- Algoritmo Quine–McCluskey
- Algoritmo de Davis-Putnam
- Anillo booleano
- Completitud funcional
- Diagrama de decisión binario
- Fórmula booleana cuantificada verdadera
- Fórmula proposicional
- Forma normal algebraica
- Formas canónicas (álgebra de Boole)
- Función booleana
- Función booleana simétrica
- Función mayorante
- Función paridad
- George Boole
- Juego de las fórmulas
- Lógica proposicional
- Leyes de De Morgan
- Mapa de Karnaugh
- Matriz booleana
- Operador a nivel de bits
- Polinomio de Zhegalkin
- Problema de satisfacibilidad booleana
- Puerta OR
- Tabla de verdad
- Teorema de consenso
- Tipo de dato lógico
- Unión de conjuntos
Automatización de diseño electrónico
- Aplicaciones potenciales de los nanotubos de carbono
- Automatización de diseño electrónico
- Diseño de sistemas
- Diseño gráfico de sistemas
- Ecuación de Black
- Electrónica digital
- Electromigración
- Esquematismo
- IEC 61131-3
- Integridad de señal
- Lenguaje ladder
- Máquina de estados algorítmica
- Matriz lógica genérica
- Núcleo de propiedad intelectual de semiconductores
- Problema de satisfacibilidad booleana
- Programmable Array Logic
- Simulador de circuitos electrónicos
- Tecnología CAD
- Teorías de satisfacibilidad módulo
- Unidad central de procesamiento
- Unidad de procesamiento gráfico
Métodos formales
- Aserción (informática)
- Cálculo lambda
- Ciclo invariante
- Demostración automática de teoremas
- Especificación formal
- Función 91 de McCarthy
- Language Of Temporal Ordering Specification
- Máquina de Turing
- Método formal
- Postcondición
- Precondición
- Principio de sustitución de Liskov
- Problema de satisfacibilidad booleana
- Proceso Unificado de Rational
- Prueba asistida por ordenador
- Semántica de lenguajes de programación
- Semántica de transformación de predicados
- Teoría de conjuntos
- Teoría de tipos homotópica
- Teorías de satisfacibilidad módulo
- Verificación formal
- Verificación y validación de los modelos de simulación por ordenador
- Vienna Development Method
También se conoce como 3-SAT, Problema de satisfabilidad, Problema de satisfabilidad booleana.