Download - Programación 3: fundamentos
Programación 3
Fundamentos
Angel Vázquez-Patiñ[email protected]
Departamento de Ciencias de la ComputaciónUniversidad de Cuenca
19 de septiembre de 2016
19/09/16 Angel Vázquez-Patiño 2/51
Objetivos
1.Revisar conceptos básicos de tipos de datos
2.Revisar conceptos de estructuras de datos
3.Entender el concepto de eficiencia de un algoritmo
4.Conocer las propiedades matemáticas de la notación O-grande
5.Conocer la complejidad de las sentencias básicas de todo programa Java
19/09/16 Angel Vázquez-Patiño 3/51
Contenido
Tipos de datos
La necesidad de las estructuras de datos
Eficiencia y exactitud
Notación O-grande
Complejidad de las sentencias básicas de Java
19/09/16 Angel Vázquez-Patiño 5/51
Tipos de datos● Fuertemente tipado (e.g., Pascal, C, Java)
– No se permiten violaciones de los tipos de datos
Ventajas● Prevención y detección de errores● Compresión y organización de ideas acerca de
sus objetos● Identificación y descripción de propiedades
únicas de ciertos tipos
19/09/16 Angel Vázquez-Patiño 6/51
Tipos de datos
Definiciones● Conjunto de valores y operaciones asociadas a
esos valores● Dos partes: un conjunto de datos y las
operaciones que se pueden realizar sobre ellos
Clasificación● Tipos primitivos● Tipos compuestos● Tipos agregados
19/09/16 Angel Vázquez-Patiño 7/51
Tipos de datos
Tipos primitivos (datos atómicos)● Conjunto de valores y operaciones sobre esos
valores
19/09/16 Angel Vázquez-Patiño 8/51
Tipos de datos
Tipos de datos compuestos● Se pueden dividir en subcampos que tengan
significado
59374051000
593: Ecuador
7: Azuay
4051000: teléfono
19/09/16 Angel Vázquez-Patiño 9/51
Tipos de datos
Tipos de datos agregados● Los datos compuestos son conocidos muchas
veces como tipos agregados● Tipos de datos cuyos valores constan de
colecciones de elementos de datos● Un tipo agregado se compone de tipos de
datos previamente definitivos
Tipos agregados básicos● Arrays, secuencias y registros
19/09/16 Angel Vázquez-Patiño 10/51
Tipos de datos
Tipos de datos agregados● Array o arreglo
– Array de enteros: [4, 6, 8, 35, 46, 0810]
● Secuencia o cadena– Cadena = “Esta es una secuencia de chars”
● Registro– Puede contener como elementos datos agregados y
primitivos
– Al contrario que en los arrays, los campos de los registros pueden ser de diferentes tipos de datos
19/09/16 Angel Vázquez-Patiño 11/51
Tipos de datos
Tipos de datos agregados● Registro
– A los campos se accede mediante identificadores
– El registro es el tipo de dato más próximo a la idea de objeto
19/09/16 Angel Vázquez-Patiño 14/51
Necesidad de estructuras de datos● ¡Eficiencia!
Definición● Una estructura de datos es una combinación
de elementos en la que cada uno es o bien un tipo de dato u otra estructura de datos
● Un conjuntos de asociaciones o relaciones (estructura) que implica a los elementos combinados
19/09/16 Angel Vázquez-Patiño 15/51
Necesidad de estructuras de datos
Solución eficiente● Si resuelve el problema dentro de las
restricciones de recursos requeridas● Cuando requiere menos recursos que las
alternativas conocidas
Costo● Cantidad de recursos que la solución
consume, especialmente tiempo
19/09/16 Angel Vázquez-Patiño 16/51
Necesidad de estructuras de datos
Selección de una estructura de datos
1)Determinar las restricciones de recursos
2)Determinar las operaciones básicas que se deben soportar y cuantificar las restricciones de recursos para cada una. E.g., operaciones básicas son la inserción de un dato en la estructura de datos o encontrar un dato determinado en dicha estructura
3)Seleccionar la estructura de datos que cumple mejor los requisitos o requerimientos
19/09/16 Angel Vázquez-Patiño 17/51
Necesidad de estructuras de datos
Selección de una estructura de datos
Preguntas a responder antes de la elección
1)¿Todos los datos se insertan en la estructura de datos al principio o se entremezclan con otras operaciones?
2)¿Se pueden eliminar los datos?
3)¿Los datos se procesan en un orden bien definido o se permite el acceso aleatorio?
19/09/16 Angel Vázquez-Patiño 19/51
Eficiencia y exactitud
Objetivos al diseñar un algoritmo● Que sea fácil de entender, codificar y depurar● Que haga uso eficiente de los recursos
Análisis de algoritmos● Número de operaciones● Medir el tiempo● Centrado en la ejecución de bucles. Funciones
lineales en función del número de instrucciones
19/09/16 Angel Vázquez-Patiño 20/51
Eficiencia y exactitud
La eficiencia como factor espacio-tiempo debe estar estrechamente
relacionada con la buena calidad, el funcionamiento y la facilidad de mantenimiento del programa.
19/09/16 Angel Vázquez-Patiño 21/51
Eficiencia y exactitud
Formato general de la eficiencia● Función del número de elementos que tienen
que ser procesados
19/09/16 Angel Vázquez-Patiño 22/51
Eficiencia y exactitud
Formato general de la eficiencia● Bucles lineales
19/09/16 Angel Vázquez-Patiño 23/51
Eficiencia y exactitud
Formato general de la eficiencia● Bucles logarítmicos
19/09/16 Angel Vázquez-Patiño 24/51
Eficiencia y exactitud
Formato general de la eficiencia● Bucles anidados
iteraciones = iteraciones del bucle externo x iteraciones bucle interno
19/09/16 Angel Vázquez-Patiño 25/51
Eficiencia y exactitud
Análisis de rendimiento● Complejidad del espacio● Complejidad del tiempo
19/09/16 Angel Vázquez-Patiño 27/51
Eficiencia y exactitud
Análisis de rendimiento● Enfoques de evaluación
– Peor caso
– Mejor caso
– Caso medio: mucho más difícil de calcular
19/09/16 Angel Vázquez-Patiño 29/51
Notación O-grande● Factor (magnitud) de eficiencia● O(n), en el orden de n● La notación O indica la cota superior del tiempo
de ejecución de un algoritmo o programa
Con la notación O se expresa una aproximación de la relación entre el tamaño de un problema y la cantidad de proceso necesario para hacerlo. Por ejemplo, si f(n) = n^2 – 2n + 3 entonces f(n) es O(n^2)
19/09/16 Angel Vázquez-Patiño 30/51
Notación O-grande
Determinar la notación O
1)En cada término, establecer el coeficiente del término en 1
2)Mantener el término mayor de la función y descartar los restantes. Los términos se ordenan de menor a mayor
19/09/16 Angel Vázquez-Patiño 36/51
Complejidad sentencias Java● Las sentencias de asignación, son de orden
constante O(1)● La complejidad de una sentencia de selección
es el máximo de las complejidades del bloque then y del bloque else
● La complejidad de una sentencia de selección múltiple (switch) es el máximo de las complejidades de cada uno de los bloques case
19/09/16 Angel Vázquez-Patiño 37/51
Complejidad sentencias Java● Para calcular la complejidad de un bucle,
condicional o automático, se ha de estimar el número máximo de iteraciones para el peor caso; entonces, la complejidad del bucle es el producto del número de iteraciones por la complejidad de las sentencias que forman el cuerpo del bucle
● La complejidad de un bloque se calcula como la suma de las complejidades de cada sentencia del bloque
19/09/16 Angel Vázquez-Patiño 38/51
Complejidad sentencias Java● La complejidad de la llamada a un método es
de orden 1, complejidad constante. Es necesario considerar la complejidad del método invocado
19/09/16 Angel Vázquez-Patiño 41/51
Complejidad sentencias Java
Ejemplo 2 ● Complejidad está determinada por el bucle
● El número de iteraciones es igual al número de veces que el algoritmo multiplica por dos a la variable k
19/09/16 Angel Vázquez-Patiño 42/51
Complejidad sentencias Java
Ejemplo 2 ● Si t es el número de veces que k se puede multiplicar hasta alcanzar el valor de n, que hace que termine el bucle, entonces k = 2^t
19/09/16 Angel Vázquez-Patiño 43/51
Complejidad sentencias Java
Ejemplo 2 ● Tomando logaritmos: t ≥ log2n; por consiguiente, el máximo de iteraciones es t = log2n
● El cuerpo del bucle consta de una sentencia simple y una sentencia de selección de complejidad O(1), por lo que tiene complejidad constante, O(1)
19/09/16 Angel Vázquez-Patiño 44/51
Complejidad sentencias Java
Ejemplo 2● Con todas estas
consideraciones, la complejidad del bucle y del método es
19/09/16 Angel Vázquez-Patiño 45/51
Complejidad sentencias Java
Ejemplo 3 ● El bucle interno está formado por tres sentencias de complejidad constante, O(1)
● El bucle externo siempre realiza n-1 veces el bucle interno
19/09/16 Angel Vázquez-Patiño 46/51
Complejidad sentencias Java
Ejemplo 3 ● A su vez, el bucle interno hace k veces su bloque de sentencias, k varía de 1 a n-1, de modo que el número total de iteraciones es
19/09/16 Angel Vázquez-Patiño 48/51
Conceptos y términos importantes● Complejidad● Eficiencia● Estructura de datos● Notación asintótica● Rendimiento de un programa● Tipo de dato
19/09/16 Angel Vázquez-Patiño 50/51
Referencia● Joyanes Aguilar, L., Zahonero Martínez, I.,
2008. Estructuras de datos en Java. McGraw-Hill, Madrid, Spain. Capítulo 1.