Algoritmia

APUNTES PARA ALGORITMOS Y ESTRUCTURAS DE DATOS II
CLASE 01

Por favor, reportar errores, omisiones y sugerencias a dfridlender@gmail.com Observaciones Preliminares En las materias Introducción a los Algoritmos y Algoritmos y Estructuras de Datos I el énfasis estaba puesto en qué hace un programa. Se especificaba detalladamente las pre- y pos- condiciones que el programa debía satisfacer y sederivaba un programa que satisfaciera dicha especificación. En Algoritmos y Estructuras de Datos II, sin descuidar las especificaciones de pre- y pos- condiciones ni la formulación de los invariantes de los ciclos, el énfasis estará puesto en cómo resuelve el programa el problema especificado. Desarrollaremos instrumentos que nos permitan comparar diferentes programas que resuelven un mismo problema.Uno de los aspectos que es importante considerar al comparar algoritmos es el referido a los recursos que el programa necesita para ejecutarse: tiempo de procesamiento, espacio de memoria, tiempo de utilización de un dispositivo. El estudio de la necesidad de recursos de un programa o algoritmo se llama análisis del algoritmo y lo que dicho análisis determina es la eficiencia del mismo. Ejemplosmotivadores. Considere las siguientes preguntas: 1. Un pintor demora 1 hora y media en pintar una pared de 3m de largo. ¿Cuánto demorará en pintar una de 5m de largo? 2. Un pintor demora 1 hora y media en pintar una pared cuadrada de 3m de lado. ¿Cuánto demorará en pintar una de 5m de lado? 3. Si lleva 5 horas inflar un globo aerostático esférico de 4m de diámetro, ¿cuánto llevará inflar uno de 8m dediámetro? 4. Un bibliotecario demora 1 día en ordenar alfabéticamente una biblioteca con 1000 expedientes. ¿Cuánto demorará en ordenar una con 2000 expedientes? La respuesta a las primeras 3 preguntas puede darse en forma precisa porque conocemos la relación entre el dato (longitud del lado o del diámetro) y la magnitud de la tarea. Además, se asume que se conoce un método simple para pintar unapared o inflar un globo. La respuesta a la cuarta pregunta, en cambio, no parece fácil de responder. No conocemos cuánto más trabajo es ordenar 2000 expedientes que 1000. Existen numerosos métodos de ordenación que usamos en la práctica sin preguntarnos realmente cuál es el mejor. La respuesta a la pregunta depende del algoritmo de ordenación que esté utilizando el bibliotecario. Supongamos que estáutilizando el algoritmo de ordenación por selección (selection sort):

2

CLASE 01

proc ssort (in/out a: array[1..n] of T) {pre : n ≥ 0 ∧ a = A} var i, minp: int i:= 1 {inv : a[1, i) está ordenado ∧ a es permutación de A ∧} {∧ los elementos de a[1, i) son menores o iguales a los de a[i, n]} do i < n → minp:= select(a,i) swap(a,i,minp) i:= i+1 od end proc {pos : a está ordenado y espermutación de A} En la primera ejecución del ciclo, este algoritmo utiliza la función select para encontrar la posición minp donde se encuentra el mínimo de todo el arreglo y luego ubica el mínimo encontrado en la primera posición del arreglo utilizando el procedimiento swap. En la segunda ejecución del ciclo, vuelve a utilizar la función select para encontrar la posición del segundo mínimo y luegoubica el segundo mínimo en la segunda posición del arreglo. En general, una vez ubicado el i-1 ésimo mínimo del arreglo en la posición i-1, el algoritmo utiliza select para encontrar la posición del i-ésimo mínimo del arreglo y luego el procedimiento swap para colocarlo en la posición i. Toda modificación del arreglo se realiza a través de swap que, como vemos a continuación, produce una permutacióndel arreglo dado. Esto garantiza que ningún valor de a se pierde ni duplica. proc swap (in/out a: array[1..n] of T, in i,j: int) {pre : a = A ∧ 1 ≤ i, j ≤ n} var tmp: T tmp:= a[i] a[i]:= a[j] a[j]:= tmp end proc {pos : a[i] = A[j] ∧ a[j] = A[i] ∧ ∀k.k ∈ {i, j} ⇒ a[k] = A[k]} A continuación, detallamos el algoritmo utilizado para encontrar la posición del i-ésimo mínimo. Dado que el algoritmo ssort...