2022-03-21

Algoritmo

• Definición: Secuencia ordenada y finita de pasos bien determinados que nos llevan de un estado inicial a uno final.
• Debemos considerarlos como una herramienta para la resolución de problemas.
• Deben resolver un problema genérico → Dada la descripción del problema el algoritmo debe resolver cualquier instancia del mismo.

Tipos abstractos de datos (TADs)

• Un tipo es un conjunto de valores asociados a operaciones.

• Tipo abstracto: No conocemos “la forma” de los valores, sólo conocemos sus operaciones.

• Son una heramienta lógico/matemática de modelar problemas.

• Signatura:

  TAD día ES NAT
  TAD plato ES String
  TAD restaurant
  	géneros restaurant
  	operaciones
  		inagurar :-> restaurant
  		cant_platos_pendientes: restaurant -> nat
  		próximo_pedido: restaurant r -> plato
  										{cant_platos_pendientes(r) > 0}
  		tomar_pedido: restaurant x plato -> restaurant
  		.
  		.
  		.
  
  Fin TAD
  

  • Las operaciones de los TADs son funciones totales → están definidas para cada valor del dominio.

• Axiomas: Los usamos para darle semántica, comportamiento a las operaciones.

  día_actual(inagurar()) = 0
  (forall r : restaurant) día_actual(nuevo_dia(r)) = día_actual(r) + 1
  cant_platos_pendientes(inagurar()) = 0
  (forall r : restaurant) (forall p : plato)
  	cant_platos_pendientes(tomar_pedido(r,p)) = cant_platos_pendientes(r) + 1
  .
  .
  .
  

• Una de las ventajas de los TADs es que no requiere de tipos primitivos que deban definirse por fuera de la misma. Veremos como ejemplo cómo se definen algunos tipos básicos.

• Género: el nombre que recibe el conjunto de valores del tipo.

• Usa: Operaciones y géneros definidos en otros TADs que utiliza el TAD que estamos definiendo.

• Exporta: Operaciones y géneros que se dejan a disposición de los usuarios del tipo.