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

Imágen de pdf Introducción: El Rol de los Algoritmos en Computación - Estructura Datos y Algoritmos

Introducción: El Rol de los Algoritmos en Computación - Estructura Datos y Algoritmosgráfica de visualizaciones

Publicado el 15 de Julio del 2020
176 visualizaciones desde el 15 de Julio del 2020
114,8 KB
17 paginas
Creado hace 7a (24/01/2013)
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
  • Links de descarga
http://lwp-l.com/pdf17911

Comentarios de: Introducción: El Rol de los Algoritmos en Computación - Estructura Datos y Algoritmos (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad