1.1. Resuelve problemas cotidianos mediante el uso
de algoritmos.
En la vida cotidiana, se emplean algoritmos
frecuentemente para resolver problemas. Algunos ejemplos son los manuales de
usuario, que muestran algoritmos para usar un aparato, o las instrucciones que
recibe un trabajador por parte de su patrón.
Algunos ejemplos
en matemática son
el algoritmo de multiplicación, para calcular el producto,
el algoritmo de la división para
calcular el cociente de dos números.
1.2. Que es un algoritmo.
En matemáticas, lógica, ciencias de la computación y disciplinas relacionadas,
un algoritmo (del griego y latín, dixit algorithmus y este
a su vez del matemático persa Al-Juarismi) es un
conjunto prescrito de instrucciones o reglas bien definidas, ordenadas y
finitas que permite realizar una actividad mediante pasos sucesivos que no
generen dudas a quien deba realizar dicha actividad. Dados un estado
inicial y una entrada, siguiendo los pasos sucesivos se llega a un estado final
y se obtiene una solución.
1.3. Clasificación de algoritmos.
- Algoritmos voraces (greedy):
seleccionan los elementos más prometedores del conjunto de candidatos hasta
encontrar una solución. En la mayoría de los casos la solución no es óptima.
- Algoritmos
paralelos: permiten la división de un problema en subproblemas de
forma que se puedan ejecutar de forma simultánea en varios procesadores.
- Algoritmos
probabilísticos: algunos de los pasos de este tipo de algoritmos
están en función de valores pseudoaleatorios.
- Algoritmos
determinísticos: el comportamiento del algoritmo es lineal: cada
paso del algoritmo tiene únicamente un paso sucesor y otro antecesor.
- Algoritmos no determinísticos: el comportamiento del
algoritmo tiene forma de árbol y a cada paso del algoritmo puede bifurcarse a
cualquier número de pasos inmediatamente posteriores, además todas las ramas se
ejecutan simultáneamente.
- Divide
y vencerás: dividen el problema en subconjuntos disjuntos obteniendo
una solución de cada uno de ellos para después unirlas, logrando así la
solución al problema completo.
- Metaheurísticas: encuentran
soluciones aproximadas (no óptimas) a problemas basándose en un conocimiento
anterior (a veces llamado experiencia) de los mismos.
- Programación dinámica: intenta resolver
problemas disminuyendo su coste computacional aumentando el coste espacial.
- Ramificación
y acotación: se basa en la construcción de las soluciones al
problema mediante un árbol implícito que se recorre de forma controlada
encontrando las mejores soluciones.
- Vuelta atrás (backtracking):
se construye el espacio de soluciones del problema en un árbol que se examina
completamente, almacenando las soluciones menos costosas.
1.4. Medios de expresión de un algoritmo.
Los algoritmos pueden ser expresados de muchas maneras, incluyendo
al lenguaje natural, pseudocódigo, diagramas
de flujo y lenguajes de programación entre otros.
Las descripciones en lenguaje natural tienden a ser ambiguas
y extensas.
El usar pseudocódigo y diagramas de flujo evita muchas
ambigüedades del lenguaje natural.
Dichas expresiones son formas más estructuradas para
representar algoritmos; no obstante, se mantienen independientes de un lenguaje
de programación específico.