Algoritmos y Estructuras de Datos I - ALIPSO.COM: Monografías, resúmenes, biografias y tesis gratis.
Aprende sobre marketing online, desarrollo de sitios web gratis en Youtube
Suscribite para recibir notificaciones de nuevos videos:
Viernes 29 de Marzo de 2024 |
 

Algoritmos y Estructuras de Datos I

Imprimir Recomendar a un amigo Recordarme el recurso

Algoritmos y Estructuras de Datos I Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires Primer Cuatrimestre de 2000. Práctica 2. Programación Funcional. Notación. Aclaraciones.

Agregado: 17 de JULIO de 2003 (Por Michel Mosse) | Palabras: 971 | Votar | Sin Votos | Sin comentarios | Agregar Comentario
Categoría: Apuntes y Monografías > Computación > Programación >
Material educativo de Alipso relacionado con Algoritmos Estructuras Datos
  • Algoritmos y Estructuras de Datos I: Algoritmos y Estructuras de Datos I Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires Primer Cuatrimestre de 2000. Práctica 5. Procedimientos. Funciones. Programación.
  • Algoritmos y Estructuras de Datos I.: Algoritmos y Estructuras de Datos I Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires Primer Cuatrimestre de 2000. Resolución de la Práctica 5. La longitud de L es Par. Programación. Algoritmos.
  • LMD (Lenguaje de Manipulación de Datos): Programación. Claúsula IN. Claúsula BETWEEN. Claúsula LIKE. Expresiones aritméticas. Funciones de columna.

  • Enlaces externos relacionados con Algoritmos Estructuras Datos

    Algoritmos y Estructuras de Datos I

    Facultad de Ciencias Exactas y Naturales

    Universidad de Buenos Aires

    Primer Cuatrimestre de 2000

    Práctica 2

    Fecha sugerida de finalización: 27/4/2000.

    Programación Funcional

    Notación

    Para escribir las funciones, usaremos la sintaxis de Gofer, tal como se ve en el taller. De esta manera, se pueden probar en la máquina las funciones definidas. Sin embargo, los tipos básicos usados en estas prácticas no coinciden exactamente con los tipos básicos de Gofer. Por ejemplo, el tipo Nat no existe en Gofer y aquí lo usaremos como básico.

    Las aridades de las funciones se dan currificadas, esto es, todas las funciones reciben un solo argumento, y pueden devolver, eventualmente, una función. La currificación reemplaza los argumentos estructurados de una función por una secuencia de argumentos simples, para permitir un tratamiento homogéneo.

    Veamos un ejemplo:

    La función suma (+) recibe dos naturales y devuelve otro natural (que es la suma de los dos argumentos). Uno escribiría la aridad de la función + de la siguiente manera:

    + :: Nat × Nat ® Nat

    Currificando, lo que hacemos es convertir el par de argumentos de la siguiente manera:

    + :: Nat ® Nat ® Nat

    Aclaraciones

    Esta práctica pide la definición de funciones, al estilo de los programas funcionales de Gofer. En general, no hay una única manera de definir una función. Sin embargo, nos interesa que las soluciones elegidas sean claras, comprensibles, compactas (breves, de ser posible), completas (que contemplen todos los casos de interés) y declarativas (que estén más cerca del qué y no del cómo).

    Cuando resulte conveniente, se pueden definir funciones auxiliares para hacer más fácil la definición de la función principal. También se pueden usar funciones definidas previamente en otros ejercicios.

    Dar explícitamente la aridad de una función (el tipo de su domino y su imagen) permite detectar errores tempranamente. No hay que olvidar que el valor que devuelve una función depende sólo de sus argumentos.

    Ejercicio 1

    i.       Definir la función parcial f : N ® N, definida por extensión de la siguiente manera:

    f (1) = 8

    f (4) = 131

    f (16) = 16


    ii.     Análogamente, definir la función parcial g : N ® N :

    g (8) = 16

    g (16) = 4

    g (131) = 1

    iii.    A partir de las funciones definidas en i y ii, definir las siguientes funciones parciales:

    h = f o g

    k = g o f

    Ejercicio 2

    Se tiene definido el tipo Nat con los siguientes elementos contructores:

           0 (cero)

           Suc(Nat) (el sucesor del número pasado como parámetro)

    Empleando solamente 0 y suc, definir las siguientes funciones:

    i.                     igual :: Nat ® Nat ® Bool

    ii.                    suma :: Nat ® Nat ® Nat

    iii.                  producto :: Nat ® Nat ® Nat

    iv.                  potencia :: Nat ® Nat ® Nat

    v.                   menor :: Nat ® Nat ® Bool

    vi.                  resta :: Nat ® Nat ® Nat (es 0 si el minuendo es menor que el sustraendo)

    vii.                división :: Nat ® Nat ® Nat (división entera; por ejemplo, división 7 3 = 2)

    viii.               resto :: Nat ® Nat ® Nat

    ix.                   mcd :: Nat ® Nat ® Nat (máximo común divisor)

    x.                    factorial :: Nat ® Nat

    xi.                   número_combinatorio :: Nat ® Nat ® Nat

    xii.                 n_Fibonacci :: Nat ® Nat (n-ésimo término de la sucesión de Fibonacci)

    De aquí en adelante utilizaremos las constantes y funciones de los naturales de la manera habitual. Por ejemplo, se puede escribir 3 en lugar de suc(suc(suc(0))) ; n + m en lugar de suma(n, m) ; etc.

    Ejercicio 3

    Definir las siguientes funciones, utilizando las definidas en el ejercicio 2.

    i.                     par :: Nat ® Bool

    ii.                    impar :: Nat ® Bool

    iii.                  par :: Nat ® Bool (redefinirla usando solamente resta y recursión)

    iv.                  divisor :: Nat ® Nat ® Bool (el primer parámetro divide al segundo)

    v.                   cuadrado_perfecto :: Nat ® Bool

    vi.                  suma_divisores :: Nat ® Nat (devuelve la suma de los divisores)

    vii.                perfecto :: Nat ® Bool (n es perfecto si la suma de los divisores propios de n es igual a n)

    viii.               mayor_divisor :: Nat ® Nat (devuelve el mayor divisor propio)

    ix.                   primo :: Nat ® Bool

    x.                    siguiente_primo :: Nat ® Nat (devuelve el primer primo mayor)


    Ejercicio 4

    Definir las siguientes funciones, de naturales en naturales:

    i.                    

    ii.                  

    iii.                 

    Ejercicio 5

    i.                     Sea f(0) = 0, f(1) = 1, f(2) = 22, f(3) = 333 = 327, etc.. Definir la función f (dar la aridad también).

    ii.                    Sea A :: Nat × Nat ® Nat (notar que esta función no está currificada)
    A(Suc(i), Suc(x)) = A(i, A(Suc(i), x))
    A(i, 0) = 1
    A(0, x) = x + 1 si x = 0, 1
    A(0, x) = x + 2 si x > 1
    Calcular A(1, 1), A(2, 2) y A(3, 2).

    iii.                  Sea A :: Nat × Nat ® Nat
    A(Suc(i), Suc(x)) = A(i, A(Suc(i), x))
    A(i, 0) = 1
    A(0, x) = x + 1 si x = 0, 1
    A(0, x) = x + 2 si x = 2
    ¿Qué ocurre si se quiere evaluar la expresión A( A(2, 0) - 1 , A(2, 2) - 1 ) ?

    Ejercicio 6

    Definir los conectivos lógicos ï y ¯ (NAND y NOR, respectivamente), vistos en la práctica 1. Basarse en las tablas de verdad de los símbolos, sin usar otras operaciones lógicas.

     Ejercicio 7

    Definir la función divisible_por_tres :: Nat ® Bool, que dice si un número es divisible por tres o no, usando el criterio de divisibilidad por tres (Un número es divisible por tres si y solo si la suma de sus cifras también lo es).


    Votar

    Ingresar una calificación para del 1 al 10, siendo 10 el máximo puntaje.

    Para que la votación no tenga fraude, solo se podrá votar una vez este recurso.

    Comentarios de los usuarios


    Agregar un comentario:


    Nombre y apellido:

    E-Mail:

    Asunto:

    Opinión:



    Aún no hay comentarios para este recurso.
     
    Sobre ALIPSO.COM

    Monografias, Exámenes, Universidades, Terciarios, Carreras, Cursos, Donde Estudiar, Que Estudiar y más: Desde 1999 brindamos a los estudiantes y docentes un lugar para publicar contenido educativo y nutrirse del conocimiento.

    Contacto »
    Contacto

    Teléfono: +54 (011) 3535-7242
    Email:

    Formulario de Contacto Online »