algoritmos. 1 definiciones de algoritmos es un procedimiento computacional bien definido que toma...
TRANSCRIPT
Algoritmos
1
Definiciones de Algoritmos
• Es un procedimiento computacional bien definido que toma algún valor, o un conjunto de valores, como entrada y produce algún valor, o un conjunto de valores, como salida.
• Es una secuencia de pasos computacionales para transformar la entrada en la salida.
• Es una herramienta para solucionar un problema computacional bien especificado.
1
Estratégia: Dividir para gobernar
Dividir el problema en subproblemas
En la resolución de un problema complejo, se divide en varios sub problemas y seguidamente se vuelven a dividir los sub problemas en otros mas sencillos, hasta que puedan implementarse en el computador.
1
Diseño top-down
Se entiende como diseño descendente ( Top-Down / Norte-Sur ) o diseño modular:
El proceso de ruptura del problema en cada etapa se llama refinamiento sucesivo.
• Cada problema se resuelve mediante un modulo (subprograma) y tiene un solo punto de entrada y un solo punto de salida.
• Un programa bien diseñado consta de un programa principal (modulo de nivel mas alto) que llama a subprogramas (módulos de nivel mas bajo), que a su vez pueden llamar otros sub programas.
Los programas que se estructuran de esta forma, se dicen que tienen diseño modular y el método de romper el programa en modos pequeños se llama programación modular.
1
Definición formal del problema cálculo del
factorial Entrada: Número entero n
Salida: Número entero fac(n) tal que: 0 si n < 0 1 si n == 0 1 si n == 1 n * fac(n-1) si n > 1
Ejemplo instancia: Entrada: 3 Salida: 6
fac(n)
1
Definición formal del problema máximo común
divisor Entrada: Números enteros m,n
Salida: Número entero mcd(n) tal que: n si m%n == 0 mcd(n, m%n) si m%n > 0
Ejemplo instancia: Entrada: 105, 6 Salida: 3
mcd(n)
Algoritmos de Búsqueda
1
Definición formal del problema de búsqueda
Entrada:• secuencia de n números <a
1, a
2,..,a
n>
• Un número b
Salida:
• un entero i, tal que b == ai (igual)
• 0 si b != ai, para i = 1,...,n
Ejemplo instancia: Entrada: <5, 6, 9, 12> y 9 Salida: 3
1
Algoritmos de Búsqueda
Definición: Son algoritmos para encontrar un dato dentro de una estructura o arreglo
- Se ha desarrollado un conjunto de algoritmos de búsqueda que varían en complejidad, eficiencia y tamaño del dominio de búsqueda.
- Si se conoce por anticipado en qué tipo de “orden” inicial se encuentran los datos, es posible elegir un algoritmo que sea más adecuado.
1
Tipos de Búsqueda
- Búsqueda Secuencial.
- Búsqueda Binaria.
1
Búsqueda Secuencial
Consiste en ir comparando el elemento que se busca con cada elemento del arreglo hasta que se encuentra. Buscar M:
I N F O M Á T I C A
M M M M M Índice resultado = 4
0
1
2
3
4
5
6
7
8
9
1
Algoritmo Búsqueda Secuencial
for (i=0; i < LARGO; i++)
if (a[i]==Elemento_buscado)
printf(“Elemento encontrado en: %d\n”, i);
1
Búsqueda Binaria
Los elementos del arreglo se encuentran ordenados y no están repetidos. En cada iteración el dominio de búsqueda se divide en 2. Buscar 32:
3 5 8 20 32 45 60 73
32 32 Resultado = 432
0
1
2
3
4
5
6
7
1
Algoritmo Búsqueda Binaria
tipo A[LARGO]
Max=LARGO-1;
min=0;
Encontrado=0;
while(min+1<max && !Encontrado){
Medio=(Max+min)/2
if (A[Medio]==Elemento){
printf(“Elemento Encontrado\n”);
Encontrado=1; /*Fuerza la salida del ciclo*/
}
if (A[Medio]<Elemento) Max=Medio;
if (A[Medio]>Elemento) min=Medio;
}
1
Búsqueda secuencial bidimensional por filas
Algoritmo:tipo A[filas][columnas]
for (i=0;i<filas;i++)
for (j=0;j<columnas;j++)
if (A[i][j]==elemento)
printf(“Encontrado en: A[%d][%d]\n”,i,j);
1
Búsqueda secuencial bidimensional por columnas
Algoritmo: tipo A[filas][columnas]
for (j=0;j<columnas;j++)
for (i=0;i<filas;i++)
if (A[i][j]==elemento)
printf(“Encontrado en: A[%d][%d]\n”,i,j);
1
Algoritmo de Búsqueda
Ejercicios:- Crear un programa que busque un caracter
dentro de un vector.- Crear un programa que busque el número
más pequeño en un vector.- Buscar un número seleccionado dentro de un
arreglo ordenado.- Hacer lo mismo pero con una lista
encadenada.
Algoritmos de Ordenamiento
1
Definición formal del problema de ordenamiento
Entrada:
• secuencia de n números <a1, a
2,..,a
n>
Salida:
• Una permutación <a'1, a'
2,..,a'
n>
reordenamiento de la secuencia, tal que:
a'1
< a'2
< ... < a'n
Ejemplo instancia: Entrada: <5,3,1,6,0> Salida: <0,1,3,5,6>
1
Algoritmos de Ordenamiento
Definición:– Son algoritmos que fueron realizados para
ordenar un conjunto de datos. Los algoritmos varían según su facilidad de entendimiento, su eficiencia, cantidad de código necesario para implementarlos, complejidad, requisitos necesarios de los datos.
1
Algoritmos de Ordenamiento
Tipos de Algoritmos:1.- Ordenamiento Burbuja.2.- Insertion-Sort3.- Quick-Sortetc...
1
Ordenamiento Burbuja
El algoritmo consiste en que los elementos más pesados se hundan y los más livianos salgan a flote.
25 25
32
15
1 1
32
15
32
1
15
25
32
1
25
15
32
25
1
15
32
25
15
1
32
25
15
1
1
Ordenamiento Burbuja
• Algoritmo
for (i=Largo-1;i>0;i--)
for (j=0;j<i;j++)
if (A[j]>A[j+1])
Intercambiar(A[j],A[j+1]);
Ordenamiento Por inserción
Ordenando una lista en forma alfabética (cont.)
Ordenando una lista en forma alfabética (cont.)
Algoritmo de sort por inserción en pseudocódigo
1
Algoritmos de Ordenamiento
Ejercicios:- Ordenar un conjunto de n enteros de menor a
mayor.- Lo mismo pero en lista encadenada
1
Stack o Pila
Definición:– Una pila es una estructura de datos, a la cual se le puede
ingresar o sacar elementos por un sólo lado. También se conoce como LIFO (Last In First Out).
1
Stack o Pila (cont.)
Operaciones básicas:– Insertar: inserta un elemento en el tope de la pila.– Sacar: Saca un elemento del tope de la pila.– Tope: Muestra el elemento ubicado en el tope de
la pila.– Vacía: Retorna verdadero si la pila está vacía.
Fila o cola
Definición:– Una pila es una estructura de datos, a la cual se le puede
ingresar elementos por un lado y retirar por el otro. También se conoce como FIFO (First In First Out).
Fila o cola (cont.)
Operaciones básicas:– Insertar: inserta un elemento alfinal de la fila.– Sacar: Saca un elemento del inicio de la fila.– Vacía: Retorna verdadero si la pila está vacía.