Resultados del primer parcial

Ya tengo algunas conclusiones sobre los resultados del parcial. Charlaremos la próxima clase sobre el tema.

Antes quisiera conocer la impresión de ustedes, para lo cual preparé una breve encuesta anónima.

TP4 rev2

Hice unos cambios a los puntos 1 y 2 del TP4. Pueden verlo en http://unajct.blogspot.com/2014/05/tp4.html.

Dudo que sean muchos los que estén trabajando con el TP4, sin embargo, para no perjudicar a nadie, les dejo la clase minHeap, es decir, la resolución de los puntos 1a, 1b y 1c. Si editan el archivo .py no olviden tomar precauciones con el estilo de indentación (yo generalmente uso tabulador).

Clase 19 de mayo y parcial

Les dejo la presentación de la clase del 19 de mayo. Vimos dispersión (hashing) y comenzamos con el trabajo práctico 4 sobre el mismo tema.

Les resumo lo que hablamos sobre el parcial:

• Será de opción múltiple.
• El contenido es todo hasta árboles binarios, binarios de búsqueda y autobalanceados.
• No habrá ejercicios de programación.
• Un tercio del parcial (también con opción múltiple) será de resolución de ejercicios prácticos (cálculo de T(n), O(n), insertar gráficamente datos en alguna de las estructuras vistas, etc.).
• El resto será evaluación de la teoría, en forma directa o aplicada. En forma aplicada significa con ejemplos o relacionando conceptos.
• De 14 a 15:10 haremos clase, para responder dudas puntuales que tengan y para avanzar con el TP4. A las 15:30 comenzará la evaluación. Traten de llegar temprano.

También señalé dos errores conceptuales que más de un alumno cometió en los prácticos.
Algunos de ustedes no tienen tema de trabajo final o tienen pendiente confirmar. Pueden hacerlo por mail o podemos hablar personalmente. Se aplica la política de que un tema queda asignado al primero que lo elige si lo confirma.

TP4

Les voy dejando la guía del Trabajo Práctico 4. Tiene dos adjuntos: listaClaveValor.py y autos.py. Como estoy teniendo problemas técnicos con los adjuntos, a continuación les pego el código de ambos archivos:


ListaClaveValor.py

class listaClaveValor:
    def __init__(self, clave=None, valor=None):
        self.__clave = clave
        self.__valor = valor
        self.__siguiente = None
    def buscarClave(self, c):
        e = self
        while e!=None and e.__clave!=c:
            e = e.__siguiente
        return e
    def buscarValor(self, v):
        e = self
        while e!=None and e.__valor!=v:
            e = e.__siguiente
        return e
    def insertar(self, c, v):
        e = self
        while e!=None and e.__clave!=c:
            ea = e
            e = e.__siguiente
        if e:
            e.__valor = v
            return e
        if ea.__clave == None:
            ea.__clave = c
            ea.__valor = v
            return ea
        e = listaClaveValor(c,v)
        ea.__siguiente = e
        return e
    def longitud(self):
        e = self
        n = 0
        while e!=None:
            n = n + 1
            e = e.__siguiente
        return n
    def valor(self):
        return self.__valor
    def clave(self):
        return self.__clave
    def siguiente(self):
        return self.__siguiente
    def __str__(self):
        e = self
        s = '['
        if self.__clave == None:
            return '[]'
        while e!=None:
            s = s + str(e.__clave) + ','
            e = e.__siguiente
        return s[:-1] + ']'


autos.py


from dispersion import *

class auto:
    def __init__(self, patente, marca, fabricacion, propietario):
        self._patente = patente
        self._marca = marca
        self._fabricacion = fabricacion
        self._propietario = propietario
    def marca(self):
        return self._marca
    def propietario(self):
        return self._propietario
    def fabricacion(self):
        return self._fabricacion

def hashPatente(p):
    b = 13
    h = 0
    for i in range(0,6):
        h = h + b**i * ord(p[i])
    return h

mapa = hashTableXXX(h=11, hash=hashPatente)
pa1 = 'ADF565'
pa2 = 'RUY276'
pa3 = 'ETI127'
pa4 = 'AE5328'
pa5 = 'BRY070'
pa6 = 'WER808'
pa7 = 'WGJ756'
pa8 = 'YEW423'
pa9 = 'VFU112'
a1 = auto(pa1, 'Toyota', 1990, 'Juan')
a2 = auto(pa2, 'Volkswagen', 1993, 'Antonio')
a3 = auto(pa3, 'Fiat', 1997, 'Adriana')
a4 = auto(pa4, 'Toyota', 2001, 'Lucia')
a5 = auto(pa5, 'Peugeot', 2003, 'Maria')
a6 = auto(pa6, 'Fiat', 2006, 'Jose')
a7 = auto(pa7, 'Toyota', 2007, 'Mariano')
a8 = auto(pa8, 'Volkswagen', 2008, 'Hernan')
a9 = auto(pa9, 'Peugeot', 2009, 'Pedro')
mapa.insertar(pa1, a1)
print "insertando", pa1, mapa.estado(), "carga:", mapa.factorCarga()
mapa.insertar(pa2, a2)
print "insertando", pa2, mapa.estado(), "carga:", mapa.factorCarga()
mapa.insertar(pa3, a3)
print "insertando", pa3, mapa.estado(), "carga:", mapa.factorCarga()
mapa.insertar(pa4, a4)
print "insertando", pa4, mapa.estado(), "carga:", mapa.factorCarga()
mapa.insertar(pa5, a5)
print "insertando", pa5, mapa.estado(), "carga:", mapa.factorCarga()
mapa.insertar(pa6, a6)
print "insertando", pa6, mapa.estado(), "carga:", mapa.factorCarga()
mapa.insertar(pa7, a7)
print "insertando", pa7, mapa.estado(), "carga:", mapa.factorCarga()
mapa.insertar(pa8, a8)
print "insertando", pa8, mapa.estado(), "carga:", mapa.factorCarga()
mapa.insertar(pa9, a9)
print "insertando", pa9, mapa.estado(), "carga:", mapa.factorCarga()

print "buscando..."
for p in [pa1,pa2,pa3,pa4,pa5,pa6,pa7,pa8,pa9]:
    a = mapa.buscar(p)
    print p,a.marca(),a.propietario()

Tema de trabajo final

La última clase hablamos sobre el trabajo final. Les resumo la cuestión de los grupos y la definición de tema.

El trabajo se hace en grupos de 1 a 3 personas, el tema es a elegir y acordar conmigo. A medida que vayan teniendo una idea del tema vayan comentándome muy brevemente por mail. Tengan en cuenta que cada grupo deberá trabajar sobre un tema distinto. La próxima clase me gustaría hablar con cada grupo y tratar de definir los temas.

Hay dos posibles tipos de trabajo:

1. Extensión de un trabajo práctico de los que hicimos, profundizando el estudio teórico del tema, implementando y analizando los algoritmos y realizando mediciones con datos aleatorios.
2. Construir un módulo de python con las estructuras y algoritmos vistos para alguno de los temas e implementar una pequeña aplicación que la utilice. Ejemplos:
• Sectorización de redes de suministro de agua potable.
• Compresor/descompresor de texto basado en códigos de Huffman.

Quienes ya tengan conocimientos sobre grafos tendrán la posibilidad de trabajar con el tema. El resto tenga presente que es el último tema que se ve. Los temas teóricos con los que pueden trabajar son:

• Estructuras fundamentales y algoritmos de ordenamiento y búsqueda
• Árboles (generales)
• Árboles binarios, de búsqueda y autobalanceados
• Heap y hashing
• Grafos
• Problemas NP

Clases del 5 y 12 de mayo

El 5 de mayo vimos árboles binarios, les dejo la presentación. También empezamos con el Trabajo Práctico 3, sobre árboles binarios, árboles binarios de búsqueda y árboles autobalanceados. Perdón por la demora en publicarlo.

A pedido de ustedes, el 12 de mayo hicimos un refuerzo de cálculo de T(n) tanto para algoritmos no recursivos como para recursivos. Introdujimos una variante en una de las técnicas vistas. También vimos las estructuras heap (a veces llamadas montón o montículo) con sus algoritmos correspondientes. Además hablamos un poco sobre el trabajo final. Publicaré otro post sobre eso.

Clase 28/4 y recursos TP2

La clase del 28/4 vimos dos ejemplos de ecuaciones de recurrencia y comenzamos con el TP2. Algunos comentarios respecto del TP2:

• Les comparto una versión corregida de los ejercicios que resolvimos en clase.
• Les comparto código con datos para quien quiera usarlo para hacer pruebas con el ejercicio 5. Dos aclaraciones:
• Dicho ejercicio no pide las respuestas a las preguntas sino las líneas de código necesarias para obtenerlas (es suficiente con las líneas sin estructurarlas en clases ni en funciones).
• No es necesario entregar código con pruebas como el que les comparto.
• Si están todos de acuerdo, intercambiaremos la opcionalidad entre los ejercicios 3 y 4. Lo discutiremos la próxima clase.
• Espero que todo esto sirva de ayuda pero tengan en cuenta que el TP sigue siendo largo.

La próxima clase veremos un tema teórico y comenzaremos con el TP3.