Computabilidad

Conceptos de informática

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

¿Qué es la computabilidad?

Problema computable

  • Existencia de algoritmo: Existe un procedimiento claro.
  • Tiempo finito: Produce salida en pasos limitados.

Problema no computable

  • No existe algoritmo: No se puede resolver para todas las entradas.
  • Cómputo infinito: Puede no concluir nunca.
1 Los problemas no computables pueden volverse computables cuando encontramos un algoritmo y/o hacemos que un algoritmo conocido termine en tiempo finito.
Conceptos de informática

Autómatas

Definición de autómata

  • Máquinas imaginarias
  • Ayudan a entender cómo funciona el cómputo
  • Tienen estados
  • Reglas para transitar entre estados

Imagen de un semáforo como analogía que representa un autómata

Conceptos de informática

Autómatas Finitos (FA)

Autómatas Finitos (FA)

  • Máquinas simples
  • Número fijo de estados
  • Sin memoria más allá del estado actual

Imagen de un semáforo y estados como analogía de los Autómatas Finitos

Conceptos de informática

Autómatas con Pila (PDA)

Autómatas con Pila (PDA)

  • Más potentes
  • Tienen estados
  • Memoria de pila para decisiones más complejas

Imagen de un semáforo y estados como analogía de los Autómatas con Pila

Conceptos de informática

Resumen

Autómatas Finitos (FA)

  • Útiles para tareas simples

Autómatas con Pila (PDA)

  • Más potentes para problemas más complejos

Importancia

  • Si un problema se modela con autómatas, PODEMOS implementar un algoritmo para resolverlo
Conceptos de informática

¡Vamos a practicar!

Conceptos de informática

Preparing Video For Download...