PDF de programación - Algoritmos

Algoritmos
Algoritmos

1

Indice

• Definición y propiedades
• Representación
• Algoritmos alternativos y equivalentes
• Programación estructurada
• Pseudocódigo
• Pseudocódigo
• Análisis de algoritmos
• Desarrollo
• Algoritmos iterativos
• Algoritmos recursivos
• Colección de algoritmos

Algoritmos

2

Definición

• Algoritmo es una secuencia ordenada de

instrucciones que resuelve un problema
concreto

• Ejemplos:

– Algoritmo de la media aritmética de N valores.

– Algoritmo para la resolución de una ecuación de

segundo grado.

• Niveles de detalle de los algoritmos:

– Alto nivel: no se dan detalles.

– Bajo nivel: muchos detalles.

Algoritmos

3

Algoritmos en la vida diaria1

• Receta (Algoritmo) de cocina: Camarones con

mayonesa de albahaca.

• Ingredientes - Input (datos de entrada o iniciales)

• Resultado u Output

Algoritmos

4

Algoritmos en la vida diaria2

Ingredientes (para 4 porciones):
• 2 cucharadas de aceite de oliva
• ½ cucharadita de ajo picado fino
• 2 tazas de camarones medianos, sin caparazón y desvenados
• 1 cucharadita de sal
• ½ cucharadita de pimienta
• 2 cucharadas de albahaca picada
Mayonesa de albahaca:
Mayonesa de albahaca:
• 1 taza de mayonesa baja en grasa
• 4 cucharadas de albahaca
• 3 pimientas negras molidas
• ½ limón, el jugo
Guarnición:
• 2 aguacates grandes, maduros en rebanadas
• 1 limón en cuartos
• 4 hojas de lechuga escarola
• 8 jitomates cherry partidos por la mitad
• Salsa picante al gusto

Algoritmos

5

Algoritmos en la vida diaria3

Preparación: (Algoritmo)

1. En una sartén caliente agrega el aceite de oliva,

agrega el ajo, camarones, sal, pimienta y albahaca.
Cocínalos 1 minuto. Apaga el fuego y deja los
camarones un minuto más. Pasa los camarones a un
tazón que esté sobre agua con hielo, déjalos dentro
tazón que esté sobre agua con hielo, déjalos dentro
solamente el tiempo necesario para que se enfríen.

2. En un tazón mezcla todos los ingredientes de la

mayonesa albahaca.

3. Corta los aguacates en rebanadas y acompaña los

camarones. Sirve en un plato decorado con hojas de
lechuga, tomates cherry, limón y si lo deseas agrega un
poco de salsa picante.

Algoritmos

6

Propiedades

Necesarias o básicas:
• Corrección (sin errores).
• Validez (resuelve el problema pedido)
• Precisión (no puede haber ambigüedad).
• Repetitividad (en las mismas condiciones, al ejecutarlo, siempre

se obtiene el mismo resultado).
se obtiene el mismo resultado).

• Finitud (termina en algún momento). Número finito de órdenes

no implica finitud.

• Eficiencia (lo hace en un tiempo aceptable)

Deseables:
• Generalidad
• Fácil de usar
• Robustez

Algoritmos

7

Representación Verbal

• Verbal: usa oraciones del lenguaje natural.

Pago Bruto

Si las horas trabajadas son menores o iguales a 40, el pago es el
producto del número de horas trabajadas y la tarifa (100 €/hora).
Si se ha trabajado más de 40 horas, el pago es de 150 (50% más
Si se ha trabajado más de 40 horas, el pago es de 150 (50% más
de la tarifa normal) por cada hora en exceso a 40.

Si horas trabajadas = 25

pago = 100x25=2500

Si horas trabajadas = 50

pago = 100x40 + 150x(50-40)=5500

Algoritmos

8

Representación Diagramas de flujo

• Diagramas de flujo: Representación gráfica

mediante cajas conectadas con flechas. Símbolos
habituales:

• Cajas ovales: indican inicio y fin.
• Cajas rectangulares: representan acciones
• Cajas rectangulares: representan acciones
• Rombos: representan decisiones a tomar. Contiene la condición

que determina la dirección a seguir.

inicio

leer horas

Verdadero

Horas<=40

Falso

Pago=100*horas

Pago=100*40+150*(horas−40)

Imprime pago

fin

Algoritmos

9

Representación Diagramas de cajas

• Diagramas de Bloques, Cajas o de Nassi-

Shneiderman

Ventaja principal: no usan flechas. Básicamente se trata
de cajas rectangulares que se apilan de acuerdo al
algoritmo.
algoritmo.

Secuencia Selección Repetición

Promedio

Leer N valores

Sumar todos los

valores

Dividir suma por

N

Imprimir resultado

M a x i m o

V

X > Y

F

M a x e s X

M a x e s Y

I m p r i m e M a x

Dividir

Hacer Q=0
Hacer R=N

R>=D

Decrementar R

menos Q

Incrementar Q

Algoritmos

10

Representación NS EasyCode

• Diagramas de Bloques, Cajas o de Nassi-

Shneiderman

Programa que soporta NS: EasyCode

http://www.easycode.de/v8_cpp.html?&L=1
http://www.easycode.de/v8_cpp.html?&L=1

• genera código a partir del diagrama de cajas.

• a partir del código genera el diagrama de cajas.

Algoritmos

11

Ejemplo NS : Máximo común divisor

• Algoritmo de Euclides:

formulación geométrica del
problema del MCD: encontrar una
"medida" común para el largo de
dos líneas.
dos líneas.

El algoritmo consiste en repetir
la resta de la línea más corta del
otro segmento mientras las líneas
sean diferentes.

Algoritmos

12

Ejemplo MCD con Easy Code

Algoritmos

13

Representación Gráficos y Pseudocódigo

• Gráficos:

T tarifa de
pago

1500

1000

500

20
20

40
40

60
60

Horas
trabajadas
trabajadas

• Pseudocódigo: descripciones cortas que usan una
mezcla de matemáticas, lógica y lenguaje natural.

Leer horas
Si horas > 40

Pago Bruto = Tarifa x 40 + 150 x (Horas - 40)

sino

Pago Bruto = 100 x Horas

Algoritmos

14

Representación Flujo de datos y tabulares

• Diagramas de flujo de datos: Representación

gráfica de alto nivel que muestran los datos de entrada
y de salida. Indican qué es lo que hace y los diagramas
de flujo o de cajas indican cómo se hace.

Horas

50 horas

H

Pago Bruto

P

55000 Ptas.

Pago

• Representaciones tabulares (tablas, arrays y

matrices). Son útiles para resumir colecciones de datos
grandes.

Algoritmos

15

Representación matemática

• Representaciones algebraicas (fórmulas y

expresiones). En ingeniería y matemáticas, los
algoritmos se expresan como fórmulas o expresiones
algebraicas. Usualmente es una representación muy
concisa.
concisa.

Media y Varianza de una serie de números:
M = (x1 + x2+ x3+ …. + xN) / N
V = [(x1

− M)2 + …. + (xN

− M)2 + (x2

− M)2] / N

Factorial de un número: Fórmula del seno:
n! = n x (n−1) x (n−2) x …. x 2 x 1 seno(x) = x − x3/ 3! + x5/ 5! − x7/ 7! ….

Algoritmos

16

Modificación de algoritmos

• Generalización y extensibilidad: proceso de

aplicar el algoritmo a más casos y de incluir más
casos dentro del algoritmo

• Robustez: proceso de hacer un algoritmo mas

fiable o robusto (se recupera de errores),
anticipando errores de entrada u otras
dificultades.

Algoritmos

17

Algoritmos alternativos y equivalentes

• Pueden haber muchas formas de llevar a cabo

un algoritmo.

• En esos casos la elección se basa en la

eficiencia (memoria y velocidad).

• El análisis de algoritmos estudia la cantidad de

recursos que demanda la ejecución de un
algoritmo.

• Preocupa más el tiempo de ejecución de un

algoritmo: Complejidad del algoritmo

Algoritmos

18

Programación estructurada

• Método para construir algoritmos a partir de un

número pequeño de bloques básicos.

• Formas fundamentales:

– Secuencia: indica secuencia temporal lineal de las

acciones a realizarse.
acciones a realizarse.

A
B

– Selección: especifica una condición que determina la

acción a realizarse.

if C

else

D

E

Algoritmos

19

Programación estructurada

– Repetición: indica que una o más acciones deben

repetirse un determinado número de veces.

while G do

H

– Invocación: corresponde al grupo de acciones

agrupadas bajo un nombre.

Calcula_promedio

Algoritmos

20

Pseudocódigo

• Lectura o entrada de datos

Input

• Repetición
while expr

instrucción

endwhile
endwhile

for i = 1 to m (en C: for(i=1;i<=m;i++)

instrucción

endfor

do

instrucción

while expr

Algoritmos

21

Pseudocódigo

• Decisión

if expr

instrucción

endif

• Escritura o salida de datos

Output
Output

Algoritmos

22

Análisis de algoritmos

Problema: Buscar el mayor valor en una lista de números

desordenados (array)

i = 2
while i <= n
while i <= n

Algoritmo: (n = número de elementos)
1 max = s1
2
3
3
4
5
6
7

i = i + 1
endwhile

if si > max then

max = si

Algoritmos

23

Análisis de algoritmos

Número de operaciones realizadas (unid):

Línea Operaciones Tiempo
1 indexado y asignación 2
2 asignación 1
3 comparación 1
4,5,6 2 indexado, comparación, 6
4,5,6 2 indexado, comparación, 6

2 asignación, suma

Tiempo total:
t(n) = 2 + 1 + (n – 1) + 6·(n – 1) = 3 + 7·(n – 1) = 7n – 4

Algoritmos

24

Notación asintótica

• Es útil concentrarse en la tasa de crecimiento del tiempo de

ejecución t como función del tamaño de la entrada n.

• Se usa la notación O grande (cota superior al ritmo de

crecimiento de un algoritmo):

Sean f(n) y g(n) funciones no negativas, f(n) es O(g(n)) si hay
Sean f(n) y g(n) funciones no negativas, f(n) es O(g(n)) si hay
un valor c > 0 y
n0

≥ 1 tal que f(n) ≤ cg(n) para n ≥ n0

• Se dice que f(n) es de orden g(n)
• Ej: 7n – 4 es O(n) si c=7 y n0 = 1
• Generalmente para cualquier polinomio

aknk + ak-1nk-1 +...+ a0 es O(nk)

Algoritmos

25

Experimento de Algoritmo

•

Contar el número de personas en una sala

1. Ponerse de pie.

2. Pensar para sí mismo “Soy el Nº 1”

3. Emparejarse con alguien; sumar sus números; tomar la

suma como su nuevo número.
suma como su nuevo número.

4. Uno de la pareja debe sentarse.

5.

Ir al paso 3 si hay alguien de pie.

Algoritmos

26

Desarrollo de un Algoritmo

• Problema:

– Se desea viajar de la estación A a la estación B de

un metro.

Algoritmos

27

Ejemplo - Algoritmo Metro

Algoritmo Metro
Input A, B
if A y B están en la misma línea L

[las dos estaciones]

then

viajar en la línea L de A a B

else

[A y B están en diferentes líneas ]

hallar to