Les dejo el final que tomaron Agustin Gravano y Veronica Becher.
Notación: Una palabra es una cadena de 0s y 1s. Denotamos con v a la cadena vacía. Definición: Un conjunto es libre de prefijos si ninguna palabra del conjunto es prefijo de otra. Por ejemplo, tanto {v} como {01,001,0001,00001} son libres de prefijos, mientras que {1,0,10} no lo es, y {v,111} tampoco.
Ejercicio: i) Especificar formalmente el problema. ii) Dar un algoritmo en pseudocódigo tal que, dado un conjunto finito de palabras, determine si el conjunto es libre de prefijos. Explicitar las estructuras de datos que se utilizan. iii)Programar el algoritmo en funcional. iv) Programar el algoritmo en imperativo. v) Especificar los ciclos del programa imperativo (pre y post condición, variante, invariante, guarda).
Saludos!
|