Anuncios

Notas tercer tercio

posted May 21, 2013, 8:46 AM by Camilo Rocha   [ updated May 21, 2013, 1:34 PM ]

Adjunto encuentran las notas del tercer tercio, actualizadas con la nota correcta de la sustentación del proyecto.

Grafos

posted May 3, 2013, 9:45 AM by Camilo Rocha   [ updated May 3, 2013, 9:48 AM ]

A continuación encuentra mi implementación del tipo abstracto Graph con listas de adyacencia:


En el archivo adjunto encuentran la colección de los tipos abstractos de datos que implementamos en el curso.

Tableros de Sudoku

posted May 1, 2013, 3:39 AM by Camilo Rocha

Adjunto encuentran algunos tableros de Sudoku para que prueben con los solucionadores.

Árboles Binarios

posted Apr 18, 2013, 5:36 PM by Camilo Rocha   [ updated Apr 18, 2013, 5:40 PM ]

A continuación encuentran mi versión del tipo abstracto de datos de árboles binarios BinTree:



En el archivo adjunto encuentran una colección de los tipos abstractos de datos que hemos implementado en el curso hasta la fecha.

Proyecto Final: Sudoku

posted Apr 9, 2013, 2:00 PM by Camilo Rocha

En la sección de Bitáctora, lecturas, etc. encuentra publicado el enunciado de la Fase 0 del proyecto. El documento correspondiente a esta fase debe entregarse el día Martes 16 de Abril.

El enunciado del proyecto fue preprado en formato html y puede ser consultado al descomprimir el archivo sudoku-html.tar.gz y abrir en un navegador el archivo html/index.html. El archivo sudoku.tar.gz contiene los fuentes iniciales del proyecto.

Notas Tercio 2 (actualizadas)

posted Apr 5, 2013, 7:36 AM by Camilo Rocha   [ updated Apr 5, 2013, 10:46 AM ]

A continuación encuentran las notas del segundo tercio. En la segunda página del documento encuentras las leyendas y convenciones que utilicé para obtener y documentar las notas.

Laboratorio 9: Parcial práctico Tercio 2

posted Mar 22, 2013, 11:16 AM by Camilo Rocha   [ updated Mar 22, 2013, 11:25 AM ]

El objetivo de este laboratorio es implementar una solución al Problema 1 de los problemas de la semana 9, utilizando la estructura de datos Stack.
  1. Baje y descomprima el archivo adjunto al laboratorio.
  2. Edite el archivo BalExpr.py con su solución. En particular
    • modifique la función main() para leer la entrada y llame, por cada caso de prueba, la función solve(...)
    • implemente en la función solve(...) la solución del problema para cada caso de prueba.
Junto con la plantilla, se suministran también archivos con ejemplos de entrada y salida.

El laboratorio debe desarrollarse en Linux y las instrucciones para la entrega se suministrarán durante el examen.

Búsqueda binaria

posted Mar 19, 2013, 6:06 PM by Camilo Rocha

A continuación encuentran el algoritmo de búsqueda binaria que estudiamos hoy en clase, con un par de ajustes. Su eficiencia logarítmica en función del tamaño del espacio de búsquda (es decir, corre en tiempo O(log2 N) en donde N es tamaño del espacio de búsqueda) radica en que cada vez que avanza la búsqueda, se descarta una mitad del espacio de búsquda pendiente, hasta que sólo resta un elemento en el espacio de búsqueda. Al final del anuncio encuentran un par de problemas para practicar el concepto de búsqueda binaria.

El código Python está completamente documentado para que puedan estudiar y entender cómo funciona. Además hay un par de pruebas.


El código es realmente corto sin los comentarios:

Problemas para practicar

  1. Considere un arreglo A[0,N) de números enteros, con N >= 0. Se dice que A tiene un punto fijo si y sólo si existe un i, con 0 <= i < N, tal que A[i] = i. Diseñe un algoritmo que dado un arreglo A[0,N) ordenado ascendentemente, calcule en tiempo O(log2 N) si A tiene un punto fijo.
  2. Suponga que A[0,N), con N >= 1, es un arreglo de enteros está ordenado ascendentemente y que x es un elemento de A:
    • Suponiendo que A no tiene elementos repetidos, diseñe un algoritmo que en tiempo O(log2 N) determine cuántos elementos en A son mayores que x.
    • Suponiendo que A no tiene elementos repetidos, diseñe un algoritmo que en tiempo O(log2 N) determine cuántos elementos en A son mayores o iguales que x.
    • Sin suponer que A no tiene elementos repetidos, diseñe un algoritmo que en tiempo O(log2 N) determine cuántos elementos en A son mayores que x.
    • Sin suponer que A no tiene elementos repetidos, diseñe un algoritmo que en tiempo O(log2 N) determine cuántos elementos en A son mayores o iguales que x.
  3. Lo mismo que (2), pero sin suponer que x está en A.

Parcial Tercio 2: Temario

posted Mar 14, 2013, 2:31 PM by Camilo Rocha   [ updated Mar 14, 2013, 2:31 PM ]

A continuación encuentran los temas que se pueden evaluar en el Parcial del Tercio 2:
  1. Complejidad temporal y espacial de programas iterativos
    • Definición del operador O
    • Propiedades (con demostración) del operador O
      • Suma de complejidades: O(f)+O(g) = O(max(f,g))
      • Producto de complejidades: O(f)O(g) = O(fg)
    • Análisis y cálculo de complejidades temporales y espaciales para programas en el lenguaje de programación Python
  2. Estructuras de datos
    • Objetivos
    • ¿Cómo se documentan?
  3. Estructuras de datos lineales
    • Propósito y principales características de sus operaciones
      • Listas ordenadas
      • Pilas
      • Colas
    • Aplicaciones
  4. Algorítmo de búsqueda binaria en estructuras lineales y ordenadas

Problema Libro Aho, Hopcroft y Ullman: Example 2.2

posted Mar 14, 2013, 10:45 AM by Camilo Rocha   [ updated Mar 14, 2013, 10:56 AM ]

Implementar una función own_print usando la siguiente plantilla:

def own_print(s):
    """
    Given a string s made from the characters in

        a,b,...,y,z,A,B,...,Y,Z,#,@
    return the string resulting from s by interpreting the characters '#' and '@'
    as described in the Aho, Hopcroft, and Ullman book, example 2.2.
    """
    r,a = '',Stack()
    
     ...
    
    return r

Restricciones

  1. Las únicas variables que puede usar la función own_print son a y r, tal como se declaran en la plantilla anterior. Los fuentes de la clase Stack hacen parte del archivo adjunto a este mensaje.
  2. Adicionalmente el orden de complejidad de own_print(s) debe ser O(n), en donde n es la longitud del parámetro s.
A modo de sugerencia para comenzar la implementación, creen un nuevo archivo en el directorio de Stack.test.py y con el mismo encabezado (from ... import ...) de este último. Este nuevo archivo, además del encabezado, debe contener únicamente la definición de la función own_print y, posiblemente, algunas pruebas (ver más adelante).


Pruebas

Pueden utilizar las siguientes pruebas para validar la implementación hecha:

print(own_print('abc'))
print(own_print('abc#'))
print(own_print('abc##'))
print(own_print('abc###'))
try:
  print(own_print('abc####'))
except ValueError:
  print('Error')
print(own_print('a#b#c'))
print(own_print('a#b#c#q'))
print(own_print(''))
print(own_print('@'))
print(own_print('@ayt@'))
try:
  print(own_print('@ayt@#a'))
except ValueError:
  print('Error')
print(own_print('@ay#t@q'))
print(own_print('@@@@@@@'))

El resultado debe ser el siguiente:

abc
ab
a

Error
c
q



Error
q


Note que hay 5 lineas en blanco, específicamente, las lineas 4, 8, 9, 10 y 13.

1-10 of 20