SAGASOFT

Desde el punto de vista de la computación, podemos aceptar la siguiente definición de algoritmo:

Secuencia ordenada de datos exentos de ambigüedad y determinísticos tal que al llevarse a cabo con fidelidad dan como resultado que se realice la tarea para el que sea ha diseñado en un tiempo finito (se obtiene la solución del problema planteado)

Existen también algoritmos lingüísticos, pero quedan fuera del ámbito de este artículo.

Los algoritmos en los que nos vamos a centrar son determinísticos, esto es, para unos mismos datos de entrada, producen siempre una salida y además es la misma. Existen también algoritmos no determinísticos o aleatorios.

Propiedades de los algoritmos:

• Finitud: Siempre acaban después de un número finito de etapas
• Precisión: Cada etapa está debe estar definida de forma precisa y las acciones a realizar rigurosamente especificadas
• Entrada: Necesita unos datos de entrada
• Salida: Siempre produce una salida
• Efectividad: Todas las acciones que hay que realizar deben ser tan básicas como para que se puedan realizar exacatamente y en un tiempo finito.

Pasos genéricos para la resolución de problemas de computación:

• Entender el problema
• Análisis del problema
• Diseñar un algoritmo para el problema
• Expresar el algoritmo como un programa
• Ejecutar el programa correctamente

Estudio/Clasificación de problemas:

• Década 30: Problemas computables y no computables. ¿Cuáles son los problemas abordables por un informático?
  Ejemplo de problema no abordable: Programa que tenga como entrada otro programa y sus datos de entrada y que responda en la salida a si el programa terminará algún día de hacer el cálculo. Es imposible resolver este problema, se conoce como “Problema de la parada”
• Década 50: Complejidad de los problemas computables (búsqueda de algoritmos más eficaces). ¿Presentan todos los problemas la misma dificultad? NO.
  Ejemplo: Problema del viajante de comercio que tiene que visitar un número finito de ciudades. ¿Cómo hacerlo en un tiempo mínimo? Si tratamos de abordar el problema intuitivamente, buscando todas las rutas posibles y eligiendo luego la más corta, para n ciudades, tenemos n-n! rutas posibles. Es un número inabordable, de ahí la necesidad de buscar algoritmos más eficaces.
• Década 70: Clasificación de los problemas computables: P y NP

Problemas P y NP:

• Problemas P: Problemas para los que conozco un algoritmo que lo resuelve en un tiempo polinomial, asumiendo que es un tiempo eficiente.
• Problemas NP: Problemas no determinísticos. Sólo se pueden resolver de manera polinomial realizando una etapa aleatoria.

Vía | Teoría de Algoritmos [ETSIIT]