Programación estructurada (2).pptx

Programación Estructurada

1. Programación estructurada Dr. Ricardo Vargas de Basterra [email protected] 1 /29 Lenguajes de Programación

2. Agenda Bienvenida y presentación Expectativas Encuadre de la asignatura Evaluación y plan de trabajo Recomendaciones Introducción Conclusiones 2 /29 Lenguajes de Programación

3. Bienvenida Es un placer recibirte a la materia “P rogramación Estructurada” 3 /29 Lenguajes de Programación

4. Presentación Dr. Ricardo Vargas de Basterra Doctor en Ciencias de la Computación Maestría en Ciencias y Maestría en Educación Ing. En Cibernética World-Class Performance San Diego State University Sielop & Internet University of Minnesota Catedrático desde 1983 Director en 4 instituciones Rector en 2 instituciones 4 /29 Lenguajes de Programación

5. Expectativas ¿Qué expectativas tienes de esta materia? ¿Qué piensas que vas a aprender? ¿Qué ya sabes del tema? 5 /29 Lenguajes de Programación

6. Materia Nombre: Programación estructurada Duración: 60 horas Horario : 15:40 a 17:20 Calendario : 3 de enero al 15 de febrero 6 /20 Lenguajes de Programación

7. Objetivo Al término de la asignatura el discente Aplicará los principios de la programación estructurada en el desarrollo de software y aplicativos para la institución. 7 /20 Lenguajes de Programación

8. Contenido 8 /20 Lenguajes de Programación

9. Reglas Generales Asistir a Clase. Hacer la tarea Participación activa individual y grupal. Cumplir fechas de entrega de tareas individuales (hasta la media noche del día señalado). Cumplir formatos de entrega. Prohibido el plagio o fraude. Se requiere tiempo de estudio. Esfuerzo por la calidad en sus trabajos. Uso de equipo de cómputo. 9 /29 Lenguajes de Programación

10. Reglas para Entrega de trabajos Se debe incluir una portada con todos los datos del estudiante. Se debe incluir un índice con los apartados que incluye la tarea. Redacta siempre una introducción . El contenido de la tarea colócalo en el cuerpo del documento con apartados específicos para cada requisito de la actividad. Todo esto dentro de la sección Desarrollo . Incluye una conclusión Agrega citas dentro del cuerpo de tu documento en formato APA. Coloca las referencias bibliográficas al final del documento, también en formato APA. Cada referencia bibliográfica debe haber sido citada al menos una vez en el cuerpo del documento. Todas las citas deben tener su referencia bibliográfica. Todas tus tareas deben ser de tu completa autoría (salvo las citas por supuesto). Los trabajos con información no propia serán anulados y evaluados con cero . 10 /29 Lenguajes de Programación

11. Calendario Inicio de Clase: lunes 7 de noviembre Fin de clase: viernes 16 de diciembre Receso: 28 de noviembre al 2 de diciembre Presentación de proyectos finales: por definir en enero 2023 Examen final: por definir enero 2023 11 /29 Lenguajes de Programación

12. Proyecto Integrador Desarrollar un Proyecto de un producto de software. El proyecto se realizará con entregas parciales cada lunes Se trata de un solo proyecto que se irá complementado. Se desarrolla en equipo 12 /29 Lenguajes de Programación

13. Evaluación Criterio Ponderación 1. Examen Escrito 30% 2. Proyecto Final 40% 3. Portafolio de evidencias y actividades de aprendizaje 30% TOTAL 100% Los criterios 2 y 3 incluirán procesos de autoevaluación y coevaluación 13 /29 Lenguajes de Programación

14. Recomendaciones generales Administra tu tiempo Pregunta tus dudas Prepárate para el examen final Evita el plagio y que se anule tu trabajo Participa activamente en casa sesión 14 /29 Lenguajes de Programación

15. Material de trabajo L as filminas que estoy usando, videos y materiales de lectura complementarios estarán en la plataforma y en la siguiente liga: https://drive.google.com/drive/folders/1i2E7EBSbyPDbSkyaGMCfni6Cur0QmhrN?usp=sharing 15 /29 Lenguajes de Programación

16. ¡Iniciamos! 16 /29 Lenguajes de Programación

17. introducción Antecedentes 17 /29 Lenguajes de Programación

18. Programación Proceso de diseñar, codificar, depurar y mantener el código fuente de programas de computadora. El código se escribe en un lenguaje de programación El código implementa un algoritmo 18 /29 Lenguajes de Programación

19. Algoritmo Conjunto finito de instrucciones ordenadas que tienen las siguientes características: Precisión Unicidad Finito Entrada Salida Generalidad Richard Johnsonbaugh 19 /29 Lenguajes de Programación

20. Expresiones algorítmicas Un algoritmo puede expresarse de distintas maneras: en forma gráfica, como un diagrama de flujo, en forma de código como en pseudocódigo o un lenguaje de programación, en forma explicativa 20 /29 Lenguajes de Programación

21. Programa Secuencia de instrucciones, escritas en un lenguaje de programación para realizar una tarea específica en una computadora Hay dos tipos fundamentales: Programa Fuente Programa Objeto Algoritmo + Estructura de Datos = Programa 21 /29 Lenguajes de Programación

22. Proceso 22 /29 Lenguajes de Programación

23. Herramientas y técnicas Diagramas de Bloques Diagramas de Flujo Grafos Tablas de Verdad Tablas de Decisiones Árboles de decisiones. Pseudocódigo 23 /29 Lenguajes de Programación

24. Diagramas de flujo 24 /29 Lenguajes de Programación

25. Pseudocódigo Descripción de alto nivel compacta e informal​ del principio operativo de un algoritmo. Diseñado para la lectura humana con independencia de cualquier lenguaje de programación. Omite detalles que no son esenciales para la comprensión humana del algoritmo (declaraciones de variables, código específico del sistema, etc.) 25 /29 Lenguajes de Programación

26. Compilación 26 /29 Lenguajes de Programación

27. Actividad En equipos de 3 personas respondan: ¿Qué es una teoría de programación? ¿Cuáles hay? ¿Qué es un lenguaje de programación? ¿Qué tipos hay? 27 /29 Lenguajes de Programación

28. Teoría de la programación Conjunto de principios que rigen un paradigma de programación y definen las características semánticas de cierto conjunto de lenguajes. Aspira a dar certidumbre sobre las formas más adecuadas de enfrentar un problema, modelarlo y encontrar su solución algorítmica para poder codificarlo en algún lenguaje y ejecutar la solución en una computadora 28 /29 Lenguajes de Programación

29. Evolución de la teoría de la programación La primer teoría de la programación.- La programación dura. Nacimiento de la Eniac (1943) La segunda teoría de programación.- La programación suave. Nace del modelo de John von Neumann (1945) La tercer teoría de programación.- Teorema de la Estructura. Resultado del trabajo de Conrado Böhm y Giuseppe Jacopini (1966). La cuarta teoría de la programación.- ADT, ocultación y acceso uniforme (1974). 29 /29 Lenguajes de Programación

30. Paradigma Duro Su característica principal es el alambrado físico por medio de cables para la definición del algoritmo. No existen reglas ni técnicas de diseño algorítmico formal. Lo único que hay son datos organizados en tipos primitivos. 30 /29 Lenguajes de Programación

31. Paradigma Libre No se cuenta con métodos formales de diseño algorítmico ni de sistemas . L os lenguajes implementan las siguientes estructuras básicas de control: secuencia, repetición, salto condicional y salto incondicional. Se desarrollan estructuras de datos más complejas tanto escalares como dinámicas así como el nacimiento de los primeros algoritmos formales. 31 /29 Lenguajes de Programación

32. Paradigma Estructurado Propone tres conceptos fundamentales: Una metodología formal de diseño basada en la descomposición funcional descendente (top-down). Un conjunto de recursos abstractos basados en la modularidad y las características de la misma (cohesión y acoplamiento) U n conjunto de estructuras básicas de programación . 32 /29 Lenguajes de Programación

33. Estructuras propuestas: 33 /29 Lenguajes de Programación

34. Paradigma orientado a objetos R esultado de una combinación de ideas, entre ellas los ADT, el ocultamiento de información y el acceso uniforme . (Parnas, Lizkov, Zilles y Hoare) Los principios de diseño son el Encapsulamiento, la Herencia y el Polimorfismo 34 /29 Lenguajes de Programación

35. Otros Paradigmas Programación orientada a aspectos Programación orientada a eventos Programación por componentes 35 /29 Lenguajes de Programación

36. Lenguajes de Programación Es una notación para codificar algoritmos de forma que puedan ser ejecutados por una computadora. (Alcalde) 36 /29 Lenguajes de Programación

37. Clasificación de los lenguajes 37 /29 Lenguajes de Programación

38. De la Programación Dura al Macroensamblador Alambrados Directos Codificación en lenguaje máquina 1E B80000 50 B82810 8ED8 8EC8 BF0000 BB1D00 8B0F BB1F00 8A07 FC F2 AE 7401 CB 4F CB Mnemónicos (add, sto, jmp) Macroensamblador (if) 38 /29 Lenguajes de Programación

39. Código Máquina Se codificaba directamente en hexadecimal Todas las operaciones de la computadora eran responsabilidad del programador Alta complejidad para programar y depurar sistemas Alto nivel de especialización Código específico para un procesador 39 /29 Lenguajes de Programación

40. Lenguajes de alto nivel 1a. Oleada Basados en paradigma libre. Fortran ( 1957 )1° de un linaje seguido por COBOL (1958), LISP (1958), ALGOL (1960), APL (1961), BASIC (1964), PL/1 (1965), Simula (1967) . Modelo Relacional y SQL (1970) 40 /29 Lenguajes de Programación

41. Segunda oleada N acen Pascal (1970), C (1972), Prolog (1972) y muchos de los anteriores hacen cambios en sus estructuras para implementar de lleno las ideas de Böhm y Jacopini 41 /29 Lenguajes de Programación

42. Tercera Oleada N acen nuevos lenguajes como Modula2 (1979), ADA (1983) y Java (1991) . Evolucionan otros como C que se convierte en C++, Pascal en Object Pascal (Delphi) y Basic en Visual Basic. 42 /29 Lenguajes de Programación

43. Taxonomía 43 /29 Lenguajes de Programación

44. El linaje de la programación 44 /29 Lenguajes de Programación

45. Más evolución 45 /29 Lenguajes de Programación

46. Paradigmas comunes 46 /29 Lenguajes de Programación

47. 47 /29 Lenguajes de Programación

48. 48 /29 Lenguajes de Programación

49. Tarea Realiza la lectura del documento: Modelo Para la Construcción de Algoritmos Apoyados en Heurísticas Capítulo 2: Apartados 2.1 y 2.2 Elabora un Mapa mental de la lectura 49 /29 Lenguajes de Programación

50. Lenguajes de Programación Tarea Revisar el material “Programas Introductorios” que está en la carpeta compartida Escribe los programas que ahí vienen y pruébalos Presenten un informe de la tarea 50 /29

51. Unidad 2 Solución de Problemas Empleando Algoritmos 51 /29 Lenguajes de Programación

52. Solución de Problemas Solo un conjunto de problemas tienen solución a través de procesos algorítmicos Antes de emprender el diseño de un algoritmo debemos tener claro si éste puede resolver el problema. 52 /29 Lenguajes de Programación

53. Teorema de Bohm-Jacopini Diagrama Propio : Aquel que posee un solo punto de inicio y uno solo de fin. Programa Propio : Posee un solo inicio y un solo fin; Todo elemento del programa es accesible, es decir, existe al menos un camino desde el inicio al fin que pasa a través de él; No posee ciclos infinitos. Equivalencia de programas : Dos programas son equivalentes si realizan, ante cualquier situación de datos, el mismo trabajo pero de distinta forma. Teorema de la estructura : Todo programa propio, realice el trabajo que realice, tiene al menos un programa propio equivalente que solo utiliza las estructuras básicas de programación, que son: la secuencia, la selección y la repetición. 53 /29 Lenguajes de Programación

54. Estructuras propuestas: 54 /29 Lenguajes de Programación

55. Construcción de Algoritmos 55 /29 Lenguajes de Programación

56. Análisis Productos: Listado de Resultados Listado de Procesos Datos de Entrada Relación de Restricciones Relación de Repeticiones Diccionario de Datos Herramientas: Árbol de Descomposición de Procesos Tablas de Decisión Árboles de Decisión 56 /29 Lenguajes de Programación

57. Diseño Productos Diseño de Secuencias Diseño de Condiciones Diseño de Repeticiones Diseño de Pruebas Diseño Integrado Herramientas Metodología Lenguaje Visual de Modelado Heurísticas 57 /29 Lenguajes de Programación

58. Construcción 58 /29 Lenguajes de Programación

59. Lenguaje Visual de Modelado (símbolos actuales) 59 /29 Lenguajes de Programación

60. Lenguaje LeMVI (pág. 141) Nuevo 60 /29 Lenguajes de Programación

61. Pseudocódigos Secuencia: Leer variable Proceso Imprimir variable/constante Condición Si condición Proceso Si condición Proceso De lo contrario Proceso Caso x 1: proceso 2: proceso N:proceso De lo contrario: Proceso Fin caso Ciclos Repite variable desde x Proceso Hasta y Repite mientras condición Proceso Fin repite Repite Proceso Hasta condición 61 /29 Lenguajes de Programación

62. Reglas de La Lógica Regla de Secuencia Regla de Equivalencia Regla de Composición Regla de Colaboración Regla de Cerradura Regla de Creación Regla de Integridad Regla de Flujo Regla de Existencia Regla de Restricción Regla de Repetición Regla de Combinación 62 /29 Lenguajes de Programación

63. Reglas de la lógica Regla de Secuencia .- Todas las tareas requieren de al menos una salida y cero, uno o más procesos y entradas. Primero se ejecutan las operaciones de entrada, luego las de proceso y finalmente las de salida. Regla de Equivalencia .- Las acciones (es decir, los procesos de entrada, proceso y salida) se consideran equivalentes entre sí y por tanto toda acción de proceso puede convertirse en entrada o salida y viceversa. Regla de Composición .- Un proceso complejo puede dividirse en subprocesos más simples colaborando en la solución y varios procesos individuales pueden combinarse en uno solo más complejo. Regla de Colaboración .- La(s) salida(s) de un proceso puede(n) usarse como entrada(s) de otro. Regla de Cerradura .- En todo lugar donde haya una acción (es decir, una entrada, un proceso o una salida) puede colocarse una estructura de control. En todo lugar que haya una estructura de control puede colocarse una acción. Regla de Creación .- En una tarea o procedimiento solo puede haber nuevas acciones o estructuras. Estas únicamente pueden agregarse entre acción y acción o entre acción y estructura o entre estructura y estructura. 63 /29 Lenguajes de Programación

64. Reglas de la lógica Regla de Integridad .- Las estructuras de control no pueden cambiar su diseño. Las operaciones son parte integral de las estructuras de control, no son estructuras independientes. Regla del Flujo .- La secuencia de ejecución está dictado por el diseño de cada estructura de control. Esta pude ser secuencial o anidada. Regla de Existencia .- Todas las variables antes de usarse deben estar definidas y si son parte de un proceso de cálculo deben tener un valor válido. Regla de Restricción .- Toda variable que deba cumplir con dominios del mundo real o del mundo virtual debe ser validado a través de una estructura de restricción. Regla de Repetición .- Toda Estructura o Acción que se escriben en más de una ocasión pueden ser introducidos con una estructura de repetición. Regla de Combinación .- Uno o más procedimientos pueden combinarse para formar otro procedimiento o una tarea. La composición puede darse por concatenación, anidación, fusión o adaptación. 64 /29 Lenguajes de Programación

65. Estrategias Espiral incremental. Agregar progresivamente funcionalidades al algoritmo. Retroceso. Iniciar por identificar las salidas y a partir de ahí identificar los procesos y luego las entradas. Divide y vencerás. Divide la tarea completa en subtareas . Fuerza Bruta. Interpretación directa del problema 65 /29 Lenguajes de Programación

66. Lenguajes de Programación Formatos para nombrar variables 66 /29

67. Lenguajes de Programación Tipos de datos en C 67 /29

68. Lenguajes de Programación Ejercicio “Hola Mundo” Investiga en línea como es el programa hola mundo en lenguaje C Instala DevC en tu computadora Transcribe el programa y ejecútalo 68 /29

69. Unidad 3 Ejecución Condicional 69 /29 Lenguajes de Programación

70. Operadores Símbolos que representan una operación. Se utilizan para construir expresiones Hay de tres tipos: Aritméticos (resultados numéricos) Relacionales (resultados booleanos) Lógicos (resultados booleanos) 70 /29 Lenguajes de Programación

71. Es un conjunto de constantes, variables y operadores con los cuales se realiza las operaciones para obtener un resultado. Ejemplo: resultado = a-(3*b+6)/c Operando Operando Operador Valor Constante o variable Expresión 71 /29 Lenguajes de Programación

72. Expresiones aritméticas Notación algorítmica para representar formulas matemáticas dentro de un programa Combina uno, dos o más valores (constantes o variables) a través de operadores aritméticos para generar un valor numérico 72 /29 Lenguajes de Programación

73. Jerarquía de operadores aritméticos 73 /29 Lenguajes de Programación

74. Ejemplo Se ejecutan por orden de jerarquía de operadores y de izquierda a derecha 74 /29 Lenguajes de Programación

75. Expresiones Relacionales Comparan dos expresiones a través de un operador relacional Generan un resultados Booleano (verdadero o falso) Jerarquía: Todos tienen la misma jerarquía Operador Significado == igualdad != Diferente > Mayor que < Menor que >= Mayor o igual <= Menor o igual 75 /29 Lenguajes de Programación

76. Ejemplos 1 > 2 = 0 falso 3 < 5 = 1 verdadero (7 – 4) == 3 = 1 verdadero 17 >= (5 + 12) = 1 verdadero i = 3; j = 7; i * j != 21 = 0 falso float a=0.1; (3*a – 0.3) == 0 = 0 falso (OJO con los reales) 3 > 1 > 0 = 1 verdadero Asignar a una variable la mayor de otras dos: a = 17; b = 15; c = a*(a>=b) + b*(b>=a); c = 17 a>=b = 1 y b>=a = 0 76 /29 Lenguajes de Programación

77. Expresiones Lógicas Comparan dos expresiones booleanas través de un operador lógico Generan un resultados Booleano (verdadero o falso) Jerarquía: 1º la Negación 2ª. Todos los demás 77 /29 Lenguajes de Programación

78. Ejemplos Se ejecutan por orden de jerarquía de operadores y de izquierda a derecha 78 /29 Lenguajes de Programación

79. 1. Aritméticos ^ *, / +, - 2. Relacionales 1. Mayor que > 2. Menor que < 3. Mayor igual que >= 4. Menor igual que <= 5. Igual = 6. Diferencia < > != 3. Lógicos AND OR NOT 3. Asignación =  Tipos de operadores y orden de ejecución 79 /29 Lenguajes de Programación

80. Flujo de Control Orden en el que se ejecutarán las instrucciones de un programa, desde su comienzo hasta que finaliza. El orden de ejecución es secuencial instrucción por instrucción La secuencia se puede alterar por una condición o por una repetición 80 /29 Lenguajes de Programación

81. Ejecución Secuencial Área de un rectángulo Lee base Lee altura area = base * altura Imprime area 81 /29 Lenguajes de Programación

82. Lenguajes de Programación Ejercicio Realiza programas para calcular lo siguiente: El área de un triángulo El área de un círculo El área de un cuadrado El área de un rectángulo El perímetro de un círculo El perímetro de cuadrado El perímetro de un rectángulo Las dos raíces de una ecuación de segundo grado 82 /29

83. Ejecución Condicional Se utilizan para determinar cual será flujo de ejecución de un programa dependiendo de una condición. Hay tres tipos: Simple Doble Mútiple 83 /29 Lenguajes de Programación

84. Condición Simple Determina si una sentencia (o bloque) se ejecuta en función del resultado de una condición Si es verdadera se ejecuta, de lo contrario la omite y continúa con la siguiente instrucción Lee nombre Si nombre = ‘Ricardo’ Entonces imprime ‘Te llamas igual que yo’ Imprime ‘Hola ‘, nombre 84 /29 Lenguajes de Programación

85. Condición Doble Dependiendo de una condición Se ejecuta una sentencia (o bloque) u otra. Luego continúa con la siguiente instrucción Lee valor Si (valor /2) = 0 Entonces imprime ‘el numero es par’ De lo contrario imprime ‘el numero es impar’ Imprime ‘Gracias por participar’ 85 /29 Lenguajes de Programación

86. Condición múltiple Dependiendo del valor que tome una variable se determina la ruta a seguir. Las rutas pueden ser tres o más Después se continúa con la siguiente instrucción Lee NumeroDia Caso NumeroDia 1: Imprime ‘Domingo’ 2: Imprime ‘Lunes’ 3: Imprime ‘Martes’ 4: Imprime ‘Miércoles’ 5: Imprime ‘Jueves’ 6: Imprime ‘Viernes’ 7: Imprime ‘Sábado’ otro: Imprime ‘No existe’ Fin del caso Imprime ‘Gracias por participar‘ 86 /29 Lenguajes de Programación

87. Anidación Se da cuando una estructura completa se coloca en la parte del proceso de otra Leer N Si N > 5 entonces Si N > 10 entonces Imprime N, ‘es mayor que diez’ De lo contrario Imprime N, ’es Mayor que 5 pero menor o igual a 10 De lo contrario Imprime N, ‘es menor que 5’ Imprime ‘Gracias por participar’ 87 /29 Lenguajes de Programación

88. Unidad 4 Iteraciones 88 /29 Lenguajes de Programación

89. Iteraciones También llamados ciclos o loops Es una estructura de control que se utiliza para repetir la ejecución de un proceso un número ‘n’ de veces 89 /29 Lenguajes de Programación

90. Mecanismos de control Existe un mecanismo de control para determinar cuando detener el ciclo Ese mecanismo de control está basado en el cumplimiento o no de una condición. Esa condición utiliza una variable de control normalmente llamada ‘i’ 90 /29 Lenguajes de Programación

91. Tipos de Ciclos 91 /29 Lenguajes de Programación

92. Ciclo cerrado ‘Repite’ Se conoce de antemano el número de veces que se repetirá un ciclo. En los lenguajes se conoce como ciclo ‘ for ’ 92 /29 Lenguajes de Programación

93. Ejemplo Se interpreta como “Repite el proceso desde que i es igual a 1 hasta 10 de uno en uno” Repite i=1 hasta 10 de +1 Inicio de bloque Proceso Fin de bloque 93 /29 Lenguajes de Programación

94. Ejemplo Se interpreta como “Repite el proceso desde que i es igual a m hasta n de menos 2 en menos 2” Los valores de n y m deben ser asignados antes de que el control de ejecución llegue a esa instrucción Repite i=m hasta n de -2 Inicio de bloque Proceso Fin de bloque 94 /29 Lenguajes de Programación

95. Ciclo abierto No se conoce de antemano el número de veces que se repetirá un proceso. Hay dos versiones: Aplicar la condición de control antes de la ejecución del ciclo Aplicar la condición de control después de la ejecución del ciclo 95 /29 Lenguajes de Programación

96. Ciclo abierto ‘Mientras’ El ciclo mientras realiza la repetición del proceso mientras una condición de control sea verdadera La condición se valida antes de realizar el proceso a repetir Dependiendo de la condición, puede suceder que el proceso a repetir no se ejecute nunca 96 /29 Lenguajes de Programación

97. Ejemplo Se interpreta como “Repite el proceso mientras que i es igual o menor que 10 ” En este tipo de ciclo el valor de la variable de control (i) debe ser actualizada dentro del proceso para buscar que el algún momento la condición deje de cumplirse y el ciclo concluya La variable i debe tener un valor inicial antes de comenzar la ejecución del ciclo Se le asigna un valor inicial a i Mientras i <= 10 Inicio de bloque Proceso i debe cambiar en algún momento Fin de bloque 97 /29 Lenguajes de Programación

98. Ejemplo Se interpreta como “Repite el proceso mientras que i es mayor que n ” El valor de n debe ser asignado antes de que el control de ejecución llegue a esa instrucción Se le asigna un valor inicial a i Se le asigna un valor inicial a n Mientras i > n Inicio de bloque Proceso i debe cambiar en algún momento Fin de bloque 98 /29 Lenguajes de Programación

99. Ciclo abierto ‘Hasta’ El ciclo hasta realiza la repetición del proceso hasta que una condición de control sea verdadera La condición se valida después de realizar el proceso a repetir Dependiendo de la condición, puede suceder que el proceso a repetir se ejecute una sola vez 99 /29 Lenguajes de Programación

100. Ejemplo Se interpreta como “Repite el proceso hasta que i sea diferente a 10 ” En este tipo de ciclo el valor de la variable de control (i) debe ser actualizada dentro del proceso para buscar que el algún momento la condición deje de cumplirse y el ciclo concluya La variable i debe tener un valor inicial antes de comenzar la ejecución del ciclo Se le asigna un valor inicial a i Inicio de bloque Proceso i debe cambiar en algún momento Hasta i <> 10 100 /29 Lenguajes de Programación

101. Ejemplo Se interpreta como “Repite el proceso hasta que i sea menor que n ” El valor de n debe ser asignado antes de que el control de ejecución llegue a esa instrucción Se le asigna un valor inicial a i Se le asigna un valor inicial a n Inicio de bloque Proceso i debe cambiar en algún momento Hasta que i < n 101 /29 Lenguajes de Programación

102. Observaciones Los ciclos infinitos se dan cuando las condiciones de control nunca se cumplen Los valores para las variables de control del ciclo debes asignarse antes de que el control de ejecución llegue al ciclo. 102 /29 Lenguajes de Programación

103. Lenguajes de Programación Reto ¿Como se podría usar un ciclo para validar la entrada de una variable? 103 /29

104. Lenguajes de Programación Ejercicio: El jardín Pedro es jardinero y le han pedido hacer un presupuesto para poner pasto en una casa que se está construyendo. El jardín es rectangular pero tiene una gran fuente circular en el centro. Pedro tiene que decirle a su cliente cuantos metros cuadrados de pasto tendrá que colocar y el importe total. Además Pedro cobra una cantidad por colocación que corresponde a su mano de obra. Alma es sobrina de Pedro y le dijo que podía hacerle un programa para que le ayudara a calcular lo que le piden. 104 /29

105. Lenguajes de Programación Tarea Revisar el material Modelo para la Construcción de Algoritmos Apoyados en Heurísticas Páginas 86 a 105 105 /29

106. ¿Qué recuerdas de la sesión anterior? Comenta las ideas principales de la sesión anterior

107. Lenguajes de Programación Funciones 107 /29

108. Actividad 1 de funciones En equipos de 3 personas respondan: ¿Qué es una Función? ¿Para que se usan? ¿Cómo se declaran? ¿Cómo se invocan? 108 /29 Lenguajes de Programación

109. Actividad 2 de funciones En equipos de 3 personas respondan: ¿Cómo se le pueden pasar valores a una función para que haga su trabajo? ¿Cómo regresa una función el resultado de su ejecución? 109 /29 Lenguajes de Programación

110. ¿Qué son?¿Para qué sirven? Son un grupo de sentencias bajo el mismo nombre que realizan una tarea específica. Sirven para facilitar la resolución de problemas mediante la aplicación del paradigma “Dividir y Conquistar”.

111. Librería MATH La librería math.h permite al programador efectuar cálculos matemáticos comunes a través de funciones.

112. Las funciones y los programas se parecen mucho, pero difieren: Los programas son usados por un usuario externo. Las funciones son utilizadas por un programador. El usuario del programa “Hola Mundo” no conoce que es la función printf. El programador que usa printf no siempre conocerá explícitamente como ésta hace para mostrar información en pantalla. El programador que escribió printf conoce exactamente su funcionamiento interno. Diferencia entre El Programa y las Funciones

113. Conceptos Básicos Función Grupo de sentencias bajo el mismo nombre que realizan una tarea específica. Llamada a una función Ejecuta el grupo de sentencias de una función. Retorno Una vez “llamada” la función, esta hace su trabajo, y regresa al mismo punto donde fue llamada.

114. Declaración de Funciones De forma similar a las variables, las funciones deben ser declaradas : La forma de declarar una función es siguiendo la forma predefinida : Por ejemplo : int potencia (int base, int exponente ); float farenheitACelsius (double celsius ); tipoDatoRetorno nombreFuncion ( lista parámetros );

115. Implementación de Funciones int potencia(int base, int exponente) { sentencias; } float farenheitACelsius(double celsius) { sentencias; } La primera línea se escribe igual que en la declaración, pero sin el punto y coma. Entre llaves se escriben las sentencias que ejecutan lo que debe realizar la función

116. ¿Cómo Retornar? Si la función debe generar un valor, lo retornará usando la sentencia return dentro del cuerpo de la función. La forma de usarla es: return (variable o expresión que se debe retornar); Esto especifica que la función debe terminar, retornando el valor calculado. Hay funciones que no retornan datos, en este caso, se puede usar return, pero sin mencionar una expresión. return;

117. Uso de Funciones Como las funciones siempre retornan un valor, el uso de una función consiste en utilizar el valor de retorno. Se lo puede hacer de dos formas: Almacenar el valor de retorno en una variable que deberá ser del mismo tipo de dato que el tipo de dato de retorno de la función. Utilizar el valor de retorno en una expresión.

118. Uso de Funciones (continuación) Ejemplo: void main( ) { int x; …. x = potencia(a,b); … } void main( ) { float c; …. c = farenheitACelsius(f); … } void main( ) { …. printf(“%d”, potencia(a,b)); … } void main( ) { …. printf(“%f”, farenheitACelsius(f)); … }

119. Lenguajes de Programación Realizar el paquete de ejercicios ¡A programar! 119 /29

120. Lenguajes de Programación Áreas de trabajo 120 /29

121. Lenguajes de Programación Áreas de trabajo: namespace Un namespace , no es más que una forma de crear un bloque, y que todas las funciones que estén dentro del mismo, estén asociadas a ese namespace (o espacio de nombres), al cual se le asigna un nombre para identificarlo. namespace hola void f() { std:: cout << “ hola ”; } 121 /29

122. Lenguajes de Programación Para que se usan Aparecen en C++ No existían en C Se usa para poder crear funciones sin el peligro que sus nombres estén repetidos en una librería cargada void f() { std :: cout << “ adios ”; } void f() { std :: cout << “hola”; } 122 /29

123. Lenguajes de Programación Cómo se usan Para identificar a que área de trabajo pertenece una función se utilizan los dobles dos puntos: “::” NombreNamespace ::función; namespace prueba { void f() { std :: cout << “hola”; } void f() { std :: cout << “ adios ”; } int main () { f(); prueba::f(); getchar (); return 0; } 123 /29

124. Lenguajes de Programación namespace std Es el namespace dónde está incluida toda la librería estándar de C++ Al incluirlo ya no tenemos que indicar std :: cout , sino que directamente indicamos cout using namespace std; int main() { f(); hola ::f(); cout << “ loquesea ”; getchar (); return 0; } 124 /29

125. Lenguajes de Programación Múltiples namespace namespace prueba { void f() { std :: cout << “hola”; } } namespace otro { void f() { std :: cout << “ adios ”; } } using namespace std; using namespace prueba; int main() { f(); otro ::f(); cout << “ loquesea ”; getchar (); return 0; } 125 /29

126. ¿Qué recuerdas de la sesión anterior? Comenta las ideas principales de la sesión anterior

127. Lenguajes de Programación apuntadores 127 /29

128. Lenguajes de Programación Definición Un apuntador es una variable que contiene la dirección en memoria de otra variable. Se pueden tener apuntadores a cualquier tipo de variable. 128 /29

129. Apuntador 2000 0010 ApuntaG 2001 0007 ApuntaD 2002 X 2003 X 2004 X 2005 X 2006 X 2007 X 2008 X 2009 X 2010 x 0000 34 A 0001 45 B 0002 12 C 0003 4 Var1 0004 99 Var2 0005 -98 Var3 0006 45 Vector1 0007 32 D 0008 55 E 0009 -9 F 0010 3 G Dirección Contenido Denominación Dirección Contenido Denominación

130. Declarar Apuntadores int *maria Declara un Apuntador del tipo entero Float *pedro Char *juan maria tiene la dirección de la variable *maría es equivalente al valor de la variable &maría obtiene la dirección de memoria de la variable maria

131. Apuntadores La dirección de x es 100 y la de y es 200 Además la variable ap es en 1000 Declara ap como apuntador Asigna ap como el apuntador de x Es decir no el valor de x que es 1 sino la Dirección de x Cual valor tendría entonces?

132. Ejemplo en c

133. Análisis del ejemplo

134. Apuntador de un Caracter

135. Aplicaciones

136. ¿Qué recuerdas de la sesión anterior? Comenta las ideas principales de la sesión anterior

137. Lenguajes de Programación Actividad Escribir una función que reciba dos valores por referencia y los invierta 137 /29

138. Punteros a Funciones

139. Lenguajes de Programación Actividad Investigar: Cadenas de caracteres Funciones disponibles sobre cadenas de caracteres Hacer un programa que pida dos cadenas, las concatene y las imprima al revés 139 /29

140. Lenguajes de Programación Ejemplo de direccionamiento con apuntadores a cadenas #include < cstdlib > #include <iostream> char * copiacadena ( char *destino, const char *origen); int main () { char destino[20]; char origen[20]; printf ("escribe la cadena: "); scanf ("%s", &origen); printf ("la cadena original es: %s \n", origen); printf ("Mando copiar la cadena \n"); copiacadena ( destino,origen ); printf ("la cadena original es: %s \n", origen); printf ("la cadena invertida es: %s \n", destino); getchar (); return 0; } char * copiacadena ( char * strDest , const char * strOrg ) { int len = strlen ( strOrg ); printf ("La longitud de la cadena original es: %d \n", len ); while ( len > 0) { *( strDest + len+1) = *( strOrg + len --); } * strDest = * strOrg ; return strDest ; } 140 /29

141. Lenguajes de Programación Tarea Investigar sobre arreglos Investigar sobre matrices Elaborar una presentación por equipos con ejemplos de los tres puntos. 141 /29

142. Trabajo con Cadena

143. Ejemplo

144. Algoritmos y estructurass de datos Algoritmos de búsqueda y ordenación 144 /29 Lenguajes de Programación

145. Lenguajes de Programación Formatos para nombrar variables 145 /29

146. Algoritmos básicos Dan soluciones a problemas comunes que pueden ser simples o complejos. Los casos fundamentales son: Intercambio de valores Contador Sumador/ Permutador Ordenación Búsqueda 146

147. Intercambio de valores Sean A y B dos variables con valores cualesquiera y se desea intercambiar éstos valores Solución posible Ejemplos: A = 3 y B = 7 A = B B = A Solución: Para evitar la perdida de valores se utiliza una variable temporal T Solución: T = A A = B B = T 147

148. Contador Un contador es una variable cuyo valor se incrementa o decrementa en una cantidad constante cada vez que se produce un determinado suceso o acción. Los contadores se utilizan con la finalidad de contar sucesos o acciones internas en un ciclo 148

149. Sumatoria Una sumatoria es una variable que suma sobre sí misma un conjunto de valores, para de esta manera tener la suma de todos ellos en una sola variable. La diferencia entre un contador y un sumador es que el primero se modifica usando valores fijos (1), la sumatoria se modifica en forma variable 149

150. Permutatoria Una permutatoria es una variable que multiplica sobre sí misma un conjunto de valores, para de esta manera tener el producto de todos ellos en una sola variable. 150  

151. Fases Contador Sumador Permutador Inicialización Contador = 0 Suma = 0 Mult = 1 Incremento/decremento Contador = Contador + 1 Contador = Contador – 1 Sumador = Sumador + valor Sumador = Sumador – valor Mult = Mult * valor 151 Tiene 3 Fases (se calculan en momentos de tiempo diferente dentro de ciclos): 1 . Inicialización (en cero o uno según el caso) 2. Calculo (Incremento, decremento, acumulación o multiplicación) 3. Utilización (la variable ya con el

152. Ejemplo Contador 152

153. 153 La Escuela

154. ¿Qué recuerdas de la sesión anterior? Comenta las ideas principales de la sesión anterior

155. Estructuras de Datos Colecciones de datos organizados que pueden ser de diferentes tipos y que comparten comportamientos Son medios para manejar grandes cantidades de datos 155

156. Estructuras de datos 156

157. Lenguajes de Programación Estructuras básicas Arreglos Matricies Registros 157 /29

158. Arreglos (Arrays) Colección de un número fijo de componentes que son del mismo tipo de dato. Forma general para declarar un arreglo de una dimensión: dataType arrayName[intExp]; Donde intExp es cualquier expresión constante que al evaluarse produce un número positivo entero. También, intExp especifica el número de componentes del arreglo.

159. Arrays Ejemplos: La instrucción: int num[5]; declara un arreglo llamado num de cinco componentes, cada uno de tipo int . num[0] num[1] num[2] num[3] num[4] num

160. Arrays Para acceder a los componentes de un arreglo , la forma general utilizada es: arrayName [ indexExp ] Donde indexExp , también llamado el index , es cualquier expresión cuyo valor debe ser un entero positivo . Especifica la posición de un componente dentro del arreglo . Ejemplo : int list[10]; // declara un arreglo llamado list de 10 componentes list[5] = 34; // almacena el valor 34 en la sexta posición del arreglo list 34 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

161. Arrays Supongamos que a es una variable de tipo int. Las instrucciones : a = 3; list[a] = 63; asignan el valor de 3 a la variable a, y luego le asigna el valor 63 a la cuarta posición del arreglo list. De la misma forma, si el valor de la variable a es 4, entonces la instrucción list[2 * a – 3] = 58; almacena el valor 58 dentro de list[5] porque 2*a-3 evalua a cinco .

162. Arrays Ejemplos : list[3] = 10; // asigna el valor de 10 al cuarto componente de list list [6] = 35; // asigna el valor de 35 a la posición siete de list list [5] = list[3] + list [6] ; // suma el contenido de list[3] y de list[6] a list[5] 10 45 35 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

163. Arrays Uso práctico de arreglos en C Problema sin arreglos : hacer un programa que en C que lea cinco números , los sume , y luego los escriba en el orden inverso como se entraron . Se necesitan declarar al menos cinco variables todas del mismo tipo para almacenar en memoria los números que se van a entrar .

164. Arrays Programa #1 #include< iostream > using namespace std; int main() { int num1, num2, num3, num4, num5; int sum; cout << “ Ingrese cinco enteros : “; cin >> num1, num2, num3, num4, num5; cout << endl ; sum = num1 + num2 + num3 + num4 + num5; cout << “The sum of the numbers = “ << sum << endl ; cout << “The numbers in reverse order are: “; cout << num5 << “ “ << num4 << “ “ << num3 << “ “ << num2 << “ “ << num1<< endl ; system(“pause”); return 0; }

165. Arrays Hacer el mismo programa pero para que lea 20 números en lugar de solo cinco . En vez de definir veinte variables del mismo tipo en el programa , es más conveniente definir un arreglo de veinte posiciones donde se pueda acumular cada valor en su lugar correspondiente , leerlos , sumarlos , y por último escribirlos en el orden inverso como se entraron .

166. Arrays Solución : #include< iostream > using namespace std; int main() { int list[100]; int sum = 0; cout << “Enter 100 integers: “; for ( int i = 0; i < 100; i ++) { cin >> list[ i ]; sum = sum + list[ i ] ; } cout << endl ; cout << “The sum of the numbers = “ << sum << endl ; cout << “The numbers in reverse order are: “; for( int i = 99; i >=0; i --) cout << list[ i ] << “ “; cout << endl ; system(“pause”); return 0; }

167. ¿Qué recuerdas de la sesión anterior? Comenta las ideas principales de la sesión anterior

168. Lenguajes de Programación Dimensiones del arreglo Hay arreglos de 1 dimensión con un solo índice para su acceso Pero puede haber arreglos de dos dimensiones con dos índices para su acceso. Ejemplo: Int A[ i,j ] Int A[i][j] 168 /29

169. Lenguajes de Programación Múltiples dimensiones 169 /29 ¿Crees que pueda haber arreglos de 3 dimensiones? ¿de 4? ¿de n dimensiones?

170. Lenguajes de Programación Ejercicio Retomemos el programa que calculaba el promedio de calificaciones de varios estudiantes Ahora convertirlo a un programa que utilice matricies Al terminar el programa de imprimir las notas de todos los estudiantes, su promedio individual, el promedio grupal y los conteos de estudiantes de excelencia, regulares y no acreditados 170 /29

171. Lenguajes de Programación 171 /29

172. ¿Qué recuerdas de la sesión anterior? Comenta las ideas principales de la sesión anterior

173. 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 == a i ( igual ) si b != a i , para i = 1,...,n Ejemplo instancia : Entrada: <5, 6, 9, 12> y 9 Salida : 3 Algoritmos de búsqueda y ordenación 173 /29 Lenguajes de Programación

174. 1 Entrada : secuencia de n números <a 1 , 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> Definición formal del problema de ordenamiento 174 /29 Lenguajes de Programación

175. 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. 175 /29 Lenguajes de Programación

176. 1 Tipos de Búsqueda Casos más famosos Secuencial Binaria 176 /29 Lenguajes de Programación

177. 1 Consiste en ir comparando el elemento que se busca con cada elemento del arreglo hasta que se encuentra . I N F O M Á T I C A R R R R R 0 1 2 3 4 5 6 7 8 9 10 Índice resultado = 4 Búsqueda Secuencial 177 /29 Lenguajes de Programación R

178. 1 Algoritmo Búsqueda Secuencial for (i=0; i < LARGO; i++) if (a[i]==Elemento_buscado) printf (“Elemento encontrado en: %d\n”, i); 178 /29 Lenguajes de Programación

179. 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. 3 5 8 20 32 45 60 73 32 32 0 1 2 3 4 5 6 7 Resultado = 4 32 179 /29 Lenguajes de Programación

180. 1 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; } Algoritmo Búsqueda Binaria 180 /29 Lenguajes de Programación

181. 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. 181 /29 Lenguajes de Programación

182. 1 Tipos de Ordenamiento Internos Externos Inserción Intercambio Casos más famosos Ordenamiento por burbuja ( bubble sort ) Quick Sort 182 /29 Lenguajes de Programación

183. 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 183 /29 Lenguajes de Programación

184. 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]); 184 /29 Lenguajes de Programación

185. 1 Búsqueda del más pequeño El algoritmo consiste en encontrar el más pequeño de un grupo de datos y colocarlo hasta arriba . 25 15 32 15 1 1 25 32 15 25 32 1 15 32 25 1 25 32 15 1 32 25 15 1 15 1 185 /29 Lenguajes de Programación

186. 1 Más Pequeño Algoritmo for ( i =0;i<=n-1;i++) { for (j=i+1;j<= n;j ++) { if (A[ i ]>A[j]) { x=A[ i ]; A[ i ]=A[j]; A[j]=x; } } } 186 /29 Lenguajes de Programación

187. Otros algoritmos de ordenación Quick Sort Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote. Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada. La lista queda separada en dos sublistas , una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados. 187 /29 Lenguajes de Programación

188. DIRECCIONES DE MEMORIA 1000 1001 1002 1003 &a es 1000 Las variables Tienen direcciones de memoria Si deseamos conocer dicha dirección En lenguaje C Se usa el operador & de dirección Ejemplo: int a; a = 3; printf(“Valor:%d Dir: %d”, a, &a ); Un puntero Es una variable que puede almacenar dirección de memoria

189. DECLARACION DE PUNTEROS Un tipo de dato El puntero solo podrá almacenar direcciones de memoria de variables del tipo especificado Se pueden definir punteros de cualquier tipo: float *pf; char *pc; Un identificador que siempre va antecedido del operador * pt almacena la dirección de x, se dice que pt apunta a x x pt int *p; 1000 1001 1002 1003 1004 1005 1000 int *pt, x; x = 3; pt = &x; 3

190. CONSULTANDO CONTENIDO Si un puntero apunta a una variable A través del puntero se puede llegar a conocer todo sobre la variable Ejemplo: c = ‘A’ printf (“%c”, *pc1); *pc1 = ‘N’ printf (“% c”,c ); Es equivalente a : printf(“%c”, c); Es equivalente a : c = ‘N’ Imprime ‘N’ pues c ya cambio char c, *pc1, *pc2; pc1 = &c; Si quiero conocer la dirección, uso directamente el puntero printf(“%d”, pc1); //Imprimo la dir. Almacenada por pc1 pc2 = pc1; //pc2 almacena la misma dir. que pc1 Si quiero conocer el contenido al que apunta un puntero, uso el operador *, sobre dicho puntero

191. EJERCICIO EN CLASE *p1 = *p2; int x,y; int *p1,*p2; x = -42; y = 163; p1 = &x; p2 = &y; *p1 = 17; *p2 = x+5; 1000 1004 Es equivalente a escribir x = y; p1 = p2; Esto indica que p1 ahora apunta a la misma variable que p2 1004 p1 = NULL; p2 = NULL; Esto es equivalente a “encerar” el puntero, y decir que no apunta a ninguna variable 1000 1004 1008 1012 x y p1 p2 -42 22 1000 1004 17 22 163 1004

192. Lenguajes de Programación Ejercicio Hacer un programa que defina las siguientes variables: Int a,b Int *p1,*p2, * Asignar lo siguiente a=1 B=2 *p1=&a *p2=&b Imprimir a b &a &b *p1 *p2 p1 p2 &p1 &p2 192 /29

193. ARITMETICA DE PUNTEROS Los operadores + y – Se pueden usar con punteros Pero el significado de la operación cambia un poco Si un entero ocupa 4 bytes, tomemos este ejemplo int x; int *p; p = &x; Si la dirección de x es un valor 100 y decimos p = p+2; Que dirección almacena p? 102 108 104 La suma indica que p se mueva 2 “enteros” mas adelante Cada entero equivale a 4 bytes 100 + 2*4 = 108

194. EJERCICIO EN CLASE main (){ double Lista[3]; double *p,*p1,*p2; int k; Lista[0] = 1; Lista[1] = 1.1; Lista[2] = 1.2; p = Lista; p = p + 2; printf (“%d”, *p); p = p - 1; printf (“%d”, *p); p1 = Lista+2; p2 = &Lista[0]; k = p1-p2; printf (“%d”, k); } 1000 1008 1016 Lista[0] Lista[1] Lista[2] p p2 p1 p se mueve 2 desfases p retrocede un desfase Da el total de desfases entre p1 y p2 1 1.1 1.2

195. Lenguajes de Programación Hacer un programa que Agregar al final del programa anterior la impresión de lo siguiente: Lista[0] Lista &Lista[0] p2 *p2 &p2 195 /29

196. ESTRUCTURAS o REGISTROS Es un grupo de “componentes”. Cada componente Tiene su propio identificador, y Se conoce como “elemento” o “campo” de la estructura Ejemplo: Es la declaración del nuevo “tipo de dato”: NombreCompleto Con este tipo de dato, podremos crear “variables”: NombreCompleto snombre , enombre ; struct NombreCompleto { char Primero[10]; char Inicial; char Ultimo[10]; };

197. USANDO ESTRUCTURAS primero inicial ultimo snombre Los registros de tipo NombreCompleto, tendrán la misma “estructura” Cada dato tiene diferente tamaño y espacio en memoria Cada dato representa una información diferente snombre es una variable de tipo NombreCompleto Tiene la misma forma que la del nuevo tipo de dato Cada miembro/campo ocupa memoria Para acceder a un campo, se indica, La variable seguida de un punto y del nombre del campo. Ejemplo snombre.Inicial = ‘L’;

198. Lenguajes de Programación Escribe estos programa /* Paso de una estructura por valor. */ #include < stdio.h > struct trabajador { char nombre[20]; char apellidos[40]; int edad; char puesto[10]; }; void visualizar( struct trabajador); main () /* Rellenar y visualizar */ { struct trabajador fijo; printf ("Nombre: "); scanf ("%s", fijo.nombre ); printf ("\ nApellidos : "); scanf ("%s", fijo.apellidos ); printf ("\ nEdad : "); scanf ("%d",& fijo.edad ); printf ("\ nPuesto : "); scanf ("%s", fijo.puesto ); visualizar(fijo); } void visualizar( struct trabajador datos) { printf ("Nombre: %s", datos.nombre ); printf ("\ nApellidos : %s", datos.apellidos ); printf ("\ nEdad : %d", datos.edad ); printf ("\ nPuesto : %s", datos.puesto ); } /* Paso de una estructura por referencia. */ #include < stdio.h > struct trabajador { char nombre[20]; char apellidos[40]; int edad; char puesto[10]; }; void visualizar( struct trabajador *); main () /* Rellenar y visualizar */ { struct trabajador fijo; printf ("Nombre: "); scanf ("%s", fijo.nombre ); printf ("\ nApellidos : "); scanf ("%s", fijo.apellidos ); printf ("\ nEdad : "); scanf ("%d",& fijo.edad ); printf ("\ nPuesto : "); scanf ("%s", fijo.puesto ); visualizar(&fijo); } void visualizar( struct trabajador *datos) { printf ("Nombre: % s",datos ->nombre); printf ("\ nApellidos : % s",datos ->apellidos); printf ("\ nEdad : % d",datos ->edad); printf ("\ nPuesto : % s",datos ->puesto); } 198 /29

199. Lenguajes de Programación Ejercicio Investiga en parejas lo siguiente: ¿Qué es una estructura tipo Pila? ¿Que comportamiento tiene? ¿Qué apuntadores requiere? ¿Cuáles son sus algoritmos básicos? Presenten dos ejemplos de su uso 199 /29

200. ¿Qué recuerdas de la sesión anterior? Comenta las ideas principales de la sesión anterior

201. TDA PILA Def: una pila es una lista ordenada de elementos en la que todas las inserciones y supresiones se realizan por un mismo extremo denominado tope o cima de la pila. Definición Estructura LIFO ( Last In First Out ): “último en entrar primero en salir ”

202. Operaciones básicas PUSH: apilar, meter POP: desapilar , sacar TOP: cima, tope Underflow (pila vacía) OverFlow (Pila Llena) TDA PILA

203. Operaciones Crear_pila (P: pila, ok: lógico) Borrar_pila (P: pila, ok: lógico) Vacía? (P: pila, resp : lógico) Llena? (P: pila, resp : lógico) Push (P: pila, X: elemento, resp : lógico) Pop (P: pila, X: elemento, resp : lógico) Top (P: pila, X: elemento, resp : lógico) TDA PILA

204. Lenguajes de Programación Comportamiento 204 /29

205. Implementación Vectores Variables estáticas Tamaño máximo fijo Peligro de desbordamiento ( overflow ) Uso ineficiente de memoria Listas enlazadas Variables dinámicas No riesgo de overflow Limitadas por memoria disponible Cada elemento necesita más memoria (guardar dirección siguiente) Uso eficiente de memoria Problema común: underflow o subdesbordamiento

206. Implementación con vectores Definición de tipos ELEMENTO = T; PILA = registro de tope: numérico; arreglo: vector[1..MAX] de ELEMENTO; finregistro; Operación Push Algoritmo PUSH (P: Pila, X: ELEMENTO, ok: lógico) es resp: lógico; INICIO Llena?(P,resp) ; si resp entonces ok:= falso; sino P.tope:= P.tope + 1; P.arreglo[P.tope]:= X; ok:= cierto; finsi; FIN TDA PILA

207. Implementación con vectores Operación Pop Algoritmo POP (P: PILA, X: ELEMENTO, ok: lógico) es INICIO Vacia (P, resp); si resp entonces ok:= falso; {no hay elementos q sacar} sino X:= P.arreglo[P.tope]; P.tope:= P.tope -1; ok:= cierto; finsi ; FIN Operación Top Algoritmo TOP (P: PILA, X: ELEMENTO, ok:lógico) es resp: lógico; INICIO Vacia? (P, resp); si resp entonces ok:= falso; {pila vacía} sino ok:= cierto; X:= P.arreglo[P.tope]; finsi; FIN TDA PILA

208. Lenguajes de Programación Ejercicio Investiga en parejas lo siguiente: ¿Qué es una estructura tipo Cola? ¿Que comportamiento tiene? ¿Qué apuntadores requiere? ¿Cuáles son sus algoritmos básicos? Presenten dos ejemplos de su uso 208 /29

209. TDA COLA Def: una cola es una lista ordenada de elementos en la que todas las inserciones se realizan por un extremo (frente o principio) y las supresiones se realizan por el otro (final). Definición Estructura F IFO ( Fir st In First Out ): “ primer o en entrar primero en salir ”

210. Operaciones básicas QUEUE: encolar, meter DEQUEUE: desencolar, sacar

211. Operaciones Crear_ co la ( C : co la, ok: lógico) Borrar_ cola ( C : col a, ok: lógico) Vacía? ( C : co la, resp: lógico) Llena? ( C : co la, resp: lógico) Queue ( C : co la, X: elemento, resp: lógico) Dequeue ( C : co la, X: elemento, resp: lógico) Tamaño (C: cola, N: numérico)

212. Implementación con vectores Si e l principio de la cola es fijo en la primera posición del vector y el final es variante para eliminar un elemento de la cola hay que desplazar todos los demás una posición ( Dequeue() es inefici ente). Si principio y final de la cola son variantes, no hacen falta desplazamientos. Problema : la cola puede desbordarse teniendo celdas libres.

213. Implementación con vectores Solución : VECTOR CIRCULAR cuando algún índice llega al final, vuelv e al comienzo del vector Para saber si la cola está llena o vacía, su tamaño se controla con el campo tam del registro Definición de tipos ELEMENTO = T; COLA = registro de prim, ult, tam : numérico; arreglo: vector[1..MAX] de ELEMENTO; finregistro;

214. Implementación con vectores Operación QUEUE Algoritmo QUEUE(C: COLA, X: ELEMENTO, resp: lógico) es INICIO Llena? (C,resp); si resp = cierto entonces {la cola está llena} Escribir “Cola llena”; resp := falso; sino {la cola no está llena, por lo que procedemos a añadir el elemento} C.ult := (C.ult + 1) mod MAX; {hacemos que ult avance de forma circular} C.arreglo[C.ult] := X; C.tam := C.tam +1; {pues ahora hay un elemento más en la cola} finsi ; FIN

215. Implementación con vectores Operación Dequeue Algoritmo DEQUEUE(C: COLA, X: ELEMENTO, resp: lógico) es INICIO Vacía? (C,resp); si resp = cierto entonces {la cola está vacía} Escribir “Cola vacía”; resp := falso; sino {hay al menos un elemento} X := C.arreglo[C.prim]; C.prim := (C.prim + 1) mod MAX; C.longitud := C.longitud -1; finsi; FIN

216. Aplicaciones de las colas Principalmente: gestión de recursos Sistemas de tiempo compartido: los recursos (CPU, memoria, …) se asignan a los procesos que están en cola de espera en el orden en el que fueron introducidos . Colas de impresión: al intentar imprimir varios documentos a la vez o la impresora está ocupada, los trabajos se almacenan en una cola según el orden de llegada. Simulación por computadora de situaciones reales: una cola de clientes en un supermercado o el tiempo de espera para ser atendidos por un operador de una línea telefónica.

217. Lenguajes de Programación Ejercicio Investiga en parejas lo siguiente: ¿Qué es una estructura tipo Doblecola ? ¿Que comportamiento tiene? ¿Qué apuntadores requiere? ¿Cuáles son sus algoritmos básicos? Presenten dos ejemplos de su uso 217 /29

218. Lenguajes de Programación Operaciones en una estructura de doble cola Escribir por la derecha Leer por la derecha Escribir por la izquierda Leer por la izquierda Consultar derecha Consultar izquierda Recorrer la cola 218 /29

219. Lenguajes de Programación Tarea Investigar sobre las siguientes estructuras: Listas encadenadas Listas encadenadas circulares Listas doblemente encadenadas Listas doblemente encadenadas circulares 219 /29

220. ¿Qué recuerdas de la sesión anterior? Comenta las ideas principales de la sesión anterior

221. Lenguajes de Programación Listas encadenadas Estructuras formadas por nodos Un nodo tiene al menos dos campos (sección de dato y sección de apuntador) Es dinámica y no contigua (dispersa) 221 /29

222. Lenguajes de Programación Nodo tiene una sección de datos y una de apuntadores Si hubiera una lista llamada Luis con dos campos: Dato Link Luis.dato Luis.link Luis.dato [apuntador] Luis.link [apuntador] Si apuntador fuera 3 Luis.dato [3] 222 /29

223. Lenguajes de Programación Tipos de Listas 223 /29

224. Lenguajes de Programación Apuntadores típicos en las Lista Primer nodo: Header / FP ( first Point) Último nodo: Last Point NIL/NULL puntero vacío 224 /29 Pointer Link Right Link Left LinkLista.dato

225. Tipos de listas encadenadas Listas simples encadenadas : Tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor Nulo o lista Vacia, si es el último nodo. Solo se puede recorrer la lista en un solo sentido

226. Tipos de listas enlazadas Listas doblemente encadenadas : Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor Nulo o la lista vacia si es el primer nodo; y otro que apunta al siguiente nodo, o apunta al valor Nulo o la lista vacia si es el último nodo. Se puede recorrer la lista en ambos sentidos

227. Tipos de listas enlazadas Listas enlazadas circulares : En una lista enlazada circular, el primer y el último nodo están unidos. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese al nodo original Se puede recorrer la lista en un solo sentido.

228. Lenguajes de Programación Tipos de listas enlazadas Listas doblemente encadenadas circulares : En una lista enlazada circular, el primer y el último nodo están unidos y cada uno apunta al otro por su doble encadenamiento Se puede recorrer la lista en ambos sentidos además de ser circular. 228 /29

229. Lenguajes de Programación Algoritmos tipos Crear Lista Añadir nodo al final Recorrer lista Buscar un nodo en la lista Eliminar un nodo Insertar un nodo en medio de otros Eliminar la lista 229 /29

230. Lenguajes de Programación Ejercicio ¿Qué cosas se deben hacer para los siguientes algoritmos: Añadir un nodo al final Eliminar un nodo Insertar un nodo en medio de otros dos 230 /29

231. LSE: BUSQUEDA Hay que ubicarse en el inicio: header E ir avanzando hasta Encontrar el nodo con la información buscada o Que ya no haya mas nodos Un apuntador se ubicara en el header Y luego irá avanzando al siguiente, y al siguiente y al siguiente 15 A 12 H 21 J 31 M -1 V 10 Q last header Busco Q P 20 P 15 P 12 P 21 P20 Busco L P 15 P 12 P 21 P 10 P 31 P -1 Al encontrar al nodo buscado, no se retorna la dirección de este nodo(apuntador) 20 15 12 21 10 31 20 31 Al encontrar el nodo, el valor de retorno es 21 porque es la dirección del nodo Si no encuentra el nodo el valor de retorno es -1

232. INSERCION AL INICIO/FINAL 15 C 12 Y 21 Q 31 L B 10 A Last 31 Header 20 H nuevo Header 18 G nuevo Last 32 Si la lista esta vacía, tanto header como last apuntan al nuevo nodo Si no, si es al inicio el nuevo header , es el nuevo nodo Si no, si es al final, el nuevo last es el nuevo nodo 20 15 12 21 10 31 32 20 18 32

233. Lista vacía e insertar en medio Debe recibir la posición donde se va a insertar Insertemos después Si Lista Vacía, el nuevo header y last, es el nuevo nodo Si la posición no existe no efectuar la inserción Si la lista solo tiene un elemento, el nuevo last es el nuevo nodo 15 B 12 Z A 31 Q W 10 M header last p R nuevo 21 91 header last H nuevo Header 50 Last 50 20 15 12 21 10 31 50 91

234. LSE: SACAR DE LA LISTA La lista no debe estar vacía!!, si tiene un solo elemento, dejarla vacía 10 5 8 2 31 25 header last tmp Tmp = header; header Header = header->sig; free(tmp); tmp tmp = last; last Last = Anterior(Last); free(tmp); Last->sig = NULL; 20 15 12 21 10 31

235. LSE: SACAR JUSTO UN NODO Lista no debe estar vacía La posición enviada debe existir en la lista Revisar si se desea eliminar el header o el last 10 5 8 2 31 25 header last p pant free(p); 20 15 12 21 10 31

236. ¿Qué recuerdas de la sesión anterior? Comenta las ideas principales de la sesión anterior

237. Arboles 237 /29 Lenguajes de Programación

238. Arboles Un árbol es una estructura de datos no lineal formada por un conjunto de nodos. Son estructuras jerárquicas, cada elemento puede tener diferentes siguientes elementos. El concepto de árbol implica una estructura en la que los datos se organizan de modo que los elementos de información están relacionados entre sí a través de ramas

239. ARBOLES - DEFINICIÓN - Estructura no lineal y de dos dimensiones de datos. Los no d os d e l o s arbo l es contienen dos o más enlaces. Normalmente se dibujan en forma opuesta a los árboles en la naturaleza. 239

240. Arboles un árbol representa una jeraquía ejemplos : estructura organizativa de una empresa tabla de contenido de un libro

241. Arboles (1) Sistema de archivos de Unix o DOS/Windows

242. Punt Izq Info Punt Der Hijo Izq Descendiente Hijo Der Desc e nd ie n t e Raíz Padre o Antepasado Hojas Hermanos Sub-árbol Izq Su b -á r b o l D e r El nível Nx de un nodo, distancia a la raíz. Raíz Nivel Número máximo de nodos de cualquier nivel es 2 N N N 1 N 2 N 3 Root ARBOLES - VOCABULARIO - Nodo: 0,1,2 hijos Todos los nodos son d e sce n d i e n tes de 8 la raíz

243. Terminología de Arboles A es el nodo raíz B es el padre de D y E C es el hermano de B D y E son los hijos de B D, E, F, G, I son nodos terminales o externos también llamados hojas A, B, C, H son nodos internos La profundidad ( nivel ) de E es 2 La altura del árbol es 3 El grado del nodo B es 2 Propiedad : ( #aristas ) = ( #nodos ) - 1

244. Ejemplos: Árbol binari o : árbol de grado 2 Cada nodo tiene como mucho dos descendientes directos Lista: árbol degenerado de grado 1 Grado de un nodo : número de descendientes directos B C B Grado del árbol : mayor grado de sus nodos D Conceptos Básicos Grado 2 Grado 3 A A C

245. Conceptos básicos A B D C G H E F I J K 1 Profundidad de un nodo: número de predecesores Altura del árbol : longitud de la rama más larga más uno. Profundida d 2 3 profundidad(A)=0 profundidad(H)=2 Altura de árbol = 4

246. Conceptos básicos Camino: existe un camino del nodo X al nodo Y, si existe una sucesión de nodos que permitan llegar desde X a Y. La sucesión debe tener un único sentido: ascendiente o descendiente. camino(A,K)={A,B,F,K} camino(C,K)={} A B D C G H E F I J K

247. Árboles: Ejercicio 1 Explica los valores de las principales características del árbol mostrado en la figura. ¿grado del árbol? ¿altura del árbol? ¿número nodos totales del árbol? ¿número de hojas? ¿número de nodos internos?

248. Árboles generales ▶ También llamados n-arios o multicamino ▶ Árboles con grado mayor a 2 A B D C G H E F I J K

249. ARBOLES BINARIOS Tipo especial de árbol Cada nodo no puede tener mas de dos hijos Un árbol puede ser un conjunto Vacío , no tiene ningún nodo O constar de tres partes: Un nodo raíz y Dos subárboles binarios: izquierdo y derecho La definición de un árbol binario es recursiva La definición global depende de si misma A B C D A B C D E H I F G J RAIZ Sub. Izq. Sub. Der.

250. ARBOLES BINARIOS COMPLETOS Un arbol de altura h esta completo si Todos los nodos hasta el nivel h-2 tienen dos hijos cada uno y En el nivel h-1, si un nodo tiene un hijo derecho, todas las hojas de su subarbol izquierdo están a nivel h Si un arbol esta lleno, tambien esta completo

251. ARBOLES BINARIOS LLENOS Un árbol de altura h, esta lleno si Todas sus hojas esta en el nivel h Los nodos de altura menor a h tienen siempre 2 hijos Recursiva Si T esta vacío, Entonces T es un árbol binario lleno de altura 0 Si no esta vacío, y tiene h>0 Esta lleno si los subárboles de la raíz, son ambos árboles binarios llenos de altura h-1

252. Árboles Binarios ▶ Está lleno si es completo y además todas sus hojas están en el mismo nivel A B C F G D E A B C G H E F I J Es completo si todo nodo interno (no hoja) tiene dos descendientes P,I,D = BDE PreOrder I,P,D = DBE EnOrder I,D,P = DEB PostOrder ABCDEGF

253. RECORRIDOS DE UN A.B. Recorrer es Visitar todos los elementos de una estructura Como recorrer un árbol Hay tantos caminos ¿cual escoger? Existe tres recorridos típicos Nombrados de acuerdo a la posición de la raíz Preorden : raíz - subarbol izq. - subarbol der . Enorden : subarbol izq. - raíz - subarbol der . Postorden : subarbol izq. - subarbol der . -raíz

254. EJEMPLO PREORDEN G G-D G-D-B G-D-B-A G-D-B-A-C G-D-B-A-C-E G D K B E H M A C F J I L G 1 D 2 B 3 A 4 C 5 E 6 F 7 G-D-B-A-C-E-F K 8 G-D-B-A-C-E-F-K H 9 G-D-B-A-C-E-F-K-H J 10 G-D-B-A-C-E-F-K-H-J I 11 G-D-B-A-C-E-F-K-H-J-I M 12 G-D-B-A-C-E-F-K-H-J-I-M L 13 G-D-B-A-C-E-F-K-H-J-I-M-L 1. Visitar raiz 2. Preorden al Subarbol Izq. 3. Preorden al Subarbol Der.

255. Ejemplo Recorridos 27 Preorder: F, B, A, D, C, E, G, I, H InOrder: A, B, C , D, E, F, G, H, I PostOrder: A, C, E, D, B, H, I, G, F LevelOrder: F, B, G, A, D, I, C, E, H

256. Árboles binarios: Implementación Nodo Árbol padre hijo izquierdo hijo derecho elemento A B C D E nul l nul l nul l nul l nul nul l l nul l

257. Lenguajes de Programación 257 /29

258. Grafos 258 /29 Lenguajes de Programación

259. DEFINICIÓN DE GRAFOS Un grafo en el ámbito de las ciencias de la computación es una estructura de datos , en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices ) y un conjunto de arcos ( aristas ) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemático de grafo. En este contexto árboles y grafos se refiere a estructuras de datos que permiten organizar y mantener información en un computador. 259 /29 Lenguajes de Programación

260. VERTICES Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado. 260 /29 Lenguajes de Programación

261. ARISTAS Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. 261 /29 Lenguajes de Programación

262. DEFINICION Un grafo G = (V,A) V, el conjunto de vértices o nodos Representan los objetos A, el conjunto de arcos Representan las relaciones V = {1, 4, 5, 7, 9} A= {(1,4), (5,1), (7,9), (7,5), (4,9), (4,1), (1,5), (9,7), (5, 7), (9,4)} 1 4 5 7 9 262 /29 Lenguajes de Programación

263. TIPOS DE GRAFOS Dirigidos: Cada arco está representado por un par ordenado de vértices. No dirigidos: El par de vértices que representa un arco no está ordenado. 263 /29 Lenguajes de Programación

264. REPRESENTACIÓN DE GRAFOS Las representaciones de grafos más habituales están basadas en matrices de adyacencia. Matriz de adyacencia Se asocia cada fila y cada columna a cada nodo del grafo, siendo los elementos de la matriz la relación entre los mismos, tomando los valores de 1 si existe la arista y 0 en caso contrario. 264 /29 Lenguajes de Programación

265. EJEMPLO 265 /29 Lenguajes de Programación

266. LISTAS DE ADYACENCIAS Se asocia a cada nodo del grafo una lista que contenga todos aquellos nodos que sean adyacentes a él. Ejemplo: 266 /29 Lenguajes de Programación

267. Ejemplos de grafos Ejemplo: Grafo de carreteras entre ciudades. 267 /29 Lenguajes de Programación

268. Ejemplos de grafos Problemas ¿Cuál es el camino más corto de Murcia a Badajoz? ¿Existen caminos entre todos los pares de ciudades? ¿Cuál es la ciudad más lejana a Barcelona? ¿Cuál es la ciudad más céntrica? ¿Cuántos caminos distintos existen de Sevilla a Zaragoza? ¿Cómo hacer un tour entre todas las ciudades en el menor tiempo posible? Ejemplo: grafo de carreteras entre ciudades. 268 /29 Lenguajes de Programación

269. Ejemplos de grafos Ejemplo: grafo de planificación de tareas. 269 /29 Lenguajes de Programación

270. Ejemplos de grafos Ejemplo: grafo de planificación de tareas. Problemas ¿En cuanto tiempo, como mínimo, se puede construir la pirámide? ¿Cuándo debe empezar cada tarea en la planificación óptima? ¿Qué tareas son más críticas (es decir, no pueden sufrir retrasos)? ¿Cuánta gente necesitamos para acabar las obras? 270 /29 Lenguajes de Programación

271. Ejemplos de grafos Ejemplo: grafo asociado a un dibujo de líneas. 1 4 2 7 3 6 5 b e a d c Modelo 1 Modelo 2 Escena 271 /29 Lenguajes de Programación