Download Algoritmos - biblioteca-uvg-2011

Algoritmos
1
Departamento de Ciencia de la Computación
Algoritmos - Significado (1/2)
Deriva de la traducción al latín del
apellido del matemático y astrónomo
árabe, Mohamed al-Khowarizmi, en la
palabra “algorismus”, posteriormente
ALGORITMO.
El interés de él era resolver ciertos
problemas de aritmética y desarrolló un
número de métodos para hacerlo.
2
Departamento de Ciencia de la Computación
Algoritmos - Significado (2/2)
Estos métodos eran presentados como
listas de instrucciones específicas (muy
parecidas a una receta) y su nombre se
ha asociado a tales métodos.
A al-Khowarizmi se le considera el
padre de la algoritmia (ciencia que trata
de los algoritmos), conjuntamente con
Euclides.
3
Departamento de Ciencia de la Computación
Algoritmos - Concepto
Método para resolver un problema mediante
una serie de pasos precisos, definidos y
finitos.
4

Preciso: Indica el orden de cada paso.

Definido: Si se sigue el algoritmo varias
veces debe producir el mismo resultado.

Finito: Tiene fin. Número definido de pasos
Departamento de Ciencia de la Computación
Algoritmos - Propiedades



Debe tener un inicio
Pasos individuales
No debe ser ambiguo



Debe tener un fin o terminación
Debe dar alguna indicación de haber
logrado el objetivo o no.

5
Siempre se sabe que acción tomar
En general, no requiere que de una
respuesta correcta.
Departamento de Ciencia de la Computación
Ejemplos:

Agregue un poco de sal (ambiguo)

Agregue 5 gramos de sal (definido)

Si el número es grande, réstele 5 (ambiguo)

Si el número es mayor a 200, réstele 5 (definido)

Avance unos metros, cruce y avance otro poco
(ambiguo)

Avance 250 metros, cruce a la derecha y avance 50
metros (definido)
6
Departamento de Ciencia de la Computación
Algoritmos - Métodos
Los métodos usuales
algoritmos son:
para

Narrativa (Lenguaje español)

Diagramas: De Flujo, UML, etc.
representar
• Ver Diagramas de Flujo - Completo v2.ppt (1-9)

7
Lenguaje de especificación de algoritmos
(pseudocódigo)
Departamento de Ciencia de la Computación
Narrativa
Problema: Sumar 3 números enteros.

Solución algorítmica:
Tomo el primer número, tomo el
segundo y lo sumo con el primero.
Tomo el tercer número y lo agrego a
lo que llevaba. Enseño el resultado de
la suma.
8
Departamento de Ciencia de la Computación
Diagrama de flujo
Problema:
Sumar 3 números enteros.

Inicio
Num1
Num2
Res  Num1 + Num2
Solución algorítmica:
Num3
Res  Res + Num3
Res
Fin
9
Departamento de Ciencia de la Computación
Pseudocódigo
Problema: Sumar 3 números enteros.

Solución algorítmica:
Inicio
Leer Num1
Leer Num2
Res  Num1 + Num2
Leer Num3
Res  Res + Num3
Escribir Res
Fin
10
Departamento de Ciencia de la Computación

11
¿¿¿ Dudas, Preguntas, Cansancio ???
Departamento de Ciencia de la Computación
Narrativa - Preparar una taza de Té













12
Tomar la tetera
Llenarla de agua
Encender el fuego (estufa)
Colocar la tetera en el fuego (estufa)
Esperar mientras no haya hervido el agua
Tomar una taza de té
Tomar una bolsa de té
Colocar la bolsa de té en la taza
Apagar el fuego (estufa)
Llenar la taza con agua de la tetera
Mientras no esté listo el té

Esperar
Fin Mientras
Si me gusta el azúcar entonces agregar 2 cucharaditas
Departamento de Ciencia de la Computación
Narrativa

Problema: Ordenar los pasos para pescar:







___ El pez se traga el anzuelo.
___ Enrollar el sedal.
___ Tirar el sedal al agua.
___ Llevar el pescado a casa.
___ Quitar el Anzuelo de la boca del pescado.
___ Poner carnada al anzuelo.
___ Sacar el pescado del agua.
EDUCACIÓN BÁSICA. ALGORITMOS Y PROGRAMACIÓN. Fundación Gabriel Piedrahita Uribe. http://www.eduteka.org
http://www.eduteka.org/AlgoritmosProgramacion.php
13
Departamento de Ciencia de la Computación
14
Departamento de Ciencia de la Computación
Ejemplo - Narrativa
Ver una película en el cine
15
Departamento de Ciencia de la Computación
1a. Versión

Solución algorítmica:
1.
2.
3.
4.
16
Ir al cine
Comprar una entrada
Ver la película
Regresar a casa
Departamento de Ciencia de la Computación
Observaciones

Pasos con condiciones


Ej: Si me gusta la película entonces voy a
verla
Pasos que se repiten

Ej: Mientras haya personas en la cola
• Esperar
• Avanzar en la cola
Fin Mientras

Avanzar pasos

17
Ej: Ir al paso X.
Departamento de Ciencia de la Computación
2a. Versión (1/2)
1.
Ver la cartelera de cines
1.
Si no proyectan la película entonces
1. Ir al paso 6
2.
2.
Sino Ir al cine
Comprar una entrada
1.
Si hay cola entonces
1. Formarse en la cola
2. Mientras haya más personas adelante
1. Avanzar en la cola
3. Fin Mientras
2.
Al llegar a la taquilla:
1. Si hay entradas entonces comprarla(s)
2. Sino @#!!!&* … Ir al paso 4
18
Departamento de Ciencia de la Computación
2a. Versión (2/2)
3.
Pasar a la sala
1.
2.
3.
Localizar la(s) butaca(s)
Apagar el celular
Mientras proyectan la película
1. Ver la película
4.
4.
5.
6.
19
Fin Mientras
Abandonar el Cine
Volver a casa
Fin
Departamento de Ciencia de la Computación
3a. Versión Paso1
1.
Ver cartelera de cines
1.
2.
Tomar el periódico
Mientras no lleguemos a la página de carteleras
1.
3.
2.
2.
4.
5.
6.
20
Fin Mientras
Elegir una película
1.
3.
Pasar la hoja
Si encuentro una película buena entonces elegirla
Sino desistir de la idea. Ir al paso 6.
Leer dirección de la sala y hora de proyección.
Elegir un medio de transporte.
Salir 1 hora antes de la hora de proyección en el medio
de transporte elegido.
Fin
Departamento de Ciencia de la Computación
21
Departamento de Ciencia de la Computación
Ejercicios

22
Desarrolle los algoritmos narrativos
que
resuelvan
los
siguientes
problemas:
1.
Cambiar una bombilla quemada del
techo.
2.
Cambiar una llanta pinchada.
Departamento de Ciencia de la Computación
Continuación…
Ver Diagramas de Flujo - Completo
v2.ppt (10-21)
23
Departamento de Ciencia de la Computación