PDF de programación - Introducción: El Rol de los Algoritmos en Computación - Estructura Datos y Algoritmos

Estructura Datos y Algoritmos

Introducción: El Rol de los Algoritmos en

Computación

ISC-213, Enero 2013
Ing. Carlos Camacho

Algoritmos

¿Qué es un Algoritmo?

Podemos decir:

● Procedimiento computacional definido por:
valores de entrada y valores de salida.

● Secuencia computacional que que transforma
una entrada a una salida.

●Resuelve un problema especifico.

19/01/2013

ISC-213, PUCMM

2

Ejemplo Algoritmo -

Ordenamiento


● Valores Entrada: Un secuencia de elementos
(a1, a2, a3, …, an).

● Valores Salida: Ordenamiento donde a1 <= a2
<= a3 …. <= an

● El caso de los elementos (23,56,11,67), la
salida es (11,23,56,67)

●A la secuencia de entrada se le llama Instancia

19/01/2013

ISC-213, PUCMM

3

Ejemplo Algoritmo - Ordenamiento

¿Por qué Ordenar?

● Operación fundamental en computación:

➔ Utilizado como paso intermedio.
➔ Muchas implementaciones existentes.

● ¿Cuál es mejor de utilizar?, depende:

➔ Cantidad de elementos.
➔ Tipo de almacenamientos.

19/01/2013

ISC-213, PUCMM

4

Algoritmo Correcto


●Un algoritmo es correcto si para toda instancia, se
detiene al obtener la salida correcta.

● Los algoritmos correctos resuelven el problema
computacional dado.

●Un algoritmo no-correcto puede no detenerse para
algunas instancias de entrada o detenerse con una
respuesta incorrecta

19/01/2013

ISC-213, PUCMM

5

Medio de expresión Algoritmo

● Descripción Alto Nivel:

➔ Se explica de forma verbal.
➔ Mostrando diagramas, omitiendo detalles.

● Descripción Formal:

➔Utilización pseudocódigo.

● Implementación:

➔ Expresado en un lenguaje de programación.

19/01/2013

ISC-213, PUCMM

6

Estructura de Datos

¿Qué son las Estructuras de Datos?

● Permite almacenar y organizar los datos
permitiendo su fácil acceso y modificación.

● Las operaciones básicas son: Agregar, Borrar y
Buscar.

● La elección de las estructuras de datos depende
del problema planteado.

19/01/2013

ISC-213, PUCMM

7

Estructura de Datos Básicas

● Arreglos:

● Punteros y Variables referencias:


● Listas Enlazadas

19/01/2013

ISC-213, PUCMM

8

Estructura de Datos Básicas

● Árboles:

● Árboles Binarios:

19/01/2013

ISC-213, PUCMM

9

Estructura de Datos Básicas

● Tarea API Colecciones en Java, 26-01-2012

19/01/2013

ISC-213, PUCMM

10

Técnica

● Puede que el algoritmo que necesitamos no esté
publicado.

● Necesitamos una técnica para diseñar y analizar
algoritmos para que podamos desarrollar nuevos:


➔Demostrar que producen la respuesta correcta
➔Entender su eficiencia

19/01/2013

ISC-213, PUCMM

11

Algoritmos como una Tecnología

● ¿Qué pasaría si las computadoras fueran
infinitamente rápidas y la memoria fuera gratis?

● Pero como no son infinitamente rápidas y la
memoria no es gratuita


➔El tiempo de cómputo y el espacio en memoria
son recursos limitados.
➔Hay que utilizarlos inteligentemente.
➔Algoritmos eficientes en tiempo y espacio.

19/01/2013

ISC-213, PUCMM

12

Eficiencia del Algoritmo

● Algoritmos de ordenamiento:

● InsertionSort → c1n^2
● MergeSort → c2*n*lgn

● InsertionSort más rápido que MergeSort para
entradas pequeñas.

● Hay un punto (tamaño de n) en el que MergeSort
ya es más rápido que InsertionSort

19/01/2013

ISC-213, PUCMM

13

Eficiencia del Algoritmo

● Con 10,000,000 de números:

•B (20 min) es 20 veces más rápida que A (2.3

días) para ordenar los números

• Ventaja de la eficiencia de MergeSort

19/01/2013

ISC-213, PUCMM

14

Análisis del Peor Caso y Caso

Promedio

● Normalmente calculamos sólo el peor caso

● El tiempo más largo de ejecución para
cualquier entrada de tamaño n

● El peor caso del tiempo de ejecución es la
frontera más alta

● Garantizamos que el alg. nunca tardará más
que eso

● Para algunos algoritmos el peor caso ocurre
muy frecuentemente (i.e. búsqueda en BD)
● El caso promedio es frecuentemente tan malo
como el peor caso

19/01/2013

ISC-213, PUCMM

15

Diseñando Algoritmos

● Hay muchas maneras de diseñar algoritmos:


● InsertionSort

● Método incremental

● Otros métodos como
● Divide y Vencerás

19/01/2013

ISC-213, PUCMM

16

Divide y Vencerás

3 pasos en cada nivel de recursión:


● Divide el problema en subproblemas
● Vencerás los problemas resolviéndolos
recursivamente, si el problema es trivial
(suficientemente pequeño) lo resuelve de
manera directa
● Combina las soluciones para obtener la
solución al problema original

19/01/2013

ISC-213, PUCMM

17