Especificación Formal de Algoritmos: Teoría y Ejercicios

Y 0 flashcards y 3 preguntas más en el documento.

Texto del documento

APUNTES PRÁCTICAS DE PROGRAMACIÓN Grado en Ingeniería Informática Universitat Oberta de Catalunya AprenAI 2026-2027 Aprende a especificar algoritmos con cálculo de predicados, precondiciones, postcondiciones y aserciones en C para Prácticas de programación de la UOC.

APREN.AI Índice 1 Fundamentos y Elementos de la Especificación Formal Introducción y necesidad de formalizar Las cuatro partes de una especificación formal Conservación del estado inicial y primer ejemplo formal 2 Cálculo de Predicados y Formalización Lógica Definición y operadores del cálculo de predicados Cuantificadores lógicos: universal y existencial Aplicación: Máximo Común Divisor (MCD) 3 Implementación de Precondiciones en C y Especificación de Problemas Complejos Validación de precondiciones mediante aserciones en C Especificación del desglose óptimo de billetes 4 Formulario Estructura de la especificación formal Cálculo de predicados y cuantificadores Validación en C y optimización Errores típicos Soluciones de las preguntas de repaso Estos apuntes pueden contener errores u omisiones.

Son un material de apoyo y no sustituyen al temario oficial ni al profesorado: contrasta la información importante. Especificación Formal de Algoritmos: Teoría y Ejercicios 1 1 Fundamentos y Elementos de la Especificación Formal AL ACABAR SABRÁS Distinguir conceptualmente entre especificación formal y algoritmo. Identificar los cuatro elementos indispensables de una especificación algorítmica. Formalizar estados iniciales utilizando constantes para registrar valores de entrada. PIÉNSALO ANTES DE LEER 1 ¿Por qué detallar una tarea en lenguaje cotidiano puede hacer fracasar el desarrollo de un programa informático?

Introducción y necesidad de formalizar Al concebir una solución computacional, el punto de inicio reside en describir con exactitud el problema a tratar. Emplear el lenguaje natural para fijar enunciados suele acarrear ambigüedades e imprecisiones. Estos defectos conllevan el diseño de soluciones erróneas y provocan pérdidas de tiempo considerables durante el desarrollo de software. Para subsanar esta problemática se recurre a la especificación de un problema, que consiste en definir de forma formal e inequívoca el estado del entorno y el resultado esperado.

Mientras que la especificación clarifica qué debe resolver un método sin determinar sus pasos internos, el algoritmo concreta cómo se resuelve dicho encargo paso a paso. Consideremos la metáfora de un servicio contratado para llevar escolares al colegio: indicar únicamente la hora de recogida genera incertidumbres operativas. Se requiere concretar el estado inicial (si los menores están vestidos, alimentados y con su material preparado) y el estado final requerido (su presencia física en la entrada del centro educativo antes de una hora estipulada). El mecanismo de traslado queda a libre criterio del ejecutor, pues la especificación solo describe la transición entre estados.

DEFINICIÓN En el ámbito de la programación, el entorno comprende el conjunto de variables de entrada y de salida asociadas al problema. La especificación formal describe la mutación válida de este entorno desde su estado inicial hasta el final, dejando las variables intermedias fuera de este marco formal. COMPRUEBA 2 ¿Por qué las variables intermedias o auxiliares no figuran en la especificación formal de un problema?

Especificación Formal de Algoritmos: Teoría y Ejercicios 2 Las cuatro partes de una especificación formal Una especificación completa y rigurosa consta estructuralmente de cuatro elementos obligatorios: Variables de entorno: declaración formal con nombres significativos y tipos asociados tanto para las entradas como para las salidas. Precondición: fórmula que establece la condición indispensable que debe verificar el entorno justo al iniciarse la ejecución, restringiendo los valores válidos admitidos. Nombre del algoritmo: identificador representativo y claro de la funcionalidad que se pretende implementar.

Postcondición: condición que el entorno debe satisfacer tras completarse la rutina, delimitando los resultados finales correctos. Conservación del estado inicial y primer ejemplo formal Durante la ejecución de un algoritmo, las variables asignadas a los parámetros de entrada pueden mutar de valor. Por ello, para referenciar en la postcondición el dato original suministrado, se introduce una constante en mayúsculas que fija ese valor de partida. EJEMPLO Diseño de la especificación para sumar los primeros enteros positivos elevados al cuadrado: 1. Declaración de variables: En algoritmo: En lenguaje C: int number; int sum; 2. Precondición: 3. Nombre del algoritmo: sumaCuadrados 4.

Postcondición: ERROR FRECUENTE Escribir el nombre de la variable mutable en la postcondición en lugar de su identificador constante inicial (por ejemplo, poner en lugar de ). Si el algoritmo altera internamente la variable number durante el cómputo, la postcondición resultaría formalmente incorrecta o indefinida. COMPRUEBA 3 ¿Qué finalidad persigue definir una constante formal en mayúsculas dentro de la precondición?

n var number: integer; sum: integer; end var {Pre: number = NUMBER NUMBER > 0} {Post: sum = i } i=1 NUMBER 2 i=1 number i=1 NUMBER Especificación Formal de Algoritmos: Teoría y Ejercicios 3 IDEAS CLAVE La especificación formal evita las ambigüedades del lenguaje natural determinando qué debe cumplir el programa y no cómo resolverlo. El entorno de especificación abarca únicamente las variables de entrada y salida, omitiendo variables temporales de resolución. Las cuatro partes constitutivas son: variables, precondición, nombre del algoritmo y postcondición. Se utilizan identificadores constantes en mayúsculas para referenciar el estado inicial en las expresiones de la postcondición.

COMPRUEBA LO QUE HAS APRENDIDO 4. ¿En qué se diferencia el cometido de una precondición del de una postcondición? 5. En un problema donde se recibe un entero positivo , ¿cómo se asegura en la precondición el registro de su valor original? Test Rodea la respuesta correcta. Las soluciones están al final. 6. ¿Cuál es la función principal de la especificación formal? 7. ¿Qué variables forman parte del entorno de la especificación? 8. ¿Por qué se utiliza NUMBER en mayúsculas en la precondición number = NUMBER? 9. ¿Cuál de los siguientes elementos NO pertenece a la especificación de un algoritmo?

x Sustituir las pruebas unitarias del sistema a) Definir inequívocamente qué debe resolverse b) Escribir código eficiente y rápido c) Declarar las variables locales del bucle d) Todas las variables de la función a) Únicamente las variables de entrada y salida b) Solo las variables globales del programa c) Las variables temporales e índices contadores d) Por una regla estética del compilador C a) Porque las variables siempre van en mayúsculas b) Para reservar memoria dinámica de entrada c) Para indicar que es un valor estático inmutable d) Precondición a) Estructura interna del bucle iterativo b) Postcondición c) Variables de entrada y salida d) Especificación Formal de Algoritmos: Teoría y Ejercicios 4 2 Cálculo de Predicados y Formalización Lógica AL ACABAR SABRÁS Identificar la sintaxis formal de los operadores aritméticos, relacionales y lógicos.

Interpretar y formular expresiones con cuantificadores universales y existenciales. Formalizar condiciones algorítmicas avanzadas como el máximo común divisor. PIÉNSALO ANTES DE LEER 10 ¿Cómo podemos asegurar de forma matemática que un valor es estrictamente el máximo divisor común sin enumerar infinitos números? Definición y operadores del cálculo de predicados Para construir precondiciones y postcondiciones sin ambigüedad se utiliza el cálculo de predicados. Un predicado es una expresión booleana evaluable como verdadera o falsa, en cuyo seno pueden intervenir variables y constantes. Por ejemplo, la proposición arroja siempre un valor falso.

En cambio, expresiones como o devuelven verdadero o falso en función del valor numérico que contenga la variable asociada en cada instante. Los predicados se estructuran mediante constantes (como 3, 89, 75), variables de entorno (tales como ) y operadores específicos categorizados en diversas familias: Categoría Símbolo Denominación Lectura formal Aritméticos , Suma, Resta más, menos , Multiplicación, División por, dividido div División (parte entera) parte entera de la división mod División (residuo) residuo de la división Sumatorio suma desde ... hasta ...

Disyunción / Conjunción o / y Negación lógica no Relacionales y Lógicos , Igualdad, Desigualdad es igual que, es distinto que , , , Desigualdades de orden menor, menor o igual, mayor, mayor o igual Implicación unilateral entonces Doble implicación si y solo si 3 + 6 > 15 edad = 45 edad × 3 > 78 edad, a o, dia n ~ + / / ¬ = = < > Especificación Formal de Algoritmos: Teoría y Ejercicios 5 Categoría Símbolo Denominación Lectura formal Conjuntos y Notaciones , , Conjunto, Pertenencia, No pertenencia conjunto formado por, pertenece a, no pertenece a , Unión, Intersección unión de, intersección de , , Universal, Existencial, Existencial negado para cualquier, existe como mínimo, no existe ningún Separador de condición tal que Asimismo, los conjuntos numéricos fundamentales se identifican mediante sus símbolos canónicos: naturales ( ), enteros ( ), racionales ( ), reales ( ) y complejos ( ), además de notaciones complementarias como valor absoluto ( ), raíz cuadrada ( ), infinito ( ) y porcentaje ( ).

COMPRUEBA 11 ¿Cuál es el valor de verdad del predicado formal si la variable edad almacena el valor 26? Cuantificadores lógicos: universal y existencial Los cuantificadores permiten establecer propiedades sobre colecciones de elementos: Cuantificador universal ( ): formaliza que una determinada condición la satisfacen absolutamente todos los integrantes de un conjunto dado. Cuantificador existencial ( ): declara que existe al menos un elemento en el conjunto especificado que cumple la relación.

EJEMPLO Modelado con cuantificador universal: «para todo número real, su cuadrado también pertenece a los reales»: Modelado combinado con antecedente: «para cualquier par de reales menores que 1, su producto también es menor que 1»: Modelado existencial: «para todo real positivo , existe otro real cuya raíz lo define»: Propiedad de densidad en la recta real («entre dos reales siempre existe otro intermedio»): {} / : N Z Q R C x % edad × 3 > 78 x R x × x R x, y R : x < 1 y < 1 x × y < 1 x x R, y R : x > 0 y × y = x x, z R, y R : x < z x < y < z Especificación Formal de Algoritmos: Teoría y Ejercicios 6 Aplicación: Máximo Común Divisor (MCD) La combinación de conectivas y cuantificadores permite especificar métodos clásicos de forma precisa, como el cálculo del máximo común divisor entre dos números enteros positivos: Variables: Precondición: Exige que las entradas sean enteras y estrictamente mayores que cero: Nombre del algoritmo: maxComunDivisor Postcondición: Estipula que debe ser divisor común exacto de e , y que ningún entero superior a puede compartir esa propiedad: ERROR FRECUENTE Confundir los cuantificadores y en la postcondición de algoritmos de optimización o búsqueda.

Para indicar que un divisor es el máximo, debe usarse garantizando que todo número estrictamente mayor incumple la condición de ser divisor simultáneo de ambos parámetros. COMPRUEBA 12 En la especificación del MCD, ¿por qué se utiliza una disyunción ( ) al evaluar para cualquier ?

ESQUEMA Operadores en el cálculo de predicados var x, y, mcd: integer; end var {Pre: x = X y = Y X > 0 Y > 0} mcd X Y mcd {Post: X mod mcd = 0 Y mod mcd = 0 j N : j > mcd (X mod j = 0 Y mod j = 0)} X mod j = 0 Y mod j = 0 j > mcd Aritméticos Operaciones básicas, div, mod y sumatorios Relacionales Igualdades y desigualdades de orden Lógicos Conjunción, disyunción, negación e implicación Conjuntos y Cuantificadores Pertenencia, unión y cuantificación universal o existencial Especificación Formal de Algoritmos: Teoría y Ejercicios 7 IDEAS CLAVE Un predicado es una sentencia booleana sujeta a constantes, variables y operadores lógicos o aritméticos.

El cuantificador universal afirma una propiedad para todos los elementos, mientras que el existencial garantiza al menos una ocurrencia. El operador mod es esencial para expresar relaciones de divisibilidad exacta ( ). La postcondición de maximalidad exige demostrar universalmente que ningún elemento mayor preserva la propiedad de divisibilidad simultánea. COMPRUEBA LO QUE HAS APRENDIDO 13. ¿Cómo se representa formalmente mediante cálculo de predicados que un valor entero positivo divide exactamente a ? 14. ¿Qué traduce la proposición formal ? Test Rodea la respuesta correcta. Las soluciones están al final. 15. ¿Qué representa el símbolo div en el cálculo de predicados? 16.

¿Cuál es el significado del cuantificador existencial ( )? 17. En la precondición del MCD, ¿qué operador conecta las condiciones X > 0 e Y > 0? 18. ¿Cómo se expresa formalmente que j no divide de forma exacta a X?

dividendo mod divisor = 0 k W x\bigin\bigN: x\bigge0 La parte entera de la división a) El operador de pertenencia a conjuntos b) El resto de una división entera c) La división en coma flotante d) Que la condición se cumple para cualquier elemento a) Que solo dos elementos son equivalentes b) Que ningún elemento verifica la fórmula c) Que al menos un elemento satisface la condición d) Conjunción ( ) a) Implicación ( ) b) Disyunción ( ) c) Doble implicación ( ) d) X div j = 0 a) X / j = 0 b) X mod j 0 c) j mod X = 0 d) Especificación Formal de Algoritmos: Teoría y Ejercicios 8 3 Implementación de Precondiciones en C y Especificación de Problemas Complejos AL ACABAR SABRÁS Traducir precondiciones formales a aserciones ejecutables en C mediante assert.

Formular restricciones de frontera en postcondiciones para garantizar unicidad y optimalidad. Controlar la activación y desactivación de aserciones mediante directivas del preprocesador. PIÉNSALO ANTES DE LEER 19 ¿Alcanza con una fórmula de suma para asegurar que un cajero entregue el mínimo cambio en billetes? Validación de precondiciones mediante aserciones en C Aunque garantizar los requisitos de entrada es competencia de quien invoca una rutina, resulta una buena práctica comprobar internamente el cumplimiento estricto de la precondición antes de operar. En caso de detectarse valores anómalos, el programa debe abortar la ejecución.

En lenguaje C, la validación se implementa mediante la macro assert, accesible a través de la inclusión de la cabecera <assert.h> : #include <assert.h> assert(number > 0); Si el argumento evaluado en assert arroja falso (por ejemplo, si number es negativo o cero), el flujo se detiene inmediatamente. Las aserciones pueden desactivarse selectivamente al compilar para optimizar el código de producción declarando antes la macro #define NDEBUG .

EJEMPLO Estructura de función con especificación y control en C para la suma de cuadrados: #include <assert.h> int squareAddition(int number) { int sum; /* { Pre: number = NUMBER ^ NUMBER > 0 } */ assert(number > 0); /* { Post: sum = suma(i=1..NUMBER) de i^2 } */ /* ... cuerpo del algoritmo ... */ return sum; } Especificación Formal de Algoritmos: Teoría y Ejercicios 9 COMPRUEBA 20 ¿Cómo se desactivan de forma sistemática todas las macros assert de un fichero fuente en C sin tener que borrarlas del código?

Especificación del desglose óptimo de billetes Analicemos un problema de mayor complejidad: determinar el desglose óptimo de un importe monetario en euros utilizando el mínimo número de billetes de denominaciones iguales o superiores a 20 € (billetes de 500 €, 200 €, 100 €, 50 € y 20 €). Para importes como 2.370 €, el desglose óptimo demanda 4 billetes de 500 €, 1 de 200 €, 1 de 100 €, 1 de 50 € y 1 de 20 €. En cambio, para una cuantía como 420 €, la combinación óptima consta de 2 billetes de 200 € y 1 de 20 €. 1.

Identificación y declaración de variables: En algoritmo: var quantity, fiveHundred, twoHundred, oneHundred, fifties, twenties: integer; end var En lenguaje C: int quantity; unsigned short fiveHundred; unsigned short twoHundred; unsigned short oneHundred; unsigned short fifties; unsigned short twenties; 2. Precondición: El importe inicial debe ser positivo y múltiplo exacto de 20 o de 50, puesto que no existen denominaciones inferiores para cubrir restos residuales: Valores como 110 € o 20.010 € quedan descartados por no verificar esta precondición. 3. Nombre del algoritmo: divideQuantity 4.

Postcondición y refinamiento por maximalidad: Una postcondición trivial que sume los importes: No resulta suficiente, pues admitiría soluciones no óptimas (como abonar 420 € enteramente con 21 billetes de 20 €). Para asegurar el menor número global de billetes, es imperativo restringir el rango admisible de cada denominación inferior: Billetes de 500 €: sin cota superior prefijada ( ). Billetes de 200 €: un máximo de 2 unidades, dado que 3 billetes (600 €) se reemplazan de manera más eficiente por uno de 500 € y uno de 100 € ( ). Billetes de 100 €: a lo sumo 1 unidad ( ). Billetes de 50 €: como máximo 1 unidad ( ). Billetes de 20 €: un tope de 4 unidades ( ).

{Pre: quantity = QUANT IT Y QUANT IT Y > 0 (QUANT IT Y mod 20 = 0 QUANT IT Y mod 50 = 0)} QUANT IT Y = 500 × fiveHundred + 200 × twoHundred + 100 × oneHundred + 50 × fifties + 20 × twenties 0 fiveHundred 0 twoHundred 2 0 oneHundred 1 0 fifties 1 0 twenties 4 Especificación Formal de Algoritmos: Teoría y Ejercicios 10 Con estas cotas, la postcondición formal definitiva queda formulada como: PROCESO Verificación y ejecución de precondiciones 1 Llamada a función El invocador envía ar gumentos de entrada 2 Evaluación assert Se comprueba la vali dez formal de la precondición 3 Fallo de aserción Si es falsa, aborta de inmediato la ejecución 4 Cálculo Si es cierta, ejecuta y garantiza la postcondición IDEAS CLAVE La verificación de precondiciones en tiempo de ejecución con assert permite detener el programa ante datos de entrada incompatibles.

Para garantizar optimización en la postcondición no basta con la ecuación de balance; se requieren cotas que impongan unicidad y minimalidad. El valor máximo de billetes menores está estrictamente determinado por el valor del billete inmediatamente superior. COMPRUEBA LO QUE HAS APRENDIDO 21. ¿Por qué es insuficiente la igualdad de balance en la postcondición del desglose de cambio? 22. ¿Qué efecto produce compilar un programa en C que usa assert habiendo definido previamente #define NDEBUG? Test Rodea la respuesta correcta. Las soluciones están al final. 23. ¿Qué librería estándar proporciona la macro assert en lenguaje C? 24.

En el desglose de billetes, ¿por qué twoHundred no puede ser mayor que 2? {Post: (QUANTITY = 500 × fiveHundred + 200 × twoHundred + 100 × oneHundred + 50 × fifties + 20 × twenties) (0 fiveHundred) (0 twoHundred 2) (0 oneHundred 1) (0 fifties 1) (0 twenties 4)} ¬ soluci n alternativa o ˊ (criterio m nimo) ı ˊ v lido. a ˊ a) b) c) d) Porque superaría el límite de memoria del tipo unsigned short a) Porque 3 billetes de 200 suman 600, reemplazables por uno de 500 y uno de 100 b) Porque el cajero no almacena más de dos billetes de ese tipo c) Porque 200 no es divisible de forma directa por 50 d) Especificación Formal de Algoritmos: Teoría y Ejercicios 11 25.

¿Qué ocurre al ejecutarse assert(number > 0) si number almacena el valor 0? 26. Según la precondición del algoritmo divideQuantity, ¿cuál de los siguientes importes es válido? 4 Formulario Estructura de la especificación formal Fórmula o procedimiento Qué significa cada símbolo Cuándo se usa Declarar variables de entorno Fijar valores en precondición Nombrar algoritmo Definir postcondición Variables: entrada y salida. Precondición: estado inicial. Postcondición: estado final. Procedimiento general para especificar formalmente el comportamiento de cualquier algoritmo. : variable de entrada. CONST: constante que fija el valor inicial. : condición sobre el dato de entrada.

Al inicio de la especificación para restringir valores válidos y permitir referenciar el valor inicial en la postcondición. : variable de salida. : relación funcional o predicado de salida. CONST: valor de entrada inmutable. Al final de la especificación para determinar el resultado exacto exigido al algoritmo. Cálculo de predicados y cuantificadores Fórmula o procedimiento Qué significa cada símbolo Cuándo se usa : cuantificador universal (para todo). : pertenencia al conjunto . : implicación lógica. Para expresar que todos los elementos de un conjunto cumplen una propiedad determinada.

Se produce un bucle infinito en el algoritmo a) La condición evalúa falso y el programa detiene su ejecución b) La variable number se inicializa en 1 automáticamente c) Se emite una advertencia pero el flujo continúa d) 15 a) 20010 b) 420 c) 110 d) {Pre: var = CONST P (CONST)} var P {Post: sal = f(CONST)} sal f x C : P (x) Q(x) C Especificación Formal de Algoritmos: Teoría y Ejercicios 12 Fórmula o procedimiento Qué significa cada símbolo Cuándo se usa : cuantificador existencial (existe al menos uno). : condición requerida. Para garantizar la existencia de al menos un elemento que satisface una condición dada. mod: residuo de la división entera entre y .

Para formular condiciones de divisibilidad exacta o verificar múltiplos. Validación en C y optimización Fórmula o procedimiento Qué significa cada símbolo Cuándo se usa assert(condición); assert : macro de <assert.h> que evalúa una condición booleana. Al comienzo de una función para abortar la ejecución si se viola la precondición. #define NDEBUG NDEBUG : directiva de preprocesamiento en C. Antes de incluir <assert.h> para desactivar las aserciones en código de producción. : número de unidades de denominación inferior. : límite máximo permitido antes de agrupar en una mayor. En postcondiciones de optimización (como el cambio de billetes) para forzar la solución mínima.

Errores típicos Usar variables mutables en la postcondición: Utilizar el identificador de la variable de entrada en vez de la constante fijada en la precondición (por ejemplo, usar number en lugar de NUMBER ). Confusión entre cuantificadores: Emplear en lugar de al definir condiciones de maximalidad o unicidad. Postcondiciones incompletas en problemas de optimización: Limitarse a formular una suma o balance sin acotar las variables inferiores, lo que permite soluciones válidas pero no óptimas. Asumir que assert actúa en compilación: Creer que assert detecta fallos al compilar; su evaluación se produce en tiempo de ejecución.

y C : P (y) P (y) A mod B = 0 A B 0 b i cota i b i cota i Especificación Formal de Algoritmos: Teoría y Ejercicios 13 Soluciones de las preguntas de repaso 1. Porque el lenguaje natural introduce ambigüedades e interpretaciones diversas sobre el punto de partida y el resultado esperado, lo que conduce a algoritmos incorrectos. 2. Porque la especificación solo define el contrato entre el estado de entrada y de salida del entorno (el qué), mientras que las variables auxiliares forman parte del diseño interno del algoritmo (el cómo). 3.

Permite congelar el valor de partida de la variable de entrada para poder referenciarlo de forma exacta e inmutable en la postcondición, aun cuando la variable sufra modificaciones durante el algoritmo. 4. La precondición establece las restricciones que deben cumplir obligatoriamente los datos de entrada para que la ejecución sea válida, mientras que la postcondición define el estado exacto en el que deben quedar las variables de salida tras finalizar el algoritmo. 5. Igualando la variable a una constante formal (generalmente en mayúsculas): . 6. b) Definir inequívocamente qué debe resolverse.

La especificación se enfoca en describir sin ambigüedad el qué resuelve el problema, separándolo del cómo. 7. b) Únicamente las variables de entrada y salida. El entorno de especificación solo involucra variables de entrada y salida; las variables de resolución interna no intervienen. 8. d) Para indicar que es un valor estático inmutable. Permite registrar el valor de partida para poder referenciarlo de manera fija e inalterable en la postcondición. 9. b) Estructura interna del bucle iterativo. El bucle o mecanismo de resolución forma parte del algoritmo (el cómo) y no de la especificación formal. 10.

Exigiendo mediante el cuantificador universal que cualquier valor numérico mayor incumpla la condición de ser divisor simultáneo de ambos operandos. 11. Es falso, ya que , y 78 no es estrictamente mayor que 78. 12. Porque para descalificar a como divisor común basta con que falle al dividir exactamente al menos a uno de los dos números. 13. Mediante la expresión formal . 14. Traduce que para todo elemento perteneciente al conjunto de los números naturales, es mayor o igual que cero. 15. a) La parte entera de la división. div representa la parte entera resultante de una división entre enteros. 16. d) Que al menos un elemento satisface la condición.

El símbolo asegura que existe como mínimo un elemento dentro del conjunto que satisface la condición dada. 17. a) Conjunción ( ). Ambas restricciones deben verificarse a la vez, por lo que se utiliza una conjunción lógica ( ). 18. c) X mod j 0. Que la división no sea exacta significa que el residuo (mod) es distinto de cero (X mod j 0). 19. No, se deben delimitar los rangos máximos de cada billete para evitar combinaciones redundantes no óptimas. 20. Añadiendo la directiva de compilación #define NDEBUG al inicio del fichero antes de incluir <assert.h> . x = X X > 0 26 × 3 = 78 j W mod k = 0 x x Especificación Formal de Algoritmos: Teoría y Ejercicios 14 21.

Porque una simple suma lineal permite infinitas combinaciones válidas en valor monetario, pero no asegura que se use el número mínimo de billetes sin acotar las cantidades inferiores. 22. Provoca que el preprocesador anule todas las macros assert, desactivando las comprobaciones en tiempo de ejecución para mejorar la eficiencia del ejecutable. 23. a) . La macro assert se encuentra definida dentro de la biblioteca estándar . 24. b) Porque 3 billetes de 200 suman 600, reemplazables por uno de 500 y uno de 100. Tres billetes de 200 € suman 600 €, importe que se representa de forma más óptima con dos billetes (uno de 500 € y uno de 100 €). 25.

b) La condición evalúa falso y el programa detiene su ejecución. Al fallar la aserción (0 no es mayor que 0), la macro assert aborta el programa inmediatamente. 26. c) 420. 420 es múltiplo de 20 (420 mod 20 = 0), cumpliendo el requisito de ser múltiplo de 20 o de 50. Especificación Formal de Algoritmos: Teoría y Ejercicios 15