Algoritmos Programas

Un algoritmo es un método, un proceso, un conjunto de instrucciones

utilizadas para resolver un problema específico. Un problema puede ser resuelto
mediante muchos algoritmos. Un algoritmo dado correcto, resuelve un
problema definido y determinado (por ejemplo, calcula una función
determinada).
La ventaja de conocer varias soluciones a un problema es que las diferentes
soluciones pueden ser más eficientes para variaciones específicas del problema
o para diferentes entradas del mismo problema. Por ejemplo, un algoritmo de
ordenación puede ser el mejor para ordenar conjuntos pequeños de números,
otro puede ser el mejor para ordenar conjuntos grandes de números y un
tercero puede ser el mejor para ordenar cadenas de caracteres de longitud
variable
 Propiedades de los algoritmos
Un algoritmo debe cumplir diferentes propiedades 2:
1. Especificación precisa de la entrada. La forma más común del algoritmo es una
transformación que toma un conjunto de valores de entrada y ejecuta algunas
manipulaciones para producir un conjunto de valores de salida. Un algoritmo debe
dejar claros el número y tipo de valores de entrada y las condiciones iniciales que
deben cumplir esos valores de entrada para conseguir que las operaciones tengan éxito.
2. Especificación precisa de cada instrucción. Cada etapa de un algoritmo debe ser
definida con precisión. Esto significa que no puede haber ambigüedad sobre las
acciones que se deban ejecutar en cada momento
3. Exactitud, corrección. Un algoritmo debe ser exacto, correcto. Se debe
poder demostrar que el algoritmo resuelve el problema. Con frecuencia, esto se
plasma en el formato de un argumento, lógico o matemático, al efecto de que si
las condiciones de entrada se cumplen y se ejecutan los pasos del algoritmo,
entonces se producirá la salida deseada. En otras palabras, se debe calcular la
función deseada y convertir cada entrada a la salida correcta. Un algoritmo se
espera que resuelva un problema.
4. Etapas bien definidas y concretas. Un algoritmo se compone de una serie
de etapas concretas, lo que significa que la acción descrita por esa etapa está
totalmente comprendida por la persona o máquina que debe ejecutar el
algoritmo. Cada etapa debe ser ejecutable en una cantidad finita de tiempo. Por
consiguiente, el algoritmo nos proporciona una “receta” para resolver el
problema en etapas y tiempos concretos.
5. Número finito de pasos. Un algoritmo se debe componer de un número finito de
pasos. Si la descripción del algoritmo consta de un número infinito de etapas, nunca se
podrá implementar como un programa de computador. La mayoría de los lenguajes
que describen algoritmos (español, inglés o pseudocódigo) proporciona un método
para ejecutar acciones repetidas, conocidas como iteraciones, que controlan las salidas
de bucles o secuencias repetitivas.
6. Un algoritmo debe terminar. En otras palabras, no puede entrar en un bucle
infinito.
7. Descripción del resultado o efecto. Por último, debe estar claro cuál es la tarea
que el algoritmo debe ejecutar. La mayoría de las veces, esta condición se expresa con
la producción de un valor como resultado que tenga ciertas propiedades. Con menor
frecuencia, los algoritmos se ejecutan para un efecto lateral, como imprimir un valor en
un dispositivo de salida. En cualquier caso, la salida esperada debe estar especificada
completamente.
 Ejemplo de algoritmos I
¿Determina si los siguientes enunciados son algoritmos o
no?
1. Escribir una lista de todos los enteros positivos.
2. "Intenta resolver este rompecabezas.”
3. "Encuentra una forma de mejorar la eficiencia del sistema."
4. “Encuentra el máximo común divisor (MCD) de dos números enteros”
5. “Buscar un elemento en una lista desordenada, revisa cada elemento desde el principio
hasta el final hasta encontrar el elemento o llegar al final de la lista."
 Programas
Un programa de computadora es una representación concreta de un algoritmo en un
lenguaje de programación. Naturalmente, hay muchos programas que son ejemplos del
mismo algoritmo, dado que cualquier lenguaje de programación moderno se puede
utilizar para implementar cualquier algoritmo (aunque algunos lenguajes de programación
facilitarán su tarea al programador más que otros). Por definición un algoritmo debe
proporcionar suficiente detalle para que se pueda convertir en un programa cuando se
necesite.
El requisito de que un algoritmo “debe terminar” significa que no todos los programas de
computadora son algoritmos. Su sistema operativo es un programa en tal sentido; sin
embargo, si piensa en las diferentes tareas de un sistema operativo (cada una con sus
entradas y salidas asociadas) como problemas individuales, cada una es resuelta por un
algoritmo específico implementado por una parte del programa sistema operativo, cada
una de las cuales termina cuando se produce su correspondiente salida
Un problema es una función o asociación de entradas con salidas.
2. Un algoritmo es una receta para resolver un problema cuyas etapas son concretas y
no ambiguas.
3. El algoritmo debe ser correcto y finito, y debe terminar para todas las entradas.
4. Un programa es una “ejecución” (instanciación) de un algoritmo en un lenguaje de
programación de computadora.
 Eficiencia de un algoritmo
La eficiencia de un algoritmo es la propiedad mediante la cual un algoritmo
debe alcanzar la solución al problema en el tiempo más corto posible o
utilizando la cantidad más pequeña posible de recursos físicos y que sea
compatible con su exactitud o corrección. Un buen programador buscará el
algoritmo más eficiente dentro del conjunto de aquellos que resuelven con
exactitud un problema dado.
La eficiencia como factor espacio-tiempo debe estar estrechamente relacionada
con la buena calidad, el funcionamiento y la facilidad de mantenimiento del
programa.
 Formato general de la eficiencia
En general, el formato se puede expresar mediante una función:
f (n) = eficiencia
Es decir, la eficiencia del algoritmo se examina como una función del número
de elementos que tienen que ser procesados.
Bucles lineales
En los bucles se repiten las sentencias del cuerpo del bucle un número
determinado de veces, que determina la eficiencia del mismo. Normalmente, en
los algoritmos los bucles son el término dominante en cuanto a la eficiencia del
mismo.
 Tarea 3
Bucles algorítmicos
Consideremos un bucle en el que su variable de control se multiplique dentro
de dicho bucle.
1. ¿Cuántas veces se repetirá el cuerpo del bucle en los siguientes segmentos de
programa?
Consideremos un bucle en el que su variable de control se divida dentro de
dicho bucle.
2. ¿Cuántas veces se repetirá el cuerpo del bucle en los siguientes segmentos de
programa?
 COMPLEJIDAD ALGORÍTMICA
Existen muchas alternativas de solución para un problema, debemos
seleccionar el algoritmo más eficiente con el mejor conjunto de pasos, que su
tiempo de ejecución sea el menor y cuyas líneas de código sean las menos
posibles.
A simple vista parece algo muy simple, pero a medida que un programa crece,
se requiere una medición más exacta y apropiada, para esto se realizan ciertas
operaciones matemáticas que establecen la eficiencia teórica del programa, al
estudio de estos casos se denomina Complejidad Algorítmica.
La complejidad algorítmica representa la cantidad de recursos (temporales y
espaciales) que necesita un algoritmo para resolver un problema y por tanto
permite determinar la eficiencia de dicho algoritmo, pero son medidas relativas
al tamaño del problema.
• Un algoritmo será más eficiente comparado con otro, siempre que consuma
menos recursos, como el tiempo y espacio de memoria necesarios para
ejecutarlo.

1. Complejidad Temporal: Tiempo de cómputo necesario para ejecutar

algún programa.
• 2. Complejidad Espacial: Memoria que utiliza un programa para su
ejecución, indica la cantidad de espacio requerido para ejecutar el algoritmo;
es decir, el espacio en memoria que ocupan todas las variables propias al
algoritmo. Para calcular la memoria estática de un algoritmo se suma la
memoria que ocupan las variables declaradas en el algoritmo. Para el caso de
la memoria dinámica, el cálculo no es tan simple ya que, este depende de
cada ejecución del algoritmo.
 Complejidad temporal de los
algoritmos
En ciencias de la computación, el análisis de algoritmos es
una parte muy importante. Es importante buscar el
algoritmo más eficiente para resolver un problema. Es
posible tener muchos algoritmos para resolver un
problema, el reto es elegir el más eficiente.
 Complejidad temporal
• La complejidad temporal es el número de operaciones que realiza un
algoritmo para completar su tarea (considerando que cada operación dura el
mismo tiempo). El algoritmo que realiza la tarea en el menor número de
operaciones se considera el más eficiente en términos de complejidad
temporal. Sin embargo, la complejidad espacial y temporal se ve afectada por
factores como el sistema operativo y el hardware, pero no los incluiremos en
discusión
Para entender la complejidad temporal, tomaremos un ejemplo en el que
compararemos dos algoritmos diferentes que se utilizan para resolver un
problema concreto.
El problema es la búsqueda. Tenemos que buscar un elemento en un arreglo
(en este problema, vamos a suponer que el arreglo está ordenado de forma
ascendente). Para resolver el problema tenemos dos algoritmos:
1. Búsqueda lineal.
2. Búsqueda binaria.
Ejemplo:
Un arreglo con diez elementos, y tenemos que encontrar el número diez en el
arreglo.
El algoritmo de búsqueda lineal comparará cada elemento del
arreglo con digito_buscado. Cuando encuentre
el digito_buscado en el arreglo regresara true.
Vamos a contar el número de operaciones que realiza. En este caso,
la respuesta es 10. Entonces la búsqueda lineal utiliza diez
operaciones para encontrar el elemento dado (este es el número
máximo de operaciones para este arreglo; este caso también es
conocido como el peor caso de un algoritmo).
En general la búsqueda lineal tardará un número n de operaciones
en su peor caso (donde n es el tamaño del arreglo)
El algoritmo de búsqueda binaria
La búsqueda binaria puede entenderse fácilmente con este ejemplo:

Si intentamos aplicar esta lógica en nuestro problema entonces,

primero compararemos digito_buscado con el elemento
central del arreglo, es decir 5. Ahora como 5 es menor que 10,
entonces empezaremos a buscar el digito_buscado en los
elementos del arreglo mayores que 5, de la misma manera hasta
que obtengamos el elemento deseado 10.
Ahora, intenta contar el número de operaciones
que la búsqueda binaria ha necesitado para
encontrar el elemento deseado. Se necesitaron
aproximadamente cuatro operaciones. Este fue el
peor caso de la búsqueda binaria. Esto demuestra
que existe una relación logarítmica entre el número
de operaciones realizadas y el tamaño total del
arreglo.
• número de operaciones = 4 (aprox.)
 Tarea 4
.

Investiga casos prácticos donde la selección de un

algoritmo particular sea crítica para el rendimiento del
sistema.