| navegación | |
Universidad del Cauca |
Contenido de la asignatura
En esta página puede consultar el contenido de la asignatura y alguna bibliografía asociada.
[28-06-2009] Notas finales
En el siguiente enlace encontrarán las notas finales de la asignatura, así como todas las notas anteriores. Estas notas ya se encuentran reportadas al sistema (HTML).
Felices Vacaciones!.
[09-07-2009] Examen Final.
En el siguiente enlace encontrarán el enunciado del examen final(pdf).
Fecha límite de entrega: jueves 23 de julio de 2009, 4:00 P.M. Grupos de máximo 2 personas.
[09-07-2009] Notas laboratorios 9 y 10
En el siguiente enlace encontrarán las notas para los laboratorios 9 y 10 (HTML).
[02-07-2009] Laboratorio 11. Grafos dirigidos con peso.
Desarrollar un programa para crear y manipular grafos dirigidos con peso. La entrada de este programa se dará por entrada estándar, y consistirá en uno o varios comandos:
NODO n
BUSCAR n
ARCO n m w
DFS n
BFS n
COSTO n m
COMPONENTES
SALIR
La implementación del grafo se hará con una lista de nodos. Igualmente, la implementación se deberá realizar de tal forma que los nodos puedan almacenar cualqiuer tipo de datos. Para el programa de prueba, los datos a almacenar y buscar son números enteros. Recuerde que cada nodo contiene un apuntador al dato (void *), la lista de adyacencia como una lista genérica y los demás atributos que requiere para los algoritmos (visitado, costo, componente)
El comando ARCO n m w deberá crear un arco entre los nodos con dato n y m con peso w. Si alguno de esos nodos no existe, se deberá crear automáticamente.
El comando DFS deberá realizar un recorrido por profundidad (DFS - Depth-First Search) desde el nodo con el dato especificado.
El comando BFS deberá realizar un recorrido por expansión (Breadth-First Search) desde el nodo con el dato especificado.
El comando COSTO n m deberá calcular el costo mínimo de ir desde el nodo con el dato n hasta el nodo con el dato m.
El comando COMPONENTES deberá imprimir el componente conexo al cual pertenece cada nodo.
[25-06-2009] Laboratorio 10. Grafos no dirigidos con peso.
Desarrollar un programa para crear y manipular grafos no dirigidos con peso. La entrada de este programa se dará por entrada estándar, y consistirá en uno o varios comandos:
NODO n
BUSCAR n
ARCO n m w
DFS n
BFS n
COSTO n m
SALIR
La implementación del grafo se hará con una lista de nodos. Igualmente, la implementación se deberá realizar de tal forma que los nodos puedan almacenar cualqiuer tipo de datos. Para el programa de prueba, los datos a almacenar y buscar son números enteros.
El comando ARCO n m w deberá crear un arco entre los nodos con dato n y m con peso w. Si alguno de esos nodos no existe, se deberá crear automáticamente.
El comando DFS deberá realizar un recorrido por profundidad (DFS - Depth-First Search) desde el nodo con el dato especificado.
El comando BFS deberá realizar un recorrido por expansión (Breadth-First Search) desde el nodo con el dato especificado.
El comando COSTO n m deberá calcular el costo mínimo de ir desde el nodo con el dato n hasta el nodo con el dato m.
[18-06-2009] Laboratorio 9. Grafos no dirigidos sin peso.
Desarrollar un programa para crear y manipular grafos no dirigidos sin peso. La entrada de este programa se dará por entrada estándar, y consistirá en uno o varios comandos:
INSERTAR n
BUSCAR n
ARCO n m
DFS n
BFS n
SALIR
La implementación del grafo se hará con una lista de nodos. Igualmente, la implementación se deberá realizar de tal forma que los nodos puedan almacenar cualqiuer tipo de datos. Para el programa de prueba, los datos a almacenar y buscar son números enteros.
El comando ARCO n m deberá crear un arco entre los nodos con dato n y m. Si alguno de esos nodos no existe, se deberá crear automáticamente.
El comando DFS deberá realizar un recorrido por profundidad (DFS - Depth-First Search) desde el nodo con el dato especificado.
El comando BFS deberá realizar un recorrido por expansión (Breadth-First Search) desde el nodo con el dato especificado.
[18-06-2009] Notas segundo corte
En el siguiente enlace encontrarán las notas del segundo corte (HTML)
[04-06-2009] Segundo examen parcial.
En el siguiente enlace encontrarán el enunciado del segundo examen parcial (pdf).
Fecha límite de entrega: jueves 11 de junio de 2009, 3:59:59 P.M. Grupos de máximo 2 personas.
[04-06-2009] Notas laboratorios 6 y 7
En el siguiente enlace encontrarán las notas de los laboratorios 6 y 7 (HTML). Plazo máximo de revisión: 05 Jun 2009, 12:00 M.
[28-05-2009] Laboratorio 8. Árboles B
Desarrollar un programa para crear y manipular árboles B. La entrada de este programa se dará por entrada estándar, y consistirá en uno o varios comandos:
ORDEN n
INSERTAR n
BUSCAR n
SALIR
El comando ORDEN (mayor que 2) definirá el número de datos que se puede almacenar en cada nodo del árbol B. Por ejemplo, si se especifica el comando
ORDEN 5
Entonces cada nodo del árbol B puede contener como máximo 4 datos (ORDEN -1). Se puede asumir que el orden de los comandos es correcto, es decir que los comandos INSERTAR y BUSCAR sólo se ingresarán luego de ingresar el comando ORDEN.
El árbol B deberá ser implementado con base en nodos binarios: Cada nodo de un árbol B deberá contener una lista de nodos binarios, que contendrán los datos a almacenar.
Los nodos binarios dentro del nodo B tendrán referencias izquierda y derecha hacia los nodos B que se desprenden de ellos.
Los nodos B deberán contener una referencia al nodo padre (también de tipo nodo B). Los nodos binario no tendrán referencia al nodo padre.
Al igual que los laboratorios anteriores, la implementación del árbol B se deberá realizar de tal forma que permita almacenar cualqiuer tipo de datos dentro de los nodos.
Para el comando buscar, el programa deberá imprimir el número de comparaciones que se realizaron para encontrar el dato. Si el dato no se encuentra en el árbol, el comando buscar también deberá imprimir el número de comparaciones realizadas.
[21-05-2009] Laboratorio 7. Árboles AVL
Desarrollar un programa para crear y manipular árboles AVL. La entrada de este programa se dará por entrada estándar, y consistirá en uno o varios comandos:
INSERTAR n
BUSCAR n
ELIMINAR n
PREORDEN
INORDEN
POSTORDEN
NIVELES
SALIR
Para cada recorrido (preorden, inorden, postorden y niveles) el programa deberá imprimir la secuencia de números del recorrido en una sola línea.
[14-05-2009] Laboratorio 6. Árboles Binarios de Búsqueda
Desarrollar un programa para crear y manipular árboles binarios. La entrada de este programa se dará por entrada estándar, y consistirá en uno o varios comandos:
INSERTAR n
BUSCAR n
ELIMINAR n
PREORDEN
INORDEN
POSTORDEN
NIVELES
SALIR
Para cada recorrido (preorden, inorden, postorden y niveles) el programa deberá imprimir la secuencia de números del recorrido en una sola línea.
[14-05-2009]Notas primer corte
En el siguiente enlace encontrarán las notas del primer corte (HTML)
[30-04-2009] Primer examen parcial.
En el siguiente enlace encontrarán el enunciado del primer examen parcial (pdf).
Fecha de entrega: jueves 7 de mayo de 2009. Grupos de máximo 2 personas.
[23-04-2009] Laboratorio 5. Ad-Hoc
Un estudiante decide cambiar de vivienda, para lo cual empaca todas sus pertenencias en cajas pequeñas de diferentes tamaños. Sin embargo, al momento de llamar a una empresa de transportes para contratar la mudanza, es informado que se le cobrará de acuerdo con la cantidad de cajas a transportar. El ingenioso estudiante concluye que le será más económico transportar una sola caja que contenga a las demás, para lo cual se dispone a organizar las cajas más pequeñas dentro de las cajas más grandes.
Con el fin de generalizar la solución obtenida, el estudiante desarrolla una notación para describir la forma en la cual las cajas deberán ser organizadas, de acuerdo con su volumen: Sea m el volumen de una caja. Se dice que la caja de volumen m puede contener una o más cajas de volumen nk sí y sólo si la suma de sus volúmenes es menor que m (Suponga que las cajas n1, n2 ,.. n k pueden a su vez contener otras cajas, pero el volumen que contiene cada una de ellas no cuenta en la suma con respecto a m). Con el fin de representar el volumen de las cajas como una secuencia en la cual una caja puede contener otras cajas, la caja de volumen i se representa en la secuencia con los enteros –i e i, dentro de la cual pueden existir cajas de volumen menor. Por ejemplo la secuencia:
-9 -7 -2 2 -4 -2 -1 1 2 4 7 9
Representa una organización válida, en la cual todas las cajas están contenidas dentro de una caja de volumen 9 (que contiene una caja de volumen 7, que contiene dos cajas de volumen 2 y 4. A su vez la caja de volumen 4 contiene una caja de volumen 2 que contiene una caja de volumen 1). Por el contrario, la secuencia
-9 -7 -2 2 -3 -2 -1 1 2 3 7 -2 2 9 No es una organización válida, al igual que la secuencia -9 -7 -2 2 -3 -1 -2 3 2 1 7 9.
La entrada del programa consistirá en un conjunto indeterminado de líneas, en donde cada línea representa una secuencia de números enteros que representan los volúmenes de las cajas a empacar.
Para cada secuencia, el programa deberá determiar si las cajas están organizadas en forma correcta o no. El programa deberá terminar al encontrar una linea con la palabra end.
[16-04-2009] Laboratorio 4.Vuelta Atrás
SUDOKU:
El sudoku es un juego en el cual se tiene una cuadrícula de 9x9 posiciones, dentro de la cual se distribuyen 9 cuadrículas de 3x3 posiciones cada una. El juego consiste en posicionar todos los números del 1 al 9 en cada cuadrícula de 3x3, teniendo en cuenta las siguientes restricciones:
- Cada cuadrícula de 3x3 (9 posiciones) contiene los números del 1 al 9.
- Cada fila y columna de la cuadrícula de 9x9 debe contener los números del 1 al 9.
- Dos números iguales no se pueden encontrar en la misma fila o columna.
Desarrollar un algoritmo que determine si un sudoku dado tiene solución. Si se encuentra una solución, esta se deberá imprimir.
La entrada para este programa se dará como una serie de sudokus a solucionar. Para cada uno de ellos se deberá determinar si tiene solución o no, y si existe tal solución se deberá imprimir.
La entrada consistirá en un conjunto indeterminado de sudokus. Cada sudoku consiste en 9 líneas, cada una de las cuales contiene exactamente 9 números. El programa deberá terminar al encontrar una linea con la palabra end
[02-04-2009] Laboratorio 3.
Diseñar e implementar los siguientes algoritmos:
- Un algoritmo de dadas dos cadenas de caracteres x e y, determine si y se encuentra contenida en x.
Entrada: La entrada se dará por entrada estándar, y consistirá en una serie de líneas, cada una con dos cadenas x e y separadas por un espacio. Para cada linea, el programa deberá determinar si la cadena y está contenida en x e imprimir la posición (comenzando en 0) en la cual se encuentra y dentro de x. El programa terminará al encontrar una línea con la palabra end
Ejemplo de entrada:
estructuras ct datos dat datos datos laboratorio o end
-
Un algoritmo que dado un laberinto, la posicion inicial y la posicion final, determine si existe camino desde la posicion inicial hasta la posicion final.
Entrada: Los datos deberan ser leidos por entrada estándar, y consistirán en una serie de casos de prueba con el siguiente formato:
n m fi ci ff cf 0 0 1 1 .... 0 (m columnas) 1 0 ...... 1 (m columnas) ............ 0 1 1 0 .... 1 (hasta completar n filas, es decir un laberinto de n x m). n m fi ci ff cf 0 0 1 1 .... 0 (m columnas) 1 0 ...... 1 (m columnas) ............ 0 1 1 0 .... 1 (hasta completar n filas, es decir un laberinto de n x m). end
Para cada caso, el programa deberá determinar si existe camino desde la posición inicial hasta la posición final del laberinto. El programa deberá terminar al encontrar la palabra end.
[26-03-2009] Laboratorio 2.
Diseñar e implementar un algoritmo que dados dos números n y m, calcule el número de formas en las que n puede ser representado como la suma de m números naturales.
Entrada: La entrada al programa se dará por entrada estándar, y consistirá en una serie de líneas con el siguiente formato:
n m n m n m ... end
Para cada línea de la entrada, el programa deberá calcular e imprimir el número de formas en las que n puede ser representado como la suma de m números naturales.
El programa deberá terminar al encontrar la palabra end en la entrada.
En el siguiente enlace: (ZIP) encontrarán ejemplos de la estrategia que se utilizará en la asignatura para la lectura de datos.
En el siguiente enlace:
http://decsai.ugr.es/~mgs/ta/lista.html
Encontrarán material acerca de como usar la libreria STL de C++ (nota: se deben usar archivos .CPP para que Dev-C reconozca la libreria).