Métodos, Técnicas
y Taller de
Programación
Lic. Carlos B. Manzur Soria
Siguiente
Algoritmos
“Nuestra herramienta mental más importante para
competir con la complejidad, es la abstracción. Por tanto,
un problema no deberá considerarse inmediatamente en
términos de instrucciones de un lenguaje, sino, de elementos
naturales del problema mismo, abstraídos de alguna
manera.”
Niklaus Wirth
(Creador del Lenguaje Pascal)
Anterior Siguiente
Algoritmos
El Origen de la Palabra
“Algoritmo”
De origen árabe, proviene del
matemático y astrónomo Abu
Abdullah Muhammad Bin Musa,
quien tomó como seudónimo
Al-Khowarizmi (780-850).
Anterior Siguiente
Algoritmos
Para resolver un problema es necesario
entenderlo.
Qué debo ¿Cómo lo
hacer hago?
50% 50 %
Anterior Siguiente
Algoritmos
Definición
Simples:
● Conjunto ordenado de pasos que permiten hallar la solución de
un problema.
● Secuencia de pasos que conducen a la realización de una tarea.
● Descripción de pasos, rutinas y procedimientos que permiten
solucionar un problema
Anterior Siguiente
Algoritmos
Definición
Más completas:
Secuencia finita de instrucciones, reglas o pasos que describen de forma precisa las
operaciones que un ordenador debe realizar para llevar a cabo una tarea en un
tiempo finito. [Donald E. Knuth, 1968]
Descripción de un esquema de comportamiento expresado mediante un repertorio
finito de acciones y de informaciones elementales, identificadas, bien comprendidas y
realizables a priori. Este repertorio se denomina léxico. [Pierre Scholl, 1988]
Un conjunto finito de pasos definidos, estructurados en el tiempo y formulados con
base a un conjunto finito de reglas no ambiguas, que proveen un procedimiento para
dar la solución o indicar la falta de esta a un problema en un tiempo determinado.
[Rodolfo Quispe Otazu, 2004]
Anterior Siguiente
Algoritmos
Definición
Más completas:
Secuencia finita de instrucciones, reglas o pasos que describen de forma precisa las
operaciones que un ordenador debe realizar para llevar a cabo una tarea en un
tiempo finito. [Donald E. Knuth, 1968]
Descripción de un esquema de comportamiento expresado mediante un repertorio
finito de acciones y de informaciones elementales, identificadas, bien comprendidas y
realizables a priori. Este repertorio se denomina léxico. [Pierre Scholl, 1988]
Un conjunto finito de pasos definidos, estructurados en el tiempo y formulados con
base a un conjunto finito de reglas no ambiguas, que proveen un procedimiento para
dar la solución o indicar la falta de esta a un problema en un tiempo determinado.
[Rodolfo Quispe Otazu, 2004]
Anterior Siguiente
Algoritmos
Definición
Para la materia:
“Es una secuencia de pasos, reglas, procedimientos, e
instrucciones lógicamente ordenados y no ambiguos, que nos
llevan a la solución de un problema, mediante el uso de un
ordenador en un determinado lapso de tiempo, tiempo finito”.
[Carlos B. Manzur Soria, 2001]
Anterior Siguiente
Algoritmos
Los algoritmos son independientes del lenguaje de programación.
Cada problema descrito por un algoritmo puede escribirse y luego
ejecutarse en un lenguaje de programación. El algoritmo es la
infraestructura de cualquier solución, escrita luego en cualquier
lenguaje de programación.
(Siempre que sea posible)
Anterior Siguiente
Algoritmos
Clasificación
1. Algoritmo computacional: Es un algoritmo que puede ser ejecutado en una computadora. Ejemplo:
Fórmula aplicada para un cálculo de la raíz cuadrada de un valor x.
2. Algoritmo no computacional: Es un algoritmo que no requiere de una computadora para ser
ejecutado.
Ejemplo: Instalación de un equipo de sonido.
3. Algoritmo cualitativo: Un algoritmo es cualitativo cuando en sus pasos o instrucciones no están
involucrados cálculos numéricos.
Ejemplos: Las instrucciones para desarrollar una actividad física, encontrar un tesoro.
4. Algoritmo cuantitativo: Una algoritmo es cuantitativo cuando en sus pasos o instrucciones
involucran cálculos numéricos.
Ejemplo: Solución de una ecuación de segundo grado.
Anterior Siguiente
Algoritmos
Características
Ser definido: Pasos claros, bien definidos sin criterios de interpretación (sin ambigüedad).
Ser finito: Conjunto de pasos, instrucciones específicas y numerables, debe finalizar al cabo de la
ejecución de las mismas.
Tener cero o más entradas: Datos son proporcionados a un algoritmo como insumo (o estos
son generados de alguna forma) para llevar a cabo las operaciones que comprende.
Anterior Siguiente
Algoritmos
Características
Resultado: Debe devolver un resultado. Devolver un resultado no debe ser considerado como
únicamente “verlos” en forma impresa o en pantalla, como ocurre con las computadoras. Existen
muchos otros mecanismos susceptibles de programación que no cuentan con una salida de
resultados de esta forma. Por salida de resultados debe entenderse todo medio o canal por el cual
es posible apreciar los efectos de las acciones del algoritmo.
Efectividad: El tiempo y esfuerzo por cada paso realizado debe ser preciso, nada más ni nada
menos que aquello que se requiera para y en su ejecución.
Anterior Siguiente
Algoritmos
Partes
1. Entrada de datos, son los datos necesarios que el algoritmo necesita para ser
ejecutado.
2. Proceso, es la secuencia de pasos para ejecutar el algoritmo.
3. Salida de resultados, son los datos obtenidos después de la ejecución del algoritmo.
Anterior Siguiente
Algoritmos
Técnicas de Representación
● Diagramación libre (Diagramas de Flujo).
Anterior Siguiente
Algoritmos
Técnicas de Representación
● Diagramas Nassi-Shneiderman (Diagramas de Chapin).
Anterior Siguiente
Algoritmos
Técnicas de Representación
● Pseudocódigo (pseudocódigo).
Anterior Siguiente
Algoritmos
Técnicas de Representación
● Lenguaje natural (español, ingles, etc.)
● Fórmulas matemáticas
Anterior Siguiente
Algoritmos
Eficiencia y Eficacia
Eficiencia
● La eficiencia es una medida de la cantidad de recursos que se requieren para producir
resultados correctos.
● Eficiencia es la capacidad de lograr el efecto en cuestión con el mínimo de recursos
posibles.
Eficacia
● Eficacia es la capacidad de lograr un efecto deseado o esperado.
● Eficiencia es la capacidad de lograr el efecto en cuestión con el mínimo de recursos
posibles.
La eficacia difiere de la eficiencia en el sentido que la eficiencia hace referencia en la mejor
utilización de los recursos, en tanto que la eficacia hace referencia en la capacidad para
alcanzar un objetivo.
Anterior Siguiente
Algoritmos
Eficiencia vs. Eficacia
Eficiencia Eficacia
● Énfasis en los ● Énfasis en los
medios, recursos resultados
● Resolver problemas ● Lograr objetivos
● Cumplir tareas y ● Obtener resultados
obligaciones
● Ahorrar gastos ● Crear valores
● Enfoque reactivo ● Enfoque proactivo
Efectividad
Anterior Siguiente
Algoritmos
Fortalezas
1
Robusto: Un algoritmo debe contemplar todas las posibles facetas del
problema que queremos resolver, al elaborar un algoritmo no se nos debe
escapar ningún detalle que provoque un mal funcionamiento de nuestro
algoritmo. Si logramos construir un algoritmo robusto, cualquier giro inesperado
del problema será controlado por el algoritmo, es decir, debe ser flexible a
cambios.
Anterior Siguiente
Algoritmos
Fortalezas
2
Correcto: Es correcto cuando da una solución al problema a tratar y cumple
con todos los requerimientos especificados tal que cumplamos con los objetivos
planteados.
Anterior Siguiente
Algoritmos
Fortalezas
3
Completo: Cuando un algoritmo cuenta con todos los recursos para poder
llegar a una solución satisfactoria
Anterior Siguiente
Algoritmos
Fortalezas
4
Eficiente: Cuando logra llegar a sus objetivos planteados utilizando la menor
cantidad de recursos posibles. Los resultados más eficientes se alcanzan cuando
se hace uso adecuado de estos factores, en el momento oportuno, al menor
costo posible y cumpliendo con las normas de calidad requeridas. O al contrario,
cuando se incrementan los resultados con los mismos recursos.
Anterior Siguiente
Algoritmos
Fortalezas
5
Eficaz: Cuando se alcanza el objetivo primordial de manera efectiva. Eficacia mide
los resultados alcanzados en función de los objetivos que se han propuesto,
presuponiendo que esos objetivos se mantienen alineados con la visión que se ha
definido. Mayor eficacia se logra en la medida que las distintas etapas necesarias
para arribar a esos objetivos, se cumplen de manera organizada y ordenada sobre la
base de su prioridad e importancia. La efectividad se encuentra en el equilibrio entre
la producción de los resultados deseados y la capacidad de producción.
Puede darse el caso de que exista un algoritmo eficaz pero no eficiente. Debemos tratar de
encontrar el equilibrio que satisfaga nuestras necesidades.
Anterior Siguiente
Algoritmos
Algo interesante que ver:
Sitios de Interés:
● https://es.wikipedia.org/wiki/Al-Juarismi
● https://www.biografiasyvidas.com/biografia/j/jwarizmi.htm
● https://www.uaa.mx/direcciones/dgdv/editorial/docs/algoritmos.pdf
● http://www.aliat.org.mx/BibliotecasDigitales/sistemas/Analisis_y_dise
nio_de_algoritmos.pdf
● http://robotica.uv.es/pub/Libro/PDFs/CAPI3.pdf
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Introducción
Ya contando con un algoritmo que funciona correctamente, es necesario definir criterios de
rendimiento o comportamiento. Estos criterios se centran principalmente en su simplicidad y en el uso
eficiente de los recursos.
Se piensa muchas veces que un algoritmo sencillo no es muy eficiente. Sin embargo, la sencillez es una
característica muy interesante a la hora de diseñar un algoritmo, pues facilita su verificación, el estudio
de su eficiencia y su mantenimiento. De ahí que muchas veces prima la simplicidad y legibilidad del
código frente a alternativas más crípticas y eficientes del algoritmo.
Respecto al uso eficiente de los recursos, éste suele medirse en función de dos parámetros: el espacio,
es decir, memoria que utiliza, y el tiempo, lo que tarda en ejecutarse.
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Análisis Temporal y Espacial
Un algoritmo será más eficiente si consume menos recursos: tiempo y espacio de memoria necesario
para ejecutarlo.
● Dimensión Temporal: Medida del tiempo empleado.
● Dimensión Espacial: Medida de los recursos invertidos.
La eficiencia de un programa tiene dos elementos (cuantificadores) fundamentales como medida de
complejidad: tiempo y espacio.
● La eficiencia o complejidad temporal, se mide en términos de la cantidad de tiempo de ejecución
del programa.
● La eficiencia o complejidad espacial, es una medida de la cantidad de memoria requerida por un
programa.
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Análisis de Eficiencia
El análisis de la eficiencia de los algoritmos (memoria y tiempo de ejecución) consta de dos fases:
1- Análisis A Priori (o teórico)
Entrega una función que limita el tiempo de cálculo de un algoritmo. Consiste en obtener una
expresión que indique el comportamiento del algoritmo en función de los parámetros.
Esto es interesante porque:
La predicción del costo del algoritmo puede evitar una implementación posiblemente laboriosa.
Es aplicable en la etapa de diseño de los algoritmos, constituyendo uno de los factores fundamentales
a tener en cuenta.
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Análisis de Eficiencia
La estrategia teórica tiene como ventajas que no depende del computador ni del lenguaje de
programación, ni siquiera de la habilidad del programador.
Permite evitar el esfuerzo inútil de programar algoritmos ineficientes y de desperdiciar tiempo de
máquina para ejecutarlos.
También permite conocer la eficiencia de un algoritmo cualquiera que sea el tamaño de entrada que se
aplique.
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Análisis de Eficiencia
2- Prueba A Posteriori (experimental o empírica)
Se recogen estadísticas de tiempo y espacio consumidas por el algoritmo mientras se ejecuta. La
estrategia empírica consiste en programar los algoritmos y ejecutarlos en un computador con
valores de prueba, haciendo medidas para:
● Una máquina concreta.
● Un lenguaje concreto.
● Un compilador concreto.
● Datos concretos.
● Sistema operativo concreto.
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Medida del Tiempo
Hay dos estudios posibles sobre el tiempo:
● Uno que proporciona una medida teórica (a priori), que consiste en obtener una función que
acote (por arriba o por abajo) el tiempo de ejecución del algoritmo para unos valores de entrada
dados.
● Y otro que ofrece una medida real (a posteriori), consistente en medir el tiempo de ejecución del
algoritmo para unos valores de entrada dados y en un ordenador concreto.
En el análisis A priori, no puede ser expresada en segundos o en otra unidad de tiempo concreta, pues
no existe un ordenador estándar al que puedan hacer referencia todas las medidas.
Denotaremos por T(n) el tiempo de ejecución de un algoritmo para una entrada de tamaño n.
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Principio de Invarianza
Teóricamente T(n) debe indicar el número de instrucciones ejecutadas por un ordenador idealizado.
Para ello es necesario acotar de alguna forma la diferencia que se puede producir entre distintas
implementaciones de un mismo algoritmo, ya sea del mismo código ejecutado por dos máquinas de
distinta velocidad, como de dos códigos que implementen el mismo método. Esta diferencia es la que
acota el siguiente principio:
Dado un algoritmo y dos implementaciones suyas I1 e I2, que tardan T1(n) y T2(n)
segundos respectivamente, el Principio de Invarianza afirma que existe una
constante real c > 0 y un número natural n0 tales que para todo n ≥ n0 se verifica que
T1(n) ≤ cT2(n).
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Operaciones Elementales (OE)
Es importante hacer notar que el comportamiento de un algoritmo puede cambiar notablemente para
diferentes entradas (por ejemplo, cuán ordenados que se encuentren ya los datos a ordenar). De
hecho, para muchos programas el tiempo de ejecución es en realidad una función de la entrada
específica, y no sólo del tamaño de ésta.
Así suelen estudiarse tres casos para un mismo algoritmo:
● Peor caso.
● Mejor caso.
● Caso medio.
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Operaciones Elementales (OE)
A la hora de medir el tiempo, siempre lo haremos en función del número de operaciones elementales
que realiza dicho algoritmo, entendiendo por “Operaciones Elementales” (en adelante OE) aquellas
que el ordenador realiza en tiempo acotado por una constante.
Así, consideraremos OE las operaciones aritméticas básicas, asignaciones a variables de tipo
predefinido por el compilador, los saltos (llamadas a funciones y procedimientos, retorno desde ellos,
etc.), las comparaciones lógicas y el acceso a estructuras indexadas básicas, como son los vectores y
matrices.
Cada una de ellas contabilizará como 1OE.
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Operaciones Elementales (OE)
1. static int buscar(int vec[ ],int c)
2. { int j=0; // arreglo ordenado
3. while((vec[ j]<c)&&(j<vec.length))
4. j++; //j=j+1;
5. if(vec[j]==c)
6. return(j);
7. return(-1);
8. }
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Operaciones Elementales
Para determinar el tiempo de ejecución, calcularemos primero el número de operaciones
elementales (OE) que se realizan:
● En la línea (2) se ejecuta 1 OE (una asignación).
● En la línea (3) se efectúa la condición del bucle, con un total de 4 OE (dos comparaciones, un
acceso al vector, y un &&).
● La línea (4) está compuesta por un incremento y una asignación (2 OE).
● La línea (5) está formada por una comparación y un acceso al vector (2 OE).
● La línea (6) contiene un RETURN (1 OE) si la condición se cumple.
● La línea (7) contiene un RETURN (1 OE), cuando la condición del IF anterior es falsa.
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Operaciones Elementales
Mejor Caso:
En el caso mejor para el algoritmo, se efectuará la línea (2) y de la línea (3) sólo la primera mitad
de la condición, que supone 2 OE (suponemos que las expresiones se evalúan de izquierda a
derecha, y con “cortocircuito”, es decir, una expresión lógica deja de ser evaluada en el
momento que se conoce su valor, aunque no hayan sido evaluados todos sus términos). Tras
ellas la función acaba ejecutando las líneas (5), y dependiendo del resultado de la evaluación, la
línea (6) o línea (7).
En consecuencia, T(n)=1+2+3=6.
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Operaciones Elementales
Peor Caso:
En el caso peor, se efectúa la línea (3), el bucle se repite n–1 veces hasta que se cumple la segunda
condición, después se efectúa la condición de la línea (5) y la función acaba al ejecutarse.
Cada iteración del bucle está compuesta por las líneas (3) y (4), junto con una ejecución adicional de
la línea (3) que es la que ocasiona la salida del bucle.
n-1
Por tanto: T(n)= 1 + ( ( ⅀ ( 4 + 2) + 4) + 2 + 1
i=0
T(n) = 1 + ( (n-1)*6)+4) + 3
T(n) = 6n + 2
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Operaciones Elementales
Caso Medio:
Asumimos que el este caso, el bucle se repetirá sólo la mitad de las veces
(n-1) / 2
Por tanto: T(n)= 1 + ( ( ⅀ ( 4 + 2) + 2) + 2 + 1
i=0
T(n) = 1 + ( (n-1)/2 *6)+2) + 3
T(n) = 3n + 3
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Reglas Generales para el Cálculo del
Número de OE
Se asume que el tiempo de una OE es de orden 1.
La constante “ c ” del Principio de la Invarianza se asume, como 1.
El tiempo de ejecución de una secuencia de instrucciones (elementales y no
elementales), se obtiene sumando los tiempos de ejecución de cada
instrucción
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Reglas Generales para el Cálculo del
Número de OE
Instrucción “switch”
switch( n )
{ case 1: S1
case 2: S2
.
.
case k: Sk
}
tiempo de ejecución: T(n) = T(c) + max { T(S1), …, T(Sk) }
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Reglas Generales para el Cálculo del
Número de OE
Instrucción “if”
if( C )
S1
else
S2
tiempo de ejecución: T(n) = T(C) + max { T(S1), T(S2) }
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Reglas Generales para el Cálculo del
Número de OE
Instrucción “while”
while( C )
{
S
}
tiempo de ejecución: T(n) = T( C ) + (#iteraciones)* ( T(C ) + T(S) )
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Reglas Generales para el Cálculo del
Número de OE
Instrucción “for” y “do-while”
i = 1;
for (i = 0; i <= n; i++) while (i <= n)
{ {
S; S;
} i++;
while (i <= n) { S; i++; } }
tiempo de ejecución: T(n) = T( C ) + (#iteraciones)* ( T(C ) +T(S) )
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Reglas Generales para el Cálculo del
Número de OE
Llamada a una función
F (A1, …, As)
● 1, por el llamado a la función, más
● Tiempo de evaluación de los parámetros A1, …, As
● Tiempo de ejecución de la función (F)
tiempo de ejecución: F(A1, …, As) = 1 + T(A1) + … + T(As) +T( F )
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Reglas Generales para el Cálculo del
Número de OE
Función Recursiva
Las funciones de tiempo asociadas a funciones recursivas son también
recursivas.
tiempo de ejecución: T( n ) = T( n-1 ) + T( n )
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Cálculo del Número de OE
int buscar(int n, int a[ ], int c)
{ int r;
int j = 0; 1 OE
while (a[j]<c && j<n-1) 5 OE
j ++; 2 OE
if (a[j]==c ) 2 OE
r = j; 1 OE
else
r = -1; 1 OE
return r;
}
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Cálculo del Número de OE
Ejemplo 1:
n
1. y=0; y=⅀i T(n)= 1 + 1 + n *( T(C) + T(S))+T(C)
i=1
2. i=1;
3. while( i <=n) T(n)= 1 + 1 + n* (1) + n*(4) + 1
T(n)= 3 + 5n
4. { y=y+1;
5. i = i+1;
6. }
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Cálculo del Número de OE
T(n) = 1 + T(n-1)
= 1 +( 1 + T(n-2))
Ejemplo 2: = 1 +( 1 + (1+T(n-3)))
= 4 + T(n-4)
int fact(int n) = ...
{ if (n <= 1) = i + T(n-i)
return 1; = …
else = (n-1) + T(n - (n-1))
= n-1 + T(1)
return (n * fact(n – 1));
=n-1+1
} =n
Anterior Siguiente
Introducción a la Complejidad de los Algoritmos
Cálculo del Número de OE
T(n) = T(n/2)+1
Ejemplo 3: 1 si n=1 = (T((n/2)/2) +1) + 1=T(n/4)+2
T(n)= = T(n/8)+3
1 + T(n/2) si n>1 = ...
int E(int n)
{ if (n == 1) = T(n/2 i ) + i
= … (por sustitución de i )
return 0; log2 n
= T(n/ 2 ) + log2n
else
= T(n/n)+ log 2n
return (E(n/2)+1)); T(n) = 1 + log n
2
}
O(n)= log n
2
Anterior
