Algoritmos

Algoritmos y Estructuras de Datos
Tarea 1
Profesor: Sergio Rajsbaum
Ayudante: Jorge Figueroa
fecha de hoy: 26 de agosto 2006
fecha de entrega: 4 de septiembre 2006 – No se aceptan tareasdespu´es de esta fecha
— explica en detalle y con claridad todas tus respuestas —
— Tus algoritmos deber´an ser lo m´as eficiente posibles —
— explica el funcionamiento de tus algoritmos informalmente,luego escribe el c´odigo, y
luego demuestra correctez y complejidad.—
Se permite trabajar en equipos de hasta tres personas.
Pero cada uno debe entregar la tarea resuelta por separado, e indicar elnombre de su compa˜nero de equipo.
Tema: Introducci´on al an´alisis de correctez y complejidad de algoritmos.
1. Demuestra que 40 · 2n + n5 2 o(3n), y presenta una gr´afica de estas funciones quejustifique
el resultado.
2. El siguiente algoritmo compara cadenas en el sentido lexicogr´afico. Es decir, en el sentido
en que lo hacen los diccionarios para ordenar palabras. Entrada: c1, c2: soncadenas de
caracteres terminadas por el caracter especial de terminaci´on de cadena ’\0’. Este caracter,
por definici´on, es menor que cualquier otro. salida: −1 si c1 es menor lexicograficamente
quec2; 0 si c1 es igual a c2; 1 si c1 es mayor lexiograficamente que c2.
El primer ´ındice de la cadena es el 0. Es decir, para C = “hola” tenemos C[0] ==0 h 0,
C[1] ==0 o 0, C[2] ==0 l 0, C[3] ==0 a0, C[4] ==0 \0 0. Sea |C| la longitud de la cadena, en
este caso, |C| = 5.
Function compara lexicograficamente(c1, c2):
i = 0
do
if c1[i] < c2[i] then return(−1) fi
if c1[i] > c2[i] thenreturn(1) fi
if c1[i] ==0 \0 0 then return(0) fi
i = i + 1
while(true)
Figure 1: Algoritmo de comparaci´on lexicogr´afica.
Prop´on una definici´on de comparaci´on de dos matrices (en lugar de cadenas)de manera
lexicogr´afica, cada una de 2 dimensiones (en lugar de 1 dimensi´on, como son las cadenas).
Demuestra la correctez y analiza la complejidad de tu algoritmo.
1
Tip: Para la complejidad,...